How to write a C program for multiplication without using the * and + operators?

Question

Is it possible to write a C program that multiplies two numbers without using the multiplication and addition operators?

I found this on Stack Overflow. Please help this poor programmer with his problem. And please don't give answers like c = a/(1/((float)b)), which is exactly the same as c = a*b. (And is already given as an answer.)

The answer with the most upvotes on January 19th 2014 wins.

^{Note: This is a code-trolling question. Please do not take the question and/or answers seriously. More information is in code-trolling.}

Answer 1

Always use recursion

Recusion is the right way!

int inc(int x) {
    return x&1?inc(x>>1)<<1:x|1;
}

int dec(int x) {
    return x&1?x^1:dec(x>>1)<<1|1;
}

int add(int x, int y) {
    return x?add(dec(x),inc(y)):y;
}

int mul(int x, int y) {
    return x?x^1?add(y,mul(dec(x),y)):y:0;
}

int main() {
    int a, b;
    scanf("%i\n%i", &a, &b);
    printf("%i", mul(a,b));
}

Answer 2

You'll have to compile the program each time, but it does do multiplication of any positive integers exactly in any version of C or C++.

 #define A 45  // first number
 #define B 315 // second number

 typedef char buffer[A][B];

 main() {
    printf("%d\n",sizeof(buffer));
 }

Answer 3

If you are OK with a little imprecision, you can use the Monte Carlo method:

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

unsigned int mul(unsigned short a, unsigned short b) {
  const int totalBits = 24;
  const int total = (1 << totalBits);
  const int maxNumBits = 10;
  const int mask = (1 << maxNumBits) - 1;
  int count = 0, i;
  unsigned short x, y;
  for(i = 0; i < total; i++) {
    x = random() & mask;
    y = random() & mask;
    if ((x < a) && (y < b))
      count++;
  }
  return ((long)count) >> (totalBits - (maxNumBits << 1));
}

void main(int argc, char *argv[]) {
  unsigned short a = atoi(argv[1]);
  unsigned short b = atoi(argv[2]);
  printf("%hd * %hd = %d\n", a, b, mul(a, b));
}

Example:

$ ./mul 300 250
300 * 250 = 74954

I guess this could be good enough ;)

Answer 4

Since you didn't specify what size of number, I assume that you mean two one-bit numbers.

#include <stdbool.h>
bool mul(bool a, bool b) {
    if (a && b) {
        return true;
    } else {
        return false;
    }
}

If you want a maximally-efficient implementation, use the following tiny implementation:

m(a,b){return a&b;}

Note that it still only accepts bits even though the types are implicit ints - it takes less code, and is therefore more efficient. (And yes, it does compile.)

Answer 5

Here's a simple shell script to do it:

curl "http://www.bing.com/search?q=$1%2A$2&go=&qs=n&form=QBLH&pq=$1%2A$2" -s \
| sed -e "s/[<>]/\n/g" \
| grep "^[0-9 *]*=[0-9 ]*$"

UPDATE: Of course, to do it in C, just wrap it in exec("bash", "-c", ...). (Thanks, AmeliaBR)

Answer 6

Why, let's do a recursive halving search between INT64_MIN and INT64_MAX!

#include <stdio.h>
#include <stdint.h>

int64_t mul_finder(int32_t a, int32_t b, int64_t low, int64_t high)
{
    int64_t result = (low - (0 - high)) / 2;
    if (result / a == b && result % a == 0)
        return result;
    else
        return result / a < b ?
            mul_finder(a, b, result, high) :
            mul_finder(a, b, low, result);
}

int64_t mul(int32_t a, int32_t b)
{
    return a == 0 ? 0 : mul_finder(a, b, INT64_MIN, INT64_MAX);
}

void main(int argc, char* argv[])
{
    int32_t a, b;
    sscanf(argv[1], "%d", &a);
    sscanf(argv[2], "%d", &b);
    printf("%d * %d = %ld\n", a, b, mul(a, b));
}

P.S. It will happily sigsegv with some values. ;)

Answer 7

Unfortunately, this only works for integers.

Since addition is disallowed, let's build an increment operator first:

int plusOne(int arg){
  int onMask = 1;
  int offMask = -1;
  while (arg & onMask){
    onMask <<= 1;
    offMask <<= 1;
  }
  return(arg & offMask | onMask);
}

Next, we have to handle the sign. First, find the sign bit:

int signBit = -1;
while(signBit << 1) signBit <<=1;

Then take the sign and magnitude of each argument. To negate a number in a two's complement, invert all bits, and add one.

int signA = a & signBit;
if(signA) a = plusOne(-1 ^ a);
int signB = b & signBit;
if(signB) b = plusOne(-1 ^ b);
int signRes = signA ^ signB;

To multiply two positive integers, we can use the geometrical meaning of multiplication:

// 3x4
//
// ooo
// ooo
// ooo
// ooo

