Multiplication algorithms (version 1.0)

Dec 14th, 2016
506
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #! python3
2. # -*- encoding: utf-8 -*-
3.
4. #https://www.coursera.org/learn/algorithms-divide-conquer
5. #Lab 1, Ulf Benjaminsson, 2016-12-14
6. import sys;
7. NUMBER_A = 3141592653589793238462643383279502884197169399375105820974944592;
8. NUMBER_B = 2718281828459045235360287471352662497757247093699959574966967627;
9.
10. #(a, b, product)
11. def makeTestCase(a, b):
12.     return (a, b, a*b);
13.
14. def makeTestCases():
15.     return [
16.         makeTestCase(1, 1),
17.         makeTestCase(11, 10),
18.         makeTestCase(-100, 200),
19.         makeTestCase(314159, 271828),
20.         makeTestCase(10, 100),
21.         makeTestCase(-10, 100),
22.         makeTestCase(NUMBER_A, NUMBER_B)
23.     ];
24.
25. #implements https://en.wikipedia.org/wiki/Grid_method_multiplication
26. #As a warmup to more proper algorithms.
27. def gridAlgo(a,b):
28.     negate = not ((a < 0) == (b < 0)); #compare sign of the numbers (mixed sign multiplication = negative result)
29.     digits_a = [int(i) for i in str(abs(a))];
30.     digits_b = [int(i) for i in str(abs(b))];
31.     digits_a.reverse(); #arrange digits in order of magnitude; 1s, 10s, 100s etc
32.     digits_b.reverse(); #to keep my loops simple. :)
33.     factors = [[0] * len(digits_b) for i in range(len(digits_a))]; #2 dimensional array of [digits_a x digits_b] indexes
34.     for pos_a, digit_a in enumerate(digits_a):
35.         digit_a_value = digit_a * (10**pos_a); #10**pos_a == 10^n == place value in base 10
36.         for pos_b, digit_b in enumerate(digits_b):
37.             digit_b_value = digit_b * (10**pos_b); #10**pos_b == 10^n == place value in base 10
38.             factors[pos_a][pos_b] = digit_a_value * digit_b_value;
39.     return -sum(sum(factors,[])) if negate else sum(sum(factors,[]));
40.
41. #TODO:
43.     result = 0;
44.     return result;
45.
46. #TODO:
47. def karatsubaAlgo(a,b):
48.     result = 0;
49.     return result;
50.
51. def multiply(a, b):
52.     result = gridAlgo(a,b);
53.     return result;
54.
55. def main():
56.     samples = makeTestCases();
57.     for (a, b, correctAnswer) in samples:
58.         result = multiply(a, b);
59.         passed = result ==  correctAnswer;
60.         print('{!s} {:d} x {:d} = {:d}'.format(
61.                 "Passed:" if passed else "\tFailed:", a, b, result)
62.         );
63.         if(not passed):