Delphi's Random Number Generator
John Donaldson
if it is a valid random number generator. I am looking for as much
technical information as possible to provide to our legal counsel about how
the Random Function works and how the seed determines the numbers generated
within the specified ranges.
The application I developed generates a random sample which auditors then
use to test for compliance with state tax regulations. Based on the results
of the audit, an assessment is made. Our statistician has concluded that
our procedures are correct, but he can not explain to the court what the
Random Number Generator does or how it works.
Thank you for any assistance,
John Donaldson,
Senior Developer
Florida Department of Revenue
Avatar Zondertau
> Function and if it is a valid random number generator. I am looking
> for as much technical information as possible to provide to our legal
> counsel about how the Random Function works and how the seed
> determines the numbers generated within the specified ranges.
>
> The application I developed generates a random sample which auditors
> then use to test for compliance with state tax regulations. Based on
> the results of the audit, an assessment is made. Our statistician
> has concluded that our procedures are correct, but he can not explain
> to the court what the Random Number Generator does or how it works.
The source code is available. It's in the System unit and it's called
either _RandInt (the overloaded version that generates random integers)
or _RandExt (the overloaded version that generates random floating
point numbers). The Randomize function, which initializes the random
seed, is also in System.pas.
Note that the implementation of Random may change between Delphi
versions, so if this is really important to you, you may want to
copy-paste them into your program and use those version instead. This
keeps you from having to check them again for every new Delphi version.
Note that the random functions are in sassembly, but can easily be
translated in more readable form. This is a translation of Delphi 7's
_RandInt:
function _RandInt(Range: LongInt): LongInt;
var
NewSeed: LongInt;
begin
NewSeed := RandSeed * $08088405 + 1;
RandSeed := NewSeed;
Result := Int64(EDX) * Int64(Range) shr 32;
end;
Robert Marquardt
http://evoting.cs.may.ie/FoI_request/PMIRandom_Numbers.ps
http://www.google.com/search?q=cache:gebc1hD2P-QJ:www.nace.ac.il/Web_Folder/Han_Taun/TTI/Issue4/Art%2520pp%252052_59.pdf+Delphi+random+number+generator&hl=de
(Sorry, only available in Google cache)
John Herbster
"John Donaldson" <john...@comcast.net> wrote
> My department is facing litigation concerning Delphi's
> Random Function and if it is a valid random number
> generator.
I addition to the other *good* replies:
Delphi's random number is a pseudo-random number
generator, often called a PRNG. It will cycle through the
2^32 (i.e. 4,294,967,296) possible values of a 32-bit
computer word in a *pseudo* random order then repeat
the same sequence. This "RandSeed" word is then
converted into the other possible outputs of Delphi's
Random function. The Delphi random does allow a
fairly random selection of the starting value using the
Randomize procedure.
> Our statistician ... can not explain to the court what the
> Random Number Generator does or how it works.
Hmm...
For your next project, if it is important to generate, really
random or unpredictable sequences of numbers, then you
need to do some study. You could start by reading the
notes in QualityCentral report #6619:
http://qc.borland.com/wc/wc.exe/details?reportid=6619
Regards, JohnH
PS: Did you solve your random FPU precision problem.
krisztian pinter
i doubt that delphi's random generator has any validation. for a
project of this magnitude, you have better to implement a known
pseudorandom algorithm yourself. i'm sure borland never signs
anything about it. nor they did a complete mathematical analysis.
it is well beyond the scope of the built-in random stuff.
Bryan Feeney
generator is a fairly poor pseudo-random number generator (PRNG). It has
a relatively short cycle length, and it is easy to find patterns in it.
The usual way out of this is to "re-seed" the PRNG using the Randomize
call (if you haven't done this you may be in trouble).
There was a case of software for a gambling website being written in
Delphi. A researcher looking at the site realised it was written in
Delphi. He correctly guessed that they "randomised" the PRNG with the
date and time, and was able to write an application that could predict
what cards all the other players had and would receive given the status
of the table.
This does not mean that there's an inherent bias in Delphi's PRNG, or
that it won't cover all possibilities (so no-one can claim they've been
victimised). It just means that it does not offer enough "randomness"
for serious statistical or cryptographic work. A better example of a
PRNG algorithm is ISAAC, the details of which can be found on
www.wikipedia.com
It should be noted that is impossible for any program to provide truly
random numbers, as every program is inherently deterministic. It is for
this reason that Intel, in their Pentium 3 or 4 range (can't remember
which) added an instruction to generate a random number based on the
heat of the chip. As there are so many variables affecting this, it can
be considered to be truly random.
Sorry
--
Bryan Feeney
Peter Below (TeamB)
> My department is facing litigation concerning Delphi's Random Function and
> if it is a valid random number generator. I am looking for as much
> technical information as possible to provide to our legal counsel about how
> the Random Function works and how the seed determines the numbers generated
> within the specified ranges.
>
> The application I developed generates a random sample which auditors then
> use to test for compliance with state tax regulations. Based on the results
> of the audit, an assessment is made. Our statistician has concluded that
> our procedures are correct, but he can not explain to the court what the
> Random Number Generator does or how it works.
The run-time libraries Random function is a typical linear congruential
random number generator. Starting with a seed value that is determined by
Randomize based on some system data that changes fairly rapidly (like the
system date and time) it applies a known calculation to the current seed to
calculate a number, which is returned and also becomes the new seed for the
next call to Random (so Random is not thread-safe!). This means that the
sequence of numbers generated from a given seed is 100% predictable, starting
with the same seed you will always get the same sequence of numbers. But the
distribution of these numbers is close to (but not quite identical) to a true
sequence of random numbers obtained from a random physical source (like
radioactive decay or electronic noise caused by thermal movement of charge
carriers in a conductor). The art of writing a good software (pseudo)random
number generator is to find a calculation that gives a distribution as close
to a true random sequence as possible. And which is still reasonably fast to
execute, of course <g>. Randoms implementation has not changed since
TurboPascals days, i think, you can see the implementation in System._RandInt.
Basically the seed (a longint) gets multiplied by the magic number 08088405H,
the bottom dword of the result is incremented by one and becomes the new seed.
This value is then scaled depending on the range you requested.
The subject of Random and random number generators in general has come up in
the past in these groups, sometimes resulting in rather lengthy threads. A
couple of references picked from such a previous discussion:
SK Park, KW Miller (1988) Random number generators: good ones are hard to
find, Commun. ACM 31:1192.
DG Carta (1990) Two fast implementations of the "Minimal Standard" random
number generator, Commun. ACM 33:87.
There is of course an extensive literature about this subject around.
object-oriented random number generator suite
http://inconresearch.com/eoi/on02000.htm
--
Peter Below (TeamB)
Use the newsgroup archives :
http://www.mers.com/searchsite.html
http://www.tamaracka.com/search.htm
http://groups.google.com
http://www.prolix.be
Avatar Zondertau
> Delphi. A researcher looking at the site realised it was written in
> Delphi. He correctly guessed that they "randomised" the PRNG with the
> date and time, and was able to write an application that could
> predict what cards all the other players had and would receive given
> the status of the table.
Interesting. However my Delphi (Delphi 7) uses the
QueryPerformanceCounter function to get it's random seed. The value
this function returns is very hard to predict, because it depends on
how long the computer has been running, so not date/time, and because
it's rather accurate (depends on hardware, but 3579545 ticks/sec on my
computer).
If you don't trust Randomize you can even initialize RandSeed - which
is in the interface section of System.pas - yourself, for example using
the RDTSC CPU instruction:
function RdTsc: Int64;
asm
rdtsc
end;
This function measures the number of CPU clock ticks since booting, so
that's really unpredictable. The lower 32 bits covers the enire integer
range and wraps around about every 2 seconds (assuming 2 GHz CPU).
ISTM if the problem was in the Randomize function, then it shouldn't
really be a problem. If, however, you think the Random function itself
is flawed, then that would be a problem. In that case it would be
better to buy another PRNG.
Bryan Feeney
> Interesting. However my Delphi (Delphi 7) uses the
> QueryPerformanceCounter function to get it's random seed. The value
> this function returns is very hard to predict, because it depends on
> how long the computer has been running, so not date/time, and because
> it's rather accurate (depends on hardware, but 3579545 ticks/sec on my
> computer).
This only means it's hard to predict the initial state of the random
number generator. Once you got enough numbers out of it, it's possible
you could determine where in the sequence you were, and then use
existing knowledge of how the PRNG works to predict all the following
numbers.
The solution to this is to continuously reseed the PRNG using, e.g.,
mouse movement or key-presses. There's an example of that here:
http://www.howtodothings.com/ViewArticle.aspx?article=578
A good primer on PRNGs is here:
http://triumvir.org/rng/
Lastly, the link for the story I mentioned is here:
http://www.cigital.com/papers/download/developer_gambling.pdf
Cheers
--
Bryan
Avatar Zondertau
> number generator. Once you got enough numbers out of it, it's
> possible you could determine where in the sequence you were, and then
> use existing knowledge of how the PRNG works to predict all the
> following numbers.
IC. From your post i thought you meant they used the date/time to
determine the initial state.
This problem could probably also be solved by using a larger random
seed (currently 32 bits), but of course constantly adding random data
would also help, as long as that data itself isn't predictable.
Mike Williams (TeamB)
> The cycle length for ISAAC is at least 2^40, and usually 2^8295. I
> believe its a lot less for the Delphi PRNG, though I can't find any
> concrete figures.
The cycle length for the Delphi PRNG is exactly 2^32 since the seed
itself and only the seed itself is used to calculate the next seed.
--
-Mike (TeamB)
Bryan Feeney
> This problem could probably also be solved by using a larger random
> seed (currently 32 bits), but of course constantly adding random data
> would also help, as long as that data itself isn't predictable.
It's not really the size of the seed. It's the cycle length: the longer
the length, the less likely a repeating pattern is likely to be
discovered, and the sequence cracked. The cycle length for ISAAC is at
least 2^40, and usually 2^8295. I believe its a lot less for the Delphi
PRNG, though I can't find any concrete figures. If your algorithm has
got a short cycle length, you're going to need to randomize it pretty
regularly, with unpredictable and varied values (hence key-press rate or
mouse-movement velocity).
This only applies to hard cryptography though. In the gambling example,
they didn't have the opportunity to go through enough cards (and lose
enough money!) to determine the sequence. The fact that they knew how it
was being randomised meant that they knew exactly what cards were being
dealt right from the beginning.
--
Bryan
Craig Stuntz [TeamB]
> The solution to this is to continuously reseed the PRNG using, e.g.,
> mouse movement or key-presses.
Note that some CPUs contain hardware random seed generators which
measure truly random electrical fluctuations. If such hardware is
available it's probably preferable as it works unattended. See the
Intel site for documentation.
--
Craig Stuntz [TeamB] · Vertex Systems Corp. · Columbus, OH
Delphi/InterBase Weblog : http://blogs.teamb.com/craigstuntz
Want to help make Delphi and InterBase better? Use QC!
http://qc.borland.com -- Vote for important issues
Avatar Zondertau
> > believe its a lot less for the Delphi PRNG, though I can't find any
> > concrete figures.
>
> The cycle length for the Delphi PRNG is exactly 2^32 since the seed
> itself and only the seed itself is used to calculate the next seed.
ISTM that's not enough. It also depends on the function used to
generate the next seed. If we call this function f and there exists x
such that
f(f(x)) = x then the cycle length is 2, even though the seed has 2^32
possibilities.
I dont know is the multiplication-incrementation combination avoids
this, but the fact that the new random seed depends only on the old one
is definately not enough.
Mike Williams (TeamB)
> I dont know is the multiplication-incrementation combination avoids
> this, but the fact that the new random seed depends only on the old
> one is definately not enough.
Yes, it does avoid the problem you were referring to. You'll note that
the seed always cycles through the same 2^32 possibilities in the same
order.
--
-Mike (TeamB)
Charles Line
"Bryan Feeney"
>
> He correctly guessed that they "randomised" the PRNG with the
> date and time, and was able to write an application that could predict
> what cards all the other players had and would receive given the status
> of the table
Here's their original announcement:
I remember it well.
Dr John Stockton
2005 08:19:45, seen in news:borland.public.delphi.language.delphi.genera
l, John Herbster <herb-sci1_AT_sbcglobal.net@?.?> posted :
> The Delphi random does allow a
>fairly random selection of the starting value using the
>Randomize procedure.
That appears to be dependent (in Borland's opinion), from something you
once wrote (quoted in <URL:http://www.merlyn.demon.co.uk/pas-rand.htm>),
on the version of Delphi and on something else, presumably the OS.
In some (earlier) Delphi versions, the total number of possible starting
points is much less than 2^32.
IMHO, it could be good to initialise RandSeed with the output of the
RDTSC instruction, top half XOR bottom half, BSWAP. I don't know when
RDTSC became available; my PII/300 has it.
(Nothing yet from FE.)
--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Delphi 3 Turnpike 4 ©
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
<URL:http://www.bancoems.com/CompLangPascalDelphiMisc-MiniFAQ.htm> clpdmFAQ;
<URL:http://www.borland.com/newsgroups/guide.html> news:borland.* Guidelines
Dr John Stockton
2005 07:44:51, seen in news:borland.public.delphi.language.delphi.genera
l, Avatar Zondertau <avat...@gmail.com> posted :
>
>Interesting. However my Delphi (Delphi 7) uses the
>QueryPerformanceCounter function to get it's random seed. The value
>this function returns is very hard to predict, because it depends on
>how long the computer has been running, so not date/time, and because
>it's rather accurate (depends on hardware, but 3579545 ticks/sec on my
>computer).
That's 315/88 MHz, and the US NTSC TV "color sub-carrier" frequency.
But I, with PII/300 Win98 D3, see 1193180 Hz ~ 315/264 MHz.
However, I believe that it is how long the OS has been running, not how
long the computer has been running; my computer has been running for far
longer than my OS.
--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 MIME. ©
Web <URL:http://www.merlyn.demon.co.uk/> - w. FAQish topics, links, acronyms
PAS EXE etc : <URL:http://www.merlyn.demon.co.uk/programs/> - see 00index.htm
Dates - miscdate.htm moredate.htm js-dates.htm pas-time.htm critdate.htm etc.
John Herbster
"krisztian pinter" <pint...@freemail.hu> wrote
> I doubt that delphi's random generator has any validation. ...
True, But it only takes a few seconds to generate the complete
sequence cycle for analysis and it is repeatable. --JohnH
John Herbster
"Charles Line" wrote
> > He correctly guessed that they "randomised" the PRNG
> > with the date and time, and was able to write an application
> > that could predict what cards all the other players had ...
Charles, Thank you for that reference. Without it, I
would not have believed the original claim. Rgds, JohnH
Brian Cook
says...
> JRS: In article <42971d6c$1...@newsgroups.borland.com>, dated Fri, 27 May
> 2005 08:19:45, seen in news:borland.public.delphi.language.delphi.genera
> l, John Herbster <herb-sci1_AT_sbcglobal.net@?.?> posted :
>
> > The Delphi random does allow a
> >fairly random selection of the starting value using the
> >Randomize procedure.
>
> That appears to be dependent (in Borland's opinion), from something you
> once wrote (quoted in <URL:http://www.merlyn.demon.co.uk/pas-rand.htm>),
> on the version of Delphi and on something else, presumably the OS.
>
> In some (earlier) Delphi versions, the total number of possible starting
> points is much less than 2^32.
On my computer, with Delphi 6, Randomize produces...
24 * 60 * 60 * 1000 / ~16 = 5,400,000
...values for RandSeed. A mere 0.126% of the potential values for
RandSeed.
> IMHO, it could be good to initialise RandSeed with the output of the
> RDTSC instruction, top half XOR bottom half, BSWAP. I don't know when
> RDTSC became available; my PII/300 has it.
I'd say that's good advice.
- Brian
Ben Hochstrasser
> My department is facing litigation concerning Delphi's Random Function
> and if it is a valid random number generator. I am looking for as
> much technical information as possible to provide to our legal counsel
> about how the Random Function works and how the seed determines the
> numbers generated within the specified ranges.
For portability (and documentation) reasons, I'd skip the Delphi PRNG and
use something independent, eg the Mersenne Twister:
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/PASCAL/pascal.html
--
Ben
Mike Williams (TeamB)
> On my computer, with Delphi 6, Randomize produces...
>
> 24 * 60 * 60 * 1000 / ~16 = 5,400,000
>
> ...values for RandSeed. A mere 0.126% of the potential values for
> RandSeed.
Delphi 7 improved on this and uses the Win32 API
QueryPerformanceCounter, if available, to initialize the seed.
--
-Mike (TeamB)
Jim McKay
>My department is facing litigation concerning Delphi's Random Function and
>if it is a valid random number generator. I am looking for as much
>technical information as possible to provide to our legal counsel about how
>the Random Function works and how the seed determines the numbers generated
>within the specified ranges.
>
>The application I developed generates a random sample which auditors then
>use to test for compliance with state tax regulations. Based on the results
>of the audit, an assessment is made. Our statistician has concluded that
>our procedures are correct, but he can not explain to the court what the
>Random Number Generator does or how it works.
Bruce Schneir covers RNG issues well here:
http://www.schneier.com/yarrow.html
Links in above URL go to several thorough discusions. We use an
implementation of Schneir's YARROW for cryptographic safe RNG
requirements.
Schneir has YARROW/RNG research paper (linked in above URL) here:
http://www.schneier.com/paper-prngs.pdf
--
Regards:
Jim McKay
"My theory of evolution is that Darwin was adopted."
-- Steven Wright
Posted with XanaNews: Ver: 1.17.4.1
listmember
[...]
> (so Random is not thread-safe!).
My question is, now that we have multi-core, multi-CPU
boxes (possibly in cell or grid formation, in a few years)
how do you make sure you get random numbers that are
random enough --and not duplicated accross threads
or processes.
Cheers,
Ray
Lorne
cryptographic level) RNG using ISAAC.
see details here: http://burtleburtle.net/bob/rand/isaacafa.html
I believe the Mersenne Twister is also a good alternative but I found ISAAC
easier to implement.
Both of these can produce very long random sequences but the key to it all
is in creating truly random seeds. ISAAC uses an array of 256 x 32 bit
seeds but obviously if you create your array using Randomize() you are back
where you started with only a small subset of the possible range of
sequences so you have to be very careful.
If anyone has good advice on how to create the seeds I would be interested
to here it - at the moment I use numbers from many sources including:
- calls to RDTSC
- TickCount
- system clock
- windows handles
- memory addresses of dynamic variables and objects
- cursor position
- how long my application has been running
- RDTSC since last click to get a random number
Having got 12 seeds from the above processes I then use them in a random
order as seeds to create the other 244 seeds. This is because speed is an
issue as well as randomness and I know it is a flaw and does not give me the
8192 bit sequence that is in theory possible, but for my purpose anything
over 200 bit is fine and although some of the above are not very random I
think the combination of everything I do should get me where I want to be
(ie 200 bits of randomness).
Has anyone got any practical suggestions to improve this, or any comment on
how random you think my process really is?
The software is for use on personal computers so nothing needing specialist
chips is any good.
"listmember" <listm...@letterboxes.org> wrote in message
news:xn0e2s90b...@forums.borland.com...
John Herbster
"Lorne" <Lorne_A...@hotmail.com> wrote
> If anyone has good advice on how to create the seeds,
> I would be interested
I use the OS call CryptGenRandom and leave the
improvements to experts. --JohnH
Lorne
I would like to try this out but I get an error that HCRYPTPROV is
undeclared - do you have some sample code of how to call this in Delphi
including what is needed in the uses clause?
"John Herbster" <herb-sci1_AT_sbcglobal.net> wrote in message
news:42986578$1...@newsgroups.borland.com...
Peter Below (TeamB)
> > (so Random is not thread-safe!).
>
> My question is, now that we have multi-core, multi-CPU
> boxes (possibly in cell or grid formation, in a few years)
> how do you make sure you get random numbers that are
> random enough --and not duplicated accross threads
> or processes.
By implementing your own Random function that is threadsafe, of course
<g>. If you are satisfied with the statistical properties of the RTL
Random this takes about 5 minutes. Less, if you search the newsgroup
archives for ThreadSafeRandom <g>.
Avatar Zondertau
> > boxes (possibly in cell or grid formation, in a few years)
> > how do you make sure you get random numbers that are
> > random enough --and not duplicated accross threads
> > or processes.
>
> By implementing your own Random function that is threadsafe, of
> course <g>. If you are satisfied with the statistical properties of
> the RTL Random this takes about 5 minutes. Less, if you search the
> newsgroup archives for ThreadSafeRandom <g>.
In fact it's enough to declare the random seed threadvar and copy the
random functions. This means you'll have to randomize each thread.
Peter Below (TeamB)
> In fact it's enough to declare the random seed threadvar and copy the
> random functions. This means you'll have to randomize each thread.
Mh, if several threads call Randomize very closely together they may end up
with the same seed value.
Avatar Zondertau
> > the random functions. This means you'll have to randomize each
> > thread.
>
> Mh, if several threads call Randomize very closely together they may
> end up with the same seed value.
Yes, you're right.
Perhaps if you modify Randomize to use RdTsc or to add the current
thread handle that would fix it.
Guillem
the others have given you already a big amount of useful information on how
to do it, but i would like to add one thing.
Some have suggested to have a look at the hardware random generators
included by some CPUs. While this looks pretty good, you should be very
careful with it.
The danger lies in the fact that many natural "random" phenomens are not as
"random" as they seem. In a lot of cases, scientists researching for
simulations have demonstrated that some variables affecting the result were
actually correlated (don't know if it's the correct name in english), that
is, influenced by another variable. As this correlation propagates through,
the value becomes more and more "predictable".
That's one of the reasons because linear congruential random number
generators exist. Because it's not only about the granularity (mean
"distance" between the possible values) of the random numbers generated, but
also about the "appearance" of being random.
Ok, i was writing this from memory, so probably i wrote something wrong :) I
can give you more references, but you'll have to wait until tomorrow,
because i have all my docs about simulation and random number generation at
home
Good luck
--
Best regards :)
Guillem Vicens
Dep. informática Green Service SA
www.clubgreenoasis.com
--
In order to send me a mail, remove the -nospam
"John Donaldson" <john...@comcast.net> escribió en el mensaje
news:42970c85$1...@newsgroups.borland.com...
> My department is facing litigation concerning Delphi's Random Function and
> if it is a valid random number generator. I am looking for as much
> technical information as possible to provide to our legal counsel about
> how
> the Random Function works and how the seed determines the numbers
> generated
> within the specified ranges.
>
> The application I developed generates a random sample which auditors then
> use to test for compliance with state tax regulations. Based on the
> results
> of the audit, an assessment is made. Our statistician has concluded that
> our procedures are correct, but he can not explain to the court what the
> Random Number Generator does or how it works.
>
> Thank you for any assistance,
>
> John Donaldson,
> Senior Developer
> Florida Department of Revenue
>
>
John Herbster
> >> If anyone has good advice on how to create the seeds,
> >> I would be interested
> > I use the OS call CryptGenRandom and leave the
> > improvements to experts. --JohnH
> I would like to try this out but I get an error that HCRYPTPROV
> is undeclared - do you have some sample code of how to call
> this in Delphi including what is needed in the uses clause?
I use Jedi's WinCrypt unit. My code and the header comments
from WinCrypt follow.
The reader may also want to check out the following search
http://groups-beta.google.com/groups?q=CryptGenRandom+%22how+good%22
--JohnH
procedure GetRandomBytes(var RandomBytes: array of byte; ProvType:
integer);
var hProv: HCRYPTPROV;
begin
If not CryptAcquireContext
(@hProv,{Container}nil,{Provider}nil,ProvType,{Flags}0)
then raise Exception.Create('CryptAcquireContext failed.');
If not
CryptGenRandom(hProv,length(RandomBytes),@RandomBytes[low(RandomBytes)])
then raise Exception.Create('CryptGenRandom failed.');
If not CryptReleaseContext(hProv,{dwFlags}0)
then raise Exception.Create('CryptReleaseContext failed.');
end;
{This document is Copyright © 1997-98 Project JEDI.
Visit the JEDI home page at: http://www.delphi-jedi.org/}
{---------------------------------------------------------
Copyright (c) 1996-98 Massimo Maria Ghisalberti
CopyRight (c) 1996-98 MAx!
CopyRight (c) 1996-98 Objects Built for you! (O.B.you!)
Internet EMail: ob...@tin.it ni...@tin.it (personal)
translate from: wincrypt.h
date: 08/05/98
version: 1.1 revison 3
note: use at own risk.
If you use this code, please mention O.B.you!
somewhere in your program
----------------------------------------------------------
IMPORTANT : USE ONLY IF YOU HAVE WINDOWS NT 4.X OR WINDOWS
95 OSR2 OR/AND INTERNET EXPLORER 3.X.
----------------------------------------------------------}
Guillem
i had forgotten to mention that uniformity is also important. By that i mean
a RNG should give you a distribution of random numbers more or less similar
to the distribution of an U[0,1] statistical function.
You can find more info on this in the following books:
Bratley, P., Fox, B.L., Schrage, L.E.: "A guide to simulation" 2nd Ed.
Fishman, George S.: "Discrete-event Simulation. Modeling, Programming and
Analysis"
Knuth, D.E.; "The Art of Computer Programming. Vol 2: Seminumerical
Algorithms"
Law, A.M., Kleton, W.D.: "Simulation Modelling & Analysis" 3rd Ed.
--
Best regards :)
Guillem Vicens
Dep. informática Green Service SA
www.clubgreenoasis.com
--
In order to send me a mail, remove the -nospam
"Guillem" <guillemvic...@clubgreenoasis.com> escribió en el mensaje
news:429b...@newsgroups.borland.com...
krisztian pinter
i have no answer, but i have a question!
what requirements do you have? do your company has some guidelines,
or tests to pass?
i imagine something like these:
1. no numbers left out. for a given range, the algorithm must give
back all numbers with the same chance. if there are numbers that
never comes up, that's bad.
2. memoryless. next number should not correlate with previous,
nor with the one before previous, nor with preceding ten, etc.
3. unpredictable. one can not find out the current value of seed
and then calculate the whole sequence.
4. reproducible. you can restore an earlier state, and re-play
the sequence.
Guillem
"krisztian pinter" <pint...@freemail.hu> escribió en el mensaje
news:429c433e$1...@newsgroups.borland.com...
>
> i have no answer, but i have a question!
>
> what requirements do you have? do your company has some guidelines,
> or tests to pass?
Huh? Is That question for me or for John? If first case then none. It's just
i had a *very* good simulation professor back in university. I sometimes
thought he would be able to simulate life if you just gave him an old
Spectrum with 64 K<g>
>
> i imagine something like these:
>
> 1. no numbers left out. for a given range, the algorithm must give
> back all numbers with the same chance. if there are numbers that
> never comes up, that's bad.
That's called being of complete period. It's one of the requisites of any
good RNG, although there are some that are not
>
> 2. memoryless. next number should not correlate with previous,
> nor with the one before previous, nor with preceding ten, etc.
>
That's not possible, AFAIK, with any of the today used RNG. Most of them are
based in the application of an mathematical algorithm. Unless that algorithm
is not reversible (and i don't know of anyone), you can always predetermine
any random number coming after. The RNG are not really random number
generators, but pseudo-random number generators.
The point is that the random numbers generated should
a - Be distributed as similar as possible as in a Uniform distribution
U[0,1]. That gives you granularity and pushes you towards completeness (but
does not assure it)
b - Appear to be random. This is were a lot of them fail.
> 3. unpredictable. one can not find out the current value of seed
> and then calculate the whole sequence.
As i wrote above, that's not possible with today's RNG, not even with the
LCRNG (Linear Congruential RNGs), because they all work with deterministic
algorithms.
>
> 4. reproducible. you can restore an earlier state, and re-play
> the sequence.
>
That's easy using the LCRNG, as they can be segmented. Also, having the same
seed brings you to the same random numbers.
One could think that a RNG based in temperatures of the CPU (as someone
proposed) could work because there are a zillion variables influencing in
it. The problem is that you'llfind a lot of variables influencing each
other, as f.e., the heat provided by the cache influences the heat received
and provided by the data buses going out of it, which influence the heat in
the CPU itself, also influenced by the heat coming directly from the cache.
So, there you have 2 variables influencing the result, one of them
correlated with the other.
Physical phenomens occur in systems. Generally speaking, a lot of these
systems are considered chaotic and random, as we can not predict totally
what will happen, but that does not mean they are *not* predictable. Only
that *we* can not predict them.
So, what to do if you *really* need authentic random numbers? The answer is
not easy at all. I would guess, wait until quantic computers come out.
Perhaps then we will have them, but until these computers appear, a good
LCRNG should do it.
krisztian pinter
"Guillem" <guillemvic...@clubgreenoasis.com> wrote:
>Huh? Is That question for me or for John? If first case then none.
actually, i wanted to ask John, but i'm clicking mindlessly.
however, as it was a theoretical topic, any answers are welcome :)
>> 1. no numbers left out.
>That's called being of complete period. It's one of the requisites of any
>good RNG, although there are some that are not
i guess it can be improved if we don't use the whole seed as
result, just a smaller part. say, if we have a 64bit or 128bit
random function, then use only the lowest 32bits, it will
most likely have all values. delphi gives 32 bit values, and
uses a 32bit internal. danger.
>> 2. memoryless.
>That's not possible, AFAIK, with any of the today used RNG.
i guess it is, if we use the above technique. the whole random
serie will be of course 100% predictable, but that does not
mean a correlation between the produced smaller numbers.
>> 3. unpredictable.
>they all work with deterministic algorithms.
sure, but client have no idea of the large number behind the
scenes.
>> 4. reproducible.
>That's easy using the LCRNG
yes.
>One could think that a RNG based in temperatures of the CPU
> could work because there are a zillion variables influencing in
as i learned earlier, there is no such thing as a good random
number. okay, theoretically, a perfectly random number is good
for anything, except reproducibility. we don't have perfect
randoms, but we don't need. for any application, users must tell the
the requirements, and mathematicians and others can develop a fine
method for them. for cryptography, unpredictability is the key.
for sampling, it is distribution and completeness. for a game,
almost everything is OK.
John Donaldson
include:
1. no duplicate numbers
2. ability to generate the same sample again on different PC's with the same
seed.
3. statististically valid random number. This may be a determination of a
statistician or expert witness, which would ultimately be determined by a
judge in a court case. The point is that if the number is a valid random
number, then it is not biased. If it is not biased then the state and the
taxpayer must accept the results of a statistical projection based on the
sample results.
4. the sample must be able to be drawn from ranges, such as check numbers
which may not be contiguous. void checks for example.
5.the random number generator must be able to be compiled in Delphi as this
is our developement software. Cripto++ does not seem to have a Delphi code
download program.
6. The ability to predict the random numbers needs to be next to
impossible, say .0001%
Hope this helps the discussion, which has not only been most informative but
very helpful.
John
"krisztian pinter" <pint...@freemail.hu> wrote in message
news:429c433e$1...@newsgroups.borland.com...
listmember
<nitpicking>
> Hope this helps the discussion, which has not only been most
> informative but very helpful.
I am sure (or hope) that you mean "which has not only been
most informative but _*/also/*_ very helpful" :-)
</nitpicking>
krisztian pinter
all but 3rd seem to be quite straightforward to me. obvious,
that you need a pseudo random.
3rd, on the other hand, could be a subject of a book i think.
is there such a thing "statistically valid" random number in
general? i mean, there are infinite number of tests that can be
done on a set of random numbers, so how can one tell that a
pseudo random will pass all imaginable tests? i guess that the
good approach is to do exactly those tests that is required for
the planned application. so it will not "statistically valid",
but "statistically valid for us". am i right?
Sven Pran
.............
>>That's called being of complete period. It's one of the requisites of any
>>good RNG, although there are some that are not
>
> i guess it can be improved if we don't use the whole seed as
> result, just a smaller part. say, if we have a 64bit or 128bit
> random function, then use only the lowest 32bits, it will
> most likely have all values. delphi gives 32 bit values, and
> uses a 32bit internal. danger.
Please be aware that the different bits in the seed show
different randomness: The MSB is "best" and the LSB is
not random at all (usually it simply toggles between zero
and one).
When the need is just statistical, not for crypto, then the
LCRNG (also known as the Lehmer algorithm) is almost
always quite sufficient provided it is used correctly. But
there are some conditions which must be observed when
generating discrete (integer) random numbers:
The Lehmer algorithm is: X := ((X * A) + C) modulo(M)
where A is known as the multiplier, M as the cycle length
and C is a constant. The value of C is unimportant except
that it should not be zero or divisible in M. A common and
good value is 1.
We can safely use this algorithm to generate random numbers
among R different alternatives (like integer numbers in the range
0 to R-1) if R is less than A and also less than M/A.
If this condition is not satisfied then we shall have serious
serial correlation problems in that there will be alternatives
which can never immediately follow each other.
The other prime consideration on using Lehmer is that as we
"use" seed values from the M different possibilities these values
will not be reused until we have processed all M values. So in
order to maintain the distribution probabilities on the "next"
numbers we must limit the use of this algorithm for a particular
application to some fraction of the M available runs.
An easy rule of the thumb is that if we want the statistical error
to be less than 1% we must not call the random number
generator more than M/100 times within the same process.
(We must not "draw" more than 1% of the available seeds from
the entity of all available seeds)
regards Sven
Guillem
"John Donaldson" <john...@comcast.net> escribió en el mensaje
news:429c848f$1...@newsgroups.borland.com...
> Some of our requirements which have been handled by code in most
> situations
> include:
> 1. no duplicate numbers
possible as long as you don't complete the whole period of the RNG. LCRNG
are good for this
> 2. ability to generate the same sample again on different PC's with the
> same
> seed.
that definitely cuts out physical-phenomenon-based RNGs
> 3. statististically valid random number. This may be a determination of a
> statistician or expert witness, which would ultimately be determined by a
> judge in a court case.
oh my, are we mixing bureaucracy into this? <g>
> The point is that if the number is a valid random
> number, then it is not biased. If it is not biased then the state and the
> taxpayer must accept the results of a statistical projection based on the
> sample results.
i would suggest a LCRNG with increment C = 0. I don't agree with Sven in
that it should not be zero, as LCRNG with increment C <> 0 (also called
mixed generators) were first studied and did not pass too well the
independency tests. OTOH, LCNRG with increment C= 0 (also called
multiplicative generators), were far better. See the book references i gave
you in a post before
> 4. the sample must be able to be drawn from ranges, such as check numbers
> which may not be contiguous. void checks for example.
use a U[0,1] as a basis. You can then use mathematical operations to bring
it to the range you need.
> 5.the random number generator must be able to be compiled in Delphi as
> this
> is our developement software. Cripto++ does not seem to have a Delphi
> code
> download program.
that's not a problem at all
> 6. The ability to predict the random numbers needs to be next to
> impossible, say .0001%
give them a very large range of possible values. How large depends on you.
>
> Hope this helps the discussion, which has not only been most informative
> but
> very helpful.
>
Glad we helped you :)
Sven Pran
"Guillem" <guillemvic...@clubgreenoasis.com> wrote in message
news:429d...@newsgroups.borland.com...
> Hi,
................
> i would suggest a LCRNG with increment C = 0. I don't agree with Sven in
> that it should not be zero, as LCRNG with increment C <> 0 (also called
> mixed generators) were first studied and did not pass too well the
> independency tests. OTOH, LCNRG with increment C= 0 (also called
> multiplicative generators), were far better. See the book references i
> gave you in a post before
Knuth quotes this "claim" and shows that it is incorrect.
With M equal to 2^e (power e of 2) and c=0 the generator becomes
equivalent to a maximum length generator (c > 0) with M = 2^(e-2)
without improvement in randomness.
So the only "feature" achieved by setting c = 0 is to save an addition at
the
cost of reducing the cycle length by a factor of four. (when M is a power of
2)
Sven
Guillem
what you wrote is true. Using a M = 2^e is not a good idea at all because of
the reason you give, and because it is very difficult to tell were those
random numbers would be. The possibility of having large gaps between values
is high.
However, and sorry because i had forgot about this (should have posted it
before), Hutchinson proposed in 1966 to take as M the largest prime number
inferior to 2^e. That gives what is called a PMMLCG (Prime Module
Multiplicative Linear Congruential Generator). For example, for 32 bits,
which gives you e=31 that number is 2^31 - 1 = 2147483647. Using primer
numbers allows to arrive to the complete period.
Generalizing, you can write 2^e - q, where q is a positive integer. This can
later be transformed so that you still don't need to do explicit division,
but use overflow mechanisms, additions and multiplications.
Having satisfied the requirements of uniformity and computational
efficience, alleatory appearance is what you need. As Knuth warns, using a
large module can cost a lot of computational effort, and also not all
multiplicators were statistically good. For M = 2^31 -1 = 2147483647, two
were proposed as the best:
- 7^5 = 16807, proposed by Lewis, Goodman and Miller in 1969
- 630360016, proposed by Payne, Rabung and Bogyo in 1969, and even better
than the first
--
Best regards :)
Guillem Vicens
Dep. informática Green Service SA
www.clubgreenoasis.com
--
In order to send me a mail, remove the -nospam
"Sven Pran" <no.d...@mail.please> escribió en el mensaje
news:429d...@newsgroups.borland.com...
krisztian pinter
"Sven Pran" <no.d...@mail.please> wrote:
>Please be aware that the different bits in the seed show
>different randomness: The MSB is "best" and the LSB is
>not random at all (usually it simply toggles between zero
>and one).
that is for example a very ugly behaviour. but as a correction,
we can do some other post processing on the seed. something
like a hash function.
>The Lehmer algorithm is: X := ((X * A) + C) modulo(M)
>We can safely use this algorithm to generate random numbers
>among R different alternatives (like integer numbers in the range
>0 to R-1) if R is less than A and also less than M/A.
correct me if i'm wrong, but i see in delphi source that
A = $08088405
M = $FFFFFFFF
C = $00000001
so it will be good for FFFFFFFF / 08088405 = 1F (???) alternatives?
whoa, there, this is kinda small!
Sven Pran
Don't overlook what I wrote that you should never use the Lehmer
algorithm to draw uniformly between R discrete alternatives unless
R is less than the multiplier and also the product of R and the
multiplier is less than the cycle length!
regards Sven
krisztian pinter
"Sven Pran" <no.d...@mail.please> wrote:
>>>0 to R-1) if R is less than A and also less than M/A.
...
>Don't overlook what I wrote that you should never use the Lehmer
>algorithm to draw uniformly between R discrete alternatives unless
>R is less than the multiplier and also the product of R and the
>multiplier is less than the cycle length!
you said the R must be less then M/A. didn't you?
Sven Pran
"Guillem" <guillemvic...@clubgreenoasis.com> wrote in message
news:429d...@newsgroups.borland.com...
>
>
> what you wrote is true. Using a M = 2^e is not a good idea at all because
> of the reason you give, and because it is very difficult to tell were
> those random numbers would be. The possibility of having large gaps
> between values is high.
>
> However, and sorry because i had forgot about this (should have posted it
> before), Hutchinson proposed in 1966 to take as M the largest prime number
> inferior to 2^e. That gives what is called a PMMLCG (Prime Module
> Multiplicative Linear Congruential Generator). For example, for 32 bits,
> which gives you e=31 that number is 2^31 - 1 = 2147483647. Using primer
> numbers allows to arrive to the complete period.
>
> Generalizing, you can write 2^e - q, where q is a positive integer. This
> can later be transformed so that you still don't need to do explicit
> division, but use overflow mechanisms, additions and multiplications.
>
> Having satisfied the requirements of uniformity and computational
> efficience, alleatory appearance is what you need. As Knuth warns, using a
> large module can cost a lot of computational effort, and also not all
> multiplicators were statistically good. For M = 2^31 -1 = 2147483647, two
> were proposed as the best:
>
> - 7^5 = 16807, proposed by Lewis, Goodman and Miller in 1969
> - 630360016, proposed by Payne, Rabung and Bogyo in 1969, and even better
> than the first
There is nothing wrong in using M a power of 2, but one must be careful
about
primarily the multiplier.
Personally I have implemented a very satisfactory 64 bit generator with
the multiplier 6364136223846793005 (and an increment of 1) as specified by
Knuth. My tests have all confirmed that this is indeed a very good
generator,
and the implementation was surprisingly both simple and fast (using asm).
(The implementation is available in a DLL which I have made freeware - look
at:
http://home.online.no/~svenpran/dealer.htm )
regards Sven
krisztian pinter
could you tell what tests were these please?
Sven Pran
Sure. I automatically assumed a full cycle length generator.
But it is the actual cycle length that is the decisive factor.
Sven
Sven Pran
Mainly up-down run tests with Chi-square analysis on the raw data (seed)
from the generator. In addition I always test generators with the actual
applications (also using Chi-square analysis on the raw test data).
regards Sven
Brian Cook
says...
I've never used it but I've read that Marsaglia has a good test suite...
http://www.google.com/search?hl=en&lr=&safe=off&c2coff=1
&q=marsaglia+Diehard
http://stat.fsu.edu/pub/diehard/
- Brian
Sven Pran
"Brian Cook" <bcook@rowdydogsoftware[REMOVE].com> wrote in message
news:MPG.1d07a17a4...@newsgroups.borland.com...
> In article <429d...@newsgroups.borland.com>, no.d...@mail.please
> says...
>>
>> "krisztian pinter" <pint...@freemail.hu> wrote in message
>> news:429dbcbf$1...@newsgroups.borland.com...
>> >
>> >
>> > could you tell what tests were these please?
>> >
>> >
>> > "Sven Pran" <no.d...@mail.please> wrote:
>> >
>> >>Personally I have implemented a very satisfactory 64 bit generator with
>> >>the multiplier 6364136223846793005 (and an increment of 1) as specified
>> >>by
>> >>Knuth. My tests have all confirmed that this is indeed a very good
>> >>generator,
>>
>> Mainly up-down run tests with Chi-square analysis on the raw data (seed)
>> from the generator. In addition I always test generators with the actual
>> applications (also using Chi-square analysis on the raw test data).
>
> I've never used it but I've read that Marsaglia has a good test suite...
Knuth considers the up-down test to be one of the most demanding tests
on random generators but he also stresses the importance of testing any
generator in the actual application where it is to be used.
The analysis of test results where the expected distribution is known can
usually best be done using Chi-square methods.
Sven