1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
############################################################################
#
# File: periodic.icn
#
# Subject: Procedures related to periodic sequences
#
# Author: Ralph E. Griswold
#
# Date: June 10, 2001
#
############################################################################
#
# This file is in the public domain.
#
############################################################################
#
# Sqrt(i, j) produces a rational approximation to the square root of i
# with j iterations of the half-way method. j defaults to 5.
#
############################################################################
#
# Requires: Large-integer arithmetic
#
############################################################################
#
# Links: lists, numbers, rational, strings
#
############################################################################
link lists
link numbers
link rational
link strings
record perseq(pre, rep)
procedure Sqrt(i, j) #: rational approximate to square root
local rat, half
/j := 5
half := rational(1, 2, 1)
rat := rational(integer(sqrt(i)), 1, 1) # initial approximation
i := rational(i, 1, 1)
every 1 to j do
rat := mpyrat(half, addrat(rat, divrat(i, rat, 1), 1))
return rat
end
procedure rat2cf(rat) #: continued fraction sequence for rational
local r, result, i, j
i := rat.numer
j := rat.denom
result := []
repeat {
put(result, rational(integer(i / j), 1, 1).numer)
r := i % j
i := j
j := r
if j = 0 then break
}
return perseq(result, [])
end
procedure cfapprox(lst) #: continued-fraction approximation
local prev_n, prev_m, n, m, t
lst := copy(lst)
prev_n := [1]
prev_m := [0, 1]
put(prev_n, get(lst).denom) | fail
while t := get(lst) do {
n := t.denom * get(prev_n) + t.numer * prev_n[1]
m := t.denom * get(prev_m) + t.numer * prev_m[1]
suspend rational(n, m, 1)
put(prev_n, n)
put(prev_m, m)
if t.denom ~= 0 then { # renormalize
every !prev_n /:= t.denom
every !prev_m /:= t.denom
}
}
end
procedure dec2rat(pre, rep) #: convert repeating decimal to rational
local s
s := ""
every s ||:= (!pre | |!rep) \ (*pre + *rep)
return ratred(rational(s - left(s, *pre),
10 ^ (*pre + *rep) - 10 ^ *pre, 1))
end
procedure rat2dec(rat) #: decimal expansion of rational
local result, remainders, count, seq
rat := copy(rat)
result := ""
remainders := table()
rat.numer %:= rat.denom
rat.numer *:= 10
count := 0
while rat.numer > 0 do {
count +:= 1
if member(remainders, rat.numer) then { # been here; done that
seq := perseq()
result ? {
seq.pre := move(remainders[rat.numer] - 1)
seq.rep := tab(0)
}
return seq
}
else insert(remainders, rat.numer, count)
result ||:= rat.numer / rat.denom
rat.numer %:= rat.denom
rat.numer *:= 10
}
return perseq([rat.denom], []) # WRONG!!!
end
procedure repeater(seq, ratio, limit) #: find repeat in sequence
local init, i, prefix, results, segment, span
/ratio := 2
/limit := 0.75
results := copy(seq)
prefix := []
repeat {
span := *results / ratio
every i := 1 to span do {
segment := results[1+:i] | next
if lequiv(lextend(segment, *results), results) then
return perseq(prefix, segment)
}
put(prefix, get(results)) | # first term to prefix
return perseq(prefix, results)
if *prefix > limit * *seq then return perseq(seq, [])
}
end
procedure seqimage(seq) #: sequence image
local result
result := ""
every result ||:= !seq.pre || ","
result ||:= "["
if *seq.rep > 0 then {
every result ||:= !seq.rep || ","
result[-1] := "]"
}
else result ||:= "]"
return result
end
|
