20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
# File 'lib/kgl/kmath.rb', line 20
def approx_reduction(all=false)
if self.numerator == 0
return self unless all
d = 0
d += 1 while Rational(1, 1<<d).to_f != 0.0
n = 1<<d
(d-1).downto(0) do |i|
e = (1<<i)
n -= e if Rational(1, n-e).to_f == 0.0
end
return [Rational(-1, n), Rational(1, n)]
elsif self.denominator == 1
s = self < 0 ? -1 : 1
d, n = 0, self.numerator.abs
f = n.to_f
d += 1 while (n-(1<<d)).to_f == f
(d-1).downto(0) do |i|
e = (1<<i)
n -= e if (n-e).to_f == f
end
r = Rational(n*s, 1)
return r unless all
d, n = 0, self.numerator.abs
d += 1 while (n+(1<<d)).to_f == f
(d-1).downto(0) do |i|
e = (1<<i)
n += e if (n+e).to_f == f
end
if n == r.numerator.abs
return [r]
else
return [r, Rational(n*s, 1)]
end
elsif self.numerator.abs == 1
d, n = 0, self.denominator
f = self.to_f.abs
if f == 0.0
unless all
return Rational(0, 1).approx_reduction(true)[self.numerator<0 ? 0 : 1]
else
return Rational(0, 1).approx_reduction(true)
end
end
d += 1 while Rational(1, n-(1<<d)).to_f == f
(d-1).downto(0) do |i|
e = (1<<i)
n -= e if Rational(1, n-e).to_f == f
end
r = Rational(self.numerator, n)
return r unless all
d, n = 0, self.denominator
d += 1 while Rational(1, n+(1<<d)).to_f == f
(d-1).downto(0) do |i|
e = (1<<i)
n += e if Rational(1, n+e).to_f == f
end
if n == r.denominator
return [r]
else
return [r, Rational(self.numerator, n)]
end
else
s = self < 0 ? -1 : 1
q = self.abs
if q.denominator < q.numerator
l = [q.numerator.div(q.denominator), 1]
h = [l[0]+1, 1]
else
h = [1, q.denominator.div(q.numerator)]
l = [1, h[1]+1]
end
res = [Rational(*l)]
r = Rational(*h)
foo, bar = (r-q).abs, (res[0]-q).abs
res = [r] if foo < bar || ( foo == bar && h.min < l.min )
i = 0
loop do
m = [l[0]+h[0], l[1]+h[1]]
r = Rational(*m)
if q.denominator <= r.denominator
return all ? res : res[-1]
elsif r < q
l = m
else
h = m
end
res << r*s
end
end
end
|