Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Proving the deterministic period breaking of linear congruential generators using two tile quasicrystals

Authors: Louis-Sébastien Guimond and Jirí Patera
Journal: Math. Comp. 71 (2002), 319-332
MSC (2000): Primary 65C10, 82D99; Secondary 68U99
Published electronically: September 17, 2001
MathSciNet review: 1863003
Full-text PDF

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 [Enhancements On Off] (What's this?)

  • 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:
  • 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.

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

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
Published electronically: September 17, 2001
Additional Notes: This work was supported by NSERC of Canada and FCAR of Québec.
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society