|
|
 Up |
|
|
  |
Author: Frank BussFrank Buss Date: Nov 6, 2006 17:24
If you use the standard linear congruential pseudorandom number generator
on small CPUs, it can be slow, because multiplication can be expensive.
This is a random number generator, based on the idea from
http://www.stephenwolfram.com/publications/articles/ca/86-random/
which uses only bit shifting and boolean operations. The implemenation
assumes cells of the size 4. Speed can be enhanced, if the CPU provides
rolling left/right as an assembler instruction.
1835099960 value cells
: lroll ( u1 -- u2 ) dup 1 lshift swap 2147483648 and if 1 or then ;
: rroll ( u1 -- u2 ) dup 1 rshift swap 1 and if 2147483648 or then ;
: random-bit (
|
| |
|
| | 28 Comments |
|
|
Author: Aleksej SaushevAleksej Saushev Date: Nov 6, 2006 23:59
Frank Buss writes:
> If you use the standard linear congruential pseudorandom number generator
> on small CPUs, it can be slow, because multiplication can be expensive.
> This is a random number generator, based on the idea from
> http://www.stephenwolfram.com/publications/articles/ca/86-random/
> which uses only bit shifting and boolean operations. The implemenation
> assumes cells of the size 4. Speed can be enhanced, if the CPU provides
> rolling left/right as an assembler instruction.
>
> 1835099960 value cells
> : lroll ( u1 -- u2 ) dup 1 lshift swap 2147483648 and if 1 or then ;
> : rroll ( u1 -- u2 ) dup 1 rshift swap 1 and if 2147483648 or then ;
> : random-bit ( -- 1 | 0 ) cells dup rroll or cells lroll xor dup to cells 1 and ;
> : random-byte ( -- byte ) 0 8 0 do 1 lshift random-bit or loop ;
You may be interested in P. L'Ecuyer, "Maximally Equidistributed Combined
Tausworthe Generators", Mathematics of Computation, 65, 213 (1996), 20
--213.
I have published (at RetroForth site) working Forth code for (almost)
every RNG you can find in GNU Sci Lib.
|
| |
|
| | 25 Comments |
|
|
Author: macolnmailmacolnmail Date: Nov 7, 2006 05:40
Aleksej Saushev wrote:
> Frank Buss writes:
>
>> If you use the standard linear congruential pseudorandom number generator
>> on small CPUs, it can be slow, because multiplication can be expensive.
>> This is a random number generator, based on the idea from
>> http://www.stephenwolfram.com/publications/articles/ca/86-random/
>> which uses only bit shifting and boolean operations. The implemenation
>> assumes cells of the size 4. Speed can be enhanced, if the CPU provides
>> rolling left/right as an assembler instruction.
>>
>> 1835099960 value cells
>> : lroll ( u1 -- u2 ) dup 1 lshift swap 2147483648 and if 1 or then ;
>> : rroll ( u1 -- u2 ) dup 1 rshift swap 1 and if 2147483648 or then ;
>> : random-bit ( -- 1 | 0 ) cells dup rroll or cells lroll xor dup to cells 1 and ;
>> : random-byte ( -- byte ) 0 8 0 do 1 lshift random-bit or loop ; >
> You may be interested in P. L'Ecuyer, "Maximally Equidistributed Combined
> Tausworthe Generators", Mathematics of Computation, 65, 213 (1996), 203--213.
> ...
|
| Show full article (1.23Kb) |
| 24 Comments |
|
|
Author: Aleksej SaushevAleksej Saushev Date: Nov 7, 2006 06:37
macolnmail@yahoo.ca writes:
> Aleksej Saushev wrote:
>> Frank Buss writes:
>>
>>> If you use the standard linear congruential pseudorandom number generator
>>> on small CPUs, it can be slow, because multiplication...
|
| Show full article (1.40Kb) |
| 23 Comments |
|
|
Author: Frank BussFrank Buss Date: Nov 7, 2006 07:02
Aleksej Saushev wrote:
There are some unreadable chars in it. Which encoding did you use and which
language? Looks a bit mixed from various sources.
BTW: looks like the cellular automaton implementation with 32 bits is not
so good. I've tested it and it has a cycle length of only 842,527. The
article at
http://www.stephenwolfram.com/publications/articles/ca/86-random/10/text.html
says in table 9.2 it has a cycle length of 2,002,272 , but I can't
reproduce this, maybe my implementation is wrong?
I've tested it like this:
0 value cells-start
: test
\ avoid garden-of-eden-configurations
3000000 0 do random-bit drop loop
cells to cells-start
\ count number of cycles
0 begin random-bit drop cells cells-start = if . exit then 1+ again ;
|
| Show full article (0.97Kb) |
| 22 Comments |
|
|
Author: Marcel HendrixMarcel Hendrix Date: Nov 7, 2006 09:31
Frank Buss writes Re: random number generator
[..]
I also got 842,527, using the following code, on iForth 2.0.
Even 2,002,272 is no good, so why bother?
ANEW -buss
#1835099960 VALUE rcells
: lroll ( u1 -- u2 ) 1 ROL ;
: rroll ( u1 -- u2 ) 1 ROR ;
: random-bit ( -- 1 | 0 ) rcells DUP rroll OR rcells lroll XOR DUP TO rcells 1 AND ;
|
| Show full article (1.04Kb) |
| 21 Comments |
|
|
Author: Jean-François MichaudJean-François Michaud Date: Nov 7, 2006 13:03
Marcel Hendrix wrote:
> Frank Buss writes Re: random number generator
> [..]
>
> I also got 842,527, using the following code, on iForth 2.0.
> Even 2,002,272 is no good, so why bother?
>
> ANEW -buss
>
> #1835099960 VALUE rcells
> : lroll ( u1 -- u2 ) 1 ROL ;
> : rroll ( u1 -- u2 ) 1 ROR ;
> : random-bit ( -- 1 | 0 ) rcells DUP rroll OR rcells lroll XOR DUP TO rcells 1 AND ;
>
> \ avoid garden-of-eden-configurations ...
|
| Show full article (1.31Kb) |
| 2 Comments |
|
|
Author: Jorge Acereda MaciáJorge Acereda Maciá Date: Nov 7, 2006 12:53
Frank Buss wrote:
> : lroll ( u1 -- u2 ) dup 1 lshift swap 2147483648 and if 1 or then ;
This should be faster and doesn't assume 32 bits cell size:
: lroll dup 2* swap 0< - ;
Greetings,
Jorge Acereda
|
| |
| 1 Comment |
|
|
Author: Frank BussFrank Buss Date: Nov 7, 2006 14:05
Marcel Hendrix wrote:
> I also got 842,527, using the following code, on iForth 2.0.
> Even 2,002,272 is no good, so why bother?
It is very easy to implement it e.g. in FPGAs and DSPs and I've used this
for a DSP noise signal generator with 48 bits. And my assumption was, that
it has good random properties. But I've tested it with "ent" from
http://www.fourmilab.ch/random/ and this test:
: test
here 100000 dup 0 do random-byte c, loop
s" c:\tmp\test.bin" r/w create-file drop dup >r
write-file drop r> close-file drop ;
The output of "ent" :
Entropy = 7.998105 bits per byte.
Optimum compression would reduce the size
of this 100000 byte file by 0 percent.
Chi square distribution for 100000 samples is 262.84, and randomly
would exceed this value 50.00 percent of the times.
|
| Show full article (1.94Kb) |
| 17 Comments |
|
|
|
|
|
Author: Frank BussFrank Buss Date: Nov 7, 2006 14:39
Jorge Acereda Maciá wrote:
> This should be faster and doesn't assume 32 bits cell size:
>
>: lroll dup 2* swap 0< - ;
Thanks. It is possible for rroll, too. And redefining "cells" was not a
good idea, so this is the new source, which should work for every cell
size, up to 32 bit cell size. Maybe the seed value should be changed for
greater cell sizes to avoid initial non-random numbers.
\ random number generator, based on the ideas from
\ http://www.stephenwolfram.com/publications/articles/ca/86-random/
\ seed with a non-garden-of-eden value
\ (see http://acm.uva.es/p/v100/10001.html for garden of eden explanation)
159340636 value seed
\ rolls the number u1 one bit left
: lroll ( u1 -- u2 ) dup 2* swap 0< - ;
\ rolls the number u1 one bit right
0 invert dup 1 rshift xor constant highest-bit
: rroll ( u1 -- u2 ) dup 1 rshift swap 1 and if highest-bit or then ;
|
| Show full article (1.16Kb) |
| no comments |
|
|
|
|
