Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic

Re^2: ulam's spiral too slow

by smahesh (Pilgrim)
on Apr 16, 2007 at 07:03 UTC ( #610275=note: print w/replies, xml ) Need Help??

in reply to Re: ulam's spiral too slow
in thread ulam's spiral too slow

Can you (or any fellow monk) please clarify the need for caching the prime numbers in this particular scenario?

The is_prime() check for the current $num does not depend on previous values (1..$num-1). I can understand the benefits of caching in other cases like fibonacci series where F(n) = F(n-1) + F(n-2). The OP is interating through N (e.g. 5000) points ($iter = 1..N) and checking is_prime($iter) on each value. The $iter values are unique and is_prime() is called once for each unique value. The data is plotted immediately and the is_prime'ness is not used further in the code.

While it is beneficial to cache the computed primes, in this particular scenario (OP's post), it is not providing any advantages. On the contrary, it ends up increasing memory usage of the application


Replies are listed 'Best First'.
Re^3: ulam's spiral too slow
by bart (Canon) on Apr 16, 2007 at 10:47 UTC
    Can you (or any fellow monk) please clarify the need for caching the prime numbers in this particular scenario?
    I know why I would cache it.

    You are familiar with the optimization for check primality by only testing with odd numbers, which has been pointed out several times already in this thread. You can optimize even more by only testing division with prime numbers. It's actually the same kind of optimization: apart from 2, all even numbers are not prime (hence, needn't be tested) because they're all divisible by 2.

    This extra optimization can reduce the number of tests you need to do significantly, especially for large numbers. You are already calculating all lower prime numbers in sequence, anyway. So you've already done the footwork. All you still have to do is store the found values. And change the code so it makes use of that.

    And liverpole's code doesn't make use of that. Tsk.

    I currently don't have the time to build a full-fledged memoized version of is_prime (but I might come back to it later). Maybe somebody else may feel the inclination...? It's not easy, you need to keep track of upto what level you have already calculated all primes, and fall back to liverpole's code if you're above that level, possibly raising the level if the step is small enough, i.e. you just checked the next odd number.

    And, uh, I suspect liverpole found himself in the same situation, and that he gave up on it, too. In that scenarion, the cache of the primes may just be a leftover.

      Excellent. Based on your clarification, one can indeed use the divisibility check on previous computed primes to determine if current $number is prime.

      You can learn non-Perl stuff on perlmonks too!! :-)

      Thanks, Mahesh

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://610275]
[shmem]: it is just written in another language
[choroba]: that's why we have agile - we don't have any spec
[shmem]: I'm a bit scared by agile (agile imposition) - but then it is crucial how it is lived to crucified or not
[shmem]: s/to cru/to be cru/
[moritz]: agile itself is pretty straight forward: faster feedback loops, working in smaller increments, regularly reflect and try to improve your process
[moritz]: it's just some implementations of agile that are scary

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (8)
As of 2017-04-27 14:45 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (508 votes). Check out past polls.