Optimizations and tweaks (was Re: [q-lang-users] Problem using function "isprime")

[Tim H. <q...@st...>]

Dr....@t-... (Albert Graef) writes:

[snip]
>> Not quite as pretty to look at, but I think it may run faster as it only
>> uses the primes between 2..intsqrt N rather than all odds, if I read your
>> algorithm right...
>
> Hi, Tim! From the algorithm I posted:
>
>  >                    =3D try_div 3 (intsqrt N) N otherwise;
>                                    ^^^^^^^
>
> See? :)

Yes... I had that too...

> While your algorithm looks quite neat, I doubt that it will be any
> faster, since it uses a list, while the one from the docs is just plain
> tail-recursive number crunching (which has the added benefit that it only
> needs O(1) space). I'm also a bit worried about the recursive isprime
> call, which might slow down things quite a bit if enough members of the
> [2..N] list fail the Miller-Rabin test.

Very interesting concerns, but I've just been very rude and benchmarked the
two... :)
For smallish N<1E4, it's evenly matched (3% more occasions on which mine is
faster than yours).=20
However, for N approaching 1E9 or so, the number of occasions on which my
algorithm is faster pulls away - around 2.1E9 I've been seeing about 3x as
many occasions on which mine's been faster compared to yours.

It seems to be taking 2-3% less time, when it's better.

The recursive isprime call is actually a win; effectively it's calling
intsqrt(intsqrt(intsqrt(intsqrt.....))) a few times (per prime in range,
not per-odd-number in range) which tends towards 1 quicker than your
concern about implementation slows it down.
Bear in mind that only 1/12 numbers in the range [1..1E6] is a prime, too...

It can of course be considerably quicker: just by amending=20

    primes N =3D [2] if  N=3D2;=20=20=20=20=20=20=20=20=20
             =3D [2,3] if N=3D3;               //cheating!
             =3D filter isprime [2..N] otherwise;

it's faster than yours on 10x as many ocassasion than where yours was
faster than mine, around N<=3D2E9, so it's hitting the bottom few cases of
the recursion quite a *lot*.

                                   ~~~~

What I'd like to know is whether there's any memoization going on - by the
time I've evaluated `isprime 13' once for intsqrt(N), I don't need to do it
all over again for intsqrt(intsqrt(N)), etc.

Actually, how would I write a memoize function in Q, anyway? I don't see
that, or the word `cache', in the docs anywhere :)

~Tim
=2D-=20
<http://spodzone.org.uk/>