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