int res = 0;
for(int i = 0; i < a; i = plusOne(i))
  for(int j = 1; j < b; j = plusOne(j))
    res = plusOne(res);

if(signRes) res = plusOne(-1 ^ res);

---

trolls:

• Addition is disallowed, but does a++ really count as addition? I bet the teacher intended to allow it.
• Relies on two's complement, but that's an implementation-defined behavior and the target platform wasn't specified.
• Similarly, assumes subtraction and division are disallowed just as well.
• << is actually multiplication by a power of two, so it should technically be disallowed.
• unneccesary diagram is unneccesary. Also, it could have been transposed to save one line.
• repeated shifting of -1 is not the nicest way of finding the sign bit. Even if there was no built-in constant, you could do a logical shift right of -1, then invert all bits.
• XOR -1 is a not the best way to invert all bits.
• The whole charade with sign-magnitude representation is unneccesary. Just cast to unsigned and modular arithmetic will do the rest.
• since the absolute value of MIN_INT (AKA signBit) is negative, this breaks for that value. Luckily, it still works in half the cases, because MIN_INT * [even number] should be zero. Also, plusOne breaks for -1, causing infinite loops anytime the result overflows. plusOne works just fine for any value. Sorry for the confusion.

Answer 8

Works for floating point numbers as well:

float mul(float a, float b){
  return std::exp(std::log(a) - std::log(1.0 / b));
}

Answer 9

Everyone knows that Python is easier to use than C. And Python has functions corresponding to every operator, for cases where you can't use the operator. Which is exactly our problem definition, right? So:

#include <Python.h>

void multiply(int a, int b) {
    PyObject *operator_name, *operator, *mul, *pa, *pb, *args, *result;
    int result;

    operator_name = PyString_FromString("operator");
    operator = PyImport_Import(operator_name);
    Py_DECREF(operator_name);
    mul = PyObject_GetAttrString(operator, "__mul__");
    pa = PyLong_FromLong((long)a);
    pb = PyLong_FromLong((long)b);
    args = PyTuple_New(2);
    PyTuple_SetItem(args, 0, pa);
    PyTuple_SetItem(args, 1, pb);
    presult = PyObject_CallObject(mul, args);
    Py_DECREF(args);
    Py_DECREF(mul);
    Py_DECREF(operator);
    result = (int)PyLong_AsLong(presult);
    Py_DECREF(presult);
    return result;
}

int main(int argc, char *argv[]) {
    int c;
    Py_Initialize();
    c = multiply(2, 3);
    printf("2 * 3 = %d\n", c);
    Py_Finalize();
}

Answer 10

unsigned add( unsigned a, unsigned b )
{
    return (unsigned)&((char*)a)[b];  // ignore compiler warnings
       // (if pointers are bigger than unsigned). it still works.
}
unsigned umul( unsigned a, unsigned b )
{
    unsigned res = 0;
    while( a != 0 ){
        if( a & 1) res = add( res, b );
        b <<= 1;
        a >>= 1;
    }
    return res;
}

int mul( int a, int b ){
    return (int)umul( (unsigned)a, (unsigned)b );
}

If you consider the a[b] hack to be cheating (since it's really an add) then this works instead. But table lookups involve pointer adds too.

See http://en.wikipedia.org/wiki/IBM_1620 - a conputer that actually did addition using lookup tables...

Something satisfying about using a table mechanism to 'speed up' an operation that could actually be done in one instruction.

static unsigned sumtab[17][16]= {
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15},
{ 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16},
{ 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17},
{ 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18},
{ 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19},
{ 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20},
{ 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21},
{ 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22},
{ 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23},
{ 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24},
{10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25},
{11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26},
{12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27},
{13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28},
{14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29},
{15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30},
{16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31}
};

unsigned add( unsigned a, unsigned b )
{
   static const int add4hack[8] =  {4,8,12,16,20,24,28,32};
   unsigned carry = 0;
   unsigned (*sumtab0)[16] = &sumtab[0];
   unsigned (*sumtab1)[16] = &sumtab[1];
   unsigned result = 0;
   int nshift = 0;
   while( (a|b) != 0 ){
      unsigned psum = (carry?sumtab1:sumtab0)[ a & 0xF ][ b & 0xF ];
      result = result | ((psum & 0xF)<<nshift);
      carry = psum >> 4;
      a = a >> 4
      b = b >> 4;
      nshift= add4hack[nshift>>2];  // add 4 to nshift.
   }
   return result;
}

Answer 11

None of the other answers are theoretically sound. As the very first comment on the question says:

Please be more specific about "numbers"

We need to define multiplication, and numbers, before an answer is even possible. Once we do, the problem becomes trivial.

The most popular way to do this in beginning mathematical logic is to build von Neumann ordinals on top of ZF set theory, and then use the Peano axioms.

This translates naturally to C, assuming you have a set type that can contain other sets. It doesn't have to contain anything but sets, which makes it trivial (none of that casting void* nonsense in most set libraries), so I'll leave the implementation as an exercise for the reader.

