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

[<Dr....@t-...>]

Tim Haynes wrote:
> 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). 

The trouble with theory is that it's theoretically true but practically 
useless. :) I stand corrected...

> It can of course be considerably quicker: just by amending 
> 
>     primes N = [2] if  N=2;         
>              = [2,3] if N=3;               //cheating!

I don't consider that cheating, IIRC the Milner Rabin algorithm itself 
(at least the GMP version) also uses a (fairly large) table of known 
primes. I'd even go farther:

primes N	= [2] if N=2;
		= [2,3] if N=3;
		= [2,3|filter isprime [5,7..N]] otherwise;

Does that speed up your algorithm even further? I haven't tried.

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

Ok, ok, I'm convinced. An update of the isprime section is on the TODO 
list. ;-)

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

Maybe the GMP function does some memoization internally? The Q 
interpreter doesn't do it, that I know for sure.

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

At your request :)

http://q-lang.sourceforge.net/qdoc/qdoc_12.html#SEC118

Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikwissenschaft.uni-mainz.de/~ag