なんか上手くいかない Conway's PRIMEGAME

primegame.rb

PRIMEGAME = [Rational(17, 91),
             Rational(78, 85),
             Rational(19, 51),
             Rational(23, 38),
             Rational(29, 33),
             Rational(77, 29),
             Rational(95, 23),
             Rational(77, 19),
             Rational(1, 17),
             Rational(11, 13),
             Rational(13, 11),
             Rational(15, 2),
             Rational(1, 7),
             Rational(55, 1)]

class Rational
  def int?
    self.to_i == self.to_f
  end
end

class PrimeGame
  def initialize n
    @i = n
  end

  def until_integer
    result = @i
    PRIMEGAME.each do |e|
      result = @i
      result *= e
      return result.to_i if result.int?
    end
  end

  def exponent? n
    while n > 1
      return false if n % 2 == 1
      n /= 2
    end
    true
  end

  def times n
    n.times do |i|
      @i = until_integer
      print "#{@i} "
      puts(@i) if exponent?(@i)
    end
  end
end

prime = PrimeGame.new 2
prime.times 1000

primegame.rkt

#lang racket

;; Racketだと上手くいく

(define seed
  (list
   (/ 17 91) (/ 78 85) (/ 19 51)
   (/ 23 38) (/ 29 33) (/ 77 29)
   (/ 95 23) (/ 77 19) (/ 1 17)
   (/ 11 13) (/ 13 11) (/ 15 14)
   (/ 15 2) 55))

(define (find-integer n)
  (find-integer-p n seed))

(define (find-integer-p n xs)
  (let* ([try-rational (car xs)]
         [try-mul (* n try-rational)])
    (if (integer? try-mul) try-mul
        (find-integer-p n (cdr xs)))))

(define (stream-integer n)
  (let ([result 2]
        [exponent-list null])
    (for ([i n])
      (let ([get-integer (find-integer result)])
        (set! result get-integer)
        (if (exponent? result)
            (set! exponent-list (append exponent-list (list result)))
            null)))
    exponent-list))

(define (exponent? n)
  (cond [(= n 1) true]
        [(= (modulo n 2) 0) (exponent? (/ n 2))]
        [else false]))

problem.markdown

具体的な問題点

本来ならば、

4 8 32 128 2048 8192 131072 524288 8388608 536870912 2147483648 137438953472...

といったような2の累乗のリストが生成される筈なのだが、[4, 8, 32, 128]で止まる。 ログを読んでみると、ある段階で数値がループしている。おそらくFixnumあたりがオーバーフローして 数値がループしている結果?

根本的には1000じゃ少ないからでした

--- primegame.rb.orig   2016-08-25 14:30:26.000000000 +0900
+++ primegame.rb        2016-08-25 14:35:09.000000000 +0900
@@ -15,7 +15,7 @@

 class Rational
   def int?
-    self.to_i == self.to_f
+    self.denominator == 1
   end
 end

@@ -44,11 +44,11 @@
   def times n
     n.times do |i|
       @i = until_integer
-      print "#{@i} "
+      #print "#{@i} "
       puts(@i) if exponent?(@i)
     end
   end
 end

 prime = PrimeGame.new 2
-prime.times 1000
+prime.times 100000