step_seed.rb

#!ruby

# next(next(s))
# -> (s * a + b) * a + b
# -> s * a * a + a * b + b

# nextQ(nextP(s))
# -> (s * aP + bP) * aQ + bQ
# -> s * aP * aQ + bP * aQ + bQ

# nextQ(nextP(s)) == nextP(nextQ(s))
# -> s * aP * aQ + bP * aQ + bQ == s * aQ * aP + bQ * aP + bP
# -> bP * aQ + bQ == bQ * aP + bP

# (((s * aP + bP) % M) * aQ + bQ) % M == ((s * aP + bP) * aQ + bQ) % M
# Q) 途中の % M をはしょっても大丈夫なん？
# A) 下8桁が全部0の値 = 0x100000000 の倍数に何をかけたところで 下の桁には何も影響しないよねというお話

Const = Struct.new(:a, :b)

class Const
  def inspect
    "#<Const %#.8x, %#.8x>" % [self.a, self.b]
  end
end

def combine_const(x, y)
  b1 = uint(x.b * y.a + y.b)
  b2 = uint(y.b * x.a + x.b)
  if b1 != b2
    raise "bug! b1 != b2"
  end
  Const.new(uint(x.a * y.a), b1)
end

def gen_const(a, b, n)
  result = Const.new(1, 0)
  c = Const.new(a, b)
  i = 0
  while n > 0
    if (n & 1) != 0
      result = combine_const(result, c)
    end
    c = combine_const(c, c)
    i += 1
    n >>= 1
  end
  result
end

def step_seed(seed, n, a, b)
  c = gen_const(a, b, n)
  uint(seed * c.a + c.b)
end

def uint(n)
  n & 0xffffffff
end

# 逆算の式を求める
p gen_const(0x41c64e6d, 0x6073, 0xffffffff)