PROLOG: Summing up the series procedure

Question

I have been trying to work on this problem that I found in a book, but am not able to make sense of it in my head. The problem asks me to use series(N, Total) for this procedure; 1 + 1/2 + 1/3 + 1/4 + ... + 1/(N-1). Any help making me understand this problem would be appreciated! Thanks a lot!

Answer 1

I don't understand what problem you are having.

A simple way to solve this problem is to define a recursive predicate.

You can work with fractional numbers using is/2 and rdiv/2.

This will sum from 1/1 to 1/(B-1):

series(B, B, 0).
series(A, B, Total) :-
    A < B,
    succ(A, A1),
    series(A1, B, Total1),
    Total is rdiv(1, A) + Total1.

How to read it:

• the sum (of 1/i) from B to B (excluded) is 0
• the sum (of 1/i) from A to B, where A < B, is 1/A plus the sum from A+1 to B (recursion). Note the order of predicates, they're slightly rearranged, because is/2 requires all the arguments to be ground.

Example: we use it co calculate sum 1/i for i=1,...,3 = 1/1 + 1/2 + 1/3 = 11/6:

?- series(1,4,X).
X = 11 rdiv 6 .

Answer 2

The answers presented so far can be imitated by using the meta-predicate foldl/4.

Like @mescalinum did in previous answer I will not use floats, but arbitrary-precision rational numbers. Unlike with floats, the addition of rational numbers is commutative and associative. So when summing up rational numbers, any order of additions will get us the same result.

I propose using lambdas together with the two meta-predicates init1/3 and reduce/3, like so:

seriesR(N,Val) :-
   init1(\I^E^(E is rdiv(1,I)),N-1,Rs),
   reduce(\X^Y^XY^(XY is X+Y),Rs,Val).

Sample query:

?- seriesR(4,Val).
Val = 11 rdiv 6.

---

To show that reduce/3 can help speed up the summing up---even though it has some internal overhead of its own---let's run seriesR/2 and series/3 head-to-head for some BIG N:

?- time((series(10000,_),false)).
% 40,001 inferences, 2.805 CPU in 2.804 seconds (100% CPU, 14259 Lips)
false.

?- time((seriesR(10000,_),false)).
% 180,019 inferences, 0.060 CPU in 0.060 seconds (100% CPU, 3014245 Lips)
false.

---

Edit

Let's dig a little deeper!

The implementation of lambda expressions that we use incurs measurable performance costs. These costs will likely vanish in the future, once the appropriate optimizations are done.

For the time being, let's quantify these costs...

num_num_sum(X,Y,Sum) :-
   Sum is X+Y.

r_reciprocal(X,Y) :-
   Y is rdiv(1,X).

seriesR2(N,Val) :-
   init1(r_reciprocal,N-1,Rs),
   reduce(num_num_sum,Rs,Val).   

Running seriesR/2 and seriesR2/2 head-to-head we get:

?- time((between(1,10000,_),seriesR(10,V),false)).
% 1,750,001 inferences, 0.389 CPU in 0.389 seconds (100% CPU, 4500790 Lips)
false.

?- time((between(1,10000,_),seriesR2(10,V),false)).
% 820,001 inferences, 0.137 CPU in 0.137 seconds (100% CPU, 5999216 Lips)
false.

In this example, using lambda expressions incurs a worst-case overhead of roughly a factor of 3. Significant? Maybe... but orders of magnitude less than using foldl instead of reduce!

Answer 3

As I understand it, you want a predicate that evaluates this function:

In a procedural language, you'd write something like this iterative solution:

static double iterative_harmonic_number( int n )
{
  if ( n < 1 ) throw new ArgumentOutOfRangeException("n");

  double r = 0.0 ;

  while ( n > 0 )
  {
    r += 1.0 / n-- ;
  }

  return r ;
}

Or this recursive solution:

static double recursive_harmonic_number( int n )
{
  if ( n < 1 ) throw new ArgumentOutOfRangeException("n");

  double h = (1.0 / n) ;
  if ( n > 1 ) { h += recursive_harmonic_number(n-1) ; } ;

  return h ;

}

Both of which produce the same results for n in 1..10:

         iterative       recursive
         --------------- ---
f(  1 ): 1                1
f(  2 ): 1.5              1.5
f(  3 ): 1.83333333333333 1.83333333333333
f(  4 ): 2.08333333333333 2.08333333333333
f(  5 ): 2.28333333333333 2.28333333333333
f(  6 ): 2.45             2.45
f(  7 ): 2.59285714285714 2.59285714285714
f(  8 ): 2.71785714285714 2.71785714285714
f(  9 ): 2.82896825396825 2.82896825396825
f( 10 ): 2.92896825396825 2.92896825396825

Prolog is ideally suited for a recursive solution, so let's take a look at that. You have

• 1 special case that terminates the recursion (n=1), and
• the general case (n > 1).

We can express that pretty directly in Prolog:

f( 1 , 1.0 ) .     % the terminating special case
f( N , R   ) :-    % the general case:
  N > 1 ,          % - N must be positive (and greater than 1),
  N1 is N-1 ,      % - compute N-1
  f(N1,T) ,        % - recursively evaluate it
  R is T + 1.0 / N % - add that result to the current N's reciprocal
  .                % Easy!