Anonymous user
Talk:Sieve of Eratosthenes: Difference between revisions
→Problem found in first Erlang example.
| (18 intermediate revisions by 6 users not shown) | |||
Line 253:
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
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)
| |||