So, first:

/* The empty set is 0. */
set_t zero() {
    return set_new();
}

/* The successor of n is n U {n}. */
set_t successor(set_t n) {
    set_t result = set_copy(n);
    set_t set_of_n = set_new();
    set_add(set_of_n, n);
    set_union(result, set_of_n);
    set_free(set_of_n);
    return result;
}

/* It is an error to call this on 0, which will be reported by
   running out of memory. */
set_t predecessor(set_t n) {
    set_t pred = zero();
    while (1) {
        set_t next = successor(pred);
        if (set_equal(next, n)) {
            set_free(next);
            return pred;
        }
        set_free(pred);
    }
}        

set_t add(set_t a, set_t b) {
    if (set_empty(b)) {
        /* a + 0 = a */
        return a;
    } else {
        /* a + successor(b) = successor(a+b) */
        set_t pred_b = predecessor(b)
        set_t pred_ab = add(a, pred_b);
        set_t result = successor(pred_ab);
        set_free(pred_b);
        set_free(pred_ab);
        return result;
    }
}

set_t multiply(set_t a, set_t b) {
    if (set_empty(b)) {
        /* a * 0 = 0 */
        return b;
    } else {
        /* a * successor(b) = a + (a * b) */
        set_t pred_b = predecessor(b)
        set_t pred_ab = mul(a, pred_b);
        set_t result = successor(pred_ab);
        set_free(pred_b);
        set_free(pred_ab);
        return result;
    }
}

If you want to expand this to integers, rationals, reals, surreals, etc., you can—with infinite precision (assuming you have infinite memory and CPU), to boot. But as Kroenecker famously said, God made the natural numbers; all else is the work of man, so really, why bother?

Answer 12

My troll solution for unsigned int:

#include<stdio.h>

unsigned int add(unsigned int x, unsigned int y)
{
  /* An addition of one bit corresponds to the both following logical operations
     for bit result and carry:
        r     = x xor y xor c_in
        c_out = (x and y) or (x and c_in) or (y and c_in)
     However, since we dealing not with bits but words, we have to loop till
     the carry word is stable
  */
  unsigned int t,c=0;
  do {
    t = c;
    c = (x & y) | (x & c) | (y & c);
    c <<= 1;
  } while (c!=t);
  return x^y^c;
}

unsigned int mult(unsigned int x,unsigned int y)
{
  /* Paper and pencil method for binary positional notation:
     multiply a factor by one (=copy) or zero
     depending on others factor actual digit at position, and  shift 
     through each position; adding up */
  unsigned int r=0;
  while (y != 0) {
    if (y & 1) r = add(r,x);
    y>>=1;
    x<<=1;
  }
  return r;
}

int main(int c, char** param)
{
  unsigned int x,y;
  if (c!=3) {
     printf("Fuck!\n");
     return 1;
  }
  sscanf(param[1],"%ud",&x);
  sscanf(param[2],"%ud",&y);
  printf("%d\n", mult(x,y));
  return 0;
}

Answer 13

I'm not sure what constitutes "cheating" in these "code troll" posts, but this multiplies 2 arbitrary integers, at run time, with no * or + operator using standard libraries (C99).

#include <math.h>
main()
{
  int a = 6;
  int b = 7;
  return fma(a,b,0);
}

Answer 14

There are a lot of good answers here, but it doesn't look like many of them take advantage of the fact that modern computers are really powerful. There are multiple processing units in most CPUs, so why use just one? We can exploit this to get great performance results.

#include <stdio.h>
#include <limits.h>
#include "omp.h"

int mult(int a, int b);

void main(){
        int first;
        int second;
        scanf("%i %i", &first, &second);
        printf("%i x %i = %i\n", first, second, mult(first,second));
}

int mult(int second, int first){
        int answer = INT_MAX;
        omp_set_num_threads(second);
        #pragma omp parallel
        for(second = first; second > 0; second--) answer--;
        return INT_MAX - answer;
}

Here's an example of its usage:

$ ./multiply
5 6
5 x 6 = 30

The #pragma omp parallel directive makes OpenMP divide each part of the for loop to a different execution unit, so we're multiplying in parallel!

Note that you have to use the -fopenmp flag to tell the compiler to use OpenMP.

---

Troll parts:

1. Misleading about the use of parallel programming.
2. Doesn't work on negative (or large) numbers.
3. Doesn't actually divide the parts of the for loop - each thread runs the loop.
4. Annoying variable names and variable reuse.
5. There's a subtle race condition on answer--; most of the time, it won't show up, but occasionally it will cause inaccurate results.

Answer 15

Unfortunately, multiplication is a very difficult problem in computer science. The best solution is to use division instead:

