1. Mersenne Twister
- Posted by rforno at tutopia.com
Sep 21, 2001
Derek:
As per your request, I revised your implementation of the Mersenne Twister.
I found a slight disagreement with the original. The original poses:
seed & 0xffffffff
You instead code:
remainder(seed, #FFFFFFFF)
This does not give the same result for numbers >= 2^32 - 1, as should be
most of the numbers generated by multiplying the previous one by 69069.
Of course Euphoria does not accept:
and_bits(seed, #100000000),
but:
remainder(seed, #100000000) is Ok and gives the same result.
Maybe the initial matrix is not so important, as stated elsewhere, and your
variant is perhaps better, since the original generates only odd numbers,
and yours generates odd and even numbers nearly at random, but only to stick
to the original...:)
A similar problem occurs with the final result. The maximum value that y +
#80000000 can attain is #FFFFFFFFF, and in this case the result is 1 higher
than "range". This is equally solved by substituting range / #10000000
instead of range / #FFFFFFFF.
Even it may be preferable to write (y + #80000000) / #100000000 * range, to
protect against inaccuracies of the division of range by 2^32. Maybe Rob has
something to say
about it.
Best regards.
2. Re: Mersenne Twister
On 21 Sep 2001, at 17:02, rforno at tutopia.com wrote:
>
> Derek:
> As per your request, I revised your implementation of the Mersenne Twister. I
> found a slight disagreement with the original. The original poses: seed &
> 0xffffffff You instead code: remainder(seed, #FFFFFFFF) This does not give the
> same result for numbers >= 2^32 - 1, as should be most of the numbers
> generated
> by multiplying the previous one by 69069. Of course Euphoria does not accept:
> and_bits(seed, #100000000), but: remainder(seed, #100000000) is Ok and gives
> the
> same result. Maybe the initial matrix is not so important, as stated
> elsewhere,
> and your variant is perhaps better, since the original generates only odd
> numbers, and yours generates odd and even numbers nearly at random, but only
> to
> stick to the original...:) A similar problem occurs with the final result. The
> maximum value that y + #80000000 can attain is #FFFFFFFFF, and in this case
> the
> result is 1 higher than "range". This is equally solved by substituting range
> /
> #10000000 instead of range / #FFFFFFFF. Even it may be preferable to write (y
> +
> #80000000) / #100000000 * range, to protect against inaccuracies of the
> division
> of range by 2^32. Maybe Rob has something to say about it. Best regards.
What about using string math? You can then build as big a number as you
wish, in an object used as a sequence?
x = "0283650813749136548740623403784650278362456"--ad infinitum
return(x)
Kat
3. Re: Mersenne Twister
Thanks for that. I agree with your observations and have amended my code
accordingly.
I have been using another randomiser function that is a little more
unpredicatable. It works by using the normal Euphoria supplied rand()
function, except that at random times, it alters the seed value to a random
value. It is best used for programs that run for more than a few seconds.
-------------------
atom rtime
rtime = time()
global function rand_dp(integer i)
if time() > rtime + rand(3) then
set_rand( floor(rtime * time() * (rand(i)) / (rand(i))))
rtime = time()
end if
return rand(i)
end function
----------------------
----- Original Message -----
From: <rforno at tutopia.com>
To: "EUforum" <EUforum at topica.com>
Sent: Saturday, September 22, 2001 6:02 AM
Subject: Mersenne Twister
>
> Derek:
> As per your request, I revised your implementation of the Mersenne
Twister.
> I found a slight disagreement with the original. The original poses:
> seed & 0xffffffff
> You instead code:
> remainder(seed, #FFFFFFFF)
> This does not give the same result for numbers >= 2^32 - 1, as should be
> most of the numbers generated by multiplying the previous one by 69069.
> Of course Euphoria does not accept:
> and_bits(seed, #100000000),
> but:
> remainder(seed, #100000000) is Ok and gives the same result.
> Maybe the initial matrix is not so important, as stated elsewhere, and
your
> variant is perhaps better, since the original generates only odd numbers,
> and yours generates odd and even numbers nearly at random, but only to
stick
> to the original...:)
> A similar problem occurs with the final result. The maximum value that y +
> #80000000 can attain is #FFFFFFFFF, and in this case the result is 1
higher
> than "range". This is equally solved by substituting range / #10000000
> instead of range / #FFFFFFFF.
> Even it may be preferable to write (y + #80000000) / #100000000 * range,
to
> protect against inaccuracies of the division of range by 2^32. Maybe Rob
has
> something to say
> about it.
> Best regards.
>
>
>
4. Re: Mersenne Twister
rforno writes:
> Even it may be preferable to write (y + #80000000) / #100000000 * range,
> to protect against inaccuracies of the division of range by 2^32.
> Maybe Rob has something to say about it.
I'm not sure what you are asking, but it's my understanding
that calculations on large integer values (larger than Euphoria's 31-bit
internal representation) should work out exactly, as long you
are below the 15 (or so) decimal digit accuracy
of 64-bit floating-point numbers.
Regards,
Rob Craig
Rapid Deployment Software
http://www.RapidEuphoria.com
5. Re: Mersenne Twister
- Posted by rforno at tutopia.com
Sep 22, 2001
Oh, well, we don't need that for the Mersenne Twister. And of course this
would be sloooowwww...
----- Original Message -----
From: "Kat" <gertie at PELL.NET>
To: "EUforum" <EUforum at topica.com>
Subject: Re: Mersenne Twister
>
> On 21 Sep 2001, at 17:02, rforno at tutopia.com wrote:
>
> >
> > Derek:
> > As per your request, I revised your implementation of the Mersenne
Twister. I
> > found a slight disagreement with the original. The original poses: seed
&
> > 0xffffffff You instead code: remainder(seed, #FFFFFFFF) This does not
give the
> > same result for numbers >= 2^32 - 1, as should be most of the numbers
generated
> > by multiplying the previous one by 69069. Of course Euphoria does not
accept:
> > and_bits(seed, #100000000), but: remainder(seed, #100000000) is Ok and
gives the
> > same result. Maybe the initial matrix is not so important, as stated
elsewhere,
> > and your variant is perhaps better, since the original generates only
odd
> > numbers, and yours generates odd and even numbers nearly at random, but
only to
> > stick to the original...:) A similar problem occurs with the final
result. The
> > maximum value that y + #80000000 can attain is #FFFFFFFFF, and in this
case the
> > result is 1 higher than "range". This is equally solved by substituting
range /
> > #10000000 instead of range / #FFFFFFFF. Even it may be preferable to
write (y +
> > #80000000) / #100000000 * range, to protect against inaccuracies of the
division
> > of range by 2^32. Maybe Rob has something to say about it. Best regards.
>
> What about using string math? You can then build as big a number as you
> wish, in an object used as a sequence?
>
> x = "0283650813749136548740623403784650278362456"--ad infinitum
> return(x)
>
> Kat
>
>
>
6. Re: Mersenne Twister
- Posted by rforno at tutopia.com
Sep 23, 2001
Well, I was referring to this:
constant MAX = 1073741823
atom a, b --The same if using "integer" instead of "atom"
for i = 1 to 500 do
a = rand(MAX)
b = rand(MAX)
printf(1, "%g ", a - a / b * b)
end for
The inaccuracies are not observed when the divisor is greater than the
dividend.
Of course, I know that Euphoria uses the hardware division and is not to
be blamed. Moreover, it is true that the theory forces the results to be
inaccurate due to the infinite periodic representation of the majority of
fractions.
What I was pointing to in the original mail is that, even in the presence of
slight inaccuracies, reordering the terms as I propose will give always
exact results. Further experiments convinced me that both variations of the
formula give correct results.
----- Original Message -----
From: "Robert Craig" <rds at RapidEuphoria.com>
To: "EUforum" <EUforum at topica.com>
Sent: Saturday, September 22, 2001 8:09 PM
Subject: Re: Mersenne Twister
>
> rforno writes:
> > Even it may be preferable to write (y + #80000000) / #100000000 * range,
> > to protect against inaccuracies of the division of range by 2^32.
> > Maybe Rob has something to say about it.
>
> I'm not sure what you are asking, but it's my understanding
> that calculations on large integer values (larger than Euphoria's 31-bit
> internal representation) should work out exactly, as long you
> are below the 15 (or so) decimal digit accuracy
> of 64-bit floating-point numbers.
>
> Regards,
> Rob Craig
> Rapid Deployment Software
> http://www.RapidEuphoria.com
>
>
>
