[fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?

[Graeme Geldenhuys]

Hi,

I'm busy working on some of the remaining unit tests for the tiOPF
project that doesn't run 100% to my satisfaction yet under FPC
(compared to Delphi 7). One of the tests is for a Simple Encryption
algorithm implemented in tiOPF, that runs extremely slow under FPC
2.4.x (and 2.6.0-rc), and near instant under Delphi 7. I'm trying to
figure out why.

Below is a snippet of code I tracked down which contains the slowdown.
The problem under FPC lies with line 08, and more specifically the
call to Random(255). Simply replacing the Random(255) call with a
variable speeds up the loop by some 529 times!

I did a simple GetTickCount() timing around this loop. Delphi executes
the loop in 20 ticks. FPC 2.6.0-rc2 takes 10585 ticks!!!! The outer
loop runs 200400 iterations. The types for BitValue, ByteValue and
RandSeed is of type Byte.

01 for Index := 1 to Length(Source) do
02 begin
03 OrdValue := Ord(Source[Index]);
04 for BitCount := 0 to 7 do
05 begin
06 BitValue := Byte(OrdValue and (1 shl BitCount) = 1 shl BitCount);
07 RandSeed := ByteValue;
08 ByteValue := (((Random(255) + 1) div 2) * 2) + BitValue;
09 Result[(Index - 1) * 8 + BitCount + 1] := AnsiChar(ByteValue);
10 end;
11 end;

I'm using 64bit Ubuntu Linux 10.04.3 with 64-bit FPC 2.6.0-rc2.
Anybody have any ideas why the code under FPC runs so slowly? Is it
maybe some type conversion problem in FPC? I noticed that Random()
returns a Int64 on my Linux system. I'm not sure what it returns under
Delphi 7 (the docs don't say, and I can see the implementation of it).


If you wanted to test this, I attached a fully working program code
(snippets from the original tiOPF code) to demonstrate the problem.

[m***@wisa.be]

Post by Graeme Geldenhuys
Hi,
I'm busy working on some of the remaining unit tests for the tiOPF
project that doesn't run 100% to my satisfaction yet under FPC
(compared to Delphi 7). One of the tests is for a Simple Encryption
algorithm implemented in tiOPF, that runs extremely slow under FPC
2.4.x (and 2.6.0-rc), and near instant under Delphi 7. I'm trying to
figure out why.
Below is a snippet of code I tracked down which contains the slowdown.
The problem under FPC lies with line 08, and more specifically the
call to Random(255). Simply replacing the Random(255) call with a
variable speeds up the loop by some 529 times!
I did a simple GetTickCount() timing around this loop. Delphi executes
the loop in 20 ticks. FPC 2.6.0-rc2 takes 10585 ticks!!!! The outer
loop runs 200400 iterations. The types for BitValue, ByteValue and
RandSeed is of type Byte.
01 for Index := 1 to Length(Source) do
02 begin
03 OrdValue := Ord(Source[Index]);
04 for BitCount := 0 to 7 do
05 begin
06 BitValue := Byte(OrdValue and (1 shl BitCount) = 1 shl BitCount);
07 RandSeed := ByteValue;
08 ByteValue := (((Random(255) + 1) div 2) * 2) + BitValue;
09 Result[(Index - 1) * 8 + BitCount + 1] := AnsiChar(ByteValue);
10 end;
11 end;
I'm using 64bit Ubuntu Linux 10.04.3 with 64-bit FPC 2.6.0-rc2.
Anybody have any ideas why the code under FPC runs so slowly? Is it
maybe some type conversion problem in FPC? I noticed that Random()
returns a Int64 on my Linux system. I'm not sure what it returns under
Delphi 7 (the docs don't say, and I can see the implementation of it).

I think the random() algorithm is simply much more complicated in FPC.
It tries very hard to get an evenly distributed random number, more so
than Delphi, probably.

Jonas Maebe implemented it, I think, he can probably shed some more light on
this.

Michael.

[Jonas Maebe]

Post by m***@wisa.be
I think the random() algorithm is simply much more complicated in FPC.

That's correct. We use the mersenne twister, Delphi probably a linear
congruential generator. The mersenne twister has a much larger period.


Jonas

[Graeme Geldenhuys]

Post by Jonas Maebe
That's correct. We use the mersenne twister, Delphi probably a linear
congruential generator. The mersenne twister has a much larger period.

OK thanks for the info. This is a serious performance hit, but I
understand that the FPC implementation is different. Does FPC have a
faster (comparable to Delphi) version of Random() too?

@Michael,
Should the FPC docs maybe mention the fact that the FPC version is
considerably slower that Delphi (with an explanation why of course) -
purely for the purpose of informing those porting code from Delphi to
FPC. The original code in tiOPF is so slow, I almost thought the
program froze - thus making that code really unusable in an
application. Luckily that code will normally not be used in a real app
though. Delphi developers wanting to move to FPC should really be
warned about this, and use Random() sparingly.

[m***@wisa.be]

Post by Graeme Geldenhuys

Post by Jonas Maebe
That's correct. We use the mersenne twister, Delphi probably a linear
congruential generator. The mersenne twister has a much larger period.

OK thanks for the info. This is a serious performance hit, but I
understand that the FPC implementation is different. Does FPC have a
faster (comparable to Delphi) version of Random() too?
@Michael,
Should the FPC docs maybe mention the fact that the FPC version is
considerably slower that Delphi (with an explanation why of course) -
purely for the purpose of informing those porting code from Delphi to
FPC. The original code in tiOPF is so slow, I almost thought the
program froze - thus making that code really unusable in an
application. Luckily that code will normally not be used in a real app
though. Delphi developers wanting to move to FPC should really be
warned about this, and use Random() sparingly.

A good point.

Please add an entry in the bug tracker, or it is likely I will forget :/

Michael.

[Graeme Geldenhuys]

Post by m***@wisa.be
A good point.
Please add an entry in the bug tracker, or it is likely I will forget :/

http://bugs.freepascal.org/view.php?id=20834

Report created with a patch. Tweak the text as you see fit.

[John Lee]

Why not use the previous fpc version - I guess similar to that in delphi- I
can remember an email when Jonas changed it quite a few years ago - Jonas
must have older version - but can't really remember the fpc version -
v1.0? My guess it could be found in either svn or more likely the older cvs
fpc archive.

John

Post by Graeme Geldenhuys

Post by Jonas Maebe
That's correct. We use the mersenne twister, Delphi probably a linear
congruential generator. The mersenne twister has a much larger period.

OK thanks for the info. This is a serious performance hit, but I
understand that the FPC implementation is different. Does FPC have a
faster (comparable to Delphi) version of Random() too?
@Michael,
Should the FPC docs maybe mention the fact that the FPC version is
considerably slower that Delphi (with an explanation why of course) -
purely for the purpose of informing those porting code from Delphi to
FPC. The original code in tiOPF is so slow, I almost thought the
program froze - thus making that code really unusable in an
application. Luckily that code will normally not be used in a real app
though. Delphi developers wanting to move to FPC should really be
warned about this, and use Random() sparingly.
--
Regards,
- Graeme -
_______________________________________________
fpGUI - a cross-platform Free Pascal GUI toolkit
http://fpgui.sourceforge.net
_______________________________________________
http://lists.freepascal.org/mailman/listinfo/fpc-pascal

[Peter]

Graeme,

I would recommend using Marsaglia's XORShift.
Blisteringly fast, high quality statistically, and very easy to implement.

http://en.wikipedia.org/wiki/Xorshift


Regards,
Peter

Post by Graeme Geldenhuys

Post by Jonas Maebe
That's correct. We use the mersenne twister, Delphi probably a linear
congruential generator. The mersenne twister has a much larger period.

OK thanks for the info. This is a serious performance hit, but I
understand that the FPC implementation is different. Does FPC have a
faster (comparable to Delphi) version of Random() too?
@Michael,
Should the FPC docs maybe mention the fact that the FPC version is
considerably slower that Delphi (with an explanation why of course) -
purely for the purpose of informing those porting code from Delphi to
FPC. The original code in tiOPF is so slow, I almost thought the
program froze - thus making that code really unusable in an
application. Luckily that code will normally not be used in a real app
though. Delphi developers wanting to move to FPC should really be
warned about this, and use Random() sparingly.

[Inoussa OUEDRAOGO]

Post by Peter
Graeme,
I would recommend using Marsaglia's XORShift.
Blisteringly fast, high quality statistically, and very easy to implement.
http://en.wikipedia.org/wiki/Xorshift

For those who want to test it here is an Object Pascal implementation.

[John Lee]

How does it compare re 'randomness' cf current fpc version? The wikipedia
reference doesn't make this clear. Or the original fpc/delphi versions?
Jonas?
John

Post by Peter

Post by Peter
Graeme,
I would recommend using Marsaglia's XORShift.
Blisteringly fast, high quality statistically, and very easy to

implement.

Post by Peter
http://en.wikipedia.org/wiki/Xorshift

For those who want to test it here is an Object Pascal implementation.
--
Inoussa O.
_______________________________________________
http://lists.freepascal.org/mailman/listinfo/fpc-pascal

[Graeme Geldenhuys]

Post by Peter
I would recommend using Marsaglia's XORShift.
Blisteringly fast, high quality statistically, and very easy to implement.

Thanks for the info. Like I said, the original code in tiOPF is just
an extra [sample / simple] encryption implementation. There already
exists more secure encryption implementations in tiOPF, based on DES &
Blowfish. The latter two will be used in real-world applications, and
the simple encryption not.

Either way, I'll add this to my todo list, to improve the simple
encryption - but it's a low priority item at the moment.

[Peter]

I have noticed the following code in Tstrings, in the quicksort;

" Pivot := L + Random(R - L); // they say random is best "

Post by Graeme Geldenhuys

Post by Jonas Maebe
That's correct. We use the mersenne twister, Delphi probably a linear
congruential generator. The mersenne twister has a much larger period.

OK thanks for the info. This is a serious performance hit, but I
understand that the FPC implementation is different. Does FPC have a
faster (comparable to Delphi) version of Random() too?
@Michael,
Should the FPC docs maybe mention the fact that the FPC version is
considerably slower that Delphi (with an explanation why of course) -
purely for the purpose of informing those porting code from Delphi to
FPC. The original code in tiOPF is so slow, I almost thought the
program froze - thus making that code really unusable in an
application. Luckily that code will normally not be used in a real app
though. Delphi developers wanting to move to FPC should really be
warned about this, and use Random() sparingly.

[Graeme Geldenhuys]

Post by Jonas Maebe
That's correct. We use the mersenne twister, Delphi probably a linear
congruential generator. The mersenne twister has a much larger period.

I was reading a bit more about this. The Mersenne Twister (MT)
generator has a massive period of 2^19937−1, compared to the XorShift
generator, which in turn has a period of 2^128-1.

Most text I read mentions that MT is great for statistical purposes,
and performs well in its class.

So wouldn't it maybe make more sense to let the standard (read more
common) Random() call use a higher performance random number
generator, with a much lower period. Then add the MT generator as a
call to the Maths unit - where more statistical functions are located?

Most applications are not statistical apps, they just want a random
number here or there, so such high period low performance generator is
normally not required. Having it in the Maths unit still makes in
available when needed though - for those specialised apps.

Just a thought...

[Florian Klaempfl]

Post by Graeme Geldenhuys

Post by Jonas Maebe
That's correct. We use the mersenne twister, Delphi probably a linear
congruential generator. The mersenne twister has a much larger period.

I was reading a bit more about this. The Mersenne Twister (MT)
generator has a massive period of 2^19937−1, compared to the XorShift
generator, which in turn has a period of 2^128-1.
Most text I read mentions that MT is great for statistical purposes,
and performs well in its class.
So wouldn't it maybe make more sense to let the standard (read more
common) Random() call use a higher performance random number
generator, with a much lower period.

Well, once we thought we try to do things better than Delphi ;) Some
people, I think John Lee, asked for a better random in FPC years ago so
Jonas implemented a MT.

