ulfben

Multiplication algorithms (version 1.0)

Dec 14th, 2016
272
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×