A 15 character 64 to 32-bit generator I devised which passes dieharder:
(x+=x*x+9)>>32;14 Character Random Number Generator in C
11–19 of 19 posts
Re: 14 Character Random Number Generator in C
#12Thank you for the writeup. What was the tool used to generate the .GIF of the shell?
Re: 14 Character Random Number Generator in C
#13A 15 character 64 to 32-bit generator I devised which passes dieharder: (x+=x*x+9)>>32;
Is dieharder considered as the industry standard tool for testing randomness? Is it commonly used by experts?
Re: 14 Character Random Number Generator in C
#14A 15 character 64 to 32-bit generator I devised which passes dieharder: (x+=x*x+9)>>32;
Is dieharder considered as the industry standard tool for testing randomness? Is it commonly used by experts? https://www.phy.duke.edu/~rgb/General/dieharder.php
Dieharder works OK, and you can easily install it on Ubuntu as a command-line tool. PractRand and TestU01 are more stringent and give you more knobs to play with.
Re: 14 Character Random Number Generator in C
#15Earlier quoted context omitted.
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.
No, it wasn’t. ln(2654435761) is about 22, so if you limit yourself to odd numbers, about one in 11 attempts near that number will give you a prime.
At a generous one minute to prove primality of numbers in that range using trial division, and assuming you forget to bail out early when you find the first divisor, you still very likely will find a prime within an hour.
Even in the 70s, when computer time cost real money, that shouldn’t deter you.
(I just tried this on a Mac Mini, in Swift; finding 1000 primes took about a third of a second; 3 seconds if I forget to bail out early)
Edit: as further evidence that this isn't that large a prime: we knew 2^31-1 to be prime by trial division in 1772 (Euler somehow found time to do that)
Re: 14 Character Random Number Generator in C
#16Earlier quoted context omitted.
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.
[deleted]
Re: 14 Character Random Number Generator in C
#17A 15 character 64 to 32-bit generator I devised which passes dieharder: (x+=x*x+9)>>32;
That can be made shorter:
x+=x*x+9;
x+=((x*x+9)>>32);
Re: 14 Character Random Number Generator in C
#18A 15 character 64 to 32-bit generator I devised which passes dieharder: (x+=x*x+9)>>32;
That can be made shorter: x+=x*x+9; Are you sure you don't mean x+=((x*x+9)>>32); (and does that need the outer parentheses?) I doubt the first passes dieharder, as (if my C isn't too rusty) it alternates between odd and even numbers.
I mean you assign the value of the expression to your result.
e.g:
uint64_t x = 0;
...
uint32_t y = (x+=x*x+9)>>32;Re: 14 Character Random Number Generator in C
#19Earlier 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…
This particular one isn't large, but in general a pseudo-prime will produce similar effects.