Spoiler alert: this is the answer to number 7 on Project Euler.
I'm learning Lisp and I was using compileonline.com to run my code. It was running out of memory on a simple program though, so I switched to a desktop version. However, even that is running out of memory. Can somebody tell me why this is so bad?
In its current form it doesn't hang, but if I change it to:
(if (= primecount 10001)
it hangs. Even something as small as 1000 hangs.
(setq current 3)
(setq primecount 1)
(setq primes (list 2))
(setq isprime "yes")
(loop for x from current do
(list
(setq isprime "yes")
(loop
for prime in primes do
(if (= (mod current prime) 0)
(list (setq isprime nil) (return))
nil
)
)
(if isprime
(list
(setq primecount (+ primecount 1))
(setq primes (cons current primes))
(if (= primecount 100)
(return)
nil
)
)
(setq current (+ current 1))
)
)
)
(write-line (write-to-string primes))
TL;DR: the problem is not with memory, but with speed.
You were very inventive in overcoming your lack of knowledge. :) Actually, we have progn in Common Lisp, that groups several expressions to be evaluated in order:
(defun myprimes-to (n &aux ;; &aux vars may have init values
(current 3)
(primecount 1)
(isprime t) ; "yes" ;; t is better
(primes (list 2))
(loop ;for x from current do ;; for a bare loop, just `loop` is enough
(progn ;list ;; `progn` groups expressions together to be
(setq isprime t) ; "yes" ;; evaluated in order, one after another
(loop ;; (not even needed here, see comments below)
for prime in primes do
(if (= (mod current prime) 0)
(progn ;list
(setq isprime nil)
(return)) ;; exit the loop
nil)) ;; don't have to have alternative clause
(if isprime
(progn ;list
(incf primecount) ; (setq primecount (+ primecount 1)) ;; same but shorter
(setq primes (cons current primes))
(if (= primecount n) ;; abstract the n as function's argument
(return) ;; exit the loop
nil))
;; What?? increment your loop var _only_ if it's not prime?
(setq current (+ current 1)))))
;; (write-line (write-to-string primes))
primes) ;; just return them
So if current is prime, it is retried. Since it was last added into primes, it'll now deem itself as non-prime, and the iteration will proceed. The results are correct, but the logic is garbled.
More importantly, there are two major inefficiencies there, algorithm-wise: you test by all primes so far, and in reverse. But, any given number is far more likely to have a smaller divisor than a bigger one; so we should test by primes in ascending order. And, we can stop when a prime p is p*p > current – because if current == a*b and a <= b, then a*a <= b*a == current. Stopping early gives enormous speedup, it changes run time complexity from ~ n^2 to, roughly, ~ n^1.5 (in n primes produced).
Do notice this: your code is worse than ~ n^2, algorithmically. It would be ~ n^2, if it were testing by primes in ascending order. -- Why is this important? It provides partial answer to your question: your problems are not with memory, but speed. Whatever time it takes your code to finish for n=100, it will take more than 100x that to get to n=1000 (because 1000/100 == 10, and 10^2 = 100). And it will take it more than another 100x that, to get to the n=10000. So if the n=100 problem took a second of run time, n=1000 will take 100 seconds (~ 2 minutes), and n=10001 – 200 minutes (more than 3 hours).
We can always take estimates of run-time orders of growth empirically; see this WP article.
So you need to maintain primes in ascending order, and append each new prime to their end, in O(1) time. You need to achieve same results as the code line (setq primes (append primes (list current))) would achieve; but you can't use this code line because it is O(n) in time, and will drastically slow down the overall program. Same with (setq primes (reverse (cons current (reverse primes)))). And we can't maintain primes in reverse order because we must test in ascending order, and simply calling (reverse primes) for each new current is also an O(n) time operation.
The solution is to use rplacd: (rplacd (last primes) (list current)). Even this is still not right, because last is also an O(n) operation. Instead, you will have to maintain an additional variable, pointing at the primes list's last cons cell, for that, and advance it each time you add a new prime there: (setq last_cell (cdr last_cell)).
When you'll run the fixed code, you will find it finishes the 10,000 job in about 0.1 second, and runs at about ~ n^1.4 run-time orders of growth in that range.