Post by Graeme Geldenhuys
Then add the MT generator as a
call to the Maths unit - where more statistical functions are located?
Most applications are not statistical apps, they just want a random
number here or there, so such high period low performance generator is
normally not required. Having it in the Maths unit still makes in
available when needed though - for those specialised apps.
Just a thought...

FPC uses MT at least for 10 years and nobody complained about
performance yet. So I suspect the cases might be very rare when random
performance matters and having good random numbers is always a good
thing ... I prefer not to change it but it's fine for me for delphi
compatibility's sake ;)

[Jorge Aldo G. de F. Junior]

Maybe implementing something other :

"The main advantages of the MWC method are that it invokes simple
computer integer arithmetic and leads to very fast generation of
sequences of random numbers with immense periods, ranging from around
260 to 22000000."

http://en.wikipedia.org/wiki/Multiply-with-carry

Post by Florian Klaempfl

Post by Graeme Geldenhuys

Post by Jonas Maebe
That's correct. We use the mersenne twister, Delphi probably a linear
congruential generator. The mersenne twister has a much larger period.

I was reading a bit more about this. The Mersenne Twister (MT)
generator has a massive period of 2^19937-1, compared to the XorShift
generator, which in turn has a period of 2^128-1.
Most text I read mentions that MT is great for statistical purposes,
and performs well in its class.
So wouldn't it maybe make more sense to let the standard (read more
common) Random() call use a higher performance random number
generator, with a much lower period.

Well, once we thought we try to do things better than Delphi ;) Some
people, I think John Lee, asked for a better random in FPC years ago so
Jonas implemented a MT.

Post by Graeme Geldenhuys
Then add the MT generator as a
call to the Maths unit - where more statistical functions are located?
Most applications are not statistical apps, they just want a random
number here or there, so such high period low performance generator is
normally not required. Having it in the Maths unit still makes in
available when needed though - for those specialised apps.
Just a thought...

