Go backward to Quicksort Go up to Example Programs Go forward to Long Integer Multiplication (Bag Version) |
// ---------------------------------------------------------------------------- // // 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: ***