Skip to content

Instantly share code, notes, and snippets.

@esehara
Last active August 25, 2016 05:35
Show Gist options
  • Save esehara/2212cd9ae9cbf963df87274182b7d08d to your computer and use it in GitHub Desktop.
Save esehara/2212cd9ae9cbf963df87274182b7d08d to your computer and use it in GitHub Desktop.
なんか上手くいかない Conway's PRIMEGAME
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
#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]))

具体的な問題点

本来ならば、

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

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

@nurse
Copy link

nurse commented Aug 25, 2016

根本的には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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment