Zeckendorf arithmetic: Difference between revisions
→{{header|Kotlin}}
Line 1,275:
1000100
1000100</pre>
=={{header|Julia}}==
{{trans|Tcl}}
<lang julia>
import Base.*, Base.+, Base.-, Base./, Base.string, Base.!=, Base.==, Base.<=, Base.<, Base.>, Base.>=, Base.divrem
const z0 = "0"
const z1 = "1"
const flipordered = (z1 < z0)
mutable struct Z s::String end
Z() = Z(z0)
Z(z::Z) = Z(z.s)
pairlen(x::Z, y::Z) = max(length(x.s), length(y.s))
tolen(x::Z, n::Int) = (s = x.s; while length(s) < n s = z0 * s end; s)
<(x::Z, y::Z) = (l = pairlen(x, y); boo = tolen(x, l) < tolen(y, l); return flipordered ? !boo : boo)
>(x::Z, y::Z) = (l = pairlen(x, y); boo = tolen(x, l) > tolen(y, l); return flipordered ? !boo : boo)
==(x::Z, y::Z) = (l = pairlen(x, y); tolen(x, l) == tolen(y, l))
<=(x::Z, y::Z) = (l = pairlen(x, y); boo = tolen(x, l) <= tolen(y, l); return flipordered ? !boo : boo)
>=(x::Z, y::Z) = (l = pairlen(x, y); boo = tolen(x, l) >= tolen(y, l); return flipordered ? !boo : boo)
!=(x::Z, y::Z) = (l = pairlen(x, y); tolen(x, l) != tolen(y, l))
function tocanonical(z::Z)
while occursin(z0 * z1 * z1, z.s)
z.s = replace(z.s, z0 * z1 * z1 => z1 * z0 * z0)
end
len = length(z.s)
if len > 1 && z.s[1:2] == z1 * z1
z.s = z1 * z0 * z0 * ((len > 2) ? z.s[3:end] : "")
end
while (len = length(z.s)) > 1 && string(z.s[1]) == z0
if len == 2
if z.s == z0 * z0
z.s = z0
elseif z.s == z0 * z1
z.s = z1
end
else
z.s = z.s[2:end]
end
end
z
end
function inc(z)
if z.s[end] == z0[1]
z.s = z.s[1:end-1] * z1[1]
elseif z.s[end] == z1[1]
if length(z.s) > 1
if z.s[end-1:end] == z0 * z1
z.s = z.s[1:end-2] * z1 * z0
end
else
z.s = z1 * z0
end
end
tocanonical(z)
end
function dec(z)
if z.s[end] == z1[1]
z.s = z.s[1:end-1] * z0
else
if (m = match(Regex(z1 * z0 * '+' * '$'), z.s)) != nothing
len = length(m.match)
if iseven(len)
z.s = z.s[1:end-len] * (z0 * z1) ^ div(len, 2)
else
z.s = z.s[1:end-len] * (z0 * z1) ^ div(len, 2) * z0
end
end
end
tocanonical(z)
z
end
function +(x::Z, y::Z)
a = Z(x.s)
b = Z(y.s)
while b.s != z0
inc(a)
dec(b)
end
a
end
function -(x::Z, y::Z)
a = Z(x.s)
b = Z(y.s)
while b.s != z0
dec(a)
dec(b)
end
a
end
function *(x::Z, y::Z)
if (x.s == z0) || (y.s == z0)
return Z(z0)
elseif x.s == z1
return Z(y.s)
elseif y.s == z1
return Z(x.s)
end
a = Z(x.s)
b = Z(z1)
while b != y
c = Z(z0)
while c != x
inc(a)
inc(c)
end
inc(b)
end
a
end
function divrem(x::Z, y::Z)
if y.s == z0
throw("Zeckendorf division by 0")
elseif (y.s == z1) || (x.s == z0)
return Z(x.s)
end
a = Z(x.s)
b = Z(y.s)
c = Z(z0)
while a > b
a = a - b
inc(c)
end
tocanonical(c), tocanonical(a)
end
function /(x::Z, y::Z)
(a, _) = divrem(x, y)
a
end
string(z::Z) = tocanonical(z).s
function zeckendorftest()
a = Z("10")
b = Z("1001")
c = Z("1000")
d = Z("10101")
println("Addition:")
x = a
println(x += a)
println(x += a)
println(x += b)
println(x += c)
println(x += d)
println("\nSubtraction:")
x = Z("1000")
println(x - Z("101"))
x = Z("10101010")
println(x - Z("1010101"))
println("\nMultiplication:")
x = Z("1001")
y = Z("101")
println(x * y)
println(Z("101010") * y)
println("\nDivision:")
x = Z("1000101")
y = Z("101")
println(x / y)
println(divrem(x, y))
end
zeckendorftest()
</lang>{{output}}<pre>
Addition:
Z("101")
Z("1001")
Z("10101")
Z("100101")
Z("1010000")
Subtraction:
Z("1")
Z("1000000")
Multiplication:
Z("1000100")
Z("101000101")
Division:
Z("1001")
(Z("1001"), Z("1"))
</pre>
=={{header|Kotlin}}==
| |||