CODEWITHSUNDEEP
cmultiplication
Genelia D'souza
Genelia D'souza

Reputation: 125

multiplication of two numbers

Few days back I had an interview with Qualcomm. I was kinnda stucked to one question, the question thou looked very simple but neither me nor the interviewer were satisfied with my answers, if anyone can provide any good solution to this problem.

The question is:

Multiply 2 numbers without using any loops and additions and of course no multiplication and division.

To which I replied: recursion

He said anything else at very low level.

To which the genuine thought that came to my mind was bit shifting, but bit shifting will only multiply the number by power of 2 and for other numbers we finally have to do a addition.

For example: 10 * 7 can be done as: (binary of 7 ~~ 111) 10<< 2 + 10<<1 + 10 40 + 20 + 10 = 70

But again addition was not allowed.

Any thoughts on this issue guys.

Upvotes: 6

Views: 2555

Answers (8)

Ed Heal
Ed Heal

Reputation: 59997

Here is a solution just using lookup, addition and shifting. The lookup does not require multiplication as it is an array of pointers to another array - hence addition required to find the right array. Then using the second value you can repeat pointer arithmetic and get the lookup result.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
  /* Note:As this is an array of pointers to an array of values, addition is
     only required for the lookup.

     i.e. 

     First part: lookup + a value -> A pointer to an array
     Second part - Add a value to the pointer to above pointer to get the value
  */
  unsigned char lookup[16][16] = {
    { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 },
    { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 },
    { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45 },
    { 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60 },
    { 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75 },
    { 0, 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90 },
    { 0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105 },
    { 0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120 },
    { 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99, 108, 117, 126, 135 },
    { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150 },
    { 0, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 132, 143, 154, 165 },
    { 0, 12, 24, 36, 48, 60, 72, 84, 96, 108, 120, 132, 144, 156, 168, 180 },
    { 0, 13, 26, 39, 52, 65, 78, 91, 104, 117, 130, 143, 156, 169, 182, 195 },
    { 0, 14, 28, 42, 56, 70, 84, 98, 112, 126, 140, 154, 168, 182, 196, 210 },
    { 0, 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, 165, 180, 195, 210, 225 }
  };
  unsigned short answer, mult;
  unsigned char x, y, a, b;

  x = (unsigned char)atoi(argv[1]);
  y = (unsigned char)atoi(argv[2]);
  printf("Multiple %d by %d\n", x, y);

  answer = 0;
  /* First nibble of x, First nibble of y */
  a = x & 0xf;
  b = y & 0xf;
  mult = lookup[a][b];
  answer += mult;
  printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer);

  /* First nibble of x, Second nibble of y */
  a = x & 0xf;
  b = (y & 0xf0) >> 4;
  mult = lookup[a][b];
  answer += mult << 4;
  printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer);

  /* Second nibble of x, First nibble of y */
  a = (x & 0xf0) >> 4;
  b = y & 0xf;
  mult = lookup[a][b];
  answer += mult << 4;
  printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer);

  /* Second nibble of x, Second nibble of y */
  a = (x & 0xf0) >> 4;
  b = (y & 0xf0) >> 4;
  mult = lookup[a][b];
  answer += mult << 8;
  printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer);

  return 0;
}

Upvotes: 7

Rado
Rado

Reputation: 8963

You could use logarithms and subtraction instead.

log(a*b) = log(a) + log(b)
a+b = -(-a-b)
exp(log(a)) = a 

round(exp(-(-log(a)-log(b))))

Upvotes: 1

user811773
user811773

Reputation:

Question: Multiply 2 numbers without using any loops and additions and of course no multiplication and division.

Multiplication is defined in terms of addition. It is impossible not to find addition in an implementation of multiplication.

Arbitrary precision numbers cannot be multiplied without loop/recursion.

Multiplication of two numbers of fixed bit-lengths can be implemented via a table lookup. The problem is the size of the table. Generating the table requires addition.

The answer is: It cannot be done.

Upvotes: 0

ouah
ouah

Reputation: 145829

You can separate your problems by first implementing the addition and then the multiplication based on the addition.

For the addition, implement what they do on processors at the gate level using the C bitwise operators:

http://en.wikipedia.org/wiki/Full_adder

Then for the multiplication, with the addition you implemented, use goto statements and labels so no loop statement (the for, while and do iteration statements) will be used.

Upvotes: 2

asaelr
asaelr

Reputation: 5456

You can implement addition by bits operators. But still, if you want to avoid loops, you should write a lot of code. (I used to implement multiplication without arithmetic operators, but I use loop, shifting the index until it became zero. If it can help you, tell me, and I will search the file)

Upvotes: 1

Cris Stringfellow
Cris Stringfellow

Reputation: 3808

What about russian peasant multiplication without using addition? Is there an easy way (a few lines, no loops) to simulate addition using only AND, OR, XOR and NOT?

Upvotes: 1

Alex Reynolds
Alex Reynolds

Reputation: 96937

Perhaps you could recursively add, using bitwise operations as a replacement for the addition operator. See: Adding Two Numbers With Bitwise and Shift Operators

Upvotes: 3

Akshaya Shanbhogue
Akshaya Shanbhogue

Reputation: 1448

How about multiplication tables?

Upvotes: 0

Related Questions