From: Jim Weirich <jim@...>
Date: 2004-09-16T04:32:01+09:00
Subject: Re: Bignum Troubles


James Edward Gray II said:
> Here's a look at my math:
>
> 	def initialize()
> 		# non-related setup work here
>
> 		@random_seeds = [ 12345 ]
> 	end
>
> 	# and later
>
> 	def test_random(limit)
> 		until @random_seeds.size == 5
> 			@random_seeds.push @random_seeds[-1] * 22695477 + 1
> 		end
> 		@random_seeds.shift
>
> 		return ((@random_seeds[-1] / 65536) % 16384) % limit
> 	end
>

Several things look wrong here.

(1) I don't see why you are using an array of seeds.  Only the last seed
is ever accessed, so you could get by with a single variable.  If the
original algorithm used an array, then I suspect that the algorithm wasn't
transliterated into Ruby correctly.

(2) The math doesn't need bignums.  It explicit throws away the bottow 16
bits (with the divide by 65535) and the tosses all the bits above the
remaining low 14 (with the mod 16384).  So a 30 bit number (16 + 14) would
be adequate for this particular algorithm.

Here's a simplier version of the algorithm.  It only uses one seed and the
seed never gets big enough to become a BigNum.  I tested it against the
first 10000 numbers in your sequence.

  class R2
    TWO_16 = (2**16)
    TWO_14 = (2**14)
    TWO_30 = (2**30)

    def initialize
      @seed = 12345
      3.times { @seed = next_seed }
    end

    def test_random(limit)
      @seed = next_seed
      ((@seed / TWO_16) % TWO_14) % limit
    end

    def next_seed
      (@seed * 22695477 + 1) % TWO_30
    end
  end


-- 
-- Jim Weirich     jim@weirichhouse.org    http://onestepback.org
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)