Re: Random Numbers fasters than the osax
Re: Random Numbers fasters than the osax
- Subject: Re: Random Numbers fasters than the osax
- From: email@hidden (Michael Sullivan)
- Date: Mon, 1 Apr 2002 16:42:30 -0500
- Organization: Society for the Incurably Pompous
Emmanuel writes:
>
At 8:07 PM +0100 27/3/02, Michael Sullivan wrote:
>
>That's not a huge deal, but I'm wondering if one of you math wiz folks
>
>has a vanilla random number generator handy, or a suggestion on how to
>
>build one.
>
My suggestion about how to build a Quick & Dirty one would be:
>
------------------------
>
set theNextRandomNumber to (thePreviousOne + BigBigPrime) mod (BigPrime)
>
------------------------
>
where BigPrime is any big prime number, and BigBigPrime a still bigger one.
This got me going in the right direction, but it doesn't make a lot of
sense.
It's really the same as
(previous + k) mod BigPrime
where k = BigBigPrime mod BigPrime.
Basically, there's no need to find a number larger than BigPrime. Also
-- any BigBigPrime equal to some small absolute value mod BigPrime will
be problematic. Suppose BigBigPrime = 1 mod BigPrime? then the numbers
generated will just be a series counting forward from the initial seed.
similarly if BigBigPrime = -1 mod bigPrime.
At first it seems one should just make sure that BigBigPrime mod
BigPrime is a large number, but one has to be careful that it's not
close to BigPrime/2, or BigPrime/3, or BigPrime/4, etc.
I'm not really sure there's any number that will give a good
distribution unless I only need numbers in a fairly small range.
I decided this was a little dirtier than I could deal with.
After reading the thread, I did my own search and found this website:
<
http://www-unix.mcs.anl.gov/dbpp/text/node117.html#SECTION0421000000000
0000000>
where I picked up an algorithm pretty close to your Q&D one which is
actually quite good:
NextNum = PreviousNum * largeNum mod BigPrime.
BigPrime limits the number of random numbers one can generate.
conveniently 2^31-1 (the largest 31-bit number and a Mersenne prime) is
prime. This is pretty close to the limit of applescript's integer math
(32-bit), so it makes for a good choice. Anything much larger would
require implementing larger-precision arithmetic.
I decided (possibly without good reason) that LargeNum needs to be
larger than sqrt(BigPrime) to get good distribution no matter the seed.
(if largeNum is small, then with a small seed, one will travel
monotonically up the range from 1 to 2G for the first fairly large
number of iterations). I also liked the idea of making LargeNum prime,
but I'm not sure if that's important. I think as long as LargeNum and
BigPrime are relatively prime, things work well (which they will be
unless largeNum = 1 or BigPrime).
Anyway, here's the script I ended up writing which needs a little work
on the interface before I web it, but should do the trick if anyone else
is interested:
--begin script:
--
--psRand
--
--simple random number generator script
--will clean up interface a bit and submit to mods
--Based on the algorithm x(k+1) = largeNum * x(k) mod veryLargePrime
--Thanks to Emmanuel for this direction, and Ian Foster's page for
--the algorithm I used:
--
<
http://www-unix.mcs.anl.gov/dbpp/text/node117.html#SECTION0421000000000
0000000>
--
--I chose largeNum = 2^19 - 1 and 2^31 - 1 for veryLargePrime.
--This means it will generate random numbers in the range of
--1 to ~1billion. No number will be repeated until every number
--has been seen once. These are 31-bit pseudo-random numbers.
--
--In theory, this algorithm with these number choices should generate
--a statistically good spread of pseudo random numbers for sim
--applications within the following limits:
--
--Significant digits: 5-6
--Term length: 10^6-8 iterations.
--
--First test demonstrates speed gain over the random number osax
--Second test also demonstrates statistically acceptable
--distribution over a range of 1 to 100.
--
--c. 2002 Michael E. Sullivan
email@hidden
--freeware use and abuse with credit
--
randomizeGenerator()
--speed tests:
set t1 to the ticks
repeat with i from 1 to 10000
set k to Random(0, 0)
end repeat
set t2 to the ticks
repeat with i from 1 to 10000
set k to Random(1, 1000)
end repeat
set t3 to the ticks
repeat with i from 1 to 10000
set k to random number
end repeat
set t4 to the ticks
{t2 - t1, t3 - t2, t4 - t3}
--> { 62, 107, 400}
--Test of distribution from 1 to 100:
set theList to {}
repeat with i from 1 to 100
copy 0 to end of theList
end repeat
repeat with i from 1 to 10000
set k to Random(1, 100)
set temp to item k of theList
set item k of theList to temp + 1
end repeat
theList
--> {91, 93, 91, 115, 96, 108, 106, 107, 86, 102, 115, 104, 111, 96,
101, 88, 96, 110, 109, 102, 113, 100, 103, 106, 116, 102, 101, 94, 112,
107, 96, 95, 103, 104, 95, 92, 110, 99, 105, 85, 72, 105, 131, 106, 104,
114, 98, 110, 85, 93, 93, 111, 84, 105, 98, 95, 106, 93, 98, 94, 100,
102, 93, 84, 101, 83, 92, 78, 116, 97, 100, 103, 93, 90, 108, 104, 95,
116, 113, 85, 97, 103, 106, 103, 97, 95, 94, 97, 98, 86, 94, 104, 105,
95, 95, 107, 102, 117, 96, 96}
script psRand
property kBigPrime : 2.147483647E+9
property kA : 524287
property kLast : missing value
on randomizeGenerator()
set psRand's kLast to the ticks
end randomizeGenerator
on seedGenerator(n)
set psRand's kLast to n
end seedGenerator
on Random01()
set k to (kLast) * kA mod (kBigPrime)
set psRand's kLast to k
return k / kBigPrime
end Random01
on Random(a, b)
if a = 0 and b = 0 then
return psRand's Random01()
end if
if b - a < 0 then
set {a, b} to {b, a}
end if
set kTemp to psRand's Random01()
set k to kTemp * (psRand's kBigPrime) mod (b - a + 1) + a
return k
end Random
end script
on randomizeGenerator()
set psRand's kLast to the ticks
end randomizeGenerator
on seedGenerator(n)
set psRand's kLast to n
end seedGenerator
on Random(a, b)
if a = 0 and b = 0 then
return psRand's Random01()
end if
if b - a < 0 then
set {a, b} to {b, a}
end if
set kTemp to psRand's Random01()
set k to kTemp * (psRand's kBigPrime) mod (b - a + 1) + a
return k
end Random
-- end script
Thanks to everyone who gave me a pointer or two here and refired my
Number theory interest. The list includes Emmanuel, Arthur, Caleb,
Chris N., James Robinson, Deivy Petrescu, Avram Aelony and PPCGod... I
hope I'm not missing anyone. Oh yeah, Mr. Tea was also exceedingly
helpful :).
Michael
--
Michael Sullivan
Business Card Express of CT Thermographers to the Trade
Cheshire, CT email@hidden
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.