What is the bottleneck in this predicate related to prema?

Question

So, like this: I'm trying to calculate the sum of all primes below two million (for this problem ), but my program is very slow. I know that the algorithm itself is terribly bad and rude, but it seems slower than me. Here I limit the search to 20,000, so the result does not wait too long.
I don’t think this predicate is hard to understand, but I’ll explain it anyway: I calculate a list of all primes below 20,000 and then sum them up. The total part of the fine, part of the prime numbers is very slow.

problem_010(R) :- p010(3, [], Primes), sumlist([2|Primes], R). p010(20001, Primes, Primes) :- !. p010(Current, Primes, Result) :- ( prime(Current, Primes) -> append([Primes, [Current]], NewPrimes) ; NewPrimes = Primes ), NewCurrent is Current + 2, p010(NewCurrent, NewPrimes, Result). prime(_, []) :- !. prime(N, [Prime|_Primes]) :- 0 is N mod Prime, !, fail. prime(ToTest, [_|Primes]) :- prime(ToTest, Primes). 

I would like to know why it is so slow. Is this a good implementation of the stupid brute force algorithm or is there some reason why Prolog crashes?

EDIT: I already found something by adding new primes instead of letting them top the list, I have primes that are most common at startup, so it is ~ 3 times faster. Still need to understand, though :)

Answer 1

OK, before editing the problem was only an algorithm (imho). As you noticed, it’s more efficient to check if the number is first divided by smaller primes; in the final set there are more numbers divisible by 3 than by 32147.

Another improvement to the algorithm is to stop checking when primes are greater than the square root of a number.

Now, after your change, there really are some prolog problems: you are using append / 3. append / 3 is pretty slow since you have to go through the whole list to put an element at the end. Instead, you should use difference lists, which quickly puts an element in the tail.

Now, what is a list of differences? Instead of creating a regular list [1,2,3] you create this file [1,2,3 | T]. Please note that we leave the tail unreasonable. Then, if we want to add one element (or more) to the end of the list, we can simply say T = [4 | NT]. awesome?

The next solution (accumulate primes in reverse order, stop when premiere> SQRT (N), difference of lists to add) takes 0,063 for 20k primes and 17sec for 2m primes, and the source code took 3.7sec for 20k and Append / 3 version 1.3sec.

 problem_010(R) :- p010(3, Primes, Primes), sumlist([2|Primes], R). p010(2000001, _Primes,[]) :- !. %checking for primes till 2mil p010(Current, Primes,PrimesTail) :- R is sqrt(Current), ( prime(R,Current, Primes) -> PrimesTail = [Current|NewPrimesTail] ; NewPrimesTail = PrimesTail ), NewCurrent is Current + 2, p010(NewCurrent, Primes,NewPrimesTail). prime(_,_, Tail) :- var(Tail),!. prime(R,_N, [Prime|_Primes]):- Prime>R. prime(_R,N, [Prime|_Primes]) :-0 is N mod Prime, !, fail. prime(R,ToTest, [_|Primes]) :- prime(R,ToTest, Primes). 

also, given the addition of numbers when creating them, to avoid extra o (n) due to sumlist / 2
in the end, you can always implement the AKS algorithm, which runs in polynomial time (XD)

Answer 2

Firstly, Prolog does not fail here.

There are very smart ways to generate prime numbers. But, as a cheap start, just accumulate primes in reverse order! (7.9s → 2.6s) Thus, smaller ones are checked earlier. Then consider checking only primes up to 141. Large primes cannot be a factor.

Then, instead of going only through numbers that are not divisible by 2, you can add 3, 5, 7.

There are people writing documents on this "problem." See, for example, this article , although this is a slightly complicated discussion about what the “genuine” algorithm was, 22 centuries ago, when the last issue of abacus was released, it was marked as salamis tablets .

Answer 3

First of all, adding at the end of the list with append/3 is pretty slow. If you need to, use the difference lists instead. (Personally, I try to avoid append/3 as much as possible)

Secondly, your prime/2 always checks the entire list when checking a prime. This is too slow. Instead, you can simply check the identifier, you can find the integral coefficient up to the square root of the number you want to check.

 problem_010(R) :- p010(3, 2, R). p010(2000001, Primes, Primes) :- !. p010(Current, In, Result) :- ( prime(Current) -> Out is In+Current ; Out=In ), NewCurrent is Current + 2, p010(NewCurrent, Out, Result). prime(2). prime(3). prime(X) :- integer(X), X > 3, X mod 2 =\= 0, \+is_composite(X, 3). % was: has_factor(X, 3) is_composite(X, F) :- % was: has_factor(X, F) X mod F =:= 0, !. is_composite(X, F) :- F * F < X, F2 is F + 2, is_composite(X, F2). 

Disclaimer: I found this implementation of prime/1 and has_factor/2 by googling.

This code gives:

 ?- problem_010(R). R = 142913828922 Yes (12.87s cpu) 

Here is another quick code:

 problem_010(R) :- Max = 2000001, functor(Bools, [], Max), Sqrt is integer(floor(sqrt(Max))), remove_multiples(2, Sqrt, Max, Bools), compute_sum(2, Max, 0, R, Bools). % up to square root of Max, remove multiples by setting bool to 0 remove_multiples(I, Sqrt, _, _) :- I > Sqrt, !. remove_multiples(I, Sqrt, Max, Bools) :- arg(I, Bools, B), ( B == 0 -> true % already removed: do nothing ; J is 2*I, % start at next multiple of I remove(J, I, Max, Bools) ), I1 is I+1, remove_multiples(I1, Sqrt, Max, Bools). remove(I, _, Max, _) :- I > Max, !. remove(I, Add, Max, Bools) :- arg(I, Bools, 0), % remove multiple by setting bool to 0 J is I+Add, remove(J, Add, Max, Bools). % sum up places that are not zero compute_sum(Max, Max, R, R, _) :- !. compute_sum(I, Max, RI, R, Bools) :- arg(I, Bools, B), (B == 0 -> RO = RI ; RO is RI + I ), I1 is I+1, compute_sum(I1, Max, RO, R, Bools). 

This runs an order of magnitude faster than the code above:

 ?- problem_010(R). R = 142913828922 Yes (0.82s cpu) 

Answer 4

Consider using, for example, the sieve method ("Sieve from Eratosthenes"): first create a list [2,3,4,5,6, .... N], using, for example, the numerical list / 3. The first number on the list is prime, save it. Eliminate it multiple from the rest of the list. The next number in the remaining list is again simple. Exclude it multiple again. And so on. The list will be reduced quite quickly, and you will receive only the remaining prime numbers.