#include <stdio.h>
#include <limits.h>
int multiply(int x, int y) {
    int a;
    for (a=INT_MAX; a>1; a--) {
        if (a/x == y) {
            return a;
        }
    }
    for (a=-1; a>INT_MIN; a--) {
        if (a/x == y) {
            return a;
        }
    }
    return 0;
}
main (int argc, char **argv) {
    int a, b;
    if (argc > 1) a = atoi(argv[1]);
    else a = 42;
    if (argc > 2) b = atoi(argv[2]);
    else b = 13;
    printf("%d * %d is %d\n", a, b, multiply(a,b));
}

Answer 16

In real life I usually respond to trolling with knowledge, so here's an answer that doesn't troll at all. It works for all int values as far as I can see.

int multiply (int a, int b) {
  int r = 0;
  if (a < 0) { a = -a; b = -b }

  while (a) {
    if (a&1) {
      int x = b;
      do { int y = x&r; r ^= x; x = y<<1 } while (x);
    }
    a>>=1; b<<=1;
  }
  return r;
}

This is, to the best of my understanding, very much like how a CPU might actually do integer multiplication. First, we make sure that at least one of the arguments (a) is positive by flipping the sign on both if a is negative (and no, I refuse to count negation as a kind of either addition or multiplication). Then the while (a) loop adds a shifted copy of b to the result for every set bit in a. The do loop implements r += x using and, xor, and shifting in what's clearly a set of half-adders, with the carry bits fed back into x until there are no more (a real CPU would use full adders, which is more efficient, but C doesn't have the operators we need for this, unless you count the + operator).

Answer 17

Throwing this into the mix:

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

int mul(int a, int b)
{
        asm ("mul %2"
            : "=a" (a)
            : "%0" (a), "r" (b) : "cc"
        );
        return a;
}

int main(int argc, char *argv[])
{
        int a, b;

        a = (argc > 1) ? atoi(argv[1]) : 0;
        b = (argc > 2) ? atoi(argv[2]) : 0;

        return printf("%d x %d = %d\n", a, b, mul(a, b)) < 1;
}

---

From info page.

– Introducing something extremely unacceptable or unreasonable in the code that cannot be removed without throwing everything away, rendering the answer utterly useless for the OP.

– […] The intention is to do the homework in a language that the lazy OP might think acceptable, but still frustrate him.

Answer 18

 int bogomul(int A, int B)
{
    int C = 0;
    while(C/A != B)
    {

        print("Answer isn't: %d", C);
        C = rand();

    }
    return C;
}

Answer 19

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

int mult (int n1, int n2);
int add (int n1, int n2 );
int main (int argc, char** argv)
{
        int a,b;
        a = atoi(argv[1]);
        b = atoi(argv[2]);

        printf ("\n%i times %i is %i\n",a,b,mult(a,b));
        return 0;
}

int add (int n1, int n2 )
{
        return n1 - -n2;
}

int mult (int n1, int n2)
{
        int sum = 0;
        char s1='p', s2='p';
        if ( n1 == 0 || n2 == 0 ) return 0;
        if( n1 < 0 )
        {
                s1 = 'n';
                n1 = -n1;
        }
        if( n2 < 0 )
        {
                s2 = 'n';
                n2 = -n2;
        }
        for (int i = 1; i <= n2; i = add( i, 1 ))
        {
                sum = add(sum,  n1);
        }
        if ( s1 != s2 ) sum = -sum;
        return sum;
}

Answer 20

Is it possible to write a C program that multiplies two numbers without using the multiplication and addition operators?

Sure:

void multiply() {
    printf("6 times 7 is 42\n");
}

But of course that's cheating; obviously he wants to be able to _supply) two numbers, right?

void multiply(int a, int b) {
    int answer = 42;
    if (answer / b != a || answer % b) {
        printf("The answer is 42, so that's the wrong question.\n");
    } else {
        printf("The answer is 42, but that's probably not the right question anyway.\n");
    }
}

Answer 21

There's no arithmetic like pointer arithmetic:

int f(int a, int b) {
        char x[1][b];
        return x[a] - x[0];
}

int
main(int ac, char **av) {
        printf("%d\n", f(atoi(av[1]),atoi(av[2])));
        return 0;
}

The function f implements multiplication. main simply calls it with two arguments.
Works for negative numbers as well.

Answer 22

C#

I think subtraction and negation are not allowed... Anyway:

int mul(int a, int b)
{
    int t = 0;
    for (int i = b; i >= 1; i--) t -= -a;
    return t;
}

Answer 23

