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

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?

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

No. But I will check it out.

Project Euler. Lol

Definitely not faster than my approach.

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

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

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

If so you can use

``````(10^k - 1) % q == 1    # we got integer for this  k
``````
``````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
# 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.

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

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:

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.

``````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>
``````

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