Anyone interested in helping with a new random number generator?

[Nitorami]

I noted this function but doubted it works, because initialising and generating ten values twice in succession (within the same program) actually provides the same ten numbers.

And if you start the whole program twice, how do you make sure a different stream is generated? This was abouchez's point: with only the timer as entropy source, what is the difference between two program instances run simultaneously?

[ad1mt]

There must be strong mixing between password and date time value.

The password stretching/mixing algorithm is simple, and I've thoroughly tested it to make sure it works well.
The internal minimum password length is 77 characters, and if the password length is < 77 I mangle it until it is 77 characters long.
I then look at the long password as an integer where each character is a digit to the base 96 (the number of printable characters in the ascii set).
I then convert the long password to a bigint, by using 31 as the base, rather than 32 (space), otherwise a password of all spaces would equal a bigint password value of zero, which would create all the LCG parameters equal to zero. Using 31 as the base means that a password of all spaces equals a non-zero bigint value.
I then multiply the bigint password by the date_time_microseconds value. The internal password length is chosen carefully so that after multiplying by the date_time, it is 144 hex digits long. The password-date-time product is than chopped into 8 byte chunks and each chunk becomes one of the 18 LCG parameters. I've thoroughly tested the method of multiplying the long password by the date-time, to ensure that just single microsecond change in the date-time, changes most of the digits in the final bigint product. This was luck, not clever design, and I'm not sure why it works so well; maybe a maths expert could explain this   

If the PRNG is used simply to produce random numbers without a password, I create a 129 hex digit value using the default LCG parameters of the PRNG (this is not random yet).
I then multiply this by the date_time, to produce random value 144 hex digits long, and I use this to seed the LCGs.
The initial 129 hex digit value will always be the same, but multiplying by the date_time ensures the final 144 hex digit value is always different. This randomising process can be called up to 10 million times per second without repeating.

[ad1mt]

I noted this function but doubted it works, because initialising and generating ten values twice in succession (within the same program) actually provides the same ten numbers.

In the EMULATE_MICROSECS_FROM_TIMER code, it generates the microseconds value on the first call; and on subsequent calls, it increments the previous value.

And if you start the whole program twice, how do you make sure a different stream is generated? This was abouchez's point: with only the timer as entropy source, what is the difference between two program instances run simultaneously?

This is a good point, and I'm thinking about how to improve the algorithm to fix it.
Thanks for pointing this out.

[Nitorami]

An obvious solution is to use the record address, it will be different in each program instance. Other sources of entropy could be the process ID and thread ID. There is not much easily available entropy in the system really, if you need more it will likely become hardware and OS specific, and you'll need asssembler to access it. Maybe take a look at abouchez' link.

[Nitorami]

I've thoroughly tested the method of multiplying the long password by the date-time, to ensure that just single microsecond change in the date-time, changes most of the digits in the final bigint product. This was luck, not clever design, and I'm not sure why it works so well; maybe a maths expert could explain this

I'm not an expert but to put it simple, multiplication is a strong mixing function; just not for the lower bits !
O'Neill has criticized the seed sequence generator in the C PRNG, and proposed a better alternative https://www.pcg-random.org/posts/developing-a-seed_seq-alternative.html, which I translated to Pascal for my own purposes. In principle, it mixes each element of an input array with all other elements,  using an internal digest and a simple mix function

Code: Pascal  [Select][+][-]

1. function Mix (x,y: dword): dword;
2. var z: dword;
3. begin
4.   z := $ca01f9dd*x - $4973f715*y; //slower but provably better than xor
5.   result := z xor hi(z);
6. end;
7.  

The algorithm makes sure that each change in an input bit will flip each output bit with a 50% chance. In principle, this is not dissimilar to what a bigint multiplication does internally, but by splitting it up into individual 32bit multiplications, it does not require bigint.

[ad1mt]

Other sources of entropy could be the process ID and thread ID.

I've used the process-ID in previous implementations.

An obvious solution is to use the record address, it will be different in each program instance.

That's a good suggestion that I had not thought of.
I think a combination of process-ID and PRNG record memory address will give a good solution to this problem.

There is not much easily available entropy in the system really, if you need more it will likely become hardware and OS specific, and you'll need asssembler to access it.

For problems like this, if you can guarantee uniqueness, that is sometimes a better solution than using randomness.
Also, I usually try to avoid using OS-specific or hardware-specific solutions, and prefer software-based solutions that will work on any platform. Even if that means designing/coding my own algorithm. Designing your own algorithm is also more interesting as a learning exercise.

[ad1mt]

O'Neill has ...[cut]... proposed a better alternative...[cut]... In principle, it mixes each element of an input array with all other elements,  using an internal digest and a simple mix function

Code: Pascal  [Select][+][-]

1. function Mix (x,y: dword): dword;
2. var z: dword;
3. begin
4.   z := $ca01f9dd*x - $4973f715*y; //slower but provably better than xor
5.   result := z xor hi(z);
6. end;
7.  

