Another method to multiply two numbers without usi

Question

This question already has answers here:

How can I perform multiplication without the '*' operator? (33 answers)

Closed 2 years ago.

I had an interesting interview yesterday where the interviewer asked me a classic question: How can we multiply two numbers in Java without using the * operator. Honestly, I don't know if it's the stress that comes with interviews, but I wasn't able to come up with any solution.

After the interview, I went home and breezed through SO for answers. So far, here are the ones I have found:

First Method: Using a For loop

// Using For loop
public static int multiplierLoop(int a, int b) {
    int resultat = 0;
    for (int i = 0; i < a; i++) {
        resultat += b;
    }

    return resultat;
}

Second Method: Using Recursion

// using Recursion
public static int multiplier(int a, int b) {

    if ((a == 0) || (b == 0))
        return 0;
    else
        return (a + multiplier(a, b - 1));

}

Third Method: Using Log10

**// Using Math.Log10
public static double multiplierLog(int a, int b) {
    return Math.pow(10, (Math.log10(a) + Math.log10(b)));
}**

So now I have two questions for you:

1. Is there still another method I'm missing?
2. Does the fact that I wasn't able to come up with the answer proves that my logical reasoning isn't strong enough to come up with solutions and that I'm not "cut out" to be a programmer? Cause let's be honest, the question didn't seem that difficult and I'm pretty sure most programmers would easily and quickly find an answer.

Answer 1

For completeness:

Math.multiplyExact(int,int):

Returns the product of the arguments, throwing an exception if the result overflows an int.

if throwing on overflow is acceptable.

Answer 2

There is a method called Russian Peasant Multiplication. Demonstrate this with the help of a shift operator,

public static int multiply(int n, int m)
{ 
    int ans = 0, count = 0;
    while (m > 0)
    {
        if (m % 2 == 1)             
            ans += n << count;
        count++;
        m /= 2;
    }

    return ans;
}

The idea is to double the first number and halve the second number repeatedly till the second number doesn’t become 1. In the process, whenever the second number become odd, we add the first number to result (result is initialized as 0) One other implementation is,

static int russianPeasant(int n, int m) {
    int ans = 0;

    while (m > 0) {
        if ((m & 1) != 0)
            ans = ans + n;

        n = n << 1;
        m = m >> 1;
    }
    return ans;
}

refer :

• https://www.geeksforgeeks.org/russian-peasant-multiply-two-numbers-using-bitwise-operators/
• https://www.geeksforgeeks.org/multiplication-two-numbers-shift-operator/

Answer 3

I don't know whether that has to be a strictly "programming question". But in Maths:

x * y = x / (1 / y) #divide by inverse

So:

Method 1:

public static double multiplier(double a, double b) {

    // return a / (1 / b);

    // the above may be too rough
    // Java doesn't know that "(a / (b / 0)) == 0"
    // a special case for zero should probably be added:

    return 0 == b ? 0 : a / (1 / b);
}

Method 2 (a more "programming/API" solution):

Use big decimal, big integer:

new BigDecimal("3").multiply(new BigDecimal("9"))

There are probably a few more ways.

Answer 4

Use BigInteger.multiply or BigDecimal.multiply as appropriate.

Answer 5

TL;DR - Inform the interviewer that re-inventing the wheel is a bad idea

Rather than entertain the interviewer's Code Golf question, I would have answered the interview question differently:

Brilliant engineers at Intel, AMD, ARM and other microprocessor manufacturers have agonized for decades as how to multiply 32 bit integers together in the fewest possible cycles, and in fact, are even able to produce the correct, full 64 bit result of multiplication of 32 bit integers without overflow.

(e.g. without pre-casting a or b to long, a multiplication of 2 ints such as 123456728 * 23456789 overflows into a negative number)

In this respect, high level languages have only one job to do with integer multiplications like this, viz, to get the job done by the processor with as little fluff as possible.

Any amount of Code Golf to replicate such multiplication in software IMO is insanity.

There's undoubtedly many hacks which could simulate multiplication, although many will only work on limited ranges of values a and b (in fact, none of the 3 methods listed by the OP perform bug-free for all values of a and b, even if we disregard the overflow problem). And all will be (orders of magnitude) slower than an IMUL instruction.

For example, if either a or b is a positive power of 2, then bit shifting the other variable to the left by log can be done.

if (b == 2)
   return a << 1;
if (b == 4)
   return a << 2;
... 

But this would be really tedious.

In the unlikely event of the * operator really disappearing overnight from the Java language spec, next best, I would be to use existing libraries which contain multiplication functions, e.g. BigInteger.multiply(), for the same reasons - many years of critical thinking by minds brighter than mine has gone into producing, and testing, such libraries.

BigInteger.multiply would obviously be reliable to 64 bits and beyond, although casting the result back to a 32 bit int would again invite overflow problems.

The problem with playing operator * Code Golf

There's inherent problems with all 3 of the solutions cited in the OP's question:

• Method A (loop) won't work if the first number a is negative.

 for (int i = 0; i < a; i++) {
      resultat += b;
  }

Will return 0 for any negative value of a, because the loop continuation condition is never met

• In Method B, you'll run out of stack for large values of b in method 2, unless you refactor the code to allow for Tail Call Optimisation

multiplier(100, 1000000)

"main" java.lang.StackOverflowError

• And in Method 3, you'll get rounding errors with log10 (not to mention the obvious problems with attempting to take a log of any number <= 0). e.g.

multiplier(2389, 123123);

returns 294140846, but the actual answer is 294140847 (the last digits 9 x 3 mean the product must end in 7)

Even the answer using two consecutive double precision division operators is prone to rounding issues when re-casting the double result back to an integer:

static double multiply(double a, double b) {
    return 0 == (int)b 
       ? 0.0 
       : a / (1 / b);
}

e.g. for a value (int)multiply(1, 93) returns 92, because multiply returns 92.99999.... which is truncated with the cast back to a 32 bit integer.

And of course, we don't need to mention that many of these algorithms are O(N) or worse, so the performance will be abysmal.

Answer 6

Others have hit on question 1 sufficiently that I'm not going to rehash it here, but I did want to hit on question 2 a little, because it seems (to me) the more interesting one.

So, when someone is asking you this type of question, they are less concerned with what your code looks like, and more concerned with how you are thinking. In the real world, you won't ever actually have to write multiplication without the * operator; every programming language known to man (with the exception of Brainfuck, I guess) has multiplication implemented, almost always with the * operator. The point is, sometimes you are working with code, and for whatever reason (maybe due to library bloat, due to configuration errors, due to package incompatibility, etc), you won't be able to use a library you are used to. The idea is to see how you function in those situations.

The question isn't whether or not you are "cut out" to be a programmer; skills like these can be learned. A trick I use personally is to think about what, exactly, is the expected result for the question they're asking? In this particular example, as I (and I presume you as well) learned in grade 4 in elementary school, multiplication is repeated addition. Therefore, I would implement it (and have in the past; I've had this same question in a few interviews) with a for loop doing repeated addition.

The thing is, if you don't realize that multiplication is repeated addition (or whatever other question you're being asked to answer), then you'll just be screwed. Which is why I'm not a huge fan of these types of questions, because a lot of them boil down to trivia that you either know or don't know, rather than testing your true skills as a programmer (the skills mentioned above regarding libraries etc can be tested much better in other ways).