2h
comment How to implement a best-first search in Haskell?
exactly. each step is simply step (x:xs) | goodEnuf x = x | otherwise = merge (prioritized (children x)) xs.
3h
comment Modified Sieve of Eratosthenes has very long runtime
@DavidK did you mean the 2/3 of 1/2 (i.e. 1/3 overall)? the sequence is 1 / 2, 1*2 / 2*3, 1*2*4 / 2*3*5, 1*2*4*6 / 2*3*5*7, 1*2*4*6*10 / 2*3*5*7*11, ...
3h
comment Modified Sieve of Eratosthenes has very long runtime
@tinstaafl vector<bool> is what's supposed to be bit-packed, but I think sizeof(bool) is 1, not 1/8. You can add a printf statement to check it on your compiler. -- The thing with space is cache locality. Bit-packed segments seem to be the accepted wisdom.
16h
comment Printing prime numbers in Java using recursion
the empirical orders of growth of your algorithm is ~ n^2.5, in n primes produced.
16h
comment Modified Sieve of Eratosthenes has very long runtime
right; but the point is the comparing of values, not links fixing - that is very cheap, exactly because it's a linked list. How to do your approach efficiently is also not an obvious task - it is easy to do in O(n^1.5) (perhaps even O(n^1.5 log n)) fashion overall (when restarting from the top for each prime's multiples), and it's harder to achieve the optimal O(n (log n)^2 log (log n)) (i.e. there's an extra log n factor there). With direct access of course we easily get O(n log n log (log n)), in n primes produced (since N ~ n log n).
17h
comment Printing prime numbers in Java using recursion
@Ben they did speak about finding first 1000 primes. and I gave you evidence that it is worse than N^2.
17h
comment Modified Sieve of Eratosthenes has very long runtime
but your - 1 seems to just be wrong (e.g. consider upperLimit==26 ... I doubt that you get the correct result with this code). and saving twice as much space is equally valid an optimization for calculating sum as well as for anything else (though yes, for primes under just 2000000 it doesn't matter).
17h
comment Printing prime numbers in Java using recursion
@Ben no it won't amortize to anything smaller because the testing is done in the wrong order. n=1000 primes means ~ N=8000 numbers to test, by an O(N^2) algorithm; don't be so sure that it will run fast just because n=1000 seems small (you did say "anyway"...) - its complexity is atrocious (see e.g. this Haskell test entry with the equivalent algorithm showing ~ N^2.2 , ~ n^2.5 run-time behaviour.
18h
comment Modified Sieve of Eratosthenes has very long runtime
you meant long long (yes, the problem was only in 1 place, I misread the code). BTW why the - 1 in upperSqrt definition? Why not + 1 or just nothing? (e.g. upperLimit==26 ... ). -- Also, you don't mark any even numbers, which is good, but they still take up the place in the array...
18h
comment Modified Sieve of Eratosthenes has very long runtime
the fixing of links is only a small part of the story: the key to the sieve's efficiency is its conflation of address and value which is destroyed if elements are actually removed - forcing us to search for, and compare, the values in O(n) time, instead of using the value as address directly, i.e. in O(1) time.
18h
revised Can someone explain me the following prime number generation method?
c/e
18h
comment Modified Sieve of Eratosthenes has very long runtime
"prime multiples" no such thing. this wording is a bit off. :)
1d
comment Modified Sieve of Eratosthenes has very long runtime
won't this code fail on 32-bit int platforms? (in 2 places)
1d
revised Early lisp implementations--source
edited tags
1d
comment Sieve of Eratosthenes - Finding Primes Python
... see also: more discussion about the "sqrt" issue and its effects, an actual Python code for a postponed trial division, and some related Scala. --- And kudos to you, if you came up with that code on your own! :)
1d
comment Sieve of Eratosthenes - Finding Primes Python
no, it's not the sieve of Eratosthenes, but rather a sieve of trial division. Even that is very suboptimal, because it's not *postponed*: any candidate number need only be tested by primes not above its square root. Implementing this along the lines of the pseudocode at the bottom of the linked above answer (the latter one) will give your code immense speedup (even before you switch to the proper sieve) and/because it'll greatly minimize the stack usage - so you mightn't need your try block after all.
2d
revised Function composition and $ - one compiles, another doesn't
added 478 characters in body
Jul
19
comment Why does Haskell allow a list of Shape, but no list of Square or Circle or Triangle
(fixed some typos (I think)) double-plus-good for different type and constructor names, for novices!
Jul
19
revised Why does Haskell allow a list of Shape, but no list of Square or Circle or Triangle
typos fixed :)
Jul
19
comment How does this Prime number generation code work?
... and the next x=x+1 is tried, and so it goes until int range wraparound makes x negative... but the algorithm is quadratic and very slow so maybe you won't reach this point.
1 2 3 4 5