Go backward to Long Integer Multiplication (Bag Version) Go up to Example Programs |
// ---------------------------------------------------------------------------- // // mult3.cc // digit-wise integer multiplication with bags and no over-synchronization // // $Id: app_mult3.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); Atom(int); Ref(ThreadBag<Number>); ThreadBagRes(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(ThreadBag<Number> bag, int k) { Number a = Wait(bag, k); Number b = Wait(bag, k+1); 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; 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)); } // ---------------------------------------------------------------------------- // // 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); exit(rt_main(multmain, 1, argv, rt_arg, 0)); } // ---------------------------------------------------------------------------- // end of mult3.cc // ---------------------------------------------------------------------------- // Local Variables: *** // mode: C++ *** // End: ***