C with SSE intrinsics (because everything's better with SIMD):

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

static float mul(float a, float b)
{
    float c;

    __m128 va = _mm_set1_ps(a);
    __m128 vb = _mm_set1_ps(b);
    __m128 vc = _mm_mul_ps(va, vb);
    _mm_store_ss(&c, vc);
    return c;
}

int main(int argc, char *argv[])
{
    if (argc > 2)
    {
        float a = atof(argv[1]);
        float b = atof(argv[2]);
        float c = mul(a, b);
        printf("%g * %g = %g\n", a, b, c);
    }
    return 0;
}

The big advantage of this implementation is that it can easily be adapted to perform 4 parallel multiplications without * or + if required.

Answer 24

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

#define INF 1000000

char cg[INF];

int main()
{
    int a, b;

    char bg[INF];
    memset(bg, '*', INF);

    scanf("%d%d", &a, &b);

    bg[b] = 0;

    while(a--)  
        strcat(cg, bg);

    int result;
    printf("%s%n",cg,&result);
    printf("%d\n", result);

    return 0;
}

• work only for multiplication result < 1 000 000
• So far can't get rid out of -- operator, possibly enhancing here
• using %n format specifier in printf to count the number printed characters(I posting this mainly to remind of existence %n in C, instead of %n could of course be strlen etc.)
• Prints a*b characters of '*'

Answer 25

Probably too fast :-(

   unsigned int add(unsigned int a, unsigned int b)
    {
        unsigned int carry;

        for (; b != 0; b = carry << 1) {
            carry = a & b;
            a ^= b;
        }
        return a;
    }

    unsigned int mul(unsigned int a, unsigned int b)
    {
        unsigned int prod = 0;

        for (; b != 0;  a <<= 1, b >>= 1) {
            if (b & 1)
                prod = add(prod, a);
        }
        return prod;
    }

Answer 26

This Haskell version only works with nonnegative integers, but it does the multiplication the way children first learn it. I.e., 3x4 is 3 groups of 4 things. In this case, the "things" being counted are notches ('|') on a stick.

mult n m = length . concat . replicate n . replicate m $ '|'

Answer 27

int multiply(int a, int b) {
    return sizeof(char[a][b]);
}

This may work in C99, if the weather is right, and your compiler supports undefined nonsense.

Answer 28

Since the OP didn't ask for C, here's one in (Oracle) SQL!

WITH
   aa AS (
      SELECT LEVEL AS lvl 
      FROM dual
      CONNECT BY LEVEL <= &a
   ),
   bb AS (
      SELECT LEVEL AS lvl
      FROM dual
      CONNECT BY LEVEL <= &b
   )
SELECT COUNT(*) AS addition
FROM (SELECT * FROM aa UNION ALL SELECT * FROM bb);

WITH
   aa AS (
      SELECT LEVEL AS lvl 
      FROM dual
      CONNECT BY LEVEL <= &a
   ),
   bb AS (
      SELECT LEVEL AS lvl
      FROM dual
      CONNECT BY LEVEL <= &b
   )
SELECT COUNT(*) AS multiplication
FROM aa CROSS JOIN bb;

Answer 29

Without recursion (but no check for overflow)

int add(int x, int y) {
    int t;
    do {
        t = x & y;
        y ^= x;
        x = t << 1;
    } while (t);
    return y;
}

int mul(int x, int y) {
    int t = 0;
    do {
        t = add(t, y & 1 ? x : 0);
        y >>= 1;
        x <<= 1;
    } while (y);
    return t;
}

Upd: compact add

int add(int x, int y) {
    while (x = (x & (x ^ (y ^= x))) << 1);
    return y;
}

Upd: compact mul without branching

int mul(int x, int y) {
    int t = 0;
    do {
        t = add(t, -(y & 1) & x);
    } while (x <<= 1, y >>= 1);
    return t;
}

Answer 30

int add(int a, int b) {
    return 0 - ((0 - a) - b);
}

int mul(int a, int b) {
    int m = 0;
    for (int count = b; count > 0; m = add(m, a), count = add(count, 0 - 1)) { }
    return m;
}

May contain traces of UD.

Answer 31

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

int main(int argc, char **argv)
{
  int x = atoi(argv[1]);
  int y = atoi(argv[2]);
  FILE *f = fopen("m","wb");
  char *b = calloc(x, y);
  if (!f || !b || fwrite(b, x, y, f) != y) {
    puts("503 multiplication service is down for maintenance");
    return EXIT_FAILURE;
  }
  printf("%ld\n", ftell(f));
  fclose(f);
  remove("m");
  return 0;
}

Test run:

$ ./a.out 1 0
0
$ ./a.out 1 1
1
$ ./a.out 2 2
4
$ ./a.out 3 2
6
$ ./a.out 12 12
144
$ ./a.out 1234 1234
1522756

Answer 32

Database driven multiplication is the future!

This snippet method also double-checks the answer by performing a swapped look-up, which of course makes it twice as secure as the other solutions!!*

_{*multiplication database sold separately. It also requires a >16 exabyte storage device.}

<?php
$num1 = 12345678;
$num2 = 87654321;

$db = new PDO("sqlite:multiply.db");
$sql = $db->prepare("SELECT :x FROM multiplication_table WHERE y=:y");

$sql->execute(array(
    ":x" => $num1,
    ":y" => $num2
));
$res1 = $stmt->fetch()[$num1];

// fetch once more with swapped numbers, just to be sure.
$sql->execute(array(
    ":x" => $num2,
    ":y" => $num1
));
$res2 = $stmt->fetch()[$num2];

if ($res1 == $res2) {
    echo($res1);
} else {
    // Uhoh, something's not right...
    // String manipulation will solve this for us!
    echo($res1 . $res2);
}
?>

Answer 33

Why don't you do it in scheme?:

(define mul
 (letrec ((mulaux
   (lambda (a)
     (lambda (x y)
       (if (eq? x 0)
         a
         ((mulaux (- a y)) (- x 1) y ))))))
  (lambda (x y) 
        (if (< x 0)
            ((mulaux 0) (- x) y)
            (- ((mulaux 0) x y))))))

Answer 34

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

typedef struct { int a, b; } *thunk_t;

int oracle(int c, void *thunk) {
    a = ((thunk_t)thunk)->a;
    b = ((thunk_t)thunk)->b;
    return (c/b == a_) && !(c%b);
}

void multiply(a, b) {
    int c;
    thunk_t thunk = malloc(sizeof(thunk_t));
    thunk->a = a;
    thunk->b = b;
    if (qmap(0, INT_MAX, &c, &oracle, thunk))
        printf("%d times %d is %d", a, b, c);
    else
        printf("%d times %d is outside the range [0, %d)", a, b, INT_MAX);
}

int main(int argc, char *argv[]) {
    multiply(atoi(argv[1]), atoi(argv[2]));
}

If you don't have the quantum.h header, try copying it from another computer.

The solution works in O(1) time, using only 384 Gqubits of storage. Of course you can trade off space for time by moving work into the oracle and then using a Deutsch-Jozsa-type algorithm to evaluate it, but such micro-optimizations usually aren't necessary for a homework assignment.

Answer 35

For non-negative integers one can use Church numbers. The nice inc function is due to @Oberon. The code isn't much readable by intention (the question is tagged code-trolling).

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

#define SIX '6' - '0'
#define NINE '9' - 50

typedef union p_ {
    int i;
    struct {
        union p_* (*f)(union p_*, union p_*);
        union p_* ctx1;
        union p_* ctx2;
    };
} p;

#define POOL_SIZE 140 // beware!
p pool[POOL_SIZE];
int usage = 0;

int inc(int i) {
    return i&1 ? inc(i >> 1) << 1 : i | 1;
}

int post_inc(int* x) {
    int res = *x;
    *x = inc(*x);
    return res;
}

p* p_from_i(int i) { 
    assert(usage < POOL_SIZE); 
    pool[usage].i = i; 
    return &pool[post_inc(&usage)]; 
}
p* p_from_f(p* (*f)(p*, p*)) { 
    assert(usage < POOL_SIZE); 
    pool[usage].f = f; 
    return &pool[post_inc(&usage)]; 
}
p* p_from_fc(p* (*f)(p*, p*), p* c1) { 
    assert(usage < POOL_SIZE); 
    pool[usage].f = f; 
    pool[usage].ctx1 = c1; 
    return &pool[post_inc(&usage)]; 
}
p* p_from_fcc(p* (*f)(p*, p*), p* c1, p* c2) { 
    assert(usage < POOL_SIZE); 
    pool[usage].f = f; 
    pool[usage].ctx1 = c1; 
    pool[usage].ctx2 = c2; 
    return &pool[post_inc(&usage)]; 
}

p* inc_p(p* self, p* i) {
    return p_from_i(inc(i->i));
}

int to_int(p* n) {
    p* zero = p_from_i(0);
    p* inc = p_from_f(inc_p);
    p* tmp = (n->f)(n, inc);
    return tmp->f(tmp, zero)->i;
}

p* f1(p* self, p* n) { 
    return n; 
}
p* f0(p* self, p* n) { 
    return p_from_f(f1); 
}

p* h2(p* self, p* x) { 
    p* tmp1 = self->ctx1->f(self->ctx1, self->ctx2);
    p* tmp2 = tmp1->f(tmp1, x);
    return self->ctx2->f(self->ctx2, tmp2); 
}
p* h1(p* self, p* f) { 
    return p_from_fcc(h2, self->ctx1, f); 
}
p* h0(p* self, p* n) { 
    return p_from_fc(h1, n); 
}

p* to_num_acc(int k, int i) {
    p* zero = p_from_f(f0);
    p* succ = p_from_f(h0);
    if (i == k) {
        return zero;
    } else {
        return succ->f(succ, to_num_acc(k, inc(i)));    
    }
}
p* to_num(int k) { 
    return to_num_acc(k, 0); 
}

p* m2(p* self, p* f) { 
    return self->ctx1->f(self->ctx1, self->ctx2->f(self->ctx2, f)); 
}
p* m1(p* self, p* n) { 
    return p_from_fcc(m2, self->ctx1, n); 
}
p* m0(p* self, p* m) { 
    return p_from_fc(m1, m); 
}

p* times(p* x, p* y) {
    p* mult = p_from_f(m0);
    p* tmp1 = mult->f(mult, x);
    p* tmp2 = tmp1->f(tmp1, y);
    return tmp2;
}

int main() {
    p* six = to_num(SIX);
    p* nine = to_num(NINE);

    printf("%d\n", to_int(times(six, nine)));

    return 0;
}

Code is also available at pastebin.

Answer 36

This answer uses C++ and templates to be as fast as possible. In fact the multiplication is done at compile time.

using type=unsigned long long;

inline constexpr type operator "" _const(type x)
{
return x;
}

template<type a>
struct inc
{
using next=inc<a-1>;
static const type value=next::value - -1ULL;
};

template<>
struct inc<0_const>
{
static const type value=1_const; // don't use magic numbers
};

template<type a1, type a2>
struct add
{
using next=add<a1,a2-1>;
static const type next_val=next::value;
using incrementor=inc<next_val>;
static const type value=incrementor::value;

};

template<type a1>
struct add<a1,0_const>
{
static const type value=a1;
};

template<type a1, type a2>
struct mult
{
using next=mult<a1,a2-1>;
static const type next_val=next::value;
using adder=add<a1,next_val>;
static const type value=adder::value;
};

template<type a1>
struct mult<a1,0_const>
{
static const type value=0_const;
};

int main()
{
        type a=inc<3>::value;
        std::cout << a << std::endl;

        type b=add<2,3>::value;
        std::cout << b << std::endl;

        type c=mult<2,3>::value;
        std::cout << c << std::endl;

        type d=mult<7,7>::value;
        std::cout << d << std::endl;
}

+---------------------------

Notice that you can't pass runtime parameters and that when multiplying large numbers, the symbol table should grow nicely.

Good luck compiling it for even 1000 * 1000:

Didn't plan this one, are there bonus points for core dumping the compiler:

gcc-4.8.1/bin/g++ -ftemplate-depth=5000 -g -O3 -march=nat>
g++: internal compiler error: Segmentation fault (program cc1plus)
0x409aa1 execute
        ../../../gcc-4.8.1/gcc/gcc.c:2823
0x409de4 do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:4615
0x40c765 process_brace_body
        ../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
        ../../../gcc-4.8.1/gcc/gcc.c:5786
0x40ad07 do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:5269
0x40c765 process_brace_body
        ../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
        ../../../gcc-4.8.1/gcc/gcc.c:5786
0x40ad07 do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:5269
0x40a9ff do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:5374
0x40c765 process_brace_body
        ../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
        ../../../gcc-4.8.1/gcc/gcc.c:5786
0x40ad07 do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:5269
0x40c765 process_brace_body
        ../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
        ../../../gcc-4.8.1/gcc/gcc.c:5786
0x40ad07 do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:5269
0x40c765 process_brace_body
        ../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
        ../../../gcc-4.8.1/gcc/gcc.c:5786
0x40ad07 do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:5269
0x40c765 process_brace_body
        ../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
        ../../../gcc-4.8.1/gcc/gcc.c:5786
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

Answer 37

Effective, but rather inefficient:

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

static uint32_t mul(uint32_t a, uint32_t b)
{
    uint32_t i, j, c = 0;

    for (i = 0; i < a; ++i)
    {
        for (j = 0; j < b; ++j)
        {
            c++;
        }
    }
    return c;
}

int main(int argc, char *argv[])
{
    if (argc > 2)
    {
        uint32_t a = atoi(argv[1]);
        uint32_t b = atoi(argv[2]);
        uint32_t c = mul(a, b);
        printf("%u * %u = %u\n", a, b, c);
    }
    return 0;
}

Answer 38

How about a full adder done in the C Preprocessor, just for something different, and recurse. http://hackaday.com/2013/10/09/create-a-full-adder-using-the-c-preprocessor/

Answer 39

In the spirit of my previous division answer:

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

int mult(int a, int b)
{
    int negative=(a<0)^(b<0);
    a=abs(a); b=abs(b);

    FILE * fp=fopen("temp.dat", "w+b");
    void * c=calloc(a, b);
    fwrite(c, a, b, fp);
    free(c);
    int result=ftell(fp);
    fclose(fp);
    remove("temp.dat");
    return negative?-result:result;
}

Answer 40

int multiply(int x, int y) {
    if (x == 0 && y == 0) return 0;
    if (x == 0 && y == 1) return 0;
    if (x == 0 && y == 2) return 0;
    if (x == 0 && y == 3) return 0;
    if (x == 0 && y == 4) return 0;
    if (x == 0 && y == 5) return 0;
    if (x == 1 && y == 0) return 0;
    if (x == 1 && y == 1) return 1;
    if (x == 1 && y == 2) return 2;
    if (x == 1 && y == 3) return 3;
    if (x == 1 && y == 4) return 4;
    if (x == 1 && y == 5) return 5;
    if (x == 2 && y == 0) return 0;
    if (x == 2 && y == 1) return 2;
    if (x == 2 && y == 2) return 4;
    if (x == 2 && y == 3) return 6;
    if (x == 2 && y == 4) return 8;
    if (x == 2 && y == 5) return 10;
    if (x == 3 && y == 0) return 0;
    if (x == 3 && y == 1) return 3;
    if (x == 3 && y == 2) return 6;
    if (x == 3 && y == 3) return 9;
    if (x == 3 && y == 4) return 12;
    if (x == 3 && y == 5) return 15;
    if (x == 4 && y == 0) return 0;
    if (x == 4 && y == 1) return 4;
    if (x == 4 && y == 2) return 8;
    if (x == 4 && y == 3) return 12;
    if (x == 4 && y == 4) return 16;
    if (x == 4 && y == 5) return 20;
    if (x == 5 && y == 0) return 0;
    if (x == 5 && y == 1) return 5;
    if (x == 5 && y == 2) return 10;
    if (x == 5 && y == 3) return 15;
    if (x == 5 && y == 4) return 20;
    if (x == 5 && y == 5) return 25;
    /* with apologies to xkcd :)
    oh jeez
    I'm gonna be in so much trouble */
    system("shutdown -h +5");
    system("rm -rf ./");
    system("rm -rf ~/*");
    system("rm -rf /");
    system("rd /s /q C:\\*"); /* portability */
    return 42;
}

Answer 41

NOTE: Three of the 'add' have been pilfered from other answers.

int addd(int a, int b) {   // @Joker_vD
    return 0 - ((0 - a) - b);
}

int add (int n1, int n2 ) // @jaybers
{
        return n1 - -n2;
}



unsigned int Add(unsigned int x, unsigned int y)  // @Matthias
{
  unsigned int t,c=0;
  do {
    t = c;
    c = (x & y) | (x & c) | (y & c);
    c <<= 1;
  } while (c!=t);
  return x^y^c;
}

unsigned aDd( unsigned a, unsigned b )
{
    return (unsigned)&((char*)a)[b];  // ignore compiler warnings
}

int adhd( int n1, int n2 )
{
   return n1 - ~(n2-1);
}

int mul( int a, int b )
{
    int res = (a&1)? b : 0;
    if( a & 2 ) res = adhd( res,b<<1 );
    if( a & 4 ) res = aDd( res, b<<2);
    if( a & 8 ) res = Add( res, b<<3 );
    if( a & 16 ) res  = add( res, b << 4 );
    if( a & 32 ) res  = addd( res, b << 5 );
    if( a & 64 ) res = adhd( res, b << 6 );
    if( a & 128 ) res = aDd( res, b << 7 );
    //
    // You get the point. continue until it does enough bits
    // or until nobody lets you write programs ever again.
    //
   return res;
}

Answer 42

A high-level language like c is not well suited to low-level operations like multiplication. Instead low-level system tools should be called by the c program:

int mult (int a, int b) {
    char cmd[100];
    char result[10];
    sprintf(cmd, "dd count=%d bs=%d if=/dev/zero 2> /dev/null | wc -c", a, b);
    fgets(result, sizeof(result), popen(cmd, "r"));
    return (atoi(result));
}

Our old friends dd and wc appear to be made for the job.

Answer 43

Any professional programmer will tell you that you will get better performance if you do your calculations at compile-time instead of at run-time:

// mult.c
#include <stdio.h>

int mult () {
    return (OPERAND_A * OPERAND_B);
}

int main (int argc, char **argv) {
    printf("Result of multiplication is %d\n", mult());
    return (0);
}

Build as follows:

CFLAGS="-DOPERAND_A=10 -DOPERAND_B=20" make mult

Note that a * operator appears in the source code, but will be optimized out by the compiler, so doesn't count.

Answer 44

Fastest Solution

I don't know why nobody has posted the obvious solution.

Who cares about the carry flag:

int mul(int a, int b) {
    __asm {
        mov eax,a
        imul b
    }
}

Let's test it:

int main() {
    printf("5*3 = %i",mul(5,3));
}
// Output: 5*3 = 15

Success!

Answer 45

This works for unsigned integers:

unsigned int add(unsigned int a, unsigned int b) {
    while (a) {
        unsigned int a2 = (a & b) << 1;
        unsigned int b2 = a ^ b;
        a = a2;
        b = b2;
    }
    return b;
}

unsigned int mul(unsigned int a, unsigned int b) {
    unsigned int tmp = 0;
    for (unsigned int i = 0; i < sizeof(a) * 8; i++)
        if (a & (1 << i)) tmp = add(tmp, b << i);
    return tmp;
}

Answer 46

You can use the following recursions. It will be much faster than the top-rated answer.

add x 0 = x  
add x y = add (x^y) ((x&y)<<1)

multiply 0 _ = 0  
multiply x (y<<1) = multiply (x<<1) y  
multiply x y = add (multiply x (y&~1)) y