For the most part, all of us take for granted that the cpu can do multiplication in a timely matter. However, there are some systems that do not have multiplication. Furthermore, how is multiplication actually done? Multiplication is nothing more than repeated applications of additions. For example, if we want to compute 5 x 4 we can add 5 4 times or add 4 5 times and keep track of the sum. Let’s take a look how this might look like in Python 2.7.
import sys def main(argv): if len(argv) != 2: sys.exit('Usage: simple_multi.py <a> <b>') a = int(sys.argv) b = int(sys.argv) sum = 0 for i in range(a): sum += b print "The result of " + str(a) + " times " + str(b) + " is: " + str(sum) if __name__ == "__main__": main(sys.argv[1:])
And the output:
Sweet. Now for most of you this will be it. Trust me, for me the multiplication symbol is it. I never thought I will have to code multiplication. That is until it came up. I have a friend who happens to be a mathematician with a particular fascination to numbers and counting. So he came up to me claiming that he has this fast way to do multiplication that has to do with the ten’s places and basic multiplication. Basic multiplication being the 10 x 10 grid (or 12 x 12) we all had to memorize at some point. So I decided to put him up for the test, I wrote his algorithm in Python as well as the one above and Russian Multiplication. I won’t spend time trying to explain the algorithms. If you want to, you will find the link helpful enough to explain Russian Multiplication. If you want to find out more about my friend’s Ten’s Multipication, send him a message on his blog DeadEndMath. All in python, running on the same computer with the same Linux time command measuring their performance. Before we get to the data, let’s take a look at the code:
import sys def main(argv): if len(argv) != 2: sys.exit('Usage: tens_multi.py <a> <b>') a = sys.argv b = sys.argv sum = 0; c = len(a) - 1; for i in a: d = len(b) - 1; for j in b: sum += int(i)*int(j)*(10**c)*(10**d); d -= 1; c -= 1; print "The result of " + a + " times " + b + " is: " + str(sum) if __name__ == "__main__": main(sys.argv[1:])
And the output for verification:
Well, at least we got the same results. Let us look at the Russian Multiplication in Python:
import sys def main(argv): if len(argv) != 2: sys.exit('Usage: russian_multi.py <a> <b>') a = int(sys.argv) b = int(sys.argv) sum = 0; if a == 0 or b == 0: print 0; exit(); if b%2 == 1: sum += a; while b != 1: a = a*2; b = b/2; if b%2 == 1: sum += a; print "The result of " + str(a) + " times " + str(b) + " is: " + str(sum) if __name__ == "__main__": main(sys.argv[1:])
Again, good thing we got the same results. Now we know we have all three versions of multiplication and they are all computing products of 2 numbers correctly. Now let us look at their time compression. I have organized the data in a table for convince:
|4 x 5||0.013||0.013||0.014|
|22 x 54||0.014||0.014||0.014|
|5142 x 9810||0.014||0.014||0.014|
|716234 x 847263||0.040||0.014||0.014|
|817263548 x 827461930||NaN||0.014||0.014|
So what can we see? Well first of all the data gathered is from the linux time command. When execute any program in a Linux shell, you can add the command time before the program. This will return you with an output similar to the one below after the command is complete. the times shown are subjective to your computer specifications and current status (i.e. running programs). Here is an example of a Linux time output:
So what does all this mean? The real time is total execution time. The user time is how long it took the user to key in the input. The sys time is the time your command was running on the cpu. In the table above, the time was taken from the sys value of execution of each command. You will notice that simple multiplication gets more cpu consuming as the length of the input increases, while the time for Ten’s and Russian Multiplication remained constant. This means that either algorithm could work as a substitute to multiplication if you happen to work in an environment that does not support multiplication natively. As a final note let me add that even a basic multiplication in Python operates within the same time as Ten’s and Russian multiplication, if not a second faster.