## Random Coprimes and PiOctober 10, 2016 I've always enjoyed doing computer simulations. While I enjoy doing math, simulations are a way to get useful information without too much mental exercise. If you're lucky, scratching away with pencil on paper will get you an analytical solution for your problem, but often the approximate results of a simulation will quickly get you the information you need to move forward on a project. One feature of most simulations is random numbers; and, as we know, computers can generate pseudorandom numbers that look good to the casual observer, but they're not good enough for cryptography and many simulations. One problem is that generators have a cycle length, and the pseudorandom sequence starts to repeat when you demand too many numbers. Another is that the random distribution is not quite uniform.
rand(), in the C language for simple simulations with good results. Seasoned simulators would never use such built-in generators, since better generators are easy to program. Is there a way to test such generators?
There are actually quite a few different statistical tests for randomness, some involving dice throws, and more exotic ones that simulate monkeys on typewriters. American mathematician and computer scientist, George Marsaglia (1924-2011), collected many of these together into a series of tests called Diehard.[1] Better random number generators give better Diehard scores.
One popular and efficient random number generator that scores well in Diehard is the Mersenne twister.[2-3] This generator gets its name from the fact that its period is a Mersenne prime. Mersenne primes are prime numbers of the form 2, but such primes are rare. There are just 45 Mersenne primes in the first 2,270,720 primes. The period of the commonly used Mersenne Twister is ^{n} - 12, which is the 24th Mersenne prime.
^{19937}-1
of the coprimality of two natural numbers chosen at random. The analytical solution, found by a couple of teenagers, was published in a short, one page note.[5]
P√(6/.
My simulation program can be found here, with the results graphed below. I must admit that the program has not been carefully optimized, but it does use the Mersenne Twister as a random number generator. Archimedes (c. 287 BC - c. 212 BC) calculated that pi is between 3.1408 and 3.1429. More than two millennia later, I get the same precision by this simulation. At least the exercise was good programming practice.
P)
## References:- Robert G. Brown, Dirk Eddelbuettel, and David Bauer, "Dieharder: A Random Number Test Suite, Version 3.31.1," Duke University Web Site.
- M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on Modeling and Computer Simulation, vol. 8, no. 1 (January, 1998), pp 3-30, doi:10.1145/272991.272995. A PDF copy can be found here.
- Takuji Nishimura, "A C-program for MT19937: Integer version," April 6, 1998.
- Sergei Abramovich and Yakov Yu. Nikitin, "On the probability of co-primality of two natural numbers chosen at random (Who was the first to pose and solve this problem?)," arXiv, August 18, 2016.
- A. D. Abrams and M.T. Paris, "The probability that (a, b) = 1," The College Mathematics Journal, vol. 23 (1992) p.47. (PDF file).
- Vassilios Hombas, "What's the probability of a rational ratio being irreducible?" International Journal of Mathematical Education in Science and Technology, vol. 44, no. 3 (2013), pp.408-410, doi.org/10.1080/0020739X.2012.703332.
Linked Keywords: Computer simulation; mathematics; math; thought; mental exercise; luck; lucky; pencil; paper; closed-form expression; analytical solution; approximation; approximate; random number; computer; pseudorandom number generator; cryptography; cycle detection; cycle length; uniform distribution; dice; randomness; Google image search; Wikimedia Commons; programming language; random number generation; random number generating function; C language; statistics; statistical; infinite monkey theorem; monkeys on typewriters; American; mathematician; computer science; computer scientist; George Marsaglia (1924-2011); Diehard tests; efficiency; efficient; Mersenne twister; Mersenne prime; prime numbers; Marin Mersenne (1588-1648); Descartes; father; Blaise Pascal; acoustics; Mersenne's laws; oscillation; frequency; fiber; string; source code; Internet; histogram; pseudorandom number; Gnumeric; academic publishing; paper; arXiv; Sergei Abramovich; St.Petersburg University; Yakov Yu. Nikitin; State University of New York at Potsdam; calculation; calculating; probability; coprime integers; coprimality; natural number; adolescence; teenager; fraction; irreducibility; irreducible; numerator; denominator; greatest common divisor; pi; Archimedes (c. 287 BC - c. 212 BC); millennium; millennia; precision; control flow; loop; double loop. |
RSS Feed
## Google Search
Latest Books by Dev Gualtieri
- Schroeder Diffuser - July 24, 2017
- Rough Microparticles - July 17, 2017
- Robot Musicians - July 10, 2017
- Walter Noll (1925-2017) - July 6, 2017
- cosmogony - July 3, 2017
- Crystal Prototypes - June 29, 2017
- Voice Synthesis - June 26, 2017
- Refining Germanium - June 22, 2017
- Granular Capillarity - June 19, 2017
- Kirchhoff–Plateau Problem - June 15, 2017
- Self-Assembly - June 12, 2017
- Physics, Math, and Sociology - June 8, 2017
- Graphene from Ethylene - June 5, 2017
- Crystal Alignment Forces - June 1, 2017
- Martian Brickwork - May 29, 2017
- Carbon Nanotube Textile - May 25, 2017
- The Scent of Books - May 22, 2017
- Patterns from Randomness - May 18, 2017
- Terpene - May 15, 2017
- The Physics of Inequality - May 11, 2017
- Asteroid 2015 BZ509 - May 8, 2017
- Fuzzy Fibers - May 4, 2017
- The Sofa Problem - May 1, 2017
- The Wisdom of Composite Crowds - April 27, 2017
- J. Robert Oppenheimer and Black Holes - April 24, 2017
- Modeling Leaf Mass - April 20, 2017
- Easter, Chicks and Eggs - April 13, 2017
- You, Robot - April 10, 2017
- Collisions - April 6, 2017
- Eugene Garfield (1925-2017) - April 3, 2017
- Old Fossils - March 30, 2017
- Levitation - March 27, 2017
- Soybean Graphene - March 23, 2017
- Income Inequality and Geometrical Frustration - March 20, 2017
- Wireless Power - March 16, 2017
- Trilobite Sex - March 13, 2017
- Freezing, Outside-In - March 9, 2017
- Ammonia Synthesis - March 6, 2017
- High Altitude Radiation - March 2, 2017
- C.N. Yang - February 27, 2017
- VOC Detection with Nanocrystals - February 23, 2017
- Molecular Fountains - February 20, 2017
- Jet Lag - February 16, 2017
- Highly Flexible Conductors - February 13, 2017
- Graphene Friction - February 9, 2017
- Dynamic Range - February 6, 2017
- Robert Boyle's To-Do List for Science - February 2, 2017
- Nanowire Ink - January 30, 2017
- Random Triangles - January 26, 2017
- Torricelli's law - January 23, 2017
- Magnetic Memory - January 19, 2017
- Graphene Putty - January 16, 2017
- Seahorse Genome - January 12, 2017
- Infinite c - January 9, 2017
- 150 Years of Transatlantic Telegraphy - January 5, 2017
- Cold Work on the Nanoscale - January 2, 2017
### Deep ArchiveDeep Archive 2006-2008
Blog Article Directory on a Single Page |

Copyright © 2017 Tikalon LLC, All Rights Reserved.

Last Update: 07-24-2017