14 Character Random Number Generator in C
theorangeduck.com
14 Character Random Number Generator in C
1–10 of 19 posts
Re: 14 Character Random Number Generator in C
#2Cool, and even cooler that the idea is due to Knuth.
I found this typo entertaining:
Technically it could be replaced by any other large prime number. The most important thing is that it must have few factors, and be large enough to distribute information into the higher value bits when the integer overflows.
Surely any prime number has "few factors", i.e. none other than itself and 1? I guess the "prime" in the first sentence is a typo, since the second sentence reads as if the first one didn't say "prime".
Re: 14 Character Random Number Generator in C
#3Cool, and even cooler that the idea is due to Knuth. I found this typo entertaining: Technically it could be replaced by any other large prime number. The most important thing is that it must have few factors, and be large enough to distribute information into the higher value bits when the integer overflows. Surely any prime number has "few factors", i.e. none other than itself and 1? I guess the "prime" in the firs…
I noticed that too, I think he may be referring to the fact that generating super large actual prime numbers is hard, so people use probabilistic algorithms to generate probably almost primes
Re: 14 Character Random Number Generator in C
#4Cool, and even cooler that the idea is due to Knuth. I found this typo entertaining: Technically it could be replaced by any other large prime number. The most important thing is that it must have few factors, and be large enough to distribute information into the higher value bits when the integer overflows. Surely any prime number has "few factors", i.e. none other than itself and 1? I guess the "prime" in the firs…
I noticed that too, I think he may be referring to the fact that generating super large actual prime numbers is hard, so people use probabilistic algorithms to generate probably almost primes
This one isn't superlarge, by a wide shot. √2,654,435,761 = 51521.2166102, so even an extremely naive trial division loop needs just over 50k trial divisions.
I haven't benchmarked it, but I think that should easily run in under a second on any phone sold in the last 10 years. If you do it a bit smarter and skip even divisors, I think it could run in under a second on 30 year old hardware (25k iterations, 200-ish cycles per loop (division was very expensive, back then) takes a 5MHz CPU)
Re: 14 Character Random Number Generator in C
#5Cool, and even cooler that the idea is due to Knuth. I found this typo entertaining: Technically it could be replaced by any other large prime number. The most important thing is that it must have few factors, and be large enough to distribute information into the higher value bits when the integer overflows. Surely any prime number has "few factors", i.e. none other than itself and 1? I guess the "prime" in the firs…
My understanding was that for it to work, it must have few factors, and in particular no small ones, so easiest just to chose a large prime number.
Re: 14 Character Random Number Generator in C
#6Re: 14 Character Random Number Generator in C
#7I'm glad that the author included a disclaimer: this is fine for generating pleasing pictures, but should not be used for anything serious (such as crypto, or even Monte Carlo simulations etc.)
Re: 14 Character Random Number Generator in C
#8Earlier quoted context omitted.
I noticed that too, I think he may be referring to the fact that generating super large actual prime numbers is hard, so people use probabilistic algorithms to generate probably almost primes
This one isn't superlarge, by a wide shot. √2,654,435,761 = 51521.2166102, so even an extremely naive trial division loop needs just over 50k trial divisions. I haven't benchmarked it, but I think that should easily run in under a second on any phone sold in the last 10 years. If you do it a bit smarter and skip even divisors, I think it could run in under a second on 30 year old hardware (25k iterations, 200-ish cyc…
For context: factor(2654435761) on original series Ti-89 takes almost exactly two seconds.
Re: 14 Character Random Number Generator in C
#9This is really elegant. It's always fun to find something artsy in code. We often forget how important creativity is in software engineering.
Re: 14 Character Random Number Generator in C
#10Earlier quoted context omitted.
I noticed that too, I think he may be referring to the fact that generating super large actual prime numbers is hard, so people use probabilistic algorithms to generate probably almost primes
This one isn't superlarge, by a wide shot. √2,654,435,761 = 51521.2166102, so even an extremely naive trial division loop needs just over 50k trial divisions. I haven't benchmarked it, but I think that should easily run in under a second on any phone sold in the last 10 years. If you do it a bit smarter and skip even divisors, I think it could run in under a second on 30 year old hardware (25k iterations, 200-ish cyc…
The problem wasn't in proving this particular number was prime, it was finding a large prime number to begin with. I don't know what the state of the art was back in the day, but 32 bits would certainly have been too large for the Sieve of Eratosthenes.