FPC uses MT at least for 10 years and nobody complained about
performance yet. So I suspect the cases might be very rare when random
performance matters and having good random numbers is always a good
thing ... I prefer not to change it but it's fine for me for delphi
compatibility's sake ;)
_______________________________________________
http://lists.freepascal.org/mailman/listinfo/fpc-pascal

[Andreas Berger]

Post by Florian Klaempfl
FPC uses MT at least for 10 years and nobody complained about
performance yet. So I suspect the cases might be very rare when random
performance matters and having good random numbers is always a good
thing ... I prefer not to change it but it's fine for me for delphi
compatibility's sake ;)

Or maybe it's because no one had anything to compare it to. I have a
program that sends encrypted data every night to our data base. The
encryption part (which I wrote with random numbers) is VERY slow. I
never gave it much thought since it is running at a time where not much
else is happening. But I will look into it now.

[ik]

Post by Florian Klaempfl
FPC uses MT at least for 10 years and nobody complained about
performance yet. So I suspect the cases might be very rare when random
performance matters and having good random numbers is always a good
thing ... I prefer not to change it but it's fine for me for delphi
compatibility's sake ;)

I have a better idea.

Today FPC allow me to register different memory allocation implementation
that GetMem etc will use.
The same for string and widechar etc...

Why not to add such support for randomness as well ? Allow me to register
different random functions. Also might change the randomize procedure.

That way, we can use many random types according to how we wish to have it.
So in one unit I can use the Delphi's version, on the other the FPC's
version, and on the 3rd, something else.

On Delphi mode btw you can use by default the Delphi equivalent, and also
allow compiler directive and cli tags to active/inactive such algorithms.

What do you think ?

Ido

[Jürgen Hestermann]

Post by Florian Klaempfl
Well, once we thought we try to do things better than Delphi ;) Some
people, I think John Lee, asked for a better random in FPC years ago so
Jonas implemented a MT.

I think there are two very different approaches. I wrote a small tool
for testing network performance that simply generates a file with random
numbers. I used random() for the data because I wanted to avoid any
possible compression. There is no need to have a *real* random number in
this case. I always wondered, why this program reported slightly faster
network transfer in Delphi than in Lazarus/FPC but now I now why. Here
it is a bad thing that the calculation of the random numbers impacts the
speed calculation. IMO the generation of numbers should be much faster
than 100 MB/s but it already delays the whole process.

A completely different thing is statistics. Then you realy need a good
random() function. In this case the quality of the numbers is much more
important than speed.

But now we have a fast random() function in Delphi and a statistical
good one in FPC but none of them has both.

[Graeme Geldenhuys]

compression. There is no need to have a *real* random number in this case. I
always wondered, why this program reported slightly faster network transfer
in Delphi than in Lazarus/FPC but now I now why. Here it is a bad thing that

I just found another slow-down case in my code too. I have a data
generator that uses Random() for various things. I generate a few
million records of data to stress test our application. I always
thought the slowness was due to the data being stored on a RDBMS, but
some testing revealed that a large portion of the time taken to
complete the task is actually the numerous calls to Random(), not
solely the data storage as I always suspected.

Apparently XorShift can generate 125 million random numbers per second
[see url and page 5] - that's if I understood the technical paper
correctly, and not sure what machine they used for the test.
--- http://www.jstatsoft.org/v08/i14/paper

A completely different thing is statistics. Then you realy need a good
random() function. In this case the quality of the numbers is much more
important than speed.

Exactly. There are multiple cases for using random numbers. The
average Joe does care too much about the quality of the numbers.
Allowing FPC to have multiple random number generators - via two or
more different functions, or a plugable generator - does seem like a
good solution. I would suggest the default Random() call uses a higher
speed performance generator though, and not the MT one.

[Jürgen Hestermann]

Post by Graeme Geldenhuys
I would suggest the default Random() call uses a higher
speed performance generator though, and not the MT one.

Fully agree. Especially, because ex Delphi (and ex Turbo Pascal) users
would expect it like that. And most of them (coming from Delphi/TP)
believe that the randomness is not very reliable. They mainly don't even
know (like me) that the FPC random() is much more sophisticated.

[Felipe Monteiro de Carvalho]

On Thu, Dec 8, 2011 at 7:27 AM, Jürgen Hestermann

Fully agree. Especially, because ex Delphi (and ex Turbo Pascal) users would
expect it like that. And most of them (coming from Delphi/TP) believe that
the randomness is not very reliable. They mainly don't even know (like me)
that the FPC random() is much more sophisticated.

Based on what they expect that? For sure not based on reading the
Delphi documentation about Random:

http://docs.embarcadero.com/products/rad_studio/delphiAndcpp2009/HelpUpdate2/EN/html/delphivclwin32/System_Random.html

There is no mention of it being fast and also not about it being weak
statistically, so those are undocumented behavior. But it is written:

"Note: Because the implementation of the Random function may change
between compiler versions, we do not recommend using Random for
encryption or other purposes that require reproducible sequences of
pseudo-random numbers."

So are we supporting usage of Random in Delphi which depends on
implementation details even while the documentation never said they
were guaranteed but instead explicitly says it can change?

And what if it changes in the future to being slow and statistically
strong, we change again too?

And what about people using FPC only and depending on our Random being
statistically strong, they are less important then theorical Delphi
migrants?

[Florian Klaempfl]

Post by Felipe Monteiro de Carvalho
On Thu, Dec 8, 2011 at 7:27 AM, Jürgen Hestermann

Fully agree. Especially, because ex Delphi (and ex Turbo Pascal) users would
expect it like that. And most of them (coming from Delphi/TP) believe that
the randomness is not very reliable. They mainly don't even know (like me)
that the FPC random() is much more sophisticated.

Based on what they expect that?

In this border case they expect delphi compatibility because it effects
their code and not others.

[Graeme Geldenhuys]

Post by Felipe Monteiro de Carvalho
And what if it changes in the future to being slow and statistically
strong, we change again too?

The random number generator can be implemented in such a way that the
backend generator is user selectable.

Post by Felipe Monteiro de Carvalho
And what about people using FPC only and depending on our Random being
statistically strong, they are less important then theorical Delphi
migrants?

[like what was told to me numerous times before] They (FPC users)
should speak up now, or forever hold your peace. And those that have
spoken so far, all seem to be fine with a less statistically strong
default Random(), and have the statistically strong one available in
the Maths unit.

[Florian Klaempfl]

Post by Graeme Geldenhuys
[like what was told to me numerous times before] They (FPC users)
should speak up now,

Actually those who depend on speed should have spoken up ten years ago
when the MT was implemented.

[Graeme Geldenhuys]

Post by Florian Klaempfl
Actually those who depend on speed should have spoken up ten years ago
when the MT was implemented.

I for one did not even know about the existence of Free Pascal 10 year
ago. I don't believe I am alone either.

On a side note:
As for Jonas doing the implementation. I think we should give the
correct person credit here. The current repository only goes back as
far as 2005-05-16 (fpc release 2.0.0). But I believe Jonas simply
added the existing Object Pascal implementation or MT to FPC some 10
years ago, but the real implementor was:

