Обсуждение: random() function documentation

Hi Hackers,

I just noticed that the since the random() rewrite¹, the documentation's
claim² that it "uses a simple linear congruential algorithm" is no
longer accurate (xoroshiro128** is an xorshift variant, which is a
linear-feedback shift register algorithm).

I don't have a suggestion for the exact wording, since I don't know
whether xoroshiro128** qualifies as "simple", or to what level of
specificity we want to document the algorithm.

- ilmari

[1] https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=3804539e48e794781c6145c7f988f5d507418fa8
[2] https://www.postgresql.org/docs/devel/functions-math.html#FUNCTIONS-MATH-RANDOM-TABLE

=?utf-8?Q?Dagfinn_Ilmari_Manns=C3=A5ker?= <ilmari@ilmari.org> writes:
> I just noticed that the since the random() rewrite¹, the documentation's
> claim² that it "uses a simple linear congruential algorithm" is no
> longer accurate (xoroshiro128** is an xorshift variant, which is a
> linear-feedback shift register algorithm).

> I don't have a suggestion for the exact wording, since I don't know
> whether xoroshiro128** qualifies as "simple", or to what level of
> specificity we want to document the algorithm.

How about we just say "uses a linear-feedback shift register algorithm"?
"Simple" is in the eye of the beholder anyway.

            regards, tom lane

Tom Lane <tgl@sss.pgh.pa.us> writes:

> =?utf-8?Q?Dagfinn_Ilmari_Manns=C3=A5ker?= <ilmari@ilmari.org> writes:
>> I just noticed that the since the random() rewrite¹, the documentation's
>> claim² that it "uses a simple linear congruential algorithm" is no
>> longer accurate (xoroshiro128** is an xorshift variant, which is a
>> linear-feedback shift register algorithm).
>
>> I don't have a suggestion for the exact wording, since I don't know
>> whether xoroshiro128** qualifies as "simple", or to what level of
>> specificity we want to document the algorithm.
>
> How about we just say "uses a linear-feedback shift register algorithm"?

That works for me.  Nice and simple, and not overly specific.  Should we
perhaps also add a warning that the same seed is not guaranteed to
produce the same sequence across different (major?) versions?

> "Simple" is in the eye of the beholder anyway.

Indeed.

>             regards, tom lane

- ilmari

=?utf-8?Q?Dagfinn_Ilmari_Manns=C3=A5ker?= <ilmari@ilmari.org> writes:
> Tom Lane <tgl@sss.pgh.pa.us> writes:
>> How about we just say "uses a linear-feedback shift register algorithm"?

> That works for me.  Nice and simple, and not overly specific.  Should we
> perhaps also add a warning that the same seed is not guaranteed to
> produce the same sequence across different (major?) versions?

I wouldn't bother, on the grounds that then we'd need such disclaimers
in a whole lot of places.  Others might see it differently though.

            regards, tom lane

On Mon, 11 Apr 2022 at 20:20, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> >> How about we just say "uses a linear-feedback shift register algorithm"?

I think it'd be sufficient to just say that it's a deterministic
pseudorandom number generator. I don't see much value in documenting
the internal algorithm used.

> > Should we
> > perhaps also add a warning that the same seed is not guaranteed to
> > produce the same sequence across different (major?) versions?
>
> I wouldn't bother, on the grounds that then we'd need such disclaimers
> in a whole lot of places.  Others might see it differently though.

Agreed, though I think when the release notes are written, they ought
to warn that the sequence will change with this release.

Regards,
Dean

>>>> How about we just say "uses a linear-feedback shift register algorithm"?
>
> I think it'd be sufficient to just say that it's a deterministic
> pseudorandom number generator. I don't see much value in documenting
> the internal algorithm used.

Hmmm… I'm not so sure. ISTM that people interested in using the random 
user-facing variants (only random?) could like a pointer on the algorithm 
to check for the expected quality of the produced pseudo-random stream?

See attached.

>>> Should we perhaps also add a warning that the same seed is not 
>>> guaranteed to produce the same sequence across different (major?) 
>>> versions?
>>
>> I wouldn't bother, on the grounds that then we'd need such disclaimers
>> in a whole lot of places.  Others might see it differently though.
>
> Agreed,

Agreed.

> though I think when the release notes are written, they ought
> to warn that the sequence will change with this release.

Yes.

-- 
Fabien.

Fabien COELHO <coelho@cri.ensmp.fr> writes:
>>> How about we just say "uses a linear-feedback shift register algorithm"?

>> I think it'd be sufficient to just say that it's a deterministic
>> pseudorandom number generator. I don't see much value in documenting
>> the internal algorithm used.

> Hmmm… I'm not so sure. ISTM that people interested in using the random 
> user-facing variants (only random?) could like a pointer on the algorithm 
> to check for the expected quality of the produced pseudo-random stream?

> See attached.

I don't want to get that specific.  We were not specific before and
there has been no call for such detail in the docs.  (Unlike
closed-source software, anybody who really wants algorithmic details
can find all they want to know in the source code.)  It would just
amount to another thing to forget to update next time someone changes
the algorithm ... which is a consideration that leads me to favor
Dean's phrasing.

            regards, tom lane

Dean Rasheed <dean.a.rasheed@gmail.com> writes:

> On Mon, 11 Apr 2022 at 20:20, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>
>> >> How about we just say "uses a linear-feedback shift register algorithm"?
>
> I think it'd be sufficient to just say that it's a deterministic
> pseudorandom number generator. I don't see much value in documenting
> the internal algorithm used.
>
>> > Should we
>> > perhaps also add a warning that the same seed is not guaranteed to
>> > produce the same sequence across different (major?) versions?
>>
>> I wouldn't bother, on the grounds that then we'd need such disclaimers
>> in a whole lot of places.  Others might see it differently though.
>
> Agreed, though I think when the release notes are written, they ought
> to warn that the sequence will change with this release.

WFM on both points.

> Regards,
> Dean

- ilmari

=?utf-8?Q?Dagfinn_Ilmari_Manns=C3=A5ker?= <ilmari@ilmari.org> writes:
> Dean Rasheed <dean.a.rasheed@gmail.com> writes:
>> I think it'd be sufficient to just say that it's a deterministic
>> pseudorandom number generator. I don't see much value in documenting
>> the internal algorithm used.

> WFM on both points.

Sold then, I'll make it so.

            regards, tom lane