hi friends. I am supposed to write and algorithm which uses recursion (Divide-And-Conquer) to multiply two arrays.These arrays hold big Numbers that are greater than long(int 64) or double capacity. Would please help to write this algorithm in C#?
A:
Here's a start: divide each number into 2 pieces, multiply the pieces recursively, and add them up with the right offset.
Keith Randall
2010-05-05 05:34:52
i know this, but how to implement by arrays ?! i save my big numbers in two arrays.
persian Dev
2010-05-05 05:38:30
@Keith, do you mean use normal array multiplication procedure but for actual multiplication use divide and conquer?
Archie
2010-05-05 06:28:55
Divide the arrays in half. Use the following formula for 2k-bit multiplication: (A + B * 2^k) * (C + D * 2^k) = A*C + (A*D + B*C) * 2^k + B*D 2^(2k). Divide your first multiplicand in half to get A and B, the second multiplicand to get C and D.
Keith Randall
2010-05-05 17:05:53