"Translated to OP and Delphi interface added by Roman Krejci (6.12.1999)"
--- system.inc (line 478)

Just so that we are "statistically correct" with the credits too. ;-)

[Florian Klaempfl]

Post by Graeme Geldenhuys

Post by Florian Klaempfl
Actually those who depend on speed should have spoken up ten years ago
when the MT was implemented.

I for one did not even know about the existence of Free Pascal 10 year
ago. I don't believe I am alone either.

Indeed, but people depending for years of FPC's random function and
dicussed it years ago might not followed up this mailing list anymore
but just use it so they cannot speak up today either.

[Graeme Geldenhuys]

Post by Florian Klaempfl
dicussed it years ago might not followed up this mailing list anymore
but just use it so they cannot speak up today either.

That's their loss.

[Felipe Monteiro de Carvalho]

On Thu, Dec 8, 2011 at 8:48 AM, Graeme Geldenhuys

[like what was told to me numerous times before]  They (FPC users)
should speak up now, or forever hold your peace. And those that have
spoken so far, all seem to be fine with a less statistically strong
default Random(), and have the statistically strong one available in
the Maths unit.

You can count me as a -1

[Vincent Snijders]

Post by Graeme Geldenhuys

Post by Felipe Monteiro de Carvalho
And what if it changes in the future to being slow and statistically
strong, we change again too?

The random number generator can be implemented in such a way that the
backend generator is user selectable.

Post by Felipe Monteiro de Carvalho
And what about people using FPC only and depending on our Random being
statistically strong, they are less important then theorical Delphi
migrants?

[like what was told to me numerous times before]  They (FPC users)
should speak up now, or forever hold your peace.

When I used fpc in past to write statistical simulation I also
investigated the random number generator and was pleased to see that
it used the Mersenne Twister. I hope a upcoming change won't break my
programs or make there outcome suspect because of the poor quality of
the random number generator.

Writing a fast number generator is almost a one liner:
http://en.wikipedia.org/wiki/Linear_congruential_generator

Vincent (not holding his peace)

[Henry Vermaak]

Post by Vincent Snijders

Post by Graeme Geldenhuys

Post by Felipe Monteiro de Carvalho
And what if it changes in the future to being slow and statistically
strong, we change again too?

The random number generator can be implemented in such a way that the
backend generator is user selectable.

Post by Felipe Monteiro de Carvalho
And what about people using FPC only and depending on our Random being
statistically strong, they are less important then theorical Delphi
migrants?

[like what was told to me numerous times before] They (FPC users)
should speak up now, or forever hold your peace.

When I used fpc in past to write statistical simulation I also
investigated the random number generator and was pleased to see that
it used the Mersenne Twister. I hope a upcoming change won't break my
programs or make there outcome suspect because of the poor quality of
the random number generator.

I agree, quality first. Especially when faster lower quality
alternatives are so easy to implement.

Henry

[Graeme Geldenhuys]

Post by Henry Vermaak
I agree, quality first.

I would normally agree with that. But such huge magnitudes slower
(20ms vs 10585ms) on a new Quad-Core type system? That just seems a
bit excessive, and considering most use cases are not even for
statistical type applications.

[Vinzent Höfler]

On Thu, 08 Dec 2011 10:52:01 +0100, Graeme Geldenhuys

Post by Graeme Geldenhuys

Post by Henry Vermaak
I agree, quality first.

I would normally agree with that. But such huge magnitudes slower
(20ms vs 10585ms) on a new Quad-Core type system? That just seems a
bit excessive, and considering most use cases are not even for
statistical type applications.

Well, considering that the MT is a very bad choice as PRNG for a stream-
cipher (even if it's never used in "production code", it still gives me the
creeps), I'd say, your use case isn't the typical one, either. ;)

In my case I needed a thread-safe version, so may I request that
System.Random() shall be protected against concurrent access - making it
even slower?

I mean, using your own random generator for whatever reason (statistical
properties, cryptographically strong, lightning fast) isn't exactly rocket
science. ;)

<http://stop-me.svn.sourceforge.net/viewvc/stop-me/trunk/src/lfsr.pas?revision=53&view=markup>

Especially because you could speed-up your code alone by using the 64
random bits you are actually getting from the Random() call instead of
generating a stream of 512 bits for each single character. ;)

So, to come to a conclusion, I do not see any reason why the current
implementation of System.Random() shall be changed.


Vinzent.

[Dimitrios Chr. Ioannidis]

Hi,

[like what was told to me numerous times before] They (FPC users)
should speak up now, or forever hold your peace. And those that have
spoken so far, all seem to be fine with a less statistically strong
default Random(), and have the statistically strong one available in
the Maths unit.

IMO, there is two separate subjects in this discussion. The first
obviously is the implementation and the Delphi compatibility of the
Random function but for me the hidden and most valuable subject is the
fpc's lack of documentation. If the algorithm used to implement the
Random function was documented then it wouldn't be any reason for this
discussion . The user will be warned, informed and acted accordingly to
suit his needs.

And plz don't use the UTS ( Use The Source) on me. There is situations
that you don't have the time and the state of mind to read and study all
the fpc sources.

In the end IMO don't change the Random implementation just documented it.

regards,

[Tomas Hajny]

.
.

Post by Graeme Geldenhuys

Post by Felipe Monteiro de Carvalho
And what about people using FPC only and depending on our Random being
statistically strong, they are less important then theorical Delphi
migrants?

[like what was told to me numerous times before] They (FPC users)
should speak up now, or forever hold your peace. And those that have
spoken so far, all seem to be fine with a less statistically strong
default Random(), and have the statistically strong one available in
the Maths unit.

It's always that people who want changes are louder than those who are
happy with the current state. Changing something (to worse, at least for
some users) shouldn't be done just because people not happy with the
current state are louder than those who are happy now, should it?

Anyway: some people expressed their wish to keep the current solution as
the default option exactly like you suggested, and you still argue with
them that their view is not valid - strange...

Tomas

[Graeme Geldenhuys]

Post by Tomas Hajny
Anyway: some people expressed their wish to keep the current solution as
the default option exactly like you suggested,

Did I suggest this?

Post by Tomas Hajny
and you still argue with
them that their view is not valid - strange...

Clearly somewhere our lines have crossed. Strange indeed...

[Tomas Hajny]

Post by Graeme Geldenhuys

Post by Tomas Hajny
Anyway: some people expressed their wish to keep the current solution as
the default option exactly like you suggested,

Did I suggest this?

.
.

Sorry, I wasn't clear - you suggested that people interested in keeping
the current solution raised their voice (which at least Felipe and
Karl-Michael did).

Tomas

[waldo kitty]

Post by Graeme Geldenhuys

Post by Felipe Monteiro de Carvalho
And what about people using FPC only and depending on our Random being
statistically strong, they are less important then theorical Delphi
migrants?

