Looking for more algorithms for quasirandom numbers

11292019, 01:06 PM
(This post was last modified: 11302019 06:16 AM by Namir.)
Post: #1




Looking for more algorithms for quasirandom numbers
Hi All Math Lovers,
In another thread of mine, ttw mentions quasirandom numbers. Quasirandom numbers (QRNs) present a better spread over a range of values than pseudorandom numbers (PRNs). On the other hand, QRNs will often fail randomness tests. They true purpose to to cover more uniformly a range of values in one of more dimensions. This is part of ttw's response in my other thread, where he mentions QRNs: Quote:The easiest multidimensional quasirandom sequence is the Richtmeyer sequence. One uses the fractional part of multiples of the square roots of primes. Sqrt(2), Sqrt(3), etc. It's quick to do these by just setting x(i)=0 updating by x(i)=Frac(x(i)+Sqrt(P(i))). Naturally one just stores the fractional parts of the irrationals and updates. (List mode). The sequence is also called the Kronecker or Weyl sequence at times. The above text includes the algorithm of setting x(1)=0 updating by x(i)=Frac(x(i)+Sqrt(P(i))). The array of P() represents prime numbers starting with 2. You can change x(1) to had a uniform random number as a seed (to generate different sequences every time you apply the algorithm) or simply set x(1) = sqrt(P(1)) = sqrt(2). I am curious about other formulas to calculate sequences of quasirandom numbers. You are welcome to use your imagination. My first attempt was something like: Code: n = number of x to generate The above code produces x() with a mean near 0.5 and standard deviation near 0.28. The auto correlations for the first 50 lags are in the orde rof 10^(2) to 10^(4). I am curious about other formulas to calculate sequences of quasirandom numbers. You are welcome to use your imagination. You can even commit math heresy!!! As long as it works, you are fine (and forgiven) :) Namir 

11292019, 04:49 PM
(This post was last modified: 11292019 06:24 PM by SlideRule.)
Post: #2




RE: Looking for more algorithms for quasirandom numbers
Perusal of Quasirandom sequences in art and integration, John D. Cook Consulting, illumes the phenomena with references to more descriptive books; Random Number Generation and QuasiMonte Carlo Methods & Monte Carlo and QuasiMonte Carlo Methods, on the same.
BEST! SlideRule 

11302019, 01:36 AM
Post: #3




RE: Looking for more algorithms for quasirandom numbers
(11292019 01:06 PM)Namir Wrote: This is part of ttw's response in my other thread, where he mentions QRNs: Quote:The easiest multidimensional quasirandom sequence is the Richtmeyer sequence. One uses the fractional part of multiples of the square roots of primes. Sqrt(2), Sqrt(3), etc. It's quick to do these by just setting x(i)=0 updating by x(i)=Frac(x(i)+Sqrt(P(i))). Naturally one just stores the fractional parts of the irrationals and updates. (List mode). The sequence is also called the Kronecker or Weyl sequence at times. Using "quote" in place of "code" will autowrap large blocks of text! Remember kids, "In a democracy, you get the government you deserve." 

11302019, 01:29 PM
Post: #4




RE: Looking for more algorithms for quasirandom numbers
(11302019 01:36 AM)mfleming Wrote:(11292019 01:06 PM)Namir Wrote: This is part of ttw's response in my other thread, where he mentions QRNs: I learned that the hard way :) 

11302019, 07:52 PM
Post: #5




RE: Looking for more algorithms for quasirandom numbers
The few leads I got from the nice folks on this web were able to lead me to methods that generate sequences of quasirandom numbers that are practically perfectly distributed. I got what I was looking for. Thanks!!!
Namir 

12012019, 05:52 AM
Post: #6