The algorithm makes sure that each change in an input bit will flip each output bit with a 50% chance. In principle, this is not dissimilar to what a bigint multiplication does internally, but by splitting it up into individual 32bit multiplications, it does not require bigint.

What are those "magic" numbers in the code?
I instinctively dislike "magic" numbers in algorithms, especially in cryptography.

[Thaddy]

Those magic numbers are often - almost always - primes, pseudo primes or (as I mentioned earlier in the discussion) odd tau numbers (perfect squares) . This works good in prng's because of their specific bit patterns. I will write a demo later.

[Nitorami]

As Thaddy said. In this case, they were chosen chosen to achieve good mixing. Similar as in a LCG, not all multipliers are good, and a lot of effort has gone into finding good ones. There are still many to choose from, and the mixing will still work with different multipliers.The obvious minimum requirement is that they may not be even, otherwise the LSB would always be 0.

[Thaddy]

I found a better quasi-prng.
- very short
- infinite period
- fast
- good equi-distribution

Code: Pascal  [Select][+][-]

1. {$I-}
2. function goldenSimple: Double;inline;
3. {$push}{$J+}
4. const
5.   r: Double = 0.5;
6. {$pop}
7. begin
8.   r := Frac(r + 0.618033988749895); // φ-1
9.   goldenSimple := r;
10. end;
11.  
12. var
13.   i:integer;
14. begin
15.   for i := 0 to 99 do writeln(GoldenSimple:1:2);
16. end.

Not mine, slightly modified by me, but based on code analyses by DeepSeek from my code.
Can also look like this:

Code: Pascal  [Select][+][-]

1. {$I-}{$mode delphi}{$warn 5037 off}
2. type
3.   TQuasiPrng = record
4.     class var r:Double;
5.     class operator initialize(var value:TQuasiPrng);
6.     class function next:Double;static;inline;
7.   end;
8.  
9. class operator TQuasiPrng.Initialize(var value:TQuasiPrng);
10. begin
11.   value.r := 0.5;
12. end;
13.  
14. class function TQuasiPrng.Next:Double;
15. begin
16.   r := Frac(r + 0.618033988749895); // φ-1
17.   result := r;
18. end;  
19.  
20. var
21.   i:integer;
22. begin
23.   for i := 0 to 9 do writeln(TQuasiPrng.Next:1:2);
24. end.
25.  

[MathMan]

Thaddy - you probably meant that as a joke, right?

- very short <= I give you that
- infinite period <= no the period is at max 2^52, because that is the precision of the significant of double
- fast <= granted
- good equi-distribution <= in fact it is too good, from the distribution pattern below/above 1/2 on can deduce regularity in line with the Fibonacci series

Cheers,
MathMan

[Thaddy]

Yes? The formula as such has unlimited period because φ − 1 is irrational, , it is the fraction of the golden ratio, even given the 64 bit / 53 bit (It is the (x ^53)-1 I believe, not x ^52, which is indeed the limitation of double. Other bits are rounded but valid.
It is also a quasi-prng, not a prng, but the equi-distribution is near perfect and so it is good for things like monte-carlo simulations. A quasi-prng is a special case  prng, some call it even a different category, . You can compare it to the famous fibonnaci application as prng, but that is not equi-distributed.
It is a nice tool for daily fast generation.
You can rewrite the formula for any period you want. I just used a shortcut.

You can also compare it with splitmix, which has many of the same characteristics.

[MathMan]

Yes? The formulaas such has unlimited period because φ − 1 is irrational,, it is the fraction of the golden ratio, ...

I'm well aware of the above, but you did an implementation of a mathematical formula here, and that imposes limitations.

... even given the 64 bit / 53 bit (It is the (x ^53)-1 I believe, not x ^52, which is indeed the limitation of double. Other bits are rounded but valid.

It is 52 bit, because that is the stored variable part of the mantissa. The high bit (53) is always implicitely set to 1, and by that not changeable by floating point operations.

It is also a quasi-prng, not a prng, but the equi-distribution is near perfect and so it is good for things like monte-carlo simulations. A quasi-prng is a special case  prng, some call it even a different category, . You can compare it to the famous fibonnaci application as prng, but that is not equi-distributed.
It is a nice tool for daily fast generation.
You can rewrite the formula for any period you want. I just used a shortcut.

You can also compare it with splitmix, which has many of the same characteristics.

I don't deny that - all I stated was that the algorithm is very easily detected when looking at the sequence of above/below 1/2 values delivered back.

[Thaddy]

That is all true. I know. It is not meant for csprng's, although its properties means it is a good seed generator.
E.g. for chacha20.
The state can be recovered from at most three consecutive values as with most algorithms with just one state.
Observe that not any irrational number exposes the equi-distribution of GoldenRatio-1, e.g. Pi-3 or e-2 expose immediately obvious cycling.

[ad1mt]

...[cut]... not all multipliers are good, and a lot of effort has gone into finding good ones.

In a cryptography setting, this means a reduction in the number of possibilities that have to be tested in a brute-force attack.
In my algorithm, the LCG parameters can be almost any odd number, which helps to make a brute-force attack much more difficult.