Re: Why is this code causing StackOverflowError?
Yes, I meant all primes under 200. Also, thanks for the tips, I'll go fix the code right away. Nebojsa -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
Hi, On Jan 26, 5:38 pm, twitter.com/nfma nuno.filipe.marq...@gmail.com wrote: You can use the sieve of Eratosthenes... This actually is the sieve of Eratosthenes. If one really wants to go out of one's way, one can investigate the sieve of Atkin (or other improved variants) and the the various ways of optimising the algorithm (primitives + type hintes, loops, etc.). Sincerely Meikel -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
hmm... I'm just learning clojure at the moment but by looking at code what I see is: 1 - A collecting parameter called primes 2 - A test to verify if a number is a prime by calculating the reminder of the division with all (or some) of the primes already found 3 - if a number is a prime then its added to the primes list if the above is true then this is not the sieve of Eratosthenes... at least according to wikipedia: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes I've never tried the Sieve of Atkins, must give it a go and check if it's faster and if yes how fast. Cheers, Nuno 2010/1/27 Meikel Brandmeyer m...@kotka.de Hi, On Jan 26, 5:38 pm, twitter.com/nfma nuno.filipe.marq...@gmail.com wrote: You can use the sieve of Eratosthenes... This actually is the sieve of Eratosthenes. If one really wants to go out of one's way, one can investigate the sieve of Atkin (or other improved variants) and the the various ways of optimising the algorithm (primitives + type hintes, loops, etc.). Sincerely Meikel -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.comclojure%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
You are right. This isn't exactly sieve of Eratosthenes. My plan was to implement it, but instead, I wrote this, because it was simpler (at least for my knowledge of Clojure). But since it's too slow, I'll transform it to real sieve of Eratosthenes, to check it's performance. On Jan 27, 2:43 pm, twitter.com/nfma nuno.filipe.marq...@gmail.com wrote: hmm... I'm just learning clojure at the moment but by looking at code what I see is: 1 - A collecting parameter called primes 2 - A test to verify if a number is a prime by calculating the reminder of the division with all (or some) of the primes already found 3 - if a number is a prime then its added to the primes list if the above is true then this is not the sieve of Eratosthenes... at least according to wikipedia:http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes I've never tried the Sieve of Atkins, must give it a go and check if it's faster and if yes how fast. Cheers, Nuno 2010/1/27 Meikel Brandmeyer m...@kotka.de Hi, On Jan 26, 5:38 pm, twitter.com/nfma nuno.filipe.marq...@gmail.com wrote: You can use the sieve of Eratosthenes... This actually is the sieve of Eratosthenes. If one really wants to go out of one's way, one can investigate the sieve of Atkin (or other improved variants) and the the various ways of optimising the algorithm (primitives + type hintes, loops, etc.). Sincerely Meikel -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.comclojure%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
Hi, On Jan 27, 2:43 pm, twitter.com/nfma nuno.filipe.marq...@gmail.com wrote: hmm... I'm just learning clojure at the moment but by looking at code what I see is: 1 - A collecting parameter called primes 2 - A test to verify if a number is a prime by calculating the reminder of the division with all (or some) of the primes already found 3 - if a number is a prime then its added to the primes list if the above is true then this is not the sieve of Eratosthenes... at least according to wikipedia:http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes The above is true and still it is the sieve of Eratosthenes. Just in a different form. For the sieve you have to walk for each prime found the remaining numbers and test to verify if a number is not a prime by calculating the reminder of the division with the current prime. Then you skip to the next unmarked number, which is again prime. We do just one walk and check against the accumulated prime list as we go. This does in the end exactly the same. Sincerely Meikel -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
Meikel, while the end result is the same, the time complexity of the algorithm is definately not. The exact difference is calculated in Melissa E. O'Neill's paper, The Genuine Sieve of Eratosthenes [1], which also includes some highly performant implementations of incremental SoE-like prime number generators in Haskell. (A highly entertaining paper, by the way. :-)) The most basic thing to note is that the SoE requires no arithmetic operations other than addition... Trial division requires repeated computations of remainder, which end up being quite expensive asymptotically. I've had a go at implementing an incremental SoE-like sieve in Clojure: http://gist.github.com/287986 It uses transients and appears to be quite a lot faster than the clojure.contrib.lazy-seq/primes implementation, although regrettably nowhere near as fast as the straightforward implementation of the same thing in Python... :-( (See [2] for a super-optimised Python version.) The version which is not using transients is slower, and to a really spectacular degree at that -- I wonder if that's one case of a programme spending more time in GC than on the actual computation at hand. Sincerely, Michal [1] www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf [2] http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/2068412#2068412 -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
I was about to ask the same question on this list about this code adapted from SICP section 3.5.3 pre (defn pi-summands [n] (cons (/ 1.0 n) (lazy-seq (map - (pi-summands (+ n 2)) /pre which causes a stack overflow when I run (nth (pi-summands 1) 1) but it looks like you have answered this question. To get the 10,000th element from this list means that we have to keep map calls on the stack with all of their context. Is that correct? Is it also true that the Scheme version of this code would have the same problem? pre (define (pi-summands n) (cons-stream (/ 1.0 n) (stream-map - (pi-summands (+ n 2) /pre I would hope so. I don't want to get Scheme envy. Thanks for your help, Brenton On Jan 26, 6:17 am, Nebojsa Stricevic nebojsa.strice...@gmail.com wrote: Greetings, I'm new to Clojure and working my way through Project Euler problems for learning. I wrote function for calculating prime number below some integer value max. But it doesn't work for large numbers, causing StackOverflowError. (defn primes-below calculates all primes bellow max [max] (loop [numbers (range 2 max) primes []] (if (empty? numbers) primes (let [p (first numbers) numbers (filter #(pos? (rem % p)) numbers) primes (cons p primes)] (recur numbers primes) (primes-below 200) I guess problem is not with loop-recur, or am I wrong? Thanks in advance. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
Hi, Am 27.01.2010 um 17:57 schrieb Michał Marczyk: while the end result is the same, the time complexity of the algorithm is definately not. The exact difference is calculated in Melissa E. O'Neill's paper, The Genuine Sieve of Eratosthenes. Dang. Details matter. Sincerely Meikel -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
I've transformed algorithm to this: (defn primes-bellow calculates all primes bellow max [max] (loop [numbers (vec (range 2 max)) primes [] last-p 0] (let [p (first (drop-while zero? (drop (dec last-p) numbers)))] (if ( p (. Math sqrt max)) (concat primes (filter pos? numbers)) (let [numbers (reduce #(assoc %1 %2 0) numbers (range (- p 2) max p)) primes (conj primes p)] (recur numbers primes p)) And I think, that this is real SoE, and it can calculate sum of first 200 prime numbers in ~35 sec, on 1.4 Celeron M. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
2010/1/27 Meikel Brandmeyer m...@kotka.de: Dang. Details matter. :-) 2010/1/27 Nebojsa Stricevic nebojsa.strice...@gmail.com: I've transformed algorithm to this: [ ... elided ... ] And I think, that this is real SoE, and it can calculate sum of first 200 prime numbers in ~35 sec, on 1.4 Celeron M. I'd go as far as to say that it models a hand-performed SoE run supremely closely (including skipping over the beginning of the list when finding the next prime after crossing out the multiples of the previous one). That in itself is very nice indeed! Strangely, while it computes all primes below 200 without a problem (in ~7-8 s on my machine), it throws an IndexOutOfBounds when the upper bound given is odd (try (primes-below 21)). The simple solution would be to add 1 to odd upper bounds at the start. Also, I think you meant the sum of the primes under 200, the first 200 primes would be hard to obtain using this function. Still, a cool and very readable purely functional non-incremental sieve. :-) Sincerely, Michal -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
On Tue, Jan 26, 2010 at 9:17 AM, Nebojsa Stricevic nebojsa.strice...@gmail.com wrote: Greetings, I'm new to Clojure and working my way through Project Euler problems for learning. I wrote function for calculating prime number below some integer value max. But it doesn't work for large numbers, causing StackOverflowError. (defn primes-below calculates all primes bellow max [max] (loop [numbers (range 2 max) primes []] (if (empty? numbers) primes (let [p (first numbers) numbers (filter #(pos? (rem % p)) numbers) primes (cons p primes)] (recur numbers primes) (primes-below 200) I guess problem is not with loop-recur, or am I wrong? The problem is that 'filter' is lazy, and each time through the loop you wrap another layer of filter around numbers. So each time, (first numbers) is calling through one more layer of filter than the previous time. Eventually this gets deep enough to overflow the stack. Of course with this algorithm you *need* filter to be lazy, or you'd never get past the first iteration of the loop. I'm afraid you'll have to come up with a new algorithm. There are a few options, but I suppose you don't want too many hints yet? --Chouser http://joyofclojure.com/ -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
Aha... I understand now. Thanks a lot for help. I will try to find other solution. And yes, I'm not looking for too much help. On Jan 26, 3:33 pm, Chouser chou...@gmail.com wrote: On Tue, Jan 26, 2010 at 9:17 AM, Nebojsa Stricevic nebojsa.strice...@gmail.com wrote: Greetings, I'm new to Clojure and working my way through Project Euler problems for learning. I wrote function for calculating prime number below some integer value max. But it doesn't work for large numbers, causing StackOverflowError. (defn primes-below calculates all primes bellow max [max] (loop [numbers (range 2 max) primes []] (if (empty? numbers) primes (let [p (first numbers) numbers (filter #(pos? (rem % p)) numbers) primes (cons p primes)] (recur numbers primes) (primes-below 200) I guess problem is not with loop-recur, or am I wrong? The problem is that 'filter' is lazy, and each time through the loop you wrap another layer of filter around numbers. So each time, (first numbers) is calling through one more layer of filter than the previous time. Eventually this gets deep enough to overflow the stack. Of course with this algorithm you *need* filter to be lazy, or you'd never get past the first iteration of the loop. I'm afraid you'll have to come up with a new algorithm. There are a few options, but I suppose you don't want too many hints yet? --Chouserhttp://joyofclojure.com/ -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
There are a few options, but I suppose you don't want too many hints yet? Oops.. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
Hi, On Jan 26, 3:17 pm, Nebojsa Stricevic nebojsa.strice...@gmail.com wrote: I'm new to Clojure and working my way through Project Euler problems for learning. I wrote function for calculating prime number below some integer value max. But it doesn't work for large numbers, causing StackOverflowError. (defn primes-below calculates all primes bellow max [max] (loop [numbers (range 2 max) primes []] (if (empty? numbers) primes (let [p (first numbers) numbers (filter #(pos? (rem % p)) numbers) primes (cons p primes)] (recur numbers primes) (primes-below 200) I guess problem is not with loop-recur, or am I wrong? The problem is lazyness of the filter call. You don't really get a filtered list of numbers but some promise that you will get it, when you require it. So you are basically piling a filter on a filter on a filter When you know call first, the computations to hold the promise are started causing an overflow due to the deep nesting. One way to solve this problem is to use doall around the filter call. This will remove the laziness issue, but it will also traverse the numbers list several times. Here is a different approach to this problem, which does not have this problem. (Also note: this style of loop is a good candidate for reduce) (defn primes-below [max] (reduce (fn [primes x] (if (some #(zero? (rem x %)) primes) primes (conj primes x))) [] (range 2 max))) Hope this helps. Sincerely Meikel -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
Hi Chris, On Jan 26, 3:33 pm, Chouser chou...@gmail.com wrote: Of course with this algorithm you *need* filter to be lazy, or you'd never get past the first iteration of the loop. I'm sorry. I have to ask. Why? Sincerely Meikel -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
On Tue, Jan 26, 2010 at 9:52 AM, Meikel Brandmeyer m...@kotka.de wrote: Hi Chris, On Jan 26, 3:33 pm, Chouser chou...@gmail.com wrote: Of course with this algorithm you *need* filter to be lazy, or you'd never get past the first iteration of the loop. I'm sorry. I have to ask. Why? Hm, now that you ask, I see I didn't read the code carefully enough. I was assuming the numbers seq was infinitely long. --Chouser http://joyofclojure.com/ -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
Thanks a lot for help. I have much better understanding of laziness now! But I guess I'll need to do some more math research, because both algorithms provided here (my + removed laziness and the one from Meikel) are too slow for calculating all primes below 200. On Jan 26, 4:48 pm, Chouser chou...@gmail.com wrote: On Tue, Jan 26, 2010 at 9:52 AM, Meikel Brandmeyer m...@kotka.de wrote: Hi Chris, On Jan 26, 3:33 pm, Chouser chou...@gmail.com wrote: Of course with this algorithm you *need* filter to be lazy, or you'd never get past the first iteration of the loop. I'm sorry. I have to ask. Why? Hm, now that you ask, I see I didn't read the code carefully enough. I was assuming the numbers seq was infinitely long. --Chouserhttp://joyofclojure.com/ -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why is this code causing StackOverflowError?
You can use the sieve of Eratosthenes... 2010/1/26 Nebojsa Stricevic nebojsa.strice...@gmail.com Thanks a lot for help. I have much better understanding of laziness now! But I guess I'll need to do some more math research, because both algorithms provided here (my + removed laziness and the one from Meikel) are too slow for calculating all primes below 200. On Jan 26, 4:48 pm, Chouser chou...@gmail.com wrote: On Tue, Jan 26, 2010 at 9:52 AM, Meikel Brandmeyer m...@kotka.de wrote: Hi Chris, On Jan 26, 3:33 pm, Chouser chou...@gmail.com wrote: Of course with this algorithm you *need* filter to be lazy, or you'd never get past the first iteration of the loop. I'm sorry. I have to ask. Why? Hm, now that you ask, I see I didn't read the code carefully enough. I was assuming the numbers seq was infinitely long. --Chouserhttp://joyofclojure.com/ -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.comclojure%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
