Julia code optimization calculating decimal period

Question

Im trying to solve problem 417 in ProjetEuler. I wrote a code to optimize and calculate the procedure but its still far from enough. I based my algorithem from the findings in this website https://mathworld.wolfram.com/DecimalExpansion.html

The only tasking part of the code is in the check function but no matter how I look at it the Time complexity shouldnt be big enough for my PC to handle. and yet it is painfuly slow. I added more process's to help and it seemed to speed up the runtime by no less than double, but its not enough.

using Distributed;
@everywhere using SharedArrays
addprocs()
function createDict(limit)
   a = Dict(2 => true);
   for i = 0:(floor(log2(limit))+1)
       for j = 0:13
           if ((2^i * 5^j) <= limit)
               get!(a,(2^i * 5^j),true)
           end
       end
   end
   return a;
end
arr = createDict(10^6)

@everywhere function check(x)
   mem = []
   for i = 1:x
       power = i-1;
       num = (BigInt(10)^power) % x
       push!(mem,num)
       for j = 1:(length(mem)-1)
           (mem[j] == num ) && return (i-j);
       end    
   end
end

@everywhere function test(limit,arr)
    a = SharedArray{Int16}(limit)
    @sync @distributed for i=3:limit
        flag = false;
        flag = get(arr,i,false)
        (flag == false) && (a[i] = check(i))
    end
    return sum(a);
end
@elapsed test(10^6,arr)

the createDict just holds all the fractions that are finite in arr up to certain limit(I overshoot it just in case, its done once) check function returns the decimal cycle length and test is my main.

It also seems that the workload of the cpu drops from 100% to almost nothing after couple of minutes and yet it runs. (and isnt stuck, i can interrupt)

Could you please clarify what is your question exactly? If it is to make your algorithm more efficient implementation wise - then the answer is that using this algorithm you will not be able to solve this problem efficiently no matter what implementation or what programming language you use. Note for example that even calculating BigInt(10)^power where power is of order of 100_000_000 takes over 1 second and you want to do this calculation millions of times. — Bogumił Kamiński
The thing is even at limit = 10^4 the runtime is about 194 [sec] in my machine so I thought that Im doing something bad with the way Im coding. Thanks for answering, I'll look into other algorithems about dealing with high powers since far as I know its essential here because numerical algorithems may be more accurate but they always got roundup errors as they approximate the result. Though there is one question that Id like to get an answer to, Why does 1//5 == 1/5 gives false and 1//2 == 1/2 is true? both are finite — Alex Zh
I changed the BigInt(10)^power to pow *= 10 in the loop so that num = po %x while initializing it at 1, The speed up was small, got 174 [sec] instead of 194 [sec] with limit = 10^4. There most be something else that is slowing it down though I cant seem to figure what — Alex Zh

Bogumił Kamiński Bogumił Kamiński · Accepted Answer · 2020-07-04T19:33:17

Keeping in mind that in my opinion the key to the solution of this problem is located elsewhere (and following the SO policy I do not want to comment on it), the way to rewrite check to improve its speed is e.g.:

function check(x)
    mem = Dict{Int,Int}()
    num = 1
    for i = 1:x
        haskey(mem, num) && return i - mem[num]
        mem[num] = i
        num = 10num % x
    end
end

Julia code optimization calculating decimal period

1 Answers