Go backward to Long Integer Multiplication Go up to Tutorial

Long Integer Multiplication (Bag Version)

// ----------------------------------------------------------------------------
// Long Integer Multiplications (Bag Version)
// ----------------------------------------------------------------------------
#include <rt++.h>

typedef char Digit;
typedef Array<Digit> Number;
...

// ----------------------------------------------------------------------------
// sum of two numbers
// ----------------------------------------------------------------------------
Number sum(Number a, Number b)
{
  ...
  return(s);
}

// ----------------------------------------------------------------------------
// product of number and digit
// ----------------------------------------------------------------------------
Number prod(Number a, Digit b)
{
  ...
  return(p);
}

// ----------------------------------------------------------------------------
// multiplication of two numbers
// ----------------------------------------------------------------------------
Number mult(Number a, Number b)
{
  int lb = Length(b);
  int n = 2*lb-1;
  ThreadBag<Number> bag(n);
  for (int i = 0; i < lb; i++)
    {
      ThreadBag2<Number, Number, Digit>(bag, prod, a, b[i]);
    }
  for (int j = 0; j < n-2 ; j += 2)
    {
      Number a = Wait(bag, j);
      Number b = Wait(bag, j+1);
      ThreadBag2<Number, Number, Number>(bag, sum, a, b); 
    }
  return(Wait(bag, n-1));
}

...

The program is based on the concept of thread bags that collect thread results and provide them in the order in which they have been computed (i.e. in the order in which the threads have terminated):  

1. The declaration  

   ThreadBag<Number> bag(n);
   

   declares a bag that can hold up to n threads of result type Number. It is also possible to declare bags without an explicit size specification but this is less efficient.
2. A statement  

   ThreadBag2<Number, Number, Digit>(bag, prod, a, b[i]);
   

   creates a new thread computing prod(a, b[i]). The thread itself is anonymous but its result can be retrieved via bag.
3. The expression  

   Wait(bag, j)
   

   returns the j-th thread result in bag where it is undefined by which thread this result was computed (but two calls of Wait with the same index in the same program run always return the same result).

Atom(Digit);
Ref(Number);

ThreadBagRes(Number);

Above solution has one disadvantage compared to the approach presented in the previous section. The main program waits for the first phase thread results in the bag before it starts the second phase threads. We can overcome this over-synchronization by passing the thread bag directly to the second phase threads and let these threads themselves synchronize with their required arguments. This idea is sketched below (the full program can be found here).  

// ----------------------------------------------------------------------------
// Long Integer Multiplications (Bag Version)
// ----------------------------------------------------------------------------
#include <rt++.h>

typedef char Digit;
typedef Array<Digit> Number;
...

// ----------------------------------------------------------------------------
// sum of two thread bag results
// ----------------------------------------------------------------------------
Number sum(ThreadBag<Number> a, int j)
{
  Number a = Wait(bag, j);
  Number b = Wait(bag, j+1);
  ...
  return(s);
}

// ----------------------------------------------------------------------------
// product of number and digit
// ----------------------------------------------------------------------------
Number prod(Number a, Digit b)
{
  ...
  return(p);
}

// ----------------------------------------------------------------------------
// multiplication of two numbers
// ----------------------------------------------------------------------------
Number mult(Number a, Number b)
{
  int lb = Length(b);
  int n = 2*lb-1;
  ThreadBag<Number> bag(n);
  for (int i = 0; i < lb; i++)
    {
      ThreadBag2<Number, Number, Digit>(bag, prod, a, b[i]);
    }
  for (int j = 0; j < n-2 ; j += 2)
    {
      ThreadBag2<Number, ThreadBag<Number>, int>(bag, sum, bag, j); 
    }
  return(Wait(bag, n-1));
}

...

In order to get an executable program, the following top-level declarations have to be provided to the garbage collector

Atom(Digit);
Ref(Number);
Atom(int);
Ref(ThreadBag<Number>);

ThreadBagRes(Number);