# [FAQ]If I have big big loop, How to reduce the running time

For example:
if n = One trillion

``````for _ in 1:n
######
end
``````

in python, binary expansion can help, how to do in Julia.

``````import .Base: *, +
struct FieldElement
Num::BigInt
Prime::BigInt
function FieldElement(Num, Prime)
if Num < 0 || Prime ≤ Num
return "Num \$(Num) not in field range 0 to \$(Prime - 1)"
else
new(Num, Prime)
end
end
end

function +(A::FieldElement, B::FieldElement)
if A.Prime != B.Prime
return "Cannot add two numbers in different Fields"
else
res = mod(A.Num + B.Num, B.Prime)
return FieldElement(res, B.Prime)
end
end

function *(Num::BigInt, A::FieldElement)
sum = A
for _ in 2:Num
sum += A
end
return sum
end

using BenchmarkTools
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
@btime (BigInt(2)^BigInt(10)) * FieldElement(Gx, p)
``````

so like that even big Num, will take more time…

Ok, lets try your “#####” and a bit more:

``````julia> using BenchmarkTools
[ Info: Precompiling BenchmarkTools [6e4b80f9-dd63-53aa-95a3-0cdb28fa8baf]
julia> function trillion()
j=1
for i in 1:1_000_000_000_000_000_000
j=i
#######
end
end
trillion (generic function with 1 method)

julia> @btime trillion()
1.099 ns (0 allocations: 0 bytes)
``````

Wow, I knew, Julia is just lightning fast, no need for python anymore or binary expansion.

5 Likes

but if n =2^{32} even more, It also takes a lot of time.

So, maybe it’s my extremely overpowered rig:

``````julia> function less_than_a_trillion()
j=1
for i in 1:(2^32)
j=i
######
end
end
trillion (generic function with 1 method)

julia> @btime less_than_a_trillion()
1.099 ns (0 allocations: 0 bytes)
``````

I always wondered why it’s so warm and cosy here…

Of course, I am joking, it is just that I don’t really understand your question. For me, it seems way too general to be answered in a serious way. But if you like, you could elaborate a bit more on your question?

2 Likes

I am almost sure the compiler is smart enough to replace the loop by just `j = 2^32`, so this test is useless, a rebinding a variable is almost always a no-op. It is impossible to do a serious test unless we know actually what will be done inside the loop.

3 Likes

I add some details for my question.

Isn’t this equal to:

``````Num * A.Num
``````

like

``````function *(Num::BigInt, A::FieldElement)
return FieldElement( Num * A.Num, A.Prime )
end
``````

?

not equal,

``````function *(Num::BigInt, A::FieldElement)
return FieldElement(mod(Num * A.Num, A.Prime), A.Prime)
end
``````

I’m sorry, But I didn’t notice that FieldElement could do this.

But mostly I want to know about special multiplications (which can only be done by adding all the time, e.g., addition on elliptic curves).

Yes, sorry, missed the `mod`.