Re: [PrimeNumbers] Re: 1a. Estimate the time for the Miller-Rabin test on big prime numbers
- --- jbrennen <jb@...> wrote:
> --- Phil Carmody wrote:If it's testimonial time, then I'd like to pull up an example from
> > "Almost all programming can be seen as an exercise in caching."
> > -- Terje Mathisen
> When I first started coding prime-constellation-searching sieves
> many years ago, I found that contrary to my intuition, I got faster
> searching in many cases by keeping the sieve depth fairly shallow,
> and using a small window (so I'd run the main sieve loop a lot, but
> each time was very fast). I did a lot more primality tests, but by
> keeping the core sieve data in the processor's first-level cache,
> the sieve ran blazingly fast, more than enough to make up for the
> extra primality tests.
mid July 2006.
I noticed that my primorial sieve could do some of my tests blazingly
quickly, and others fairly slowly. I noticed, for example, that
sieving n#+/-1 from n=500000-1000000 was slower than first sieving
n=500000-750000 and then sieving n=750000-1000000 to the same depth.
This is despite the fact that the split technique necessitates the
calculation of 500000# % p twice for every p.
Testing intermediate lengths, and smaller, and larger, proved to
me that the cache was a vital factor, so I made some minor tweaks
to improve L2 usage, and instantly got a 25% boost in the cases
where I was obviously being slowed before the tweaks. And yes, the
500000-1000000 range had also become quicker to do in one swell foop.
Hence my repeated quoting of Terje's .sig.
() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed
[stolen with permission from Daniel B. Cristofani]
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around