From: Martin Bryce <nx-2000@...>
Date: 2008-08-18T04:55:28+09:00
Subject: Re: Not So Random (#173)

Hallo everybody. Please go easy on me, this quiz solution is my third 
ruby program ;) This language is a new discovery and it fascinates me, 
but I learnt to program in the old-fashioned imperative world in high 
school and I'm sure that it shows pretty clearly in the code (I made a 
couple of "shout-outs" in the code to all fellow former users of the one 
and only Borland Turbo Pascal 7 compiler :)

I decided to enter the "contest" hoping that somebody will show how 
these "translated Pascal" constructs of mine can be rephrased in a "more 
Ruby" way, maybe ;) Then, along the way, i discovered a really strange 
thing that I'd like to discuss with you.

The first class adheres to the quiz specifications, but I will be frank, 
anyway: I cheated. ;) The class simply stores the already generated 
numbers... after all, I tought, the tradeoff beween a few kilobytes of 
memory and the millions of cycles and butchering of mathematics caused 
by continuously reseeding the main PRNG should be acceptable. If 
somebody wants to pull hundreds of thousands of numbers in different 
sequences from such a thing, he is doing the wrong thing anyway....

  class Rseq

    @@Instances = 0
    @@Previous = 0
    @@Randomize = rand 2**29
    @@Randomize.freeze

    def getID
      @@Instances = @@Instances.succ
      return ( @@Instances * 43589 + @@Randomize )
    end

    def initialize(arg_to_rand=0)
      @ID = getID
      @ID.freeze
      @arg = arg_to_rand
      @@Previous = @ID
      srand(@ID)
      @cache = [ rand( @arg ) ]
      @pos = 0
    end

    def next
      @pos = @pos.succ
      if @pos <= @cache.length
        return @cache[(@pos-1)]
      else
        if @@Previous != @ID
          @@Previous = @ID
          srand ( @ID + @pos )
          end
        @cache.push rand(@arg)
        return @cache.last
      end
    end

    def reset
      @pos = 0
    end

  end


A better way to answer the basic quiz specifications for arbitrarily 
large outputs could be to hash a counter, I realized, so I wrote another 
class that works that way. Just for fun. A literal counter should work 
fine with a good hash function (maybe with some feedback), but I decided 
to use a string as "counter" because I believed that the Ruby hash 
function was optimized for those.

  class HRand

    MAXINT = (2**(1.size*8 - 2) - 1).to_f

    def initialize(arg_to_rand=0)
      @arg = arg_to_rand.to_i
      if @arg.is_a? Bignum
        @FIXNUM = false
        bytes = @arg.size
        @D = (0x7F<< ((bytes-1)*8))
        (bytes-2).times {|k| @D = (@D && (0xFF << (k*8))) }
        else
        @FIXNUM = true
      end
      @FIXNUM.freeze

      @s = ''
      10.times { @s = @s + rand(255).chr }
      @s.freeze
      @index = 0
    end

    def next
    @index = @index.succ
    if @FIXNUM
      h = (@s + @index.to_s).hash.abs
      return (h / MAXINT * @arg).to_i
      else
      num = 0
      words = @arg.size/1.size
      words.times {|k| n = n + ((@s + k.chr + @index.to_s).hash.abs << 
k*1.size*8) }
      num[bytes*8-1] = 0
      fraction = Rational(n,@D)
      return (@arg * fraction).to_i
      end
    end

    def reset
    @index = 0
    end
  end

And it doesn't work.
Not surprising, in itself.
But it's totally unexpected and surprising that the fault, as far as I 
can tell, doesn't lie in my code but in core Ruby o___O
The HRand objects output long runs of the same numbers because the 
string.hash method returns SEQUENTIAL numbers for alphabetically 
sequential strings!

I was taught that a hash function should strive to distribute the inputs 
in its keyspace with maximal randomness, and that it should mask any 
normally possible input pattern (those that are not a knowledgeable 
attack at the function, I mean)..... That's not a hash function, that's 
a checksum!

Does Ruby use such a dreadful function for its internal hash tables? If 
so, filling a hash with previously ordered data is going to (over)fill 
the hash buckets one by one... @___@
-- 
Posted via http://www.ruby-forum.com/.