From: antispam@fricas.org
Michael S wrote:
> On Tue, 23 Dec 2025 17:54:05 -0000 (UTC)
> antispam@fricas.org (Waldek Hebisch) wrote:
>
>> Michael S wrote:
>> > On Mon, 22 Dec 2025 18:41:10 +0100
>> > Janis Papanagnou wrote:
>> >
>> >> On 2025-12-22 18:13, James Kuyper wrote:
>> >> > On 2025-12-22 07:18, Janis Papanagnou wrote:
>> >> >> On 2025-12-22 12:44, James Kuyper wrote:
>> >> >>> On 2025-12-22 03:48, Michael Sanders wrote:
>> >> >>>> Is it incorrect to use 0 (zero) to seed srand()?
>> >> >>>>
>> >> >>>> int seed = (argc >= 2 && strlen(argv[1]) == 9)
>> >> >>>> ? atoi(argv[1])
>> >> >>>> : (int)(time(NULL) % 900000000 + 100000000);
>> >> >>>>
>> >> >>>> srand(seed);
>> >> >>>
>> >> >>> No, why whould you think so?
>> >> >>
>> >> >> There's number sequence generators that produce 0 sequences if
>> >> >> seeded with 0. ...
>> >> >
>> >> > The details of how the seed affects the random number sequence
>> >> > are unspecified by the standard. I personally would consider a
>> >> > pseudo-random number generator to be quite defective if there
>> >> > were any seed that produced a constant output.
>> >>
>> >> I wouldn't have mentioned that if there weren't a whole class of
>> >> such functions that expose exactly that behavior by design. Have
>> >> a look for PN-(Pseudo Noise-)generators and LFSR (Linear Feedback
>> >> Shift Registers). These have been defined to produce random noise
>> >> (bit pattern with good statistical distribution). With
>> >> sophisticated generator polynomials they produce also sequences of
>> >> maximum period; say, for N=31 a non-repeating sequence of length
>> >> 2^N - 1. The one element that is missing from the sequence is the
>> >> 0 (that reproduces itself).
>> >>
>> >> Technically you pick some bit-values from fixed positions
>> >> (depending on the generator polynomial) of the register and xor
>> >> the bits to shift the result into the register. Here's ad hoc an
>> >> example...
>> >>
>> >> #include
>> >> #include
>> >>
>> >> int main ()
>> >> {
>> >> uint32_t init = 0x00000038;
>> >> uint32_t reg = init;
>> >> uint32_t new_bit;
>> >> int count = 0;
>> >> do {
>> >> new_bit = ((reg >> 2) + (reg >> 4) + (reg >> 6) + (reg >>
>> >> 30)) & 0x1;
>> >> reg <<= 1;
>> >> reg |= new_bit;
>> >> reg &= 0x7fffffff;
>> >> count++;
>> >> } while (reg != init);
>> >> printf ("period: %d\n", count);
>> >> }
>> >>
>> >>
>> >> Janis
>> >>
>> >> >> [...]
>> >>
>> >
>> > Pay attention that C Standard only requires for the same seed to
>> > always produces the same sequence. There is no requirement that
>> > different seeds have to produce different sequences.
>> > So, for generator in your example, implementation like below would
>> > be fully legal. Personally, I wouldn't even consider it as
>> > particularly poor quality:
>> >
>> > void srand(unsigned seed ) { init = seed | 1;}
>> >
>> > [O.T.]
>> > In practice, using LFSR for rand() is not particularly bright idea
>> > for different reason: LFSR is a reasonably good PRNG for a single
>> > bit, but not when you want to generate a group of 31 pseudo-random
>> > bits. In order to get 31 new bits, without predictable repetitions
>> > from the previous value, you would have to do 31 steps. That's
>> > slow! The process can be accelerate by generation of several bits
>> > at time via look up tables, but in order to get decent speed the
>> > table has to be rater big and using big tables in standard library
>> > is bad sportsmanship.
>> >
>> > It seems that overwhelming majority C RTLs use Linear Congruential
>> > Generators, probably because for Stanadard library compactness of
>> > both code and data is considered more important than very high
>> > speed (not that on modern HW LCGs are slow) or superior random
>> > properties of Mersenne Twisters.
>>
>> There is a paper "PCG: A Family of Simple Fast Space-Efficient
>> Statistically Good Algorithms for Random Number Generation"
>> by M. O’Neill where she gives a family of algorithms and runs
>> several statistical tests against known algorithms. Mersenne
>> Twister does not look good in tests. If you have enough (128) bits
>> LCGs do pass tests. A bunch of generators with 64-bit state also
>> passes tests. So the only reason to prefer Mersenne Twister is
>> that it is implemented in available libraries. Otherwise it is
>> not so good, have large state and needs more execution time
>> than alternatives.
>>
>
> I don't know. Testing randomness is complicated matter.
> How can I be sure that L’Ecuyer and Simard’s TestU01 suite tests things
> that I personally care about and that it does not test things that are
> of no interest for me? Especially, the latter.
It is extremaly unlikely that TestU only tests things that are
important to you. However, IMO value of such test is that
generator which passes the test avoids several common traps.
If any of them is relevant for you, generator will avoid it.
Of course, you may have _very_ special situation with
extremaly uncommon problem, but this is unlikely and anyway
in such case you probably should extensively test generator
that you want to use.
> Also, the TestU01 suit is made for generators with 32-bit output.
> M. O’Neill used ad hoc technique to make it applicable to generators
> with 64-bit output. Is this technique right? Or may be it put 64-bit
> PRNG at unfair disadvantage?
My point of view is that generator can be used to generate long
bistream. Then you can cut the bitstream and get number of
desired size. Good tests should check that such usage leads
to reasonable properties. So, fact that one generator produces
32-bit pieces and other produces 64-bit pieces should be irrelevant
to the test.
> Besides, I strongly disagree with at least one assertion made by
> O’Neill: "While security-related applications should
> use a secure generator, because we cannot always know the future
> contexts in which our code will be used, it seems wise for all
> applications to avoid generators that make discovering their entire
> internal state completely trivial."
> No, I know exactly what I am doing/ I know exactly that for my
> application easy discovery of complete state of PRNG is not a defect.
O’Neill is not a prophet, ignore what she say it you think you
know better (which is probably the above).
> Anyway, even if I am skeptical about her criticism of popular PRNGs,
> intuitively I agree with the constructive part of the article -
> medium-quality PRNG that feeds medium quality hash function can
[continued in next message]
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