[like what was told to me numerous times before] They (FPC users)
should speak up now, or forever hold your peace. And those that have
spoken so far, all seem to be fine with a less statistically strong
default Random(), and have the statistically strong one available in
the Maths unit.

i wouldn't say specifically place it in the maths unit but what's wrong with
having both available via a "fastrandom" boolean parameter that is passed? if
the parameter is not passed, it is defaulted to TRUE... if one wants the MT
random, then they send FALSE in this parameter... seems simple enough... i think ;)

[Graeme Geldenhuys]

"fastrandom" boolean parameter that is passed? if the parameter is not
passed, it is defaulted to TRUE... if one wants the MT random, then they
send FALSE in this parameter... seems simple enough... i think ;)

That sounds perfect to me, but now will the FPC team accept such a
patch (with their double standards and all)? I don't mind implementing
such a change, but let me know first if I will be wasting my time or
not on a patch that will probably never be accepted.

[Reimar Grabowski]

On Thu, 08 Dec 2011 12:51:18 -0500

Post by waldo kitty
i wouldn't say specifically place it in the maths unit but what's wrong with
having both available via a "fastrandom" boolean parameter that is passed? if
the parameter is not passed, it is defaulted to TRUE... if one wants the MT
random, then they send FALSE in this parameter... seems simple enough... i think ;)

Looks like you have it reversed. The parameter should default to FALSE to not break existing code relying on FPCs random function and if you need the fast one you have to call it with TRUE. As the fast random function then has to be called with random(x, true) it will not help Graeme in any way as he wants the fast one to be the default to bring performance to the same level as Delphi and stay compatible, this means calling random without a boolean parameter.
But breaking existing code for such a "feature" is IMHO the wrong thing to do.

just my 2 cents
R.

[Jürgen Hestermann]

Post by Reimar Grabowski
The parameter should default to FALSE to not break existing code relying on FPCs random function

And what about existing code coming from Delphi/Turbo Pascal? This was a
strong argument in the past for doing even crap coding.

Post by Reimar Grabowski
As the fast random function then has to be called with random(x, true)

I think this would be the best solution: Add an additional parameter to
random() so that existing code would stop on compiling and the user has
to look up the help to see what this additional parameter means. Then
everybody is forced to choose the version that fits for his needs.

But having the same function doing something different (or at a
magnitude different speed) is the wrong way IMO. Just imagine that
divisions suddenly need 500 times the time because the last digit was
inaccurate or so. In many cases the error is not relevant in your
programs but the speed penalty surely would.

[Florian Klaempfl]

Post by Jürgen Hestermann

Post by Reimar Grabowski
The parameter should default to FALSE to not break existing code
relying on FPCs random function

And what about existing code coming from Delphi/Turbo Pascal? This was a
strong argument in the past for doing even crap coding.

As said before, this came only up because for every difference somebody
popped up and cried. When random was implemented using MT, we didn't
learn this lesson.

Post by Jürgen Hestermann
Just imagine that
divisions suddenly need 500 times the time because the last digit was
inaccurate or so.

According to measurements of me and other peoples, random is only 7-10
times slower (depending on the CPU).

[Graeme Geldenhuys]

Post by Florian Klaempfl
According to measurements of me and other peoples, random is only 7-10
times slower (depending on the CPU).

What do you feed your computer, because mine differs vastly from yours.

Not to mention that our clients still run P4 workstations under
Win2000 or XP. So lets hope no production code uses Random() a lot.

[Florian Klaempfl]

Post by Graeme Geldenhuys

Post by Florian Klaempfl
According to measurements of me and other peoples, random is only 7-10
times slower (depending on the CPU).

What do you feed your computer,

Nothing, but I don't mess with things I don't understand :) Changing
randseed (and makes absolutely no change except if your random generator
might be bad ;)) during random number generation is really a bad idea:

c:\>test
Length(psData) = 200401
ByteValue: 187
Length(Source) = 200401
First Loop....
elapsed time: 6751

c:\>test
Length(psData) = 200401
ByteValue: 174
Length(Source) = 200401
First Loop....
elapsed time: 60

Post by Graeme Geldenhuys
because mine differs vastly from yours.

[n***@z505.com]

Post by Graeme Geldenhuys

Post by Florian Klaempfl
According to measurements of me and other peoples, random is only 7-10
times slower (depending on the CPU).

What do you feed your computer, because mine differs vastly from yours.

In europe electricity is sometimes 220 volts. Twice as fast as 110 volts
in Canada, but I'm not sure about africa ;-)

Can the compiler send a warning message WARNING: random is faster if you
use the other unit in soandso.pas.

[Graeme Geldenhuys]

Post by n***@z505.com
In europe electricity is sometimes 220 volts. Twice as fast as 110 volts
in Canada, but I'm not sure about africa ;-)

:-) South Africa uses 220 volts too.

[Reimar Grabowski]

On Fri, 09 Dec 2011 07:27:46 +0100

Post by Jürgen Hestermann

Post by Reimar Grabowski
The parameter should default to FALSE to not break existing code relying on FPCs random function

And what about existing code coming from Delphi/Turbo Pascal? This was a
strong argument in the past for doing even crap coding.

Not by me, but the FPC developers. I am not interested in Delphi/TP compatability and never was, so I don't care if Delphi/TP code works or not, but I care if code written exclusively in and for FPC continues to work as it did. I think that Delphi is a burden for FPC and Lazarus, but the developers have other opinions, so be it.
I don't need a change at all. It may be irritating for a Delphi developer that his code runs slower, but profiling is no secret art and changing a random implementations to a less 'good' but faster one is a matter of minutes.
Like people already said, lots of talk about a 'problem' that 10 years noone has seen as one.

Another 2 cents
R.

[Schindler Karl-Michael]

Hi

My 2 cents:
Since computers get faster and faster with time, there is a time line for more accurate techniques, even if they are more costly. So, shifting to a faster, but less accurate method now, will cause another change in the future. The only question is on the time, when computers are so fast, that hardly anyone will bother about speed of the method. Therefore, I propose to keep the current method, because it has the better long term perspective. The needs for a faster method today should be matched with an additional procedure, let's name it random_fast. Sure enough, it would the possibility to select the generator would be more elegant, for example, when calling randomize. But I would always keep the more accurate generator as the default for the reason outlined above.

Michael Schindler

[Graeme Geldenhuys]

Post by Schindler Karl-Michael
now, will cause another change in the future. The only question is on the time, when
computers are so fast, that hardly anyone will bother about speed of the method.

I absolutely despise such logic! It's a disgrace to the programming profession.

Post by Schindler Karl-Michael
Therefore, I propose to keep the current method, because it has the better long term
perspective.

And in the mean time my code must run 529x slower than Delphi. Great.

Post by Schindler Karl-Michael
The needs for a faster method today should be matched with an additional procedure,
let's name it random_fast.

Nice, now I need to riddle my code with IFDEF statements (making in
much harder to read) because lots of the code in question is shared
between Delphi and FPC. :-/

[Felipe Monteiro de Carvalho]

