Mathematics

The Speed of Multiplication

June 18, 2013

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[1])
b = int(sys.argv[2])
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:

wpid-python_simple_multipication-2013-06-18-09-38.png

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:

Ten’s Multiplication:


import sys

def main(argv):

if len(argv) != 2:
sys.exit('Usage: tens_multi.py <a> <b>')

a = sys.argv[1]
b = sys.argv[2]
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:

wpid-python_tens_multipication-2013-06-18-09-38.png

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[1])
b = int(sys.argv[2])

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:])


The output:

wpid-python_russian_multipication-2013-06-18-09-38.png

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:

 

Simple Ten's Russian
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:

wpid-python_time_example-2013-06-18-09-38.png

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.

If you enjoyed this post, please consider leaving a comment or subscribing to the RSS feed to have future articles delivered to your feed reader.

You Might Also Like

  • obitus

    Nice data. Here is a link to the article to which you refer too as "multiplication by tens":
    http://deadendmath.com/multiplication-by-distributive-property/

  • L

    I was just wondering why you passed sys.argv[1:] to main. Is better than directly accessing it?

    • CptDeadBones

      It doesn't really matter. You can either pass it or just use it directly. There is no advantage either way.

  • Big Fat Lobster

    LOL, I think you are misinterpreting the output from the time command. 'user' is not the time the user spent in typing at the keyboard, it is the time spent by the program in user-space, in contrast to kernel-space time (whose value is given by 'sys'). So 'user' is the correct value you should look at.

    • CptDeadBones

      You are correct, but I did not misinterpret anything. User time is the time the program spent in User-Space. That part is correct. I dumb it down to say it is the time the user entered information. In reality, the time I am looking at is execution time. In other words, how long it took the program to run. When you try larger numbers the sys time will increase.