Multiply two numbers

Question

I am trying to implement multiplication of two numbers without using the * operator, as a practice for programming interviews. I have written two functions.

1) Using Long Multiplication

 static int MultiplyTwoNumbers(int num1,int num2)
 {
 List<int> leftnumber = new List<int>();
 do
 {
 leftnumber.Add(num1% 10);
 num1/= 10;
 } while (num1!=0);
 List<int> rightnumber = new List<int>();
 do
 {
 rightnumber.Add(num2% 10);
 num2/= 10;
 } while (num2!= 0);
 int result = 0;
 int counter = 1;
 for (int i = 0; i <leftnumber.Count; i++)
 {
 int tempresult = 0;
 int carry = 0;
 int innercounter = counter;
 for (int j = 0; j<rightnumber.Count; j++)
 {
 int tempVal = leftnumber[i] * rightnumber[j];
 tempVal += carry;
 if (tempVal / 10 != 0)
 {
 carry = tempVal / 10;
 tempVal = tempVal % 10;
 }
 tempresult = tempresult + (innercounter * tempVal);
 innercounter = innercounter * 10;
 }
 result +=tempresult;
 counter = counter * 10;
 }
 return result;
 }

2) using Addition

 static int multiplicationUsingAdd(int num1,int num2)
 {
 int result = 0;
 for (int i = 0; i < num2; i++)
 {
 int temp=result+ num1;
 result = temp;
 }
 return result;
 }

Which one is better and how can I improve it ?

• RJFalconer: Your first method uses the * operator. Presumably you are aiming to avoid that. (If not then return a * b is the best implementation :) ).
• svick: Better in what way? What are you looking for? (Clearly the common rules don't apply, otherwise you would just return num1 * num2.)
• RobH: @Rohit so why aren't you just using * ?
• Eric Lippert: I have a better challenge for you. Implement multiplication of two numbers without using any built-in type. Do not use int, double, decimal, bool, anything. You can implement all of mathematics without using built-ins at all. How would you do so? Remember, the people who implemented int had to start without having int already implemented; they did it somehow.
• Nikita B: @EricLippert, interesting. Does object count as built-in type for the purpose of this challenge? I don't see a way of creating a C# program without implicitly deriving from object or using other object-derived types, let alone implementing something meaningful. :)

Answer 1

You seem to be very much over-complicating this. Here is an efficient solution:

Assuming a and b are positive numbers and the result is a valid 32-bit integer value

public int Multiply(int a, int b)
{
 if (a < 0 || b < 0)
 throw new ArgumentException("Numbers must be positive");
 var min = Math.Min(a, b);
 var max = Math.Max(a, b);
 if (min == 0 || max == 0)
 return 0;
 else if (min == 1)
 return max;
 int s = min >> 1;
 int halfProduct = Multiply(s, max);
 if (min % 2 == 0)
 return halfProduct + halfProduct;
 return halfProduct + halfProduct + max;
}

So what is happening here? First we need to sort these by the smaller and larger numbers, this reduces the number of iterations required. If either of the numbers is zero, then we return zero (since x*0 == 0). If the minimum number is 1, then we return max (since x*1 == x).

Now we can apply the shift operator since shifting one to the right divides the number by 2. By recursion we keep doing this until Multiply returns 0 or max. We can then determine the value if min is even by adding the two half-products or if min is odd by adding the two half products and max.

Again, even in your original solution this will break for negative numbers. You can code around that by switching the sign (Math.Abs) and swapping the sign at the end (0 - return value, unless both are negative then you leave it positive). I'll leave that as an exercise for you.

• Der Kommissar: You could eliminate a branch by doing something like var min = a; var max = b; if (a > b) { min = b; max = a; ), this should have two speed enhancements: two reduced method calls, one reduced branch. In the case where a < b, then it's two reduced branches.

Answer 2

It breaks if num2 is negative

static int Multiply(int num1, int num2)
{
 var result = 0;
 for (int i = 0; i < Math.Abs(num2); i++)
 {
 result += num1;
 }
 if (num2 < 0)
 {
 return -result;
 }
 else
 {
 return result;
 }
}

Answer 3

I am trying to implement multiplication of two numbers. And I am looking to improve its time and space efficiency

There really isn't a better time and space efficiency than this.

static int MultiplyTwoNumbers(int num1, int num2)
{
 return num1 * num2;
}

However, I assume that you've got some other motives behind the question.

Which one is better and how can I improve it?

Of the two methods you've posted, multiplicationUsingAdd is clearly the better option for a few reasons:

1. It's simpler and easier to understand.
2. There's no memory allocation on the heap (like the new List<int>()) in the other one.
3. I haven't profiled it, but it's extremely likely to be the faster of the two.

However, it could be improved quite a bit.

1. Standard C# naming conventions always use PascalCase for method names. It should be called MultiplicationUsingAdd
2. The name MultiplicationUsingAdd is a form of leaky abstraction because the method name exposes the details of the implementation.
3. A better name would simply be Multiply. The parameters indicate how many numbers are involved and the implementation details are irrelevant.
4. The code itself can be make a little easier to read by removing some irrelevant bits (e.g. the temp variable).

Here's how I would have written it.

static int Multiply(int num1, int num2)
{
 var result = 0;
 for (int i = 0; i < num2; i++)
 result += num1;
 return result;
}

• Jaime: The asymptotic complexity of MultiplicationUsingAdd is O(min(n, m)). Long multiplication has space complexity O(log n + log m), which is pretty damn good, and time complexity O(log n * log m), which makes it a contender in real life if you are dealing with very large integers, although there are better alternatives, e.g. Karatsuba. Point being, it really is repeated addition that you should never use to multiply two numbers, as there is almost always going to be a better alternative.
• Rohit: Well I am trying to implement multiplication on my own instead of using * operator. It is more likely a interview question
• Ron Beyer: Would be good to note that, even in the OP's original code, this assumes that the operands are non-negative and that the result can be stored in an integer (int.Max * int.Max for example).
• t3chb0t: Quote: Seriously? Is this a joke? - and you wonder why the DV?
• craftworkgames: @t3chb0t Yeah, okay, fair enough. But you must admit, the way the OP worded the original question and the follow up comments, it felt like he wasn't being entirely serious about the question. I may have gone too far with that initial comment, but I didn't mean to offend anyone. My apologies.