Continued fraction/Arithmetic/G(matrix ng, continued fraction n): Difference between revisions
Content added Content deleted
Line 4,765: | Line 4,765: | ||
(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 + 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> |
(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) |
|||
# |
|||
# String concatenation operators seem to be broken, in the |
|||
# revision of Object Icon that (at the moment) I have installed. |
|||
# Therefore I have written this implementation instead of a more |
|||
# obvious one. |
|||
# |
|||
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}}== |
=={{header|Phix}}== |