SHARE
TWEET

Multiplication algorithms (version 1.0)

ulfben Dec 14th, 2016 131 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:
  42. def gradeSchoolAlgo(a,b):
  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):
  64.            print('\tShould be: {:d}'.format(correctAnswer)) ;
  65.     return 0;
  66.  
  67. if __name__ == '__main__':  
  68.     status = main();
  69.     sys.exit(status);
RAW Paste Data
Top