On Thu, Dec 8, 2011 at 10:45 AM, Graeme Geldenhuys

Post by Graeme Geldenhuys
Nice, now I need to riddle my code with IFDEF statements (making in
much harder to read) because lots of the code in question is shared
between Delphi and FPC. :-/

According to the Delphi documentation you could in the future need
ifdefs for various delphi versions anyway.

So the best solution is introducing MyRandom in your code, then no
ifdefs will be required and it is guaranteed to work in future Delphi
versions too.

[Jürgen Hestermann]

Post by Schindler Karl-Michael
The only question is on the time, when computers are so fast, that hardly anyone will bother about speed of the method.

That's nonsense. The only thing that happens if computers speed
increases is, that you put more code into the same time slot. Otherwise
working with computers would have become blinding fast but the opposite
is the case. The speed increase of computers is overcompensated by
burdening more code on them (which is also a consequence of an attitude
like yours).

I have a program that generates data for a file to test network speed.
Currently I am testing on 100 MB/s. But soon my program will be used
for 1 GB/s networks. So the data generation has to speed up by a factor
of 10 if it should not slow down. It will never happen that the speed of
the computer will make the impact of the random() function delay go
away. If random() dominates your program it will do so in ten years too.

[Graeme Geldenhuys]

speed increase of computers is overcompensated by burdening more code on
them (which is also a consequence of an attitude like yours).

+1

If random() dominates your program it will do so in ten years too.

@Karl-Michael
Apparently the Random MT function was implement 10 year ago in FPC.
Ten years later it is still f**ken slow on a new Quad-Core system. So
how long exactly are we supposed to wait before we don't notice the
function being slow? As I said, that mentality is absolute rubbish!

[Dimitri Smits]

Post by Jürgen Hestermann
But now we have a fast random() function in Delphi and a statistical
good one in FPC but none of them has both.

just my 2cts, but...


The Delphi 7 help states about "function System.Random [ ( Range: Integer) ];" the following
--
In Delphi code, Random returns a random number within the range 0 <= X < Range. If Range is not specified, the result is a real-type random number within the range

0 <= X < 1.

To initialize the random number generator, add a single call Randomize or assign a value to the RandSeed variable before making any calls to Random.

Note: Because the implementation of the Random function may change between compiler versions, we do not recommend using Random for encryption or other purposes that require reproducible sequences of pseudo-random numbers.
--


I would argue that:
- using Random for encryption always was a bad idea
- you have largely incompatible implementations and expectations when you want to make code fpc+delphi7 compilable

As for other Random functions, Delphi7 also has Math.RandG (gaussian distribution around a mean) and Math.RandomRange. I would suggest the Math.RandomMT and a simpler, faster random method + good documenting.

The above Delphi-help snippet also discourages explicitly the use for encryption and other purposes. A "See also" could be used to get some statistically better distributed random numbers.

OR, what was suggested with the "pluggable" Random number generatorcall like the memorymanagers.

like I said, just my 2cts...

kind regards,
Dimitri Smits

[Marco van de Voort]

Post by Graeme Geldenhuys

Post by Felipe Monteiro de Carvalho
And what about people using FPC only and depending on our Random being
statistically strong, they are less important then theorical Delphi
migrants?

[like what was told to me numerous times before] They (FPC users)
should speak up now, or forever hold your peace. And those that have
spoken so far, all seem to be fine with a less statistically strong
default Random(), and have the statistically strong one available in
the Maths unit.

I don't enjoy validating working programs because of this.

It's a strange case where people are advocating the introduction of a slower
"manager" to improve the speed of random :-)

IMHO people wanting a guaranteed fast random, should create a package with a
guaranteed fast random, and use that, and not confuse it with compatibility
issues.

It is only a matter of time before an user wants to create a program that
includes a package that wants fast random with a package that wants a
reliable reproducable one.

[Graeme Geldenhuys]

Post by Marco van de Voort
It's a strange case where people are advocating the introduction of a slower
"manager" to improve the speed of random :-)

It's called an acceptable compromise, by those that use it most.

Just like FPC doesn't do micro code optimizations on each and every
platform. The FPC performance [see Martin Schriebers annual posts
about FPC speed vs Delphi 7] hit is a compromise for easier
maintainability of source code. A simple trade-off.

The Maths unit is known for more advanced math and statistical
features. A strong random number generator seem a good fit for that
unit.

[Marco van de Voort]

Post by Tomas Hajny

Post by Graeme Geldenhuys

Post by Tomas Hajny
the default option exactly like you suggested,

Did I suggest this?

Sorry, I wasn't clear - you suggested that people interested in keeping
the current solution raised their voice (which at least Felipe and
Karl-Michael did).

And me. I don't see anything in a manager-record solution for this.

I'd be happy to have a random package in packages/ with a bunch of random
mgrs, but I don't see the urgent need to make this default if a better
solution is already there.

It is like the fast trunc/round discussions over again.

[Bart]

My Delphi's random is only 7 times faster then fpc's random (Celeron 700).

Bart

Post by Marco van de Voort

Post by Tomas Hajny

Post by Graeme Geldenhuys

Post by Tomas Hajny
the default option exactly like you suggested,

Did I suggest this?

Sorry, I wasn't clear - you suggested that people interested in keeping
the current solution raised their voice (which at least Felipe and
Karl-Michael did).

And me. I don't see anything in a manager-record solution for this.
I'd be happy to have a random package in packages/ with a bunch of random
mgrs, but I don't see the urgent need to make this default if a better
solution is already there.
It is like the fast trunc/round discussions over again.
_______________________________________________
http://lists.freepascal.org/mailman/listinfo/fpc-pascal

[Vincent Snijders]

Post by Graeme Geldenhuys
Hi,
I did a simple GetTickCount() timing around this loop. Delphi executes
the loop in 20 ticks. FPC 2.6.0-rc2 takes 10585 ticks!!!! The outer
loop runs 200400 iterations. The types for BitValue, ByteValue and
RandSeed is of type Byte.
01  for Index := 1 to Length(Source) do
02  begin
03    OrdValue := Ord(Source[Index]);
04    for BitCount := 0 to 7 do
05    begin
06      BitValue := Byte(OrdValue and (1 shl BitCount) = 1 shl BitCount);
07      RandSeed := ByteValue;
08      ByteValue := (((Random(255) + 1) div 2) * 2) + BitValue;
09      Result[(Index - 1) * 8 + BitCount + 1] := AnsiChar(ByteValue);
10    end;
11  end;

I have one question about this code, why is RandSeed set inside the
loop and not outside the loop or even at the program start?
If you change the randseed, then the random number generator has to be
initialized and that is more costly for a stateful RNG as the mersenne
twister.

Vincent

[Florian Klaempfl]

Post by Vincent Snijders

