Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Re: 1a. Estimate the time for the Miller-Rabin test on big prime numbers

Expand Messages
  • Phil Carmody
    ... If it s testimonial time, then I d like to pull up an example from mid July 2006. I noticed that my primorial sieve could do some of my tests blazingly
    Message 1 of 5 , Jul 17, 2006
    • 0 Attachment
      --- jbrennen <jb@...> wrote:
      > --- Phil Carmody wrote:
      > > "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.

      If it's testimonial time, then I'd like to pull up an example from
      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.

      Phil

      () 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
      http://mail.yahoo.com
    Your message has been successfully submitted and would be delivered to recipients shortly.