View Issue Details

IDProjectCategoryView StatusLast Update
0031642FPCDocumentationpublic2019-09-11 00:07
ReporterBart BroersmaAssigned ToMichael Van Canneyt 
PrioritynormalSeverityminorReproducibilityhave not tried
Status closedResolutionfixed 
Platformi386OSWindowsOS VersionWin7
Product Version3.0.1Product Build3.0.2 
Target VersionFixed in Version 
Summary0031642: Bug in documentation for Random?
Descriptionhttp://www.freepascal.org/docs-html/current/rtl/system/random.html

"Random returns a random number larger or equal to 0 and strictly less than L"

However random(a negative number) returns a number <= 0 and > L
Steps To Reproduceprogram r;
begin
  randomize;
  writeln('Random(-10) = ',Random(-10));
end.

C:\Users\Bart\LazarusProjecten>test
random(-10) = -1
C:\Users\Bart\LazarusProjecten>test
random(-10) = -4
Additional InformationDelphi documentation basically is the same (http://docwiki.embarcadero.com/Libraries/Berlin/en/System.Random) and the behaviour with neagtive inut is rather irratic
(
On Delphi 7:
Random(-10) = -776108169
Random(-10) = 244426112
Random(-10) = -1774796928
Random(-10) = 1443026331
Random(-10) = -919853036
Random(-10) = -747947900
Random(-10) = -1767321924
Random(-10) = -2114448955
Random(-10) = 1499268340
Random(-10) = -1658783534
)
TagsNo tags attached.
Fixed in Revision1649
FPCOldBugId
FPCTarget-
Attached Files

Activities

Bart Broersma

2017-04-06 18:35

reporter   ~0099412

The behaviour of Random(negative number) seems to be undefined (I asked on a Dutch Delphi forum), so maybe we should add a sentence like:

"if L < 0 the behaviour of the function is undefined"

Thaddy de Koning

2017-04-07 09:03

reporter   ~0099441

Last edited: 2017-04-07 09:09

View 4 revisions

The Delphi behavior is rather irratic because of its algorithm.
Since Delphi uses a different algorithm it exposes this repeated +/- sequence behavior. That makes it unusable as a random for negative values.
In FPC however, the behavior will give you a negative, valid range.
So indeed, the documentation needs to be updated by a remark for the negative range.
But it has nothing to do with Delphi. In Delphi its LCG prng is indeed undefined for negative ranges but in FPC it is not. It is a valid range.

Thaddy de Koning

2017-04-07 09:25

reporter   ~0099444

Note that at least in D7 and before Delphi has a bug in its random function that causes that behavior. At some point it mixes up a dword result with a signed longint. In our wiki there is a Delphi compatible random that does not suffer from that behavior and also produces a correct, defined, repeatable range for negative. http://wiki.lazarus.freepascal.org/Delphi_compatible_LCG_Random

Bart Broersma

2017-04-07 16:00

reporter   ~0099470

The behaviour of Random(negative number) is not documented, which is what this report is about.
It is undocumented in Delphi as well.

Bart Broersma

2017-04-07 18:27

reporter   ~0099476

> "if L < 0 the behaviour of the function is undefined"
That better read

"if L is negative the behaviour of the function is undefined"

Thaddy de Koning

2017-04-08 06:36

reporter   ~0099488

Last edited: 2017-04-08 07:17

View 4 revisions

There is no reason to document it as undefined.
It is defined. It is the reverse of the positive range and apart from sign has the same statistical properties. (And that is NOT the case with Delphi where it is really undefined. Don't mix that up, that's their bug)

Suggest to document as a defined range from Low(Integer) is strictly smaller and value is smaller or equal to zero.
The range is defined because the multiplication is done with range as the only negative in the calculation. Therefor it's just a sign flip on the positive range.

Maybe Jonas can confirm this if required: the twister output is cardinal, so a negative range will output negative values.

Thaddy de Koning

2017-04-08 07:00

reporter   ~0099489

Last edited: 2017-04-08 09:36

View 6 revisions

@Bart
Delphi's issue is its algorithm intermediate calculation before scaling outputs a longint and -1 * -1 = ? That's why Delphi has documented it as undefined.
This can never happen in FPC. So the behavior is FPC is defined even for a negative range.

The documentation seems partially based on the output of the Mersenne Twister itself, but that is not even public as it stands. All outputs that are published are scaled outputs. As such the documentation is indeed wrong: It is the scaling that determines signed or unsigned output, not the MT itself.
I suspect that this part of the documentation has spurious Delphi copy mode in it. Or adheres to the MT specification too much without regard to the scaling.

Bart Broersma

2017-04-08 14:25

reporter   ~0099500

Last edited: 2017-04-08 14:26

View 2 revisions

> It is defined. It is the reverse of the positive range

Where does it say so? This can be an implementation detail that may change at any time.

> That's why Delphi has documented it as undefined.
Delphi has not documented it as undefined, it has just not documented the behaviour for negative input (see http://docwiki.embarcadero.com/Libraries/Berlin/en/System.Random where it states that "Random returns a random number within the range 0 <= X < Range").
Note that this also implies that Random(0) is undefined.

Either way, my conclusionn is that our current documentation is not entirely correct.

Thaddy de Koning

2017-04-08 17:20

reporter   ~0099511

Last edited: 2017-04-08 17:31

View 2 revisions

Bart,
This "implementation detail" goes for similar implementations for scaled output in other major languages that have a mersenne twister as default prng, like Java, GNU C/C++, Scala, Visual C++, Excel ?! and many more that just like FPC conform to mt19937. mt19937 defines just the MT output as 32 bit unsigned. Scaling, however, is a very simple generic math operation depending on the scale you need. All of the above are therefor compatible with FPC given the same scale and the same randseed.
Note that is an important feature: it means data that relies on such a standard can also be used from other languages provided the RandSeed is known.

But indeed the documentation is not entirely correct. It only explains the mt19937 range and that is not even public.

Note that a look at the source code would also pointed you to my answer: it even contains code for negative range..

The only part where FPC deviates from the standard is its initial seed (0) that should be 5489, but that is minor and can be solved by setting RandSeed = 5489.

Bart Broersma

2017-04-08 18:16

reporter   ~0099515

Thaddy: this bugreport is NOT about a bug in the implementation of Random().

Thaddy de Koning

2017-04-10 14:08

reporter   ~0099541

No Bart, I know, but you insist that the documentation should reflect Delphi's
That is wrong. The documentation should reflect Lazarus random behavior, a mersenne twister, not the behavior of Delphi.
- In FPC the behavior for negative ranges IS defined, but not documented as such.
- In Delphi the behavior for negative ranges is undefined.(because it contains a bug)

So the documentation should be adapted so that it covers the defined behavior of a negative range. It should NOT read that such a behavior would be undefined. It is not... You have a habit of misreading me on this subject ;)
The assumption you make about undefined is not correct.
You can assume it is defined, but not yet documented.

Bart Broersma

2017-04-10 22:01

reporter   ~0099550

If we document random(negative) to be the same as -random(-negative), then we should also document that this is not D compatible.
I don't care either way.

Thaddy de Koning

2017-04-11 11:15

reporter   ~0099553

Last edited: 2017-04-11 11:39

View 7 revisions

I don't care if you don't care either way:the random in FPC is not compatible with Delphi random either way. You should have known by now!
Random is important! You can see from the codebase how much Jonas struggled to make it right.
If you want Delphi's random without the bug, go to the wiki and search for LCG. There you will have a Delph compatible random without the bug.

You are a very intelligent and respected person. Why do you not understand PRNG's? It's getting silly.

Michael will probably just document the behavior for the MT random.

Note that Delphi also follows a clear and documented algorithm, but with a buggy implementation
Note it is *already* documented that FPC has a different PRNG. And why.

And if you want a Delphi compatible Random + Delphi compatible documentation (because it is there before Delphi had a cardinal type, btw) use the my code in the wiki. If you are not satisfied I can re-introduce the bug in that code too.

Thaddy de Koning

2017-04-11 11:36

reporter   ~0099554

Can we resolve this in the docs, Michael?

Michael Van Canneyt

2017-04-11 11:49

administrator   ~0099555

I am waiting for input from Jonas to see whether the behaviour for negative L is intended or accidental, because this is not clear to me.

As soon as I hear from Jonas, the current behaviour will be documented more completely.

Bart Broersma

2017-04-11 15:08

reporter   ~0099556

Last edited: 2017-04-11 15:08

View 2 revisions

> if you want a Delphi compatible Random + Delphi compatible documentation
I never even suggested this.
The documentation currently does not decsribe the behaviour, which is why I filed this report.
To me it does not matter wether random is Delphi compatible or not.
This is up to the devels.

> Why do you not understand PRNG's?
I don't have to in order to understand the mismatch between documentation and behaviour.

> It's getting silly.
https://www.youtube.com/watch?v=2NS7Gkv4NNA

I will therefore refrain from further posting in this issue.

Thaddy de Koning

2017-04-11 15:32

reporter   ~0099559

As will I do, Bart. A simple positive or zero multiplied by a minus...
In this case also corrected for the range. In the code.

Tnx Michael.

Michael Van Canneyt

2019-09-10 09:05

administrator   ~0118014

I discussed with Jonas.

While the current implementation allows you to pass a negative limit, that this is possible this is purely an implementation detail.

Delphi Tokyo for instance - in a short test - returned 134775810 for Random(-100). Clearly the limit is not respected.

Currently no guarantees are made for negative limits. The implementation of random has changed in the past and may change again.
Formalizing the result for negative numbers would mean that we need to follow this in future implementations, and could become Delphi incompatible.

So we leave the behaviour for negative numbers undefined.

Bart Broersma

2019-09-10 22:52

reporter   ~0118023

> So we leave the behaviour for negative numbers undefined.
Which is not stated in the documents.
The input parameter is of type Longint, which is signed, so it would not be unreasonable to expect that random(negative number) behaves as the docs describe (which it does not, which was the exact reason I opende this bugreport. I did not care about changing the behaviour of random).

Can it please be aded to the docs that "the behaviour for negative numbers is undefined."?

Michael Van Canneyt

2019-09-10 23:23

administrator   ~0118025

I added a sentence to this effect.

Bart Broersma

2019-09-11 00:07

reporter   ~0118027

Thank you!

Issue History

Date Modified Username Field Change
2017-04-06 18:32 Bart Broersma New Issue
2017-04-06 18:32 Bart Broersma Status new => assigned
2017-04-06 18:32 Bart Broersma Assigned To => Michael Van Canneyt
2017-04-06 18:35 Bart Broersma Note Added: 0099412
2017-04-07 09:03 Thaddy de Koning Note Added: 0099441
2017-04-07 09:08 Thaddy de Koning Note Edited: 0099441 View Revisions
2017-04-07 09:08 Thaddy de Koning Note Edited: 0099441 View Revisions
2017-04-07 09:09 Thaddy de Koning Note Edited: 0099441 View Revisions
2017-04-07 09:25 Thaddy de Koning Note Added: 0099444
2017-04-07 16:00 Bart Broersma Note Added: 0099470
2017-04-07 18:27 Bart Broersma Note Added: 0099476
2017-04-08 06:36 Thaddy de Koning Note Added: 0099488
2017-04-08 06:37 Thaddy de Koning Note Edited: 0099488 View Revisions
2017-04-08 06:50 Thaddy de Koning Note Edited: 0099488 View Revisions
2017-04-08 07:00 Thaddy de Koning Note Added: 0099489
2017-04-08 07:06 Thaddy de Koning Note Edited: 0099489 View Revisions
2017-04-08 07:16 Thaddy de Koning Note Edited: 0099489 View Revisions
2017-04-08 07:17 Thaddy de Koning Note Edited: 0099488 View Revisions
2017-04-08 09:19 Thaddy de Koning Note Edited: 0099489 View Revisions
2017-04-08 09:33 Thaddy de Koning Note Edited: 0099489 View Revisions
2017-04-08 09:36 Thaddy de Koning Note Edited: 0099489 View Revisions
2017-04-08 14:25 Bart Broersma Note Added: 0099500
2017-04-08 14:26 Bart Broersma Note Edited: 0099500 View Revisions
2017-04-08 17:20 Thaddy de Koning Note Added: 0099511
2017-04-08 17:31 Thaddy de Koning Note Edited: 0099511 View Revisions
2017-04-08 18:16 Bart Broersma Note Added: 0099515
2017-04-10 14:08 Thaddy de Koning Note Added: 0099541
2017-04-10 22:01 Bart Broersma Note Added: 0099550
2017-04-11 11:15 Thaddy de Koning Note Added: 0099553
2017-04-11 11:16 Thaddy de Koning Note Edited: 0099553 View Revisions
2017-04-11 11:24 Thaddy de Koning Note Edited: 0099553 View Revisions
2017-04-11 11:33 Thaddy de Koning Note Edited: 0099553 View Revisions
2017-04-11 11:36 Thaddy de Koning Note Added: 0099554
2017-04-11 11:37 Thaddy de Koning Note Edited: 0099553 View Revisions
2017-04-11 11:38 Thaddy de Koning Note Edited: 0099553 View Revisions
2017-04-11 11:39 Thaddy de Koning Note Edited: 0099553 View Revisions
2017-04-11 11:49 Michael Van Canneyt Note Added: 0099555
2017-04-11 15:08 Bart Broersma Note Added: 0099556
2017-04-11 15:08 Bart Broersma Note Edited: 0099556 View Revisions
2017-04-11 15:32 Thaddy de Koning Note Added: 0099559
2019-09-10 09:05 Michael Van Canneyt Status assigned => resolved
2019-09-10 09:05 Michael Van Canneyt Resolution open => no change required
2019-09-10 09:05 Michael Van Canneyt FPCTarget => -
2019-09-10 09:05 Michael Van Canneyt Note Added: 0118014
2019-09-10 22:52 Bart Broersma Status resolved => feedback
2019-09-10 22:52 Bart Broersma Resolution no change required => reopened
2019-09-10 22:52 Bart Broersma Note Added: 0118023
2019-09-10 23:23 Michael Van Canneyt Status feedback => resolved
2019-09-10 23:23 Michael Van Canneyt Resolution reopened => fixed
2019-09-10 23:23 Michael Van Canneyt Fixed in Revision => 1649
2019-09-10 23:23 Michael Van Canneyt Note Added: 0118025
2019-09-11 00:07 Bart Broersma Status resolved => closed
2019-09-11 00:07 Bart Broersma Note Added: 0118027