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

General Usage
1

For example:
if n = One trillion

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

in python, binary expansion can help, how to do in Julia.
add more information about:

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…

2

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.

:wink:

5 Likes
3

:smiley:Thank you for your advice

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

4

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… :slight_smile:

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
5

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
6

I add some details for my question.

7

Isn’t this equal to:

Num * A.Num

like

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

?

9

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. :smile:

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).

10

Yes, sorry, missed the mod.