172 lines
3.7 KiB
Text
172 lines
3.7 KiB
Text
import Base.*, Base.+, Base.-, Base./, Base.show, 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); flipordered ? tolen(x, l) > tolen(y, l) : tolen(x, l) < tolen(y, l))
|
|
>(x::Z, y::Z) = (l = pairlen(x, y); flipordered ? tolen(x, l) < tolen(y, l) : tolen(x, l) > tolen(y, l))
|
|
==(x::Z, y::Z) = (l = pairlen(x, y); tolen(x, l) == tolen(y, l))
|
|
<=(x::Z, y::Z) = (l = pairlen(x, y); flipordered ? tolen(x, l) >= tolen(y, l) : tolen(x, l) <= tolen(y, l))
|
|
>=(x::Z, y::Z) = (l = pairlen(x, y); flipordered ? tolen(x, l) <= tolen(y, l) : tolen(x, l) >= tolen(y, l))
|
|
!=(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
|
|
|
|
show(io::IO, z::Z) = show(io, parse(BigInt, 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()
|