Slug #1228
Updated by John Abbott almost 6 years ago
It seems that assigning to an array element is surprisingly slow.
Look at the timings in the following session:
<pre>
>>> t0 := CpuTime();
>>> c := 0; for J := 1 to N/2 do if gcd(J,N) = 1 then incr(ref c); endif endfor;
>>> TimeFrom(t0);
8.734
>>> t0 := CpuTime();
>>> d := 0; for J := 1 to N/2 do if gcd(J,N) = 1 then d := d+mod(J^2,N); endif endfor;
>>> TimeFrom(t0);
7.442
>>> sieve := NewList(N);
>>> t0 := CpuTime();
>>> for J := 1 to N/(17*38) do if gcd(J,N) = 1 then sieve[mod(J^2,N)]:=1; endif endfor;
>>> TimeFrom(t0);
42.705
</pre>
There are 3 loops. Why is the first loop SLOWER than the second one??
Why is the third loop FAR SLOWER than either the first or second ones?
(note that the third loop does only about 0.3% 0.003% of the iterations of the other loops)
Look at the timings in the following session:
<pre>
>>> t0 := CpuTime();
>>> c := 0; for J := 1 to N/2 do if gcd(J,N) = 1 then incr(ref c); endif endfor;
>>> TimeFrom(t0);
8.734
>>> t0 := CpuTime();
>>> d := 0; for J := 1 to N/2 do if gcd(J,N) = 1 then d := d+mod(J^2,N); endif endfor;
>>> TimeFrom(t0);
7.442
>>> sieve := NewList(N);
>>> t0 := CpuTime();
>>> for J := 1 to N/(17*38) do if gcd(J,N) = 1 then sieve[mod(J^2,N)]:=1; endif endfor;
>>> TimeFrom(t0);
42.705
</pre>
There are 3 loops. Why is the first loop SLOWER than the second one??
Why is the third loop FAR SLOWER than either the first or second ones?
(note that the third loop does only about 0.3% 0.003% of the iterations of the other loops)