Mathematics of Computation

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
Retrieve article in: PDF
This article is available free of charge

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.

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, $3^{rd}$ 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.

Retrieve articles in Mathematics of Computation with MSC (2000): 65C10, 82D99, 68U99

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

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS