:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::
:: This program creates a binary file containing 11+ megabytes ::
:: of 32-bit integers from a multiply-with-carry generator ::
:: x(n)=a*x(n-1)+carry mod 2^32 ::
:: You choose the multiplier from a list and specify the name of ::
:: the file to be created. The period of the generator will be ::
:: a*2^31-1. This class of generators is particularly well sui- ::
:: ted for implementation in machine language, and I predict ::
:: that many system generators in the future will be of this ::
:: class rather than the linear congruential generators for mo- ::
:: dulus 2^32 that are common today. ::
:: To illustrate how the `carry' works, suppose from the ::
:: current (32-bit) x and (30 bit) c, one forms a*x+c. This may ::
:: be done in a 64-(or double 32-) bit register in most modern ::
:: CPU's. Then the new random x is the lower 32 bits, the new ::
:: carry the upper 32. To see how well such a simple and fast :: ::
:: generator performs on tests of randomness, this program makes ::
:: a large file with the multiply-with-carry generator implemen- ::
:: ted in 16-bit integer arithmetic. Those finding it suitable ::
:: may wish to make an assembler version for their system. ::
:: It seems to pass all tests. ::
:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::
:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::
:: This program creates the binary file mwc1616.32, containing ::
:: 11+ megabytes of integers made by concatenating two 16-bit ::
:: multiply-with-carry generators. ::
:: The two generators have the form ::
:: x(n)=a*x(n-1)+carry mod 2^16 and ::
:: y(n)=b*y(n-1)+carry mod 2^16, ::
:: with suggested choices for multipliers `a' and `b'. ::
:: The `carry' c works as follows: If a and x are 16-bit and ::
:: c at most 14 bits, then forming a*x+c produces an at-most 31- ::
:: bit result. That result mod 2^16 (the rightmost 16 bits) is ::
:: the new x and the topmost 16 bits the new carry c. The sequ- ::
:: ence of resulting x's has period the order of 2^16 in the ::
:: group of residues relatively prime to m=a*2^16-1, which will ::
:: be a*2^15-1 for the multipliers suggested here. ::
:: You will be prompted to choose a and b and two seeds. Output ::
:: is a 32-bit integer, the pair x,y side by side. ::
:: This multiply-with-carry generator is best done in assembler, ::
:: where it takes about 200 nanosecs with a Pentium 120. A Fort- ::
:: ran version takes about 300 ns. It seems to pass all tests ::
:: and is highly recommended for speed and simplicity. ::
:: The essence of a version in C requires only two statements: ::
:: x=a*(x&65535)+(x>>16); y=b*(y&65535)+(y>>16); ::
:: if x and y are 32-bit integers with carry in the top and out- ::
:: put in the bottom half. The 32-bit integer returned is ::
:: (x<<16)+(y&65525); ::
:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::
:: ----------------------------------------------------------- ::
:: 18000 18030 18273 18513 18879 19074 19098 19164 19215 19584 ::
:: 19599 19950 20088 20508 20544 20664 20814 20970 21153 21243 ::
:: 21423 21723 21954 22125 22188 22293 22860 22938 22965 22974 ::
:: 23109 23124 23163 23208 23508 23520 23553 23658 23865 24114 ::
:: 24219 24660 24699 24864 24948 25023 25308 25443 26004 26088 ::
:: 26154 26550 26679 26838 27183 27258 27753 27795 27810 27834 ::
:: 27960 28320 28380 28689 28710 28794 28854 28959 28980 29013 ::
:: 29379 29889 30135 30345 30459 30714 30903 30963 31059 31083 ::
:: ----------------------------------------------------------- ::
:::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::::::
:: This program creates a binary file, mthr4.32, with 11 mgbytes::
:: of 32-bit integers from the multiply-with-carry generator ::
x(n)=2111111111x(n-4)+1492x(n-3)+1776x(n-2)+5115x(n-1)+carry mod 2^32.
:: The period of this generator is about 2^160. It is one of ::
:: what I called "The Mother of All Random Number Generators", ::
:: a few years ago when use of `Mother of All...' was topical ::
:: and could be used for showing bombast, defiance or derision.::
:: All apply to the usage here. The `carry' part, c, is the ::
:: multiple of the modulus b=2^32 dropped in the reduction; for::
:: example, if the linear combination with the current four x's ::
:: and carry c produced the result 125*b+3621, then the new x ::
:: becomes 3621 and the new carry 125. The big advantage of this::
:: and other multiply-with-carry generators is that they allow ::
:: use of modulus 2^16 & 2^32 without the trailing-bits regular-::
:: ities encountered in congruential sequences for such moduli. ::
:: But that advantage has to be gained through assembly language::
:: if b=2^32, as no common high level language seems to allow ::
:: access to the top 32 bits of the 64-bit product of two 32-bit::
:: integers. See also the file make1616.exe and makemwc1.exe ::
:::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::::::
:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::
:: This program creates the binary file kiss.32, containing ::
:: 11+ megabytes of integers from the generator KISS, which com- ::
:: bines three simple generators. The acronym KISS means ::
:: Keep It Simple Stupid ::
:: and the idea is to use simple, fast, individually promising ::
:: generators to get a composite that will be fast, easy to code ::
:: have a very long period and pass all the tests put to it. ::
:: The three components of KISS are ::
:: x(n)=a*x(n-1)+1 mod 2^32 ::
:: y(n)=y(n-1)(I+L^13)(I+R^17)(I+L^5), ::
:: z(n)=2*z(n-1)+z(n-2) +carry mod 2^32 ::
:: The y's are a shift register sequence on 32bit binary vectors ::
:: period 2^32-1; see the description in executing makesupr.exe. ::
:: The z's are a simple multiply-with-carry sequence with period ::
:: 2^63+2^32-1. The period of KISS is thus ::
:: 2^32*(2^32-1)*(2^63+2^32-1) > 2^127 ::
:: KISS is particularly well suited for assembler programming, ::
:: where it takes about 200 nanosecs with a Pentium 120. ::
:: It seems to pass all tests and is highly recommended for ::
:: speed and simplicity (for generators with that long a period) ::
:: :::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::: ::
:: This program creates a binary file containing 11+ megabytes ::
:: of 32-bit integers from a multiply-with-carry generator ::
:: x(n)=a*x(n-1)+carry mod 2^32 ::
:: You choose the multiplier from a list and specify the name of ::
:: the file to be created. The period of the generator will be ::
:: a*2^31-1. This class of generators is particularly well sui- ::
:: ted for implementation in machine language, and I predict ::
:: that many system generators in the future will be of this ::
:: class rather than the linear congruential generators for mo- ::
:: dulus 2^32 that are common today. ::
:: To illustrate how the `carry' works, suppose from the ::
:: current (32-bit) x and (30 bit) c, one forms a*x+c. This may ::
:: be done in a 64-(or double 32-) bit register in most modern ::
:: CPU's. Then the new random x is the lower 32 bits, the new ::
:: carry the upper 32. To see how well such a simple and fast :: ::
:: generator performs on tests of randomness, this program makes ::
:: a large file with the multiply-with-carry generator implemen- ::
:: ted in 16-bit integer arithmetic. Those finding it suitable ::
:: may wish to make an assembler version for their system. ::
:: It seems to pass all tests. ::
:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::
:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::
:: This program creates the binary file mwc1616.32, containing ::
:: 11+ megabytes of integers made by concatenating two 16-bit ::
:: multiply-with-carry generators. ::
:: The two generators have the form ::
:: x(n)=a*x(n-1)+carry mod 2^16 and ::
:: y(n)=b*y(n-1)+carry mod 2^16, ::
:: with suggested choices for multipliers `a' and `b'. ::
:: The `carry' c works as follows: If a and x are 16-bit and ::
:: c at most 14 bits, then forming a*x+c produces an at-most 31- ::
:: bit result. That result mod 2^16 (the rightmost 16 bits) is ::
:: the new x and the topmost 16 bits the new carry c. The sequ- ::
:: ence of resulting x's has period the order of 2^16 in the ::
:: group of residues relatively prime to m=a*2^16-1, which will ::
:: be a*2^15-1 for the multipliers suggested here. ::
:: You will be prompted to choose a and b and two seeds. Output ::
:: is a 32-bit integer, the pair x,y side by side. ::
:: This multiply-with-carry generator is best done in assembler, ::
:: where it takes about 200 nanosecs with a Pentium 120. A Fort- ::
:: ran version takes about 300 ns. It seems to pass all tests ::
:: and is highly recommended for speed and simplicity. ::
:: The essence of a version in C requires only two statements: ::
:: x=a*(x&65535)+(x>>16); y=b*(y&65535)+(y>>16); ::
:: if x and y are 32-bit integers with carry in the top and out- ::
:: put in the bottom half. The 32-bit integer returned is ::
:: (x<<16)+(y&65525); ::
:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::
:: ----------------------------------------------------------- ::
:: 18000 18030 18273 18513 18879 19074 19098 19164 19215 19584 ::
:: 19599 19950 20088 20508 20544 20664 20814 20970 21153 21243 ::
:: 21423 21723 21954 22125 22188 22293 22860 22938 22965 22974 ::
:: 23109 23124 23163 23208 23508 23520 23553 23658 23865 24114 ::
:: 24219 24660 24699 24864 24948 25023 25308 25443 26004 26088 ::
:: 26154 26550 26679 26838 27183 27258 27753 27795 27810 27834 ::
:: 27960 28320 28380 28689 28710 28794 28854 28959 28980 29013 ::
:: 29379 29889 30135 30345 30459 30714 30903 30963 31059 31083 ::
:: ----------------------------------------------------------- ::
:::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::::::
:: This program creates a binary file, mthr4.32, with 11 mgbytes::
:: of 32-bit integers from the multiply-with-carry generator ::
x(n)=2111111111x(n-4)+1492x(n-3)+1776x(n-2)+5115x(n-1)+carry mod 2^32.
:: The period of this generator is about 2^160. It is one of ::
:: what I called "The Mother of All Random Number Generators", ::
:: a few years ago when use of `Mother of All...' was topical ::
:: and could be used for showing bombast, defiance or derision.::
:: All apply to the usage here. The `carry' part, c, is the ::
:: multiple of the modulus b=2^32 dropped in the reduction; for::
:: example, if the linear combination with the current four x's ::
:: and carry c produced the result 125*b+3621, then the new x ::
:: becomes 3621 and the new carry 125. The big advantage of this::
:: and other multiply-with-carry generators is that they allow ::
:: use of modulus 2^16 & 2^32 without the trailing-bits regular-::
:: ities encountered in congruential sequences for such moduli. ::
:: But that advantage has to be gained through assembly language::
:: if b=2^32, as no common high level language seems to allow ::
:: access to the top 32 bits of the 64-bit product of two 32-bit::
:: integers. See also the file make1616.exe and makemwc1.exe ::
:::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::::::
:::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::
:: This program creates the binary file kiss.32, containing ::
:: 11+ megabytes of integers from the generator KISS, which com- ::
:: bines three simple generators. The acronym KISS means ::
:: Keep It Simple Stupid ::
:: and the idea is to use simple, fast, individually promising ::
:: generators to get a composite that will be fast, easy to code ::
:: have a very long period and pass all the tests put to it. ::
:: The three components of KISS are ::
:: x(n)=a*x(n-1)+1 mod 2^32 ::
:: y(n)=y(n-1)(I+L^13)(I+R^17)(I+L^5), ::
:: z(n)=2*z(n-1)+z(n-2) +carry mod 2^32 ::
:: The y's are a shift register sequence on 32bit binary vectors ::
:: period 2^32-1; see the description in executing makesupr.exe. ::
:: The z's are a simple multiply-with-carry sequence with period ::
:: 2^63+2^32-1. The period of KISS is thus ::
:: 2^32*(2^32-1)*(2^63+2^32-1) > 2^127 ::
:: KISS is particularly well suited for assembler programming, ::
:: where it takes about 200 nanosecs with a Pentium 120. ::
:: It seems to pass all tests and is highly recommended for ::
:: speed and simplicity (for generators with that long a period) ::
:: :::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::: ::
Comment