[q-lang-users] Re: Optimizations and tweaks

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

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

[snip]
> 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.

Yes, a little, but not that much, I think.

[snip]
>> 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

Oh, *excellent* <rubs hands in glee>. Thanks for that. Refs as well? I have
much Q to be learning. :)

I've implemented memoization on `prime' and `isprime' functions - works
first time ;) 
It emphasizes the extreme contrast between composite and prime (or
few-large-factors not-quite-prime) inputs; whereas it was always close (3%
ish) previously, with both algorithms suffering longer computation-times
for larger nearly-prime input N, I'm now seeing improvements of 50% or more
in individual runs - my algorithm is almost constant/linear by comparison.
This one wins :)

Cheers,

~Tim
-- 
<http://spodzone.org.uk/>