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

**URL:** <https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303>\
**Category:** Performance\
**Created:** [August 17, 2024, 11:24am UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303 "2024-08-17T11:24:45Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [August 17, 2024, 11:24am UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/1 "2024-08-17T11:24:45Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [August 17, 2024, 12:23pm UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/2 "2024-08-17T12:23:51Z")

</div>

Have you tried [GitHub - hyrodium/RepeatingDecimalNotations.jl: A Julia package to handle repeating decimal numbers.](https://github.com/hyrodium/RepeatingDecimalNotations.jl) ?

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.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [August 17, 2024, 12:26pm UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/3 "2024-08-17T12:26:19Z")

</div>

> [@stevengj](#):
>
> Have you tried [GitHub - hyrodium/RepeatingDecimalNotations.jl: A Julia package to handle repeating decimal numbers.](https://github.com/hyrodium/RepeatingDecimalNotations.jl) ?

No. But I will check it out.

> [@stevengj](#):
>
> In what context is this operation performance-critical?

Project Euler. Lol

> [@stevengj](#):
>
> I’m not sure if that package is focused on efficiency (rather than convenience).

Definitely not faster than my approach.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [August 17, 2024, 1:02pm UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/4 "2024-08-17T13:02:30Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mohamed.d180](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed.d180/32/52028_2.png) [@mohamed.d180](https://discourse.julialang.org/u/mohamed.d180)\
**Post date:** [August 17, 2024, 1:34pm UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/5 "2024-08-17T13:34:10Z")

</div>

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

```julia
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
julia> repeated(1//7)
142857

```

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

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

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

```

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [August 17, 2024, 1:44pm UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/6 "2024-08-17T13:44:07Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mohamed.d180](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed.d180/32/52028_2.png) [@mohamed.d180](https://discourse.julialang.org/u/mohamed.d180)\
**Post date:** [August 17, 2024, 1:50pm UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/7 "2024-08-17T13:50:29Z")

</div>

If so you can use

```julia
(10^k - 1) % q == 1 # we got integer for this k

```

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [August 17, 2024, 1:51pm UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/8 "2024-08-17T13:51:29Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mohamed.d180](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed.d180/32/52028_2.png) [@mohamed.d180](https://discourse.julialang.org/u/mohamed.d180)\
**Post date:** [August 17, 2024, 8:09pm UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/9 "2024-08-17T20:09:06Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [August 17, 2024, 8:16pm UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/10 "2024-08-17T20:16:59Z")

</div>

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:

> <https://github.com/JuliaLang/julia/pull/49749>
>
> Constructing a floating-point number from a \`Rational\` should now be correctly r…ounded.
> 
> Implementation approach:
> 
> 1. Convert the (numerator, denominator) pair to a (sign bit, integral significand, exponent) triplet using integer arithmetic. The integer type in question must be wide enough.
> 
> 2. Convert the above triplet into an instance of the chosen FP type. There is special support for IEEE 754 floating-point and for \`BigFloat\`, otherwise a fallback using \`ldexp\` is used.
> 
> As a bonus, constructing a \`BigFloat\` from a \`Rational\` should now be thread-safe when the rounding mode and precision are provided to the constructor, because there is no access to the global precision or rounding mode settings.
> 
> Updates #45213
> 
> Updates #50940
> 
> Updates #52507
> 
> Fixes #52394
> 
> Closes #52395
> 
> Fixes #52859

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [August 17, 2024, 9:20pm UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/11 "2024-08-17T21:20:47Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mohamed.d180](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed.d180/32/52028_2.png) [@mohamed.d180](https://discourse.julialang.org/u/mohamed.d180)\
**Post date:** [August 17, 2024, 10:23pm UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/12 "2024-08-17T22:23:02Z")

</div>

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

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

```

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [August 17, 2024, 11:08pm UTC](https://discourse.julialang.org/t/most-efficient-way-to-obtain-the-decimal-representation-of-a-rational-number/118303/13 "2024-08-17T23:08:09Z")

</div>

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