Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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 Free Access

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 symmetries, J. Phys. A 27 (1994), no. 1, 115–129. MR 1288000 (95j:52039)
  • 2. Enrico Bombieri and Jean E. Taylor, Quasicrystals, tilings, and algebraic number theory: some preliminary connections, The legacy of Sonya Kovalevskaya (Cambridge, Mass., and Amherst, Mass., 1985), Contemp. Math., vol. 64, Amer. Math. Soc., Providence, RI, 1987, pp. 241–264. MR 881466 (89a:82031), http://dx.doi.org/10.1090/conm/064/881466
  • 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 26 (1993), no. 12, 2829–2853. MR 1236147 (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. Marjorie Senechal, Quasicrystals and geometry, Cambridge University Press, Cambridge, 1995. MR 1340198 (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: http://dx.doi.org/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
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