|
(1 + sqrt(2)) / 2 → 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4
(1 + 1 / sqrt(2)) / 2 → 0 1 5 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1</pre>
=={{header|ObjectIcon}}==
{{trans|ATS}}
{{trans|D}}
<syntaxhighlight lang="objecticon">
# -*- ObjectIcon -*-
#
# Object Icon, translated from a Dlang implementation that is based on
# the ATS.
#
import io
procedure string_concatenation_of (lst)
# Something I will use later on: concatenate the elements of lst as
# strings.
local n, stream
every (/n := 0) +:= *(!lst)
stream := io.RamStream ("", n)
every stream.writes (!lst)
return stream.str()
end
class CF () # A continued fraction, with memoization of terms.
protected terminated # Are there more terms to be memoized?
protected m # How many terms are memoized so far?
private memo # Memoized terms.
private static max_terms # Default maximum number of terms in
# the string representation.
private static init ()
max_terms := 20
return
end
public new ()
terminated := &no
m := 0
memo := []
return
end
protected generate ()
# Return terms for zero. To get different terms, override this
# method.
return (if m = 0 then 0 else fail)
end
private update (needed)
# If necessary, memoize more terms.
local term
while /terminated & m < needed do
{
if term := generate () then
{
# Generating a new term succeeded. Memoize the term.
put (memo, term)
m +:= 1
}
else
{
# Generating a new term failed. There are no more terms in the
# continued fraction.
terminated := &yes
}
}
return
end
public get_at (i)
update (i + 1)
# Icon arrays have 1-based indexing (so index=0 can mean "past the
# end"), but we will have a convention of 0-based indexing for
# terms of a continued fraction. (There is no "end", so there is
# no reason to adopt an Icon-like indexing scheme.)
return (if i < m then memo[i + 1] else fail)
end
private sep_str (sep)
return (if sep = 0 then "" else if sep = 1 then ";" else ",")
end
public to_string (max_terms)
# I do string concatenation in a funny way here, for no especially
# good reason. :)
local lst, sep, i, done, term
/max_terms := CF.max_terms
lst := ["["]
sep := 0
i := 0
done := &no
while /done do
{
if i = max_terms then
{
# We have reached the maximum of terms to print. Stick an
# ellipsis in the notation.
put (lst, ",...]")
done := &yes
}
else if term := get_at (i) then
{
# Getting a term succeeded. Include the term.
put (lst, sep_str (sep))
put (lst, term)
sep := min (sep + 1, 2)
i +:= 1
}
else
{
# Getting a term failed. We are done.
put (lst, "]")
done := &yes
}
}
return string_concatenation_of (lst)
end
end
final class CF_sqrt2 (CF) # A continued fraction for sqrt(2).
protected override generate ()
return (if m = 0 then 1 else 2)
end
end
class CF_rational (CF) # A continued fraction for a rational number.
private n
private d
public override new (numerator, denominator)
CF.new ()
n := numerator
d := denominator
return
end
protected override generate ()
local q, r
d = 0 & fail
q := n / d
r := n % d
n := d
d := r
return q
end
end
class HFunc () # A homographic function.
public a1
public a
public b1
public b
public new (a1, a, b1, b)
self.a1 := a1
self.a := a
self.b1 := b1
self.b := b
return
end
end
class CF_HFunc (CF) # A continued fraction that is a homographic
# function of another continued fraction.
private state
private other_cf
private index
# Call as either CF_HFunc(hfunc,cf) or CF_HFunc(a1,a,b1,b,cf).
public override new (hfunc_or_a1, cf_or_a, b1, b, cf_or_null)
CF.new ()
if \b1 then
{
state := HFunc (hfunc_or_a1, cf_or_a, b1, b)
other_cf := cf_or_null
}
else
{
state := HFunc (hfunc_or_a1.a1, hfunc_or_a1.a,
hfunc_or_a1.b1, hfunc_or_a1.b)
other_cf := cf_or_a
}
index := 0
return
end
protected override generate ()
local a1, a, b1, b
local q1, q
local term
repeat
{
a1 := state.a1
a := state.a
b1 := state.b1
b := state.b
if b1 = b = 0 then
fail
else if b1 ~= 0 & b ~= 0 then
{
q1 := a1 / b1
q := a / b
if q1 = q then
{
state.a1 := b1
state.a := b
state.b1 := a1 - (b1 * q)
state.b := a - (b * q)
return q
}
}
if term := other_cf.get_at (index) & index +:= 1 then
{
state.a1 := a + (a1 * term)
state.a := a1
state.b1 := b + (b1 * term)
state.b := b1
}
else
{
state.a := a1
state.b := b1
}
}
end
end
procedure show (expr, cf)
io.write (expr, cf.to_string())
return
end
procedure main (args)
local cf_13_11, cf_22_7, cf_sqrt2
cf_13_11 := CF_rational (13, 11)
cf_22_7 := CF_rational (22, 7)
cf_sqrt2 := CF_sqrt2 ()
show ("13/11 => ", cf_13_11)
show ("22/7 => ", cf_22_7)
show ("sqrt(2) => ", cf_sqrt2)
show ("13/11 + 1/2 => ", CF_HFunc (HFunc (1, 2, 0, 2), cf_13_11))
show ("22/7 + 1/2 => ", CF_HFunc (1, 2, 0, 2, cf_22_7))
show ("(22/7)/4 => ", CF_HFunc (1, 0, 0, 4, cf_22_7))
show ("sqrt(2)/2 => ", CF_HFunc (1, 0, 0, 2, cf_sqrt2))
show ("1/sqrt(2) => ", CF_HFunc (0, 1, 1, 0, cf_sqrt2))
show ("(2 + sqrt(2))/4 => ", CF_HFunc (1, 2, 0, 4, cf_sqrt2))
# Demonstrate a deeper nesting.
show ("(1 + 1/sqrt(2))/2 => ",
CF_HFunc (1, 0, 0, 2, # Divide by 2.
CF_HFunc (1, 1, 0, 1, # Add 1.
CF_HFunc (0, 1, 1, 0, # Take reciprocal.
CF_sqrt2 ()))))
end
</syntaxhighlight>
{{out}}
<pre>$ oiscript univariate-continued-fraction-task-OI.icn
13/11 => [1;5,2]
22/7 => [3;7]
sqrt(2) => [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...]
13/11 + 1/2 => [1;1,1,2,4]
22/7 + 1/2 => [2;1,1,3]
(22/7)/4 => [0;1,3,1,2]
sqrt(2)/2 => [0;1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...]
1/sqrt(2) => [0;1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...]
(2 + sqrt(2))/4 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]
(1 + 1/sqrt(2))/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]</pre>
=={{header|Phix}}==
|