Post by Graeme Geldenhuys
Hi,
I did a simple GetTickCount() timing around this loop. Delphi executes
the loop in 20 ticks. FPC 2.6.0-rc2 takes 10585 ticks!!!! The outer
loop runs 200400 iterations. The types for BitValue, ByteValue and
RandSeed is of type Byte.
01 for Index := 1 to Length(Source) do
02 begin
03 OrdValue := Ord(Source[Index]);
04 for BitCount := 0 to 7 do
05 begin
06 BitValue := Byte(OrdValue and (1 shl BitCount) = 1 shl BitCount);
07 RandSeed := ByteValue;
08 ByteValue := (((Random(255) + 1) div 2) * 2) + BitValue;
09 Result[(Index - 1) * 8 + BitCount + 1] := AnsiChar(ByteValue);
10 end;
11 end;

I have one question about this code, why is RandSeed set inside the
loop and not outside the loop or even at the program start?
If you change the randseed, then the random number generator has to be
initialized and that is more costly for a stateful RNG as the mersenne
twister.

Oops, mails crossed. The assignment to randseed is indeed the problem.
Why is it done? Bad random generator of delphi :)?

[Virgo Pärna]

Post by Florian Klaempfl
Oops, mails crossed. The assignment to randseed is indeed the problem.
Why is it done? Bad random generator of delphi :)?

I don't know, how bad Delphis random generator is, but I once years ago did make a mistake
of calling randomize before random. It was a school assignment for using Turbo Pascal graphics.
So I made program, that was supposed to fill screen with random dots (colour was also set with
random). Anyway, when I called randomize before random, then as a result dots didn't fill the
screen, but were mostly along the diagonal of the screen. So I'd guess, that setting randseed
multiple times could be actually bad for randomness of results. Or maybe modern algorithms are
better at situations like this?

[Graeme Geldenhuys]

Post by Vincent Snijders
I have one question about this code, why is RandSeed set inside the
loop and not outside the loop or even at the program start?

For the full code as used by tiOPF, see the following URL.

http://tiopf.svn.sourceforge.net/viewvc/tiopf/tiOPF2/Trunk/Options/tiEncryptSimple.pas?revision=2143&view=markup

I didn't write this encryption code, I merely debugged why the unit
tests for this unit took so long to complete, compared to under
Delphi.

Looking at the code again, I have no idea how it will affect the
encryption algorithm if I move the assignment to RandSeed outside the
loop (just after the first assignment to ByteValue). As a test, made
your suggested change and ran the unit tests. The unit tests still
pass, and the performance under FPC has drastically improved. FPC
(64-bit) is now roughly 4 times slower that Delphi. Much better
indeed, and an acceptable result.

I'll see if I can get hold of the original author of this code and
what they think about the suggested change - and if it will affect the
encryption algorithm at all.

Thanks Vincent for mentioning this. I totally overlooked that.

[Felipe Monteiro de Carvalho]

On Fri, Dec 9, 2011 at 9:39 AM, Graeme Geldenhuys

Post by Graeme Geldenhuys
I didn't write this encryption code, I merely debugged why the unit
tests for this unit took so long to complete, compared to under
Delphi.

It is specifically written in the Delphi documentation that Random
should not be utilized for encryption...

[Graeme Geldenhuys]

Post by Felipe Monteiro de Carvalho
It is specifically written in the Delphi documentation that Random
should not be utilized for encryption...

Delphi documentation mentions a lot of things you mustn't do... Does
that stop anybody. ;-)
Like I said, I didn't write that code, and I don't specialise in
encryption algorithms. But Florian might be right, the RandSeed
assignment might have been added due to the bad random generator of
Delphi - hopefully the original author of the code can shed some
light.

[Reimar Grabowski]

On Fri, 9 Dec 2011 10:47:15 +0200

Post by Graeme Geldenhuys
Like I said, I didn't write that code, and I don't specialise in
encryption algorithms.

That's not your fault. Your fault was to not identify the problem correctly but blame FPCs implementation and later rant about "double standards" and "unusable code", without the knowledge to back up your statements. Next time please take the time to identify the problem correctly before jumping to conclusions.
No offense ment.

R.

[Graeme Geldenhuys]

knowledge to back up your statements. Next time please take the time to identify the problem >correctly before jumping to conclusions.
No offense ment.

No offense take. Two unknown (to most) facts came out of this
discussion. 1) the FPC Random() function IS slower than Delphi's. 2)
FPC implements a different random generator than Delphi. Is this good
or bad? Considering the "must be Delphi compatible" term thrown around
so often. Even with the original (slightly non-optimal usage of
Random) code, Delphi ran it fine and fast, FPC didn't. So from a
porting point of view (Delphi to FPC), there was a problem which
others might get caught in as well.

Either way, thanks to Vincent's sharp eye, which everybody but Vincent
overlooked, the speed problem in the tiOPF code can be greatly reduced
to acceptable levels with FPC - even though FPC has a different random
generator.

Thanks to all that participated and helped solve my problem. It was an
interesting discussion as always.

[Jonas Maebe]

Post by Graeme Geldenhuys
Looking at the code again, I have no idea how it will affect the
encryption algorithm if I move the assignment to RandSeed outside the
loop

It will improve the randomness of the generated numbers. Changing the
random seed all the time removes any properties the random generator
normally has. In other words, the original code is wrong.


Jonas

[Graeme Geldenhuys]

Post by Jonas Maebe
It will improve the randomness of the generated numbers.

Thanks Jonas.

[Jorge Aldo G. de F. Junior]

even if FPC implemented a ultra high tech PRNG it would be compatible
with DELPHI :

1 - Delphi asserts that you should not use the Random function to
encryption porpuses.
2 - Delphi asserts no speed guarantees.
3 - Delphi asserts no randomness quality guarantees.

IE : to be compatible you only need the function to have the same
calling parameters and result type.

Formally, in that case, even this would be "compatible" :

Function Random(): Real;
Begin
Result := 4; { i throwed a dice to reach that result ! }
End;

Post by Graeme Geldenhuys

Post by Jonas Maebe
It will improve the randomness of the generated numbers.

Thanks Jonas.
--
Regards,
  - Graeme -
_______________________________________________
fpGUI - a cross-platform Free Pascal GUI toolkit
http://fpgui.sourceforge.net
_______________________________________________
http://lists.freepascal.org/mailman/listinfo/fpc-pascal

[Dimitri Smits]

Post by Felipe Monteiro de Carvalho
On Fri, Dec 9, 2011 at 9:39 AM, Graeme Geldenhuys

Post by Graeme Geldenhuys
I didn't write this encryption code, I merely debugged why the unit
tests for this unit took so long to complete, compared to under
Delphi.

It is specifically written in the Delphi documentation that Random
should not be utilized for encryption...

true, (but) looking at the code again, it seems that you always have a predictable sequence when using the same algorithm. Not sure if that is a good thing or a bad one in cryptology :-). After all, when you do not randomize() first, randseed has a default startupvalue (and otherwise it is typically seeded with a timestamp of somesorts).

I don't remember where I read it (ages ago), and the comment in Delphi seems to negate that this is the used algorithm, but this 'predictable sequence from the same seed'-property is especially true when using a LCG pseudo-random-number-generator.

