Or Varp's:
local luaPrecision
function toBinary(dec)
local sig,exp = math.frexp(dec)
local initexp = exp
local t = {}
exp = -1
while(sig > 0)do
for i = exp,-2 do
t[#t+1] = 0
--print(0)
end
t[#t+1] = 1
--print(1)
sig,exp = math.frexp(sig-0.5)
end
return initexp,t
end
function testRepetition(table,len)
local last = #table-len-2 --Ignore last digit
for i = last-len,0,-len do
for j = len-1,0,-1 do
if(i+j < 0)then return 1 end
if(table[last+j] ~= table[i+j])then return i+j+1 end
end
end
return 1
end
function toNumber(bin,start,last)
local n = 0
for i = start or 1,last or #bin do
n = n*2 + bin[i]
end
return n
end
luaPrecision = #select(2,toBinary(1/3))
function toFraction(dec)
local exp,bin = toBinary(dec)
if(#bin < luaPrecision/2)then --The decimal terminates quickly.
local minExp = exp - #bin - 1
if(minExp < 0)then
return toNumber(bin),math.ldexp(.5,-minExp)
else
return toNumber(bin)*math.ldexp(.5,minExp+2),1
end
end
local bestVal = math.huge
local repNum
local repStart
local potential = 3
local reps = 2
while(potential < bestVal and reps < #bin/2)do
local pos = testRepetition(bin,reps)
if(pos < #bin-reps-reps-2)then
local val = potential * math.ldexp(.5,pos)
if(val < bestVal)then
bestVal = val
repNum = reps
repStart = pos
end
end
reps = reps + 1
potential = potential * 2 + 1
end
if(bestVal == math.huge)then --No repetition found. Just write as binary.
local minExp = exp - #bin - 1
if(minExp < 0)then
return toNumber(bin),math.ldexp(.5,-minExp)
else
return toNumber(bin)*math.ldexp(.5,minExp+2),1
end
end
local num = toNumber(bin,repStart,repStart+repNum-1)
local den = math.ldexp(.5,repNum+1)-1
local rawden = den
local repExp = exp - repStart + 2
if(repExp > 0)then
num = num * math.ldexp(.5,repExp)
else
den = den * math.ldexp(.5,2-repExp)
end
if(repStart > 1)then
local binpart = toNumber(bin,1,repStart-1)
num = num + binpart * rawden
end
local gcf = den --Euclidean algorithm follows.
local tempb = num
while(tempb ~= 0)do
local t = tempb
tempb = gcf % t
gcf = t
end
return num/gcf,den/gcf
end
print(toFraction(7/9))
strike witches sanya |