(11C) Random Prime Number Generator

[Albert Chan]

(10-21-2018 05:20 PM)Dieter Wrote:  

(10-21-2018 01:31 PM)Albert Chan Wrote:  Update: without prime table, a simple way is keep picking random number until it is prime.
I think Klemm prime-wheel code do this ...

Sure, this also is the idea behind Gamo's original program. Generate an odd random integer (here within the wrong range, though) and check if it's prime. If not, try another one.

My mistake. I was thrown by Gamo code "LBL3 2 STO+0"
I thought it re-use the random number by searching forward ...

(10-21-2018 04:41 PM)Dieter Wrote:  There is another point where the program may not work as intended. The random number can be as large as 0,99999 99999. Multiplying this by 300 with 10-digit precision returns 300 exactly.

Just curious, is it a guess, or does RAN# really get that high ?

FYI, if above were done with binary math, it will not happen.
Example, for IEEE double, 1 ULP below 1.0 = 1 - 1/2^53

Assumed N >= 0, max(N RAN#) = N - N/2^53

If N is pow-of-2, above is exact (no rounding), thus less than N

If N is not pow-of-2, N/2^53 is slightly bigger than 1/2 ULP, thus rounded-up

So, with binary math, max(N RAN#) = N - 1 ULP < N