Just to be sure, the wikipedia article DOES mention that Delphi (and every other HL language that matters :-)) supplies a Random functionality that is based on a LCG.

http://en.wikipedia.org/wiki/Linear_congruential_generator

And in the java realm there are numerous other algorithms available, but the default implementation with the language libraries is a LCG, as does the C(++).

Reading the article again, I find a few paragraphs corresponding to the Delphi help. Excerpt from the 'advantages and disadvantages' part of the page:

--
LCGs should not be used for applications where high-quality randomness is critical. For example, it is not suitable for a Monte Carlo simulation because of the serial correlation (among other things). They should also not be used for cryptographic applications; see cryptographically secure pseudo-random number generator for more suitable generators. If a linear congruential generator is seeded with a character and then iterated once, the result is a simple classical cipher called an affine cipher; this cipher is easily broken by standard frequency analysis.
--

kind regards,
Dimitri Smits

[Dimitri Smits]

Post by Graeme Geldenhuys

Post by Felipe Monteiro de Carvalho
It is specifically written in the Delphi documentation that Random
should not be utilized for encryption...

Delphi documentation mentions a lot of things you mustn't do... Does
that stop anybody. ;-)

only those that take their jobs seriously and read help/manuals iso assuming? :-)

Post by Graeme Geldenhuys
Like I said, I didn't write that code, and I don't specialise in
encryption algorithms. But Florian might be right, the RandSeed
assignment might have been added due to the bad random generator of
Delphi - hopefully the original author of the code can shed some
light.

I actually doubt that that codesnippet does any real encryption.

[Graeme Geldenhuys]

Post by Dimitri Smits
I actually doubt that that codesnippet does any real encryption.

It isn't. The sample code / test program I posted is just a snippet of
the actual unit. No point in posting the whole unit here, just to
point out that a single section of code in one method is the location
of the slow-running code under FPC. I only supplied the slow-running
code to demonstrate the problem.

[Jorge Aldo G. de F. Junior]

Well, lets go to theory :

One way to build a cypher is to XOR the stream that must be encrypted
against a fixed value.

But, this is easy to break using statistical methods.

So the next logical way to do this is to XOR the stream against
another stream of numbers, kind of one time password.

But, the stream of numbers must be shared by both ends.

How ? Simple, generate the stream on-the-fly using a PRNG.

Now you only need to share the seed of the PRNG and the encrypted stream.

But for this to work the same PRNG must be used on both ends, and the
PRNG must be strong enough with a period much longer than the size of
the data being encrypted.

Whats wrong with calling RANDOMIZE during the loop ? The problem is
that you keep seeding the PRNG with the Now() (current time stamp),
defeating the whole idea. Now, instead of XORing your plain text
against a pseudo-random sequence, you are XORing your plain text
against the current time/date, something quite easily predictable.

Even in your case, seeding a Mersenne Twister in every loop
interaction will put that algorithm exactly in its worst case : the
startup sequence.

The mersenne Twister is slow to start generating good random numbers.

So your program is bug to the guts in this case.

To solve this all you have to do is to guarantee that both
communication ends use the same random number generation algorithm and
seed. This will work. (IE.: the fix will break compatibility with old
binaries). And dont seed against the last result, thats not a good
idea (This will keep the MT restarting).

A good alternative to a simple encryption algorithm is to use
cryptographic hash functions like SHA.

hash your key using SHA.

Split your file in blocks the same size of the SHA key.

XOR the first block against the first key,

output the bytes.

Hash the SHA key itself, generating a second key,

XOR the second block against that second key.

repeat until end of data. PAD the last block to match the Hash size.

Post by Graeme Geldenhuys

Post by Dimitri Smits
I actually doubt that that codesnippet does any real encryption.

It isn't. The sample code / test program I posted is just a snippet of
the actual unit. No point in posting the whole unit here, just to
point out that a single section of code in one method is the location
of the slow-running code under FPC. I only supplied the slow-running
code to demonstrate the problem.
--
Regards,
  - Graeme -
_______________________________________________
fpGUI - a cross-platform Free Pascal GUI toolkit
http://fpgui.sourceforge.net
_______________________________________________
http://lists.freepascal.org/mailman/listinfo/fpc-pascal

[Graeme Geldenhuys]

In case you didn't notice the unit name this code comes from....
tiEncryptSimple.pas
The name should be a good enough hint that it wasn't meant for
real-world apps. ;-) For real-world apps, tiOPF has other encryption
units based on DES and Blowfish.

But thanks for the theory. I'll keep it for a rainy day.

[Dimitri Smits]

On Fri, 09 Dec 2011 09:19:53 +0100, Florian Klaempfl

Post by Florian Klaempfl
Oops, mails crossed. The assignment to randseed is indeed the

problem.

Post by Florian Klaempfl
Why is it done? Bad random generator of delphi :)?

I don't know, how bad Delphis random generator is, but I once
years ago did make a mistake
of calling randomize before random. It was a school assignment for
using Turbo Pascal graphics.
So I made program, that was supposed to fill screen with random dots
(colour was also set with
random). Anyway, when I called randomize before random, then as a
result dots didn't fill the
screen, but were mostly along the diagonal of the screen. So I'd
guess, that setting randseed
multiple times could be actually bad for randomness of results. Or
maybe modern algorithms are
better at situations like this?

Randomize() is supposed to be called only once to seed the generator with an initial value.

If you made it something like so:

begin
for i := 0 to 1000 do
begin
randomize();
pixel[random(screenwidth),random(screenheight)]:= clSomeColor;
end;
end;

then you seed with a timestamp before randoming and your distribution does not change much with a lcg. Not the fault of the algorithm itself, just your mistake of doing the randomize in the loop itself (like you mentioned yourself).


kind regards,
Dimitri Smits

[Virgo Pärna]

Post by Dimitri Smits
Randomize() is supposed to be called only once to seed the generator with an initial value.

I do know that:) I made that mistake long time ago. What I thought was, that constantly
setting RandSeed is somewhat like constantly calling Randomize. In the example code randseed
was dependant of randomize output - which might or might not be as awful as randomize. And
the graphical output was just really good illustration, why it was bad.

[Marco van de Voort]

Post by Dimitri Smits
Randomize() is supposed to be called only once to seed the generator with an initial value.
begin
for i := 0 to 1000 do
begin
randomize();
pixel[random(screenwidth),random(screenheight)]:= clSomeColor;
end;
end;
then you seed with a timestamp before randoming and your distribution does
not change much with a lcg. Not the fault of the algorithm itself, just
your mistake of doing the randomize in the loop itself (like you mentioned
yourself).

(specially since high quality rng's might call OS dependent sources for
initial entropy in that first call)

[Marco van de Voort]

Post by Reimar Grabowski
Like people already said, lots of talk about a 'problem' that 10 years noone has seen as one.

(it's afaik not the first. Has been noticed once or twice before. But those
people used it in unittests, and simply changed without much ado when the
problem was identified. Contrary to the fact that before the twister
change, people complaining about random being "not as random as Delphi"
several times per year)