\"\" \"\" \"\"
Go backward to Quicksort
Go up to Example Programs
Go forward to Long Integer Multiplication (Bag Version)
RISC-Linz logo

Long Integer Multiplication

// ----------------------------------------------------------------------------
//
// mult.cc
// digit-wise integer multiplication with threads
//
// $Id: app_mult.tex,v 1.1 1996/04/01 07:24:21 schreine Exp $
// (C) 1996 Wolfgang Schreiner <Wolfgang.Schreiner@risc.uni-linz.ac.at>
//
// ----------------------------------------------------------------------------

#include <rt++.h>

typedef char Digit;
typedef Array<Digit> Number;
const int BASE = 10;

Atom(Digit);
Ref(Number);
Ref(Thread<Number>);

ThreadRes(Number);
ThreadArg2(A, Number, Number, Digit);
ThreadArg2(B, Number, Thread<Number>, Thread<Number>);

// ----------------------------------------------------------------------------
//
// check for overflow i.e. decompose <d> into <digit> and <carry>
//
// ----------------------------------------------------------------------------
static inline void over(Digit d, Digit *digit, Digit *carry)
{
  Digit c;
  if (d < BASE)
    {
      c = 0;
    }
  else
    {
      d -= BASE;
      c = 1;
    }
  *digit = d;
  *carry = c;
}

// ----------------------------------------------------------------------------
//
// sum of two numbers
//
// ----------------------------------------------------------------------------
Number sum(Thread<Number> ta, Thread<Number> tb)
{
  Number a = Wait(ta);
  Number b = Wait(tb);
  int la = Length(a);
  int lb = Length(b);
  int min = (la < lb) ? la : lb;
  int max = (la > lb) ? la : lb;
  Number c = (la > lb) ? a : b;
  Number s(max+1);
  Digit carry = 0;
  for (int i = 0; i < min; i++)
    {
      Digit digit, carry0;
      over(a[i]+b[i]+carry, &digit, &carry0);
      s[i] = digit;
      carry = carry0;
    }
  for (int j = min; j < max; j++)
    {
      Digit digit, carry0;
      over(c[j]+carry, &digit, &carry0);
      s[j] = digit;
      carry = carry0;
    }
  s[max] = carry;
  return(s);
}

// ----------------------------------------------------------------------------
//
// product of number and digit
//
// ----------------------------------------------------------------------------
Number prod(Number a, Digit b)
{
  int la = Length(a);
  Number p(la+1);
  Digit carry = 0;
  for (int i = 0; i < la; i++)
    {
      Digit digit, carry0;
      over(a[i]*b+carry, &digit, &carry0);
      p[i] = digit;
      carry = carry0;
    }
  p[la] = carry;
  return(p);
}

// ----------------------------------------------------------------------------
//
// multiplication of two numbers
//
// ----------------------------------------------------------------------------
Number mult(Number a, Number b)
{
  int lb = Length(b);
  int n = 2*lb-1;
  List< Thread<Number> > list;
  for (int i = 0; i < lb; i++)
    {
      Thread2<Number, Number, Digit> t(prod, a, b[i]);
      list.cons(t, list);
    }
  for (int j = 0; j < n-2 ; j += 2)
    {
      Thread<Number> ta(Head(list)); list.tail();
      Thread<Number> tb(Head(list)); list.tail();
      Thread2<Number, Thread<Number>, Thread<Number> > t(sum, ta, tb);
      list.cons(t, list);
    }
  return(Wait(Head(list)));
}

// ----------------------------------------------------------------------------
//
// main program
//
// ----------------------------------------------------------------------------
int multmain(int argc, char *argv[]) 
{
  for (int i = 0; i < 10; i++)
    {
      int la = 1+rand()%5000;
      int lb = 1+rand()%50;
      Number a(la);
      Number b(lb);
      for (int j = 0; j < la; j++)
        a[j] = rand()%BASE;
      for (int k = 0; k < lb; k++)
        b[k] = rand()%BASE;
      Number c = mult(a, b);
    }
  return(0);
}

void init(RT_Argument *rt_arg, int argc, char *argv[]);

int main(int argc, char *argv[]) 
{
  RT_Argument rt_arg;
  init(&rt_arg, argc, argv);
  rt_arg.stack = 15000;
  exit(rt_main(multmain, 1, argv, rt_arg, 0));
}

// ----------------------------------------------------------------------------
// end of mult.cc
// ----------------------------------------------------------------------------
// Local Variables: ***
// mode: C++ ***
// End: ***

Author: Wolfgang Schreiner
Last Modification: April 12, 1997