|
Proving the deterministic period breaking of linear congruential generators using two tile quasicrystals
Author(s):
Louis-Sébastien
Guimond;
Jirí
Patera.
Journal:
Math. Comp.
71
(2002),
319-332.
MSC (2000):
Primary 65C10, 82D99;
Secondary 68U99
Posted:
September 17, 2001
MathSciNet review:
1863003
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We describe the design of a family of aperiodic PRNGs (APRNGs). We show how a one-dimensional two tile cut and project quasicrystal (2TQC) used in conjunction with LCGs in an APRNG generates an infinite aperiodic pseudorandom sequence. In the suggested design, any 2TQC corresponding to unitary quadratic Pisot number combined with either one or two different LCGs can be used.
References:
-
- 1.
- S. Berman and R. V. Moody, The algebraic theory of quasicrystals with five-fold symmetry, J. Phys. A: Math. Gen. 27 (1994), 115-130. MR 95j:52039
- 2.
- E. Bombieri and J. E. Taylor, Quasicrystals, tilings and algebraic number theory: some preliminary connections, Contemp. Math. 64 (1987), 241-260. MR 89a:82031
- 3.
- L.-S. Guimond, Jan Patera, and Jirí Patera, Combining random number generators using cut and project sequences, Czechoslovak J. Phys. 51 # 4 (2001), 305-311.
- 4.
- -, Statistics and implementation of an APRNG, Preprint (2000), 22 pages.
- 5.
- S. Lang, Algebra,
 ed., Addison-Wesley, Massachussetts USA, 1993. - 6.
- Z. Masáková, J. Patera, and E. Pelantová, Patent pending # 09/327633, filing date: June 8, 1999.
- 7.
- -, Quadratic irrationalities and geometric properties of one-dimensional quasicrystals, Preprint CRM-2565, 1998.
- 8.
- R. V. Moody and J. Patera, Quasicrystals and icosians, J. Phys. A: Math. Gen. 26 (1994), 2829-2853. MR 94f:52030
- 9.
- Jan Patera, Methods of computer-based generation of quasicrystals, Master's thesis, Czech Technical University, 1999, email: patera@km1.fjfi.cvut.cz.
- 10.
- D. Schechtman, I. Blech, D. Gratias, and J. W. Cahn, Metallic phase with long-range orientational order and no translational symmetry, Physical Review Letters 53 (1984), 1951-1953.
- 11.
- M. Senechal, Quasicrystals and geometry, Cambridge Univ. Press, Cambridge, UK, 1995. MR 96c:52038
- 12.
- S. Webber, What are quasicrystals, Web page maintained by S. Webber:
http://www. nirim.go.jp/~weber/qc.html#1.
Similar Articles:
Retrieve articles in Mathematics of Computation
with
MSC (2000):
65C10, 82D99,
68U99
Retrieve articles in all Journals with
MSC (2000):
65C10, 82D99,
68U99
Additional Information:
Louis-Sébastien
Guimond
Affiliation:
Centre de Recherches Mathématiques, Université de Montréal, c.p. 6128, succ. centre-ville, Montréal (Québec), Canada, H3C-3J7
Email:
guimond@CRM.UMontreal.CA
Jirí
Patera
Affiliation:
Centre de Recherches Mathématiques, Université de Montréal, c.p. 6128, succ. centre-ville, Montréal (Québec), Canada, H3C-3J7
Email:
patera@CRM.UMontreal.CA
DOI:
10.1090/S0025-5718-01-01331-X
PII:
S 0025-5718(01)01331-X
Keywords:
Aperiodic pseudorandom number generator,
Monte Carlo method,
linear congruential generator,
pseudorandom number generator,
quasicrystal,
simulation
Received by editor(s):
October 15, 1999
Received by editor(s) in revised form:
March 14, 2000
Posted:
September 17, 2001
Additional Notes:
This work was supported by NSERC of Canada and FCAR of Québec.
Copyright of article:
Copyright
2001,
American Mathematical Society
|
