User:Thebigh/mysandbox: Difference between revisions
Content added Content deleted
(tweak) |
(more) |
||
Line 19: | Line 19: | ||
;See also: |
;See also: |
||
* Wikipedia entry: [[wp:Calkin%E2%80%93Wilf_tree|Calkin-Wilf tree] |
* Wikipedia entry: [[wp:Calkin%E2%80%93Wilf_tree|Calkin-Wilf tree]] |
||
==header|FreeBASIC== |
|||
Uses the code from [[Greatest common divisor#FreeBASIC]] as an include. |
|||
<lang freebasic>#include "gcd.bas" |
|||
type rational |
|||
num as integer |
|||
den as integer |
|||
end type |
|||
dim shared as rational ONE, TWO |
|||
ONE.num = 1 : ONE.den = 1 |
|||
TWO.num = 2 : TWO.den = 1 |
|||
function simplify( byval a as rational ) as rational |
|||
dim as uinteger g = gcd( a.num, a.den ) |
|||
a.num /= g : a.den /= g |
|||
if a.den < 0 then |
|||
a.den = -a.den |
|||
a.num = -a.num |
|||
end if |
|||
return a |
|||
end function |
|||
operator + ( a as rational, b as rational ) as rational |
|||
dim as rational ret |
|||
ret.num = a.num * b.den + b.num*a.den |
|||
ret.den = a.den * b.den |
|||
return simplify(ret) |
|||
end operator |
|||
operator - ( a as rational, b as rational ) as rational |
|||
dim as rational ret |
|||
ret.num = a.num * b.den - b.num*a.den |
|||
ret.den = a.den * b.den |
|||
return simplify(ret) |
|||
end operator |
|||
operator * ( a as rational, b as rational ) as rational |
|||
dim as rational ret |
|||
ret.num = a.num * b.num |
|||
ret.den = a.den * b.den |
|||
return simplify(ret) |
|||
end operator |
|||
operator / ( a as rational, b as rational ) as rational |
|||
dim as rational ret |
|||
ret.num = a.num * b.den |
|||
ret.den = a.den * b.num |
|||
return simplify(ret) |
|||
end operator |
|||
function floor( a as rational ) as rational |
|||
dim as rational ret |
|||
ret.den = 1 |
|||
ret.num = a.num \ a.den |
|||
return ret |
|||
end function |
|||
function cw_nextterm( q as rational ) as rational |
|||
dim as rational ret = (TWO*floor(q)) |
|||
ret = ret + ONE : ret = ret - q |
|||
return ONE / ret |
|||
end function |
|||
function frac_to_int( byval a as rational ) as uinteger |
|||
redim as uinteger cfrac(-1) |
|||
dim as integer lt = -1, ones = 1, ret = 0 |
|||
do |
|||
lt += 1 |
|||
redim preserve as uinteger cfrac(0 to lt) |
|||
cfrac(lt) = floor(a).num |
|||
a = a - floor(a) : a = ONE / a |
|||
loop until a.num = 0 or a.den = 0 |
|||
if lt mod 2 = 1 and cfrac(lt) = 1 then |
|||
lt -= 1 |
|||
cfrac(lt)+=1 |
|||
redim preserve as uinteger cfrac(0 to lt) |
|||
end if |
|||
if lt mod 2 = 1 and cfrac(lt) > 1 then |
|||
cfrac(lt) -= 1 |
|||
lt += 1 |
|||
redim preserve as uinteger cfrac(0 to lt) |
|||
cfrac(lt) = 1 |
|||
end if |
|||
for i as integer = lt to 0 step -1 |
|||
for j as integer = 1 to cfrac(i) |
|||
ret *= 2 |
|||
if ones = 1 then ret += 1 |
|||
next j |
|||
ones = 1 - ones |
|||
next i |
|||
return ret |
|||
end function |
|||
function disp_rational( a as rational ) as string |
|||
if a.den = 1 or a.num= 0 then return str(a.num) |
|||
return str(a.num)+"/"+str(a.den) |
|||
end function |
|||
dim as rational q |
|||
q.num = 0 |
|||
q.den = 1 |
|||
for i as integer = 0 to 20 |
|||
print i, disp_rational(q) |
|||
q = cw_nextterm(q) |
|||
next i |
|||
q.num = 83116 |
|||
q.den = 51639 |
|||
print "The term for "+disp_rational(q)+" is "+str(frac_to_int(q))</lang> |
|||
{{out}} |
|||
<pre> 0 0 |
|||
1 1 |
|||
2 1/2 |
|||
3 2 |
|||
4 1/3 |
|||
5 3/2 |
|||
6 2/3 |
|||
7 3 |
|||
8 1/4 |
|||
9 4/3 |
|||
10 3/5 |
|||
11 5/2 |
|||
12 2/5 |
|||
13 5/3 |
|||
14 3/4 |
|||
15 4 |
|||
16 1/5 |
|||
17 5/4 |
|||
18 4/7 |
|||
19 7/3 |
|||
20 3/8 |
|||
83116/51639 is the 123456789th term.</pre> |