Random functions/classes #2: Decimal to fraction converter

Code Sharing
1

This function will take a decimal and return the equivalent fraction in simplest form

function convertToFrac(dec)
    local denom = 1
    local numer = dec
    local simplified = false
    repeat
        numer = numer * 10
        denom = denom * 10
    until numer>=1 and numer%1==0
    
    repeat
        for i=2,10 do
            if numer%i==0 and denom%i==0 then
                numer = numer/i
                denom = denom/i
            else
                simplified=true
            end
        end
    until simplified
    
    return tostring(numer).."/"..tostring(denom)
end
2

@Doge Nice code. I forgot about the repeat until loop. Thanks for the reminder.

3

Your second loop stops too early. For .25 it prints 5/20 which is correct but not in simplest form.

You should also guard against invalid input. If you put in a negative number then you get an infinite loop. Same with 0.

I think that the following fixes those issues (though I only tested with a few values).

function convertToFrac(dec)
    local denom = 1
    local numer = dec
    local simplified = false
    repeat
        numer = numer * 10
        denom = denom * 10
    until math.floor(numer) == numer

    repeat
	stop = true 
        for i=2,10 do
            if numer%i==0 and denom%i==0 then
                numer = numer/i
                denom = denom/i
		stop = false
            end
        end
    until stop

    return tostring(numer).."/"..tostring(denom)
end

print(convertToFrac(0))
print(convertToFrac(.25))
print(convertToFrac(-.25))
4

Thanks, I didn’t even think to test it against negative numbers and zero

Also, I’m not quite sure why your code works instead of mine. Was it the placement of the variable that terminates the loop (stop)?
@LoopSpace

5

@Doge @LoopSpace Try the value .234 . It should give a fraction of 117/500 .

6

That’s strange, it returns 5.85e+15/2.5e+16

7

0.034 returns the correct answer

8

@Dode Some numbers aren’t going to work because they can’t be represented exactly in binary. When you start doing calculations on them, there’s going to be rounding errors.

9

Here’s a version.


function setup()
    print(decimalToFrac(-.125))
end

function decimalToFrac(v)
    local p=0
    for z=1,string.len(v) do
        p=p+1
        if string.sub(v,z,z)=="." then
           p=0
        end
    end
    local num=v*10^p local de=10^p local g1=math.abs(num) local g2=math.abs(de)
    while g1~=g2 do
        local g3=math.abs(g1-g2)
        local g4=math.min(g1,g2)
        g1=g3 g2=g4
    end
    return (num/g1.."/"..de/g1)
end
10

Another version.


function setup()
    print(decimalToFrac(.125))
end

function decimalToFrac(v)
    value,p=string.gsub(v,"^(-?%d+)(%.%d+)","%2")
    if p==1 then
        p=string.len(value)-1
    end
    local num=v*10^p local de=10^p local g1=math.abs(num) local g2=math.abs(de)
    while g1~=g2 do
        local g3=math.abs(g1-g2)
        local g4=math.min(g1,g2)
        g1=g3 g2=g4
    end
    return (num/g1.."/"..de/g1)
end
11

Nice work @dave1707. Only thing, it doesn’t support repeating decimals or 0.

For repeating decimals the numerator is the repeating digit, and the denumerator is 9, then simply by GCF as usual. (So for .333, 3/9. .444, 4/9. etc.)

0 is an easy thing, just add a check at the top of the function.

12

I found this approach on StackOverflow that gives the right answer for all the examples mentioned above. Note the first line sets a rounding error, to deal with recurring decimals. For the interest of @LoopSpace, this algorithm apparently “walks the Stern-Brocot tree”. I’ll take their word for it…

function decimalToFrac(x)
    local error=0.000001
    local n=math.floor(x)
    x=x-n  --reduce to fractional part
    if x<error then return n,1 elseif 1-error<x then return n+1,1 end
    --lower fraction is 0/1
    local lower_n,lower_d=0,1
    --upper fraction is 1/1
    local upper_n,upper_d=1,1
    while true do
        --middle fraction is (lower_n+upper_n)/(lower_d+upper_d)
        local middle_n=lower_n+upper_n
        local middle_d=lower_d+upper_d
        --if x+error <middle
        if middle_d*(x+error)<middle_n then --middle is our new upper
            upper_n,upper_d=middle_n,middle_d
        --elseif middle-x<error
        elseif middle_n<(x-error)*middle_d then
            --middle is our new lower
            lower_n,lower_d=middle_n,middle_d
        --else middle is our best fraction
        else return n*middle_d+middle_n,middle_d
        end
    end
end
13

@JakAttak Here’s an updated version that handles 0 and repeating decimals. To indicate that the fractional portion is repeating, set the second parameter to 1.@Ignatz I tried .3333 with your code above and got a wrong answer.


function setup()
    print(decimalToFrac(.36,0))  -- non repeating decimal .36
    print(decimalToFrac(.75,0))  -- non repeating decimal .75
    print(decimalToFrac(.36,1))  -- repeating decimal .36363636
    print(decimalToFrac(.75,1))  -- repeating decimal .75757575
    print(decimalToFrac(1.36,1))  -- repeating decimal 1.36363636
    print(decimalToFrac(2.75,1))  -- repeating decimal 2.75757575
end

function decimalToFrac(v,rep)
    if v==0 then
        return("0/1")
    end
    i=0
    if rep==1 and v>1 then
        i=math.floor(v)
        v=v-i
    end
    value,p=string.gsub(v,"^(-?%d+)(%.%d+)","%2")
    if p==1 then
        p=string.len(value)-1
    end
    local num=v*10^p local de=10^p 
    if rep==1 then 
        de=de-1
    end
    local g1=math.abs(num) local g2=math.abs(de)
    while math.abs(g1-g2)>.00000001 do
        local g3=math.abs(g1-g2)
        local g4=math.min(g1,g2)
        g1=g3 g2=g4
    end
    return(num/g1+i*de/g1.."/"..de/g1)
end
14

In hindsight, I probably should have tested it a bit more, it was just a random idea I had and I threw together in about 15 minutes.

Sinks back into hole

15

@Doge Sometimes a random idea can turn into something bigger. I probably wouldn’t have thought of coding that, but it gave me something to try because I always like to find other ways of coding the same routine.