Tuesday, January 29, 2013

Multiplication is a horrible thing

In one of my interview, the interviewer was saying multiplication is a horrible thing to do. I thought those days have passed, processor architectures have came a long way since then. Since, I don't work in that area, I don't know what actually the complexity of multiplication compared to addition. Finally, the solution I gave to the interviewer had couple of addition but no multiplication. But I was thinking is it really true that multiplication is still a horrible thing to do. Well, I am not sure, I am sure the answer to this question would be very different in different language. I pursued this problem is java. Here is my small piece of code

public class TryMultiplication {
  public static void main(String[] args)
    Random random = new Random();
    int tryCount = 100000000;
    int buffer = 0;
    long startTime = System.currentTimeMillis();
    while(tryCount -- > 0)
      buffer = random.nextInt()+random.nextInt();
         long endTime = System.currentTimeMillis();
    System.out.println("Total time (ms) : " + (endTime - startTime));

Apparently, there is no time difference between addition and multiplication. Well, it was never my intention to say these two takes same amount of time but I am sure in most cases (if not all) the difference is insignificant. Why? because there are other things that takes way more time than arithmetic operation, like load and store. In that case worrying about multiplication, from engineering perspective, is not very pragmatic anymore. Of course, I am aware of the fact that this kind of micro bench marking seldom produces reliable results but there is no observable time difference between addition and multiplication.

Here is a discussion about this issue, http://lemire.me/blog/archives/2010/07/19/is-multiplication-slower-than-addition/