Continued fraction/Arithmetic/G(matrix ng, continued fraction n): Difference between revisions
Content added Content deleted
Tag: Manual revert |
|||
Line 4,287: | Line 4,287: | ||
(1+√2)/2 = [1; 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, ...] |
(1+√2)/2 = [1; 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, ...] |
||
</pre> |
</pre> |
||
=={{header|Icon}}== |
|||
{{works with|Icon|9.5.22e}} |
|||
<syntaxhighlight lang="icon"> |
|||
# An implementation in Icon, using co-expressions as generators. |
|||
$define YES 1 |
|||
$define NO &null |
|||
# terminated = are there no more terms to memoize? |
|||
# m = the number of memoized terms. |
|||
# memo = the terms. |
|||
# generate = a co-expression to generate more terms. |
|||
record continued_fraction (terminated, m, memo, generate) |
|||
procedure main () |
|||
local cf_13_11, cf_22_7, cf_sqrt2, cf_1_div_sqrt2 |
|||
cf_13_11 := make_cf_rational (13, 11) |
|||
cf_22_7 := make_cf_rational (22, 7) |
|||
cf_sqrt2 := make_cf_sqrt2() |
|||
cf_1_div_sqrt2 := make_cf_hfunc (0, 1, 1, 0, cf_sqrt2) |
|||
show ("13/11", cf_13_11) |
|||
show ("22/7", cf_22_7) |
|||
show ("sqrt(2)", cf_sqrt2) |
|||
show ("13/11 + 1/2", make_cf_hfunc (2, 1, 0, 2, cf_13_11)) |
|||
show ("22/7 + 1/2", make_cf_hfunc (2, 1, 0, 2, cf_22_7)) |
|||
show ("(22/7)/4", make_cf_hfunc (1, 0, 0, 4, cf_22_7)) |
|||
show ("1/sqrt(2)", cf_1_div_sqrt2) |
|||
show ("(2 + sqrt(2))/4", make_cf_hfunc (1, 2, 0, 4, cf_sqrt2)) |
|||
show ("(1 + 1/sqrt(2))/2", make_cf_hfunc (1, 1, 0, 2, |
|||
cf_1_div_sqrt2)) |
|||
end |
|||
procedure show (expr, cf) |
|||
write (expr, " => ", cf2string (cf)) |
|||
end |
|||
procedure make_cf_sqrt2 () |
|||
return make_continued_fraction (create gen_sqrt2 ()) |
|||
end |
|||
procedure make_cf_rational (n, d) |
|||
return make_continued_fraction (create gen_rational (n, d)) |
|||
end |
|||
procedure make_cf_hfunc (a1, a, b1, b, other_cf) |
|||
return make_continued_fraction (create gen_hfunc (a1, a, b1, b, |
|||
other_cf)) |
|||
end |
|||
procedure gen_sqrt2 () |
|||
suspend 1 |
|||
repeat suspend 2 |
|||
end |
|||
procedure gen_rational (n, d) |
|||
local q, r |
|||
repeat { |
|||
if d = 0 then fail |
|||
q := n / d |
|||
r := n % d |
|||
n := d |
|||
d := r |
|||
suspend q |
|||
} |
|||
end |
|||
procedure gen_hfunc (a1, a, b1, b, other_cf) |
|||
local a1_tmp, a_tmp, b1_tmp, b_tmp |
|||
local i, term, skip_getting_a_term |
|||
local q1, q |
|||
i := 0 |
|||
repeat { |
|||
skip_getting_a_term := NO |
|||
if b1 = b = 0 then { |
|||
fail |
|||
} else if b1 ~= 0 & b ~= 0 then { |
|||
q1 := a1 / b1 |
|||
q := a / b |
|||
if q1 = q then { |
|||
a1_tmp := a1 |
|||
a_tmp := a |
|||
b1_tmp := b1 |
|||
b_tmp := b |
|||
a1 := b1_tmp |
|||
a := b_tmp |
|||
b1 := a1_tmp - (b1_tmp * q) |
|||
b := a_tmp - (b_tmp * q) |
|||
suspend q |
|||
skip_getting_a_term := YES |
|||
} |
|||
} |
|||
if /skip_getting_a_term then { |
|||
if term := get_term (other_cf, i) then { |
|||
i +:= 1 |
|||
a1_tmp := a1 |
|||
a_tmp := a |
|||
b1_tmp := b1 |
|||
b_tmp := b |
|||
a1 := a_tmp + (a1_tmp * term) |
|||
a := a1_tmp |
|||
b1 := b_tmp + (b1_tmp * term) |
|||
b := b1_tmp |
|||
} else { |
|||
a := a1 |
|||
b := b1 |
|||
} |
|||
} |
|||
} |
|||
end |
|||
procedure make_continued_fraction (gen) |
|||
return continued_fraction (NO, 0, [], gen) |
|||
end |
|||
procedure get_term (cf, i) |
|||
local j, term |
|||
if cf.m <= i then { |
|||
if \cf.terminated then { |
|||
fail |
|||
} else { |
|||
every j := cf.m to i do { |
|||
if term := @(cf.generate) then { |
|||
put (cf.memo, term) |
|||
cf.m +:= 1 |
|||
} else { |
|||
cf.terminated := YES |
|||
fail |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return cf.memo[i + 1] |
|||
end |
|||
procedure cf2string (cf, max_terms) |
|||
local s, sep, i, done, term |
|||
/max_terms := 20 |
|||
s := "[" |
|||
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. |
|||
s ||:= ",...]" |
|||
done := YES |
|||
} else if term := get_term (cf, i) then { |
|||
# Getting a term succeeded. Include the term. |
|||
s ||:= sep_str (sep) || term |
|||
sep := sep + 1 |
|||
if 2 < sep then sep := 2 |
|||
i +:= 1 |
|||
} else { |
|||
# Getting a term failed. We are done. |
|||
s ||:= "]" |
|||
done := YES |
|||
} |
|||
} |
|||
return s |
|||
end |
|||
procedure sep_str (sep) |
|||
return (if sep = 0 then "" else if sep = 1 then ";" else ",") |
|||
end |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>icon univariate-continued-fraction-task.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,2,7] |
|||
22/7 + 1/2 => [3;1,1,1,4] |
|||
(22/7)/4 => [0;1,3,1,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|J}}== |
=={{header|J}}== |