RE: Looking for more algorithms for quasirandom numbers
This is one of the sequences from my paper in "Computational investigations of lowdiscrepancy point sets II" from the 1994 Las Vegas Conference on Monte Carlo and Quasi Monte Carlo Methods. I have made a single adhoc change (described below) that improves distribution for small numbers of points.
The Halton Sequence Phi(N,P) (for odd primes, 2 is a special case not considered here) can be described as: 1. Generate the digits of N in base P (for P an odd prime). Call these digits a(1) to a(k) where k is the maximum number of digits needed. (There should be lots of subscripts but I'll treat each prime separately to reduce index management.) N=Sum from j=1 to k of a(j)*P^(j1), that is: a(k)a(k1)...a(2)(a(1). 2. Reverse the digits: a(1),a(2)....a(k1),a(k) is resulting string. 3. Treat this string as a fraction with a decimal point (pary point?) in front. Example: P=3, N=5: 5(3)=12. Reverse Phi(5,3)=.21(3) or 2/3+1/9 = 7/9 The sequence is very well distributed for example one starts with 0, 1/3, 2/3, 1/9, 4/9, 7/9, 2/9, 5/9, 8/9, 1/27, 10,27... This sequence is uniformly in the unit dcube using d different primes. For example in 3 dimensions using primes 3 and 5 gives the points: (skipping 0 which sits on the corner of the cube). (1/3, 1/5, 1/7) (2/3, 2/5, 2/7) (1/9, 3/5, 3/7) (4/9, 4/5, 4/7) (7/9,1/25,5/7) (2/9, 6/25, 6/7) (5/9, 11/25, 1/49) (8/9. 16/25, 8/49) etc. The process is sometimes termed a Kakatumivon Neumann odometer. There is a problem that I noticed about 1967 or so when I started working on quasiMonte Carlo. For large base, the Halton Sequence produces strongly correlated points until enough points are generated. (This happens with all quasirandom sequences but not as severely.) Take the first few points using bases 101 and 103. (1/101, 1/103) (2/101, 2/103) ... (100/101, 100/103) (1/10201, 101/103) (102/10201, 102/103) (203/10203, 1/10609) etc. In 19931995 period, I figured out to multiply each numerator by a number (I called a spin) to break this up. Then I used the fact the fractional parts of square roots of primes are independent to do the following seemingly strange rule. Give a prime P, to find a multiplier S, do the following. 1. Compute the nearest integers to the fractional part of the Sqrt(P), call these H and L (high and low, one is above and one below the number). 2. Compute the continued fraction of H/P and L/P; each generates a string of partial quotients. The multiplier S is the one of these satisfying the following: 3. A. Chose the one for which the sum of the partial quotients is smallest. B. If tied, chose the one with the smallest maximum partial quotient. C. If tied, chose whichever H/P or L/P is closest to the fractional part of the square root. D. Ad Hoc Alert: if P=41, use 16. (To avoid 17/41 being close to 12/29. The only such case in all primes less than 2^32) 4. To generate the modified Phi sequence Phi(N,P,S): generate the digits of N base P as above and reverse. Multiply each digit by S modulo P and sum as above. Examples: 3 dimensions: P=3, 5, 7 have S= 2, 2,and 5 respectively. (2/3, 2/5, 5/7) (1/3, 4/5, 3/7) (2/9, 1/5, 1/7) (8/9, 3/4, 6/7) etc. For the pathological case 101 and 103, the multipliers are 6 and 16 respectively (not the best but that's another post sometime). (6/101, 16/103) (12/101, 32/103) (18/101, 48/103) Clearly more spread out than the original Halton Sequence. I've got some more but Mordechay Levin's paper ArXiv 1806 shows that even the original Halton Sequence hits the theoretical lower bound for dimensions 2 and up so great changes cannot be had by tinkering. I do have a bit better, but it's even longer to compute and I haven't tested the new ideas thoroughly. HP50g code:(Number, Prime, Spin, Top, Bottom) << 0 1 > N P S T B << WHILE N REPEAT N S * P MOD T P * + 'T' STO P 'B' STO* N P IQUOT 'N' STO END T B />> >> Not necessarily the fastest but eas to work with. (If I've done this right.) 

12012019, 11:46 AM
Post: #7




RE: Looking for more algorithms for quasirandom numbers  
« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)