Most efficient way to obtain the decimal representation of a rational number?

General Usage Performance
1

Let’s say I want to obtain the decimal representation of p//q e.g. 1/2 is 0.5 so I would store that as ([0, 5], 2) where the 2nd value in the tuple is the position where the digits don’t repeat. And so 1//7 = 0.142857 then repeats wold be represented as ([0,1,4,2,8,5,7], 1) and 1/6 = 0.166666... is ([0, 1, 6], 2)

My algorithm is currently doing p = divrem(p, q) until p repeats then I terminate and return the digits found so far and the position where the repeating happened. Thsi works but I find it too slow. Is there already an efficient function to do this?

2

Have you tried GitHub - hyrodium/RepeatingDecimalNotations.jl: A Julia package to handle repeating decimal numbers. ?

I’m not sure if that package is focused on efficiency (rather than convenience). In what context is this operation performance-critical?

Note that storing the digits as an array of Int is not particularly efficient; using one byte per digit (or a string as in the package above) may be better.

1 Like
3

No. But I will check it out.

Project Euler. Lol

Definitely not faster than my approach.

4

Have you profiled your code (e.g. with @profview) to find out which part takes the most time? At first glance your algorithm seems reasonable to me, so maybe your inefficiencies are Julia-related and not arithmetic-related? For instance, allocating the decimal expansion instead of directly computing whatever project Euler wants from you in a loop.

1 Like
5

Can you try this function to get the repeated part of the rational

function repeated(r::Rational) 
      k = 1
      d = r
      while d.den != 1
           d = (10^k - 1)r
           k += 1
      end
d.num
end

for e.g

julia>  repeated(1//7)
142857

then you may convert results to string and split on the repeated

split(string(Float64(1//3)), string(rep(1//3)), limit=2)

2-element Vector{SubString{String}}:
 "0."
 "333333333333333"
1 Like
6

this is much much slower than my implementation btw. Actually, I just need to deal with the special case of 1//q.

7

If so you can use

(10^k - 1) % q == 1    # we got integer for this  k
8 
function repeating_form(k)
    # println(k)

    digits = Int[]
    remainders = Dict{Int, Int}(1=>1)
    remainder = 1

    i = 1 # keeps track of how many digits

    while true
        d, remainder = divrem(remainder, k)

        push!(digits, d)

        # has it started to repeat
        if (d!=0) && haskey(remainders, remainder)
            # ignore the first few digits
            # j = remainders[remainder]
            # # println((n, k))
            # n = n - (j-1)
            # digits = digits[j+1:end]

            # pos = mod(n, length(digits))

            # if pos == 0
            #     return digits, remainders[remainder]
            # else
            return digits, remainders[remainder]
            # end
        end

        remainders[remainder] = i
        i += 1

        # the below code is now no longer possible
        # if remainder == 0
        #     if n <= length(digits) - 1
        #         return digits[n+1], digits, remainders
        #     else
        #         return 0, digits, remainders
        #     end
        # end

        remainder = 10remainder
    end
end

This is my implementation btw.

The optimisations, I can think of are not using push! as much and preallocate an array that gets used by all.

9

But this code is invalid for 5 , 2 and its powers.

10

FTR, what you’re asking for is basically an algorithm to convert a number from rational number format to decimal floating-point format. Which reminds me of an open PR to Julia I need to revisit lol:

11

Ah forgot to mention I know those don’t have repeating digits. So for my solution good enough. I commented out some code that would handle those I think.

12

Here is an Algorithm to help you handle both cases, Try it and feel free to ask about how it works

function repeated(n::Int)
    q = n
    tows, fives = 0, 0
    while q % 2 == 0
        q = q ÷ 2
        tows += 1
    end
    while q % 5 == 0
        q = q ÷ 5
        fives += 1
    end
    d = max(tows, fives)
    k = 1
    if q == 1 
    	ans = reverse(digits(trunc(Int, 10^d * 1/n)))
    	return [zeros(Int, d - length(ans) + 1); ans], d + 1
    end
    while true
        if 10^k % q == 1
        	ans = reverse(digits(trunc(Int, 10^(d+k) * 1 / n)))
            return [zeros(Int, k + d - length(ans) + 1) ;ans], k + d - length(ans) + 2
        end
        k += 1
    end
end

Some tests

julia> repeated(7)                                                                              
([0, 1, 4, 2, 8, 5, 7], 2)                                                                      
                                                                                                
julia> repeated(6)                                                                              
([0, 1, 6], 2)                                                                                  
                                                                                                
julia> repeated(5)                                                                              
([0, 2], 2)                                                                                     
                                                                                                
julia> repeated(24)                                                                             
([0, 0, 4, 1, 6], 3)                                                                            
                                                                                                
julia> repeated(128)                                                                            
([0, 0, 0, 7, 8, 1, 2, 5], 8)

Benchmark

julia> @benchmark repeated(6)                                                                   
BenchmarkTools.Trial: 10000 samples with 193 evaluations.
 Range (min … max):  504.870 ns …  1.217 ms  ┊ GC (min … max):  0.00% … 99.92%
 Time  (median):     516.606 ns              ┊ GC (median):     0.00%
 Time  (mean ± σ):   680.181 ns ± 12.190 μs  ┊ GC (mean ± σ):  20.54% ±  2.58%

    █▄                                                          
  ▂███▆▃▂▂▂▂▂▂▂▂▂▂▂▂▂▄▇█▆▄▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂▂▂▂▂▂▂▂▂▂▂▂▁▂▁▁▂▂▂▂ ▃
  505 ns          Histogram: frequency by time          694 ns <

 Memory estimate: 304 bytes, allocs estimate: 4.

julia>
13

Not sure if I timed mine but they run in ns. Way faster.