Anonymous user
Talk:Sieve of Eratosthenes: Difference between revisions
→Problem found in first Erlang example.
| (28 intermediate revisions by 7 users not shown) | |||
Line 1:
==Needs tidying up of examples that don't fit the task description==
I just looked at Racket and Python, but it seems that these languages have examples that ignore the task description in one or more of their optimisations. It could be present in other languages examples.
I would suggest the nonconforming examples be moved to this talk page or discarded as each language needs at least one clear implementation of the full task description. <br> Several non-conforming examples is excessive I think. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 05:30, 18 November 2014 (UTC)
==Optimizations==
My Forth is very rusty, but it looks like your Forth version of the [[Sieve_of_Eratosthenes]] lacks both important features of the sieve: The outer loop should stop at the sqrt of the total limit, and the inner loop should start with the square of the just detected prime (any other multiples must already have been crossed out). Without those, the sieve won't be faster than to trial division for each number. Some other implementations seem to have the same problem. (And some only sieve odd numbers, while others don't, making overall comparison between languages more difficult). Maybe all this should also be clarified in the task description? [[User:Dirkt|Dirkt]] 02:48, 2 December 2007 (MST)
Line 217 ⟶ 223:
::::::::: Well, the postponement trick is nice, but I don't see how it can apply to the SoE code. As a quick experiment, I implemented it for the plain (non-E) sieve, and indeed it made it much faster. I then implemented the Bird SoE algorithm and it's faster than the version I had before -- but the plain sieve + postponement trick is about twice faster than my Bird implementation. (I'll put both of the new things on the two pages, if you care to look at them.)
::::::::: Also, looking at your SO answer, I don't see the conceptual difference between what you refer to as the Bird algorithm and the one at the end of the answer: the two minor differences that I see are (a) it works only on non-even numbers; (b) you use the union' thing to always spit out the first element which is done in Bird's code by pulling out the first p*p out of the union code (in fact, I first didn't do this pulling-out, and resolved the resulting infinite loop by making my merge do the same thing that your union' does). --[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 19:32, 13 September 2014 (UTC)
:::::::::: Elibarzilay: (sorry, missed your remark before): the big conceptual difference is that it's using the [http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#Linear_vs._tree-like_folds tree-like folding] function [http://en.wikipedia.org/wiki/Fold_(higher-order_function)#Tree-like_folds ''foldi''] instead of the linear folding of ''foldr'', for the logarithmic complexity advantage. M.O'Neill derives Bird sieve's complexity at above n^1.5 (in ''n'' primes produced) but the tree folding code runs empirically at the same orders of growth (~ n^1.2..1.25) as her PQ-based code, which is probably ''n (log n)^2 log(log n)''. Earliest such code that I know of is [https://www.haskell.org/pipermail/haskell-cafe/2007-July/029077.html Jul 16 2007 post by Dave Bayer]. -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 21:46, 10 November 2014 (UTC)
::::::: I'm having second thoughts about the new page now (bear with me). See, the Greek "koskinon" is a noun; it is "sieve" in English, but "sieve" in English is also a verb, a synonym of "filter". I think, ''that'' was the cause of much confusion about this issue. With the Trial Division, it is very easy and natural to use it to produce sequences of primes, unbound as well as bound, by means of filtering. And Turner's code is only "sieve" in as much as it is "filter", it doesn't build "a sieve". And how will we distinguish between the TD "sieve" and TD "filter"? The first does it in separate steps, filtering separately by each prime, and the other does that by testing against a list of primes, by a short-circuiting logic? That's not a ''basic'' distinction, [[Primality by trial division#Segmented Generate and Test|that's an optimization]]! What will we do, allow the former but forbid the latter, on the new page??
Line 227 ⟶ 235:
:: I don't consider myself active enough to remove the draft thing too... but of course I think that it's the right thing. --[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 19:32, 13 September 2014 (UTC)
::: WillNess: Sorry, but continuing down here... What I did now is: (1) Removed the sequence versions from the PbTD page since they're on the new page; (2) I first edited your version on the SoE page, but then realized that my attempt at doing the same to the Bird code is shorter and faster, so I dropped both in *instead* of your code -- I don't like removing other people's code, but I decided on doing that because it's better on speed, clarity, and being more idiomatic (feel free to tweak it however you like, specifically, the timings might be off); (3) On the new page, I've added a version that is optimized with the postponement trick.
::: FWIW, I'm getting results that still don't go in-line with the conclusion that a proper SoE should be faster: the "unfaithful" plain sieve with the postponement trick <1> is about twice faster than my Bird implementation with the same trick <3>, and that is a tiny bit faster than my Bird implementation without the trick <2>, while your version of the proper SoE with the trick is about three times slower than <1>. Based on the paper and what you said, I'd expect <1> and and <2> to be roughly the same, and <3>/<4> to be much faster. --[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 20:16, 13 September 2014 (UTC)
::::Elibarzilay: good to have a discussion with you. :) About Bird (your <2>) (and it's Richard Bird, not William Byrd): O'Neill actually derives the complexity for it too, and proves it's slightly worse than the optimal TD (your <1>). The trick to making it yet faster (which isn't in the paper) is to fold the composites ''in a tree'', substituting [https://en.wikipedia.org/wiki/Fold_(higher-order_function)#Tree-like_folds "foldi" for "foldr"]. I have a Scheme entry with SICP styled streams, that does that (and of course [[Sieve_of_Eratosthenes#List-based_tree-merging_incremental_sieve|the Haskell entry]] itself). The original version at [http://www.haskell.org/haskellwiki/Prime_numbers_miscellaneous#Implicit_Heap haskellwiki].
::::And of course what we should be comparing are [http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth empirical orders of growth], not constant factors. So if one is constantly slower than the other by the same factor ''at several size points'', it's fine. TD with postponement (i.e. the optimal TD, your <1>) runs pretty well for lower ranges (10k-20k primes) in Haskell too. It's because its complexity is O(n^1.5/(log n)^0.5) and at low ranges ''log'' is approximated by higher power law coefficient, i.e. its influence can be sizeable (I've commonly seen n^1.3 for low ranges of OTD, going steadily to n^1.45..49 for higher ranges, as it should).
::::About your edits: there's no need to add postponement to Bird's code; it achieves the same effect on its own, because it folds to the right. Postponement achieves the same effect laboriously, and should still be worse computationally [http://www.haskell.org/haskellwiki/Prime_numbers#Linear_merging because it folds from the left]. My version should probably be restored (or maybe you have a tweak on it) because it is a stepping stone from the simple lazy version ''to'' the Bird's version. (It's strange that your "postponed Bird" is slightly faster than the straight version of it.) -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 09:17, 14 September 2014 (UTC)
::::Elibarzilay: so I've switched back my postponed version for your postponed Bird's, and placed it ''before'' Bird's. You're welcome to tweak it with your ''when-bigger'', or I'll do it when I have more time (will have to check if it's faster or not). It's more-or-less equivalent to Haskell's <code>span</code>-using versions; but with Haskell's GHC, manually inlining the ''span'' as I did here, was more efficient. -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 10:09, 14 September 2014 (UTC)
::::: WillNess: I've fixed some of the indentation problems, and also removed the <code>#lang lazy</code> from partial sources (they're misleading, since the <code>#lang</code> should be used at the top of a module and determines its language, it's not just a typographical annotation of the text...). As for the speed, factors are obviously not interesting in theory, and high factors are interesting in practice only. But I didn't measure them or tried to analyze the runtime, I just tried a few semi-long runs since I'm too lazy to invest more time in this... You're welcome to do more detailed analysis of course (and to mention it: something that I didn't do since I didn't put in the effort...). Oh, and btw, my <code>when-bigger</code> trick is to avoid calling another function that will call itself recursively to collect two values, since this kind of thing would be disastrously slow in Lazy Racket (I should know, I implemented it...). My solution was a haskell-span-like function that takes a callback for the tail, which is enough here, and should generally be fast enough and clear. --[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 05:45, 15 September 2014 (UTC)
::::::yes, I know (both about the implementation :) and the meaning of the function). I even wanted to rename it <code>span</code>. -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 10:59, 15 September 2014 (UTC)
== Recent edits to Haskell and my reversal of them ==
why I made [http://rosettacode.org/mw/index.php?title=Sieve_of_Eratosthenes&diff=201761&oldid=201693 this edit]:
Much careful thought went into gradually presenting the codes. No function was missing, it was defined in a sub-section above its use. No need to define same "minus" function over and over. In Haskell, short variable names are idiomatic; long ones with tortured pronunciation aren't. "gaps" is perfectly idiomatic and is clear upon examining the code. Your redefinition of "minus" is not an improvement, as it uses two calls "<" and ">" instead of one "compare". You confused between "left" and "right" leaning structure, and it is anyway explained in the following subsection. Similarly, "gap" appears in the following subsection, as an improvement, no need to improve the previous function as it only serves as an illustration anyway. The spacing in the simple unbounded version is carefully chosen to follow closely the spacing of the original Miranda code by D. Turner. etc. etc. etc.
I kept several of the remarks you've added. Thanks. -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 14:06, 10 April 2015 (UTC)
: also, "naive" version is ''not'' based on Euler's definition. The primes in "primesEQ" are not separate, but the same - this is by design; for the reader to see the difference when separate supply is used later, in the more efficient versions. Maybe we ought to add types as you did in all the versions, not as it is now in the most efficient tree-merging version only. Will think it over... -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 14:16, 10 April 2015 (UTC)
: also, writing "primesEulerQ ()" (with the ()) is not guaranteed to prevent memoization. A compiler could "optimize" even this code, recognizing it as "common subexpression", causing it to be memoized. Only "_Y" guarantees this (well, so far, as I could see, for various versions of GHC). [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 14:29, 10 April 2015 (UTC)
:: I recognized this as your code, Will, and the main reason I made changes was so that a noobie reader could just copy and paste the code segment into a '.hs' file or REPL and try it out without without needing to patch in a "where" or definition of a function from a previous entry in the progression of codes or look up an import; for instance, I don't think one can use "compare" without importing "Data.Ord" (or at least on my version - Windows/HP 2014.2.0), which is why I changed the codes to not use "compare". Yes, I know this appears from the outside as two operations rather than one, but there are at least two operations inside "compare" and we aren't trying for the ultimate in efficiency here anyway. Anyway, just showing the "import Data.Ord" would work. It seems to me that RosettaCode is most often used by people new to a language to get a flavour of how it is used, and who may want to just paste in a code segment to try it and learn about it. If you see that this could be valuable to them, then make those changes yourself. And no problem with your reverting of my changes, I was just trying to help beginning Haskell programmers as I was in the not-too-distant past. --[[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 01:54, 11 April 2015 (UTC)
::: I just tried to make a clear presentation (you know, one feels invested and all that stuff...). Yes, that's a valuable point about the ability to run the code as-is. But OTOH to copy-paste some code from a near-by section shouldn't be much of a bother, hopefully. "compare" works inside GHCi right away, BTW, w/ 2014.2.0.0. on Win7. [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 14:44, 11 April 2015 (UTC)
::: but I kept most of your remarks and incorporated your clarifications (about Y etc.) so hopefully overall the quality had improved, thanks to your intervention. :) [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 14:50, 11 April 2015 (UTC)
:::: Strange, I just tried compare again without the "import Data.Ord" and it works, but I distinctly remember getting compiler errors saying "perhaps you meant 'compare' from Data.Ord" - never mind that point, my eyes are getting bad and perhaps I mistyped it and couldn't see the difference...
:::: I do think that you should add type signatures to all of the top level functions for two reasons: 1) its recommended Haskell style, and 2) if there are no signatures, integer numerics default to "Integer" which can be considerably slower than "Int".
:::: I see your point on using the combinator to avoid holding the lists in memory '''for the actual sequence of calculations''', however making each a function as in "primes :: () -> [Int]" rather than "primes :: [Int]" does two things: 1) for noobie people testing timing and such, it means that on every call to the '''function''' the whole calculation sequence starts from the beginning rather than using that portion of the memoized stream already computed, and 2) having the outer binding means that the result stream can not be garbage collected as the stream is consumed by say "head $ drop 1000000 primes" where I am suggesting "head $ drop 1000000 $ primes ()" will not hold onto the results stream and will have a very low memory residency; one does have to be careful when making recursive references (not using "fix" or combinators) as a reference to a function does generate a whole new stream - when that is not desired, internal simple bindings must be used to avoid the generation of new streams when they are not desired. --[[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 00:10, 12 April 2015 (UTC)
::::: but those versions are inefficient anyway. Plus, the proper way to test is to run a compiled, standalone executable, where even <code>primes :: [Int]</code> is garbage collected and runs in near constant memory; while if playing at GHCi prompt, depending on a version, I've seen even <code>primes :: () -> [Int]</code> memoized. But here I thought the aim is to showcase a language not even to (practicing) newbies (there are plenty more other resources for those), but to people even totally unfamiliar with it, just to glance over (but the snippets are still runnable of course). So for me, clarity was the utmost goal. [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 12:06, 12 April 2015 (UTC)
==Problem found in first Erlang example.==
A note. This code bugs out on
<pre>
3> erato:primes_upto(100).
** exception error: no true branch found when evaluating an if expression
in function lists:seq/3 (lists.erl, line 249)
in call from erato:find_prime/3 (erato.erl, line 18)
in call from lists:foldl/3 (lists.erl, line 1248)
in call from erato:primes_upto/1 (erato.erl, line 10)
</pre>
Problem found by user Poetaster . I just moved the report here. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 06:53, 19 September 2015 (UTC)
corrected version:
<lang Erlang>
-module( sieve_of_eratoshenes ).
-export( [primes_upto/1] ).
primes_upto( N ) ->
Ns = lists:seq( 2, N ),
Dict = dict:from_list( [{X, potential_prime} || X <- Ns] ),
{Upto_sqrt_ns, _T} = lists:split( erlang:round(math:sqrt(N)), Ns ),
{N, Prime_dict} = lists:foldl( fun find_prime/2, {N, Dict}, Upto_sqrt_ns ),
lists:sort( dict:fetch_keys(Prime_dict) ).
find_prime( N, {Max, Dict} ) -> find_prime( dict:find(N, Dict), N, {Max, Dict} ).
find_prime( error, _N, Acc ) -> Acc;
find_prime( {ok, _Value}, N, {Max, Dict} ) when Max > N*N ->
{Max, lists:foldl( fun dict:erase/2, Dict, lists:seq(N*N, Max, N))};
find_prime( {ok, _Value}, _, R) -> R.
</lang>
== R code error ==
In the R code, the inner loop does not start at the square of the prime just found. The code tries to change the index of the loop using last.prime.
for(i in last.prime:floor(sqrt(n)))
{
primes[seq.int(2L*last.prime, n, last.prime)] <- FALSE
last.prime <- last.prime + min(which(primes[(last.prime+1):n]))
}
which(primes)
}
However from R in the help function - The ‘seq’ in a ‘for’ loop is evaluated at the start of the loop;changing it subsequently does not affect the loop. If ‘seq’ has
length zero the body of the loop is skipped. Otherwise the variable ‘var’ is assigned in turn the value of each element of‘seq’. You can assign to ‘var’ within the body of the loop, but this will not affect the next iteration. When the loop terminates,
‘var’ remains as a variable containing its latest value.
If you wish to change the loop you can use a while or repeat if written below.
sieveOfEratosthenes<-function(n){
list<-2:n #list of numbers 2:n
A<-rep(TRUE,(n)) # Vector of true - if true at end prime
i<-2 #index at 2 first
repeat{
if(A[i]==TRUE)
{
A[seq(i**2,n,i)]=FALSE
}
if(i>sqrt(n))
{
break
}else{
i<-i+1
}
}
return(list[A[-1]]) #remove 1
}
:Corrected. Some oddities in your own program: once you have computed i^2, no need to compute sqrt(n), just compare i^2 and n. Also, no need for 'list', use the 'which' function. You may replace 'break' with 'return' and 'repeat' with a 'for' loop since you are incrementing the index 'i' at the end of each loop. Last, but not least, your function fails for all n < 9, probably due to a nasty bug you didn't investigate: 'seq(a, b)' is not empty when a > b. [[User:Arbautjc|Arbautjc]] ([[User talk:Arbautjc|talk]]) 12:16, 12 December 2016 (UTC)
== Pari/GP script ==
The first script uses "forprime(p=2,sqrt(lim)" which seems contrary to the task assignment.[[User:Billymacc|Billymacc]] ([[User talk:Billymacc|talk]]) 03:01, 4 May 2021 (UTC)
| |||