Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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 question. Please do not take the question and/or answers seriously. More information is in code-trolling.

share

locked by Doorknob 冰 May 10 at 16:49

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site, so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. More info: help center.

2  
@PaulR use your fantasy –  Jan Dvorak Jan 11 at 17:03
26  
Code-golf.SE should not be a place for you to mock questions you've seen on StackOverflow. –  Gareth Jan 11 at 19:40
17  
@Gareth, are you sure? The first line of this suggests this may be quite appropriate. –  Darren Stone Jan 11 at 20:27
5  
I´m waiting for someone write an algorithm based on sleep –  kbsou Jan 12 at 2:11
21  
This question isn't as ridiculous as it sounds. Actual computer hardware (transistors) don't have multiply and add operations -- they have basic logic operations like NOT, AND, OR, XOR. Figuring out how to answer this question can give you excellent insight into how a computer really works at the level of logic gates. –  Gabe Jan 12 at 6:12

46 Answers 46

up vote 147 down vote accepted

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));
}
share
8  
I would give +3 if I could: one for the ultimate recursion, one for ??:: without parentheses, one for solving the problem without trying to tweak the rules ;) –  tohecz Jan 11 at 22:52
10  
If Picasso was a programmer... –  R Hughes Jan 12 at 6:29
4  
@SargeBorsch But where'd the fun be in that? –  Oberon Jan 12 at 16:06
3  
@HC_ The inc function tests its argument to see if the lowest bit is 1; if so, it calls itself on the remaining upper bits of the argument and returns the result with the same low bit that was checked being set to 0, while if not (i.e. the lowest bit is 0), it replaces that 0 with a 1 and returns the result. The process is very similar to what you'd do if you were adding the values by hand, binary digit by binary digit. –  JAB Jan 13 at 18:28
2  
Doesn't the increment function go into an infinite loop for -1? (0xFFFF) ideone shows (-1 >> 1) == -1. –  Destrictor Jan 15 at 9:33

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));
 }
share
4  
Put it inside a structure and you don't need memory. –  Ben Jackson Jan 12 at 0:54
4  
Hahahah great!! –  Almo Jan 12 at 8:26
1  
use "%zu" format string. –  Grijesh Chauhan Jan 13 at 7:30
5  
just sizeof(char[A][B]) will work (unless A<=0 or B <=0 or A*B overflows, in which case you should get a 'bad type' sort of error) –  greggo Jan 13 at 14:59
3  
@DavidRicherby - I could simplify the code to main(){return sizeof(char[A][B]);} and you compile using cc -DA=6 -DB=7 a.c; ./a.out; echo $? –  Mark Lakata Jan 13 at 22:48

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 ;)

share
3  
You have my up vote. I heard Monte Carlo is what NASA uses for its arithmetic. But I'd like to see this without the two instances of the ++ operator. –  Darren Stone Jan 11 at 18:28
1  
@DarrenStone -= -1 –  Timtech Jan 11 at 20:06
20  
@Timtech |= 1 (will work on 50% of numbers, 100% of the time) –  Darren Stone Jan 11 at 20:20
2  
+1, but noting that it could be too slow, and you could add multi-thread support, carefully locking the 'count++' :-) –  greggo Jan 13 at 15:01
1  
There's always printf increment : printf("%*cc%n\n", count, &count, 'c'); (Prints 'c' count times, then another 'c', and stores the number of characters written back in count. –  MSalters Jan 15 at 12:44

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.)

share
8  
Nice. A deliberate misinterpretation of the question :-) –  Jan Dvorak Jan 12 at 5:59
6  
You can optimize this to return a && b;. It’s shorter, so it’s faster. –  U2744 SNOWFLAKE Jan 12 at 18:10
1  
@minitech: I decided against that in order to make the code slightly worse. If I wanted to go further with that, I'd make it return a&b;. –  col6y Jan 12 at 20:11
1  
C has #include<stdbool.h> to define true and false. –  leewangzhong Jan 15 at 2:10
1  
Yeah, #include<stdbool.h> seems to just be three #defines that you can do yourself (true, false, bool, and a flag to mark that it's been activated). You can also take a trick from one of the other answers and use implicit int for the "short" version. –  leewangzhong Jan 15 at 15:19

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)

share
41  
I can't decide which is more awful. That you're outsourcing your calculation to a search engine, or that your chosen search engine is Bing. Unfortunately, I don't think this will work for our happless OP, who needed something in C. –  AmeliaBR Jan 12 at 1:40
5  
Thanks for catching that oversight. FYI, I'm using Bing because Google makes it more complicated to issue requests like this -- you have to add headers to convince Google your request is really coming from a browser. –  Vroo Jan 12 at 5:34
2  
@abarnert hmm... does Bing understand "times"? Wolfram Alpha might, though. –  Jan Dvorak Jan 13 at 10:57
2  
@JanDvorak: Yeah, Wolfram works. (Note the %20 to avoid using any + signs.) But you still need to parse the output (in C) to get the value out of it. Which will be especially tricky, since the output appears to be an image, not text. HTML parsing plus OCR might make that the best possible answer to this problem. –  abarnert Jan 13 at 12:48
3  
@JanDvorak: That's no fun. I was looking forward to someone writing a simple OCR library with no addition or multiplication… –  abarnert Jan 13 at 12:54

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. ;)

share

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.
share
    
+1 for an actual code troll: It looks like it should work, but it very likely will blow up on the OP and s/he'll have no idea why. –  Kevin Jan 11 at 22:26
1  
It's possible to do addition without ANY addition operators by just using shift, XOR and AND. All these ++'s are making my head hurt -- single bit ADD with carry is (x ^ y) | ((x & y) << 1) (modulo any errors caused by typing in this crappy little text box.) –  Julie in Austin Jan 12 at 1:25
    
@JulieinAustin yep. The algorithm is even more inefficient than it needs to be. Should I amend the troll list? :-) –  Jan Dvorak Jan 12 at 5:31
1  
@JulieinAustin (x ^ y) | ((x & y) << 1) doesn't quite work, it won't propagate carry when x or y and carry are both true in the same position :) –  hobbs Jan 12 at 6:10
    
@hobbs solution: instead of ORing, add them recursively if carry is non-zero. –  Jan Dvorak Jan 12 at 7:29

Works for floating point numbers as well:

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

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();
}
share

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?

share
1  
Wow. You're even slower than me. –  Jan Dvorak Jan 13 at 10:50
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;
}
share
    
Oops, there is * char (although it's not multiplication) –  Sarge Borsch Jan 12 at 8:37
    
Uh, table lookup uses addition -- (a[i]) is the same as (*(a + i)). –  Julie in Austin Jan 29 at 17:18
    
@JulieinAustin I mentioned that. Table lookup can be done without adds, by merging fields (as illustrated in the IBM 1620, see link) but it's messy to set that up in C - for one thing you need to align the table to a proper address so the indices can be just or'd in. –  greggo Mar 2 at 2:23

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);
}
share

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;
}
share
1  
+1 Nice implementation of carry evaluation. I like your code :) –  tohecz Jan 12 at 12:49
    
@BЈовић: My fault, I thought trolling is not about understandig. Changed names and added comments. –  Matthias Jan 13 at 10:57
    
sorry. I misunderstood what that tag is, and what the Q really is about. You should revert it –  BЈовић Jan 13 at 12:07
    
@Matthias in this case it's useful to understand how it works so that we can appreciate how twisted that converging-carry operation is. In an actual code-troll situation the comments could be redacted :-) –  greggo Jan 13 at 14:48
    
I'd like to point out that if you want to add bit-reversed numbers (with high to lo carry prop) and you don't have a 'bitrev' instruction, this is probably a perfectly reasonable approach (after changing to c>>=1 of course) –  greggo Jan 13 at 15:18

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.
share
2  
Why not combine this with Paul R's SIMD answer, so you can run 32x as fast instead of 8x? Although really, you want to get the GPU involved as well as the cores; then it would really blaze. :) –  abarnert Jan 13 at 11:06
2  
Might as well use OpenMPI to run it on a few machines in parallel. –  millinon Jan 13 at 11:22

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));
}
share

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).

share
4  
The asker didn't troll. You are supposed to troll. –  Jan Dvorak Jan 12 at 5:56
2  
It's a stealth troll! The secret failure is on a==INT_MIN. –  Jander Jan 13 at 6:17
1  
@Jander hmm. Yeah, that's a good one. I'm guessing (on ordinary two's complement systems) the result of negating a is still negative, and the while(a) loop never terminates. –  hobbs Jan 13 at 6:22
    
@hobbs Yeah, that sounds right to me. Otherwise a very pretty answer. –  Jander Jan 13 at 6:30
 int bogomul(int A, int B)
{
    int C = 0;
    while(C/A != B)
    {

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

    }
    return C;
}
share
1  
This will fail horribly if the result overflows. Nice! I guess you shouldn't print, though. –  Jan Dvorak Jan 13 at 6:35
2  
fails for a=2, b=2, c=5 –  BЈовић Jan 13 at 7:12
    
@BЈовић: while(C/A != B || C%A)? –  abarnert Jan 13 at 11:08
2  
Note that this is really an attempt to do the same thing as Deep Thought's successor, but for all possibly universes, instead of just the one where the answer is 42. Which would be very impressive if it weren't for the bug. And the lack of error handling in case of Vogons. –  abarnert Jan 13 at 13:10
1  
Needs multiple threads. You know, to make it efficient. –  greggo Jan 13 at 14:54

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.

share
2  
"without using the multiplication and addition operators". Nice bending of the rules - this will be absolutely useless to the asker :-) –  Jan Dvorak Jan 12 at 9:36
2  
This isn't really a C solution. Plus, it fails to compile on my ARM9. –  abarnert Jan 13 at 10:51
1  
@abarnert: Fail to recognize your statement as a relevant argument. –  Sukminder Jan 13 at 11:35
    
@Sukminder: The question is "Is it possible to write a C program…?" Inline assembly is not C. The fact that some C compilers can also do inline assembly doesn't change that, any more than the fact that some C compilers can also do C++ or ObjC makes C++ or ObjC count as C code. –  abarnert Jan 13 at 12:43
2  
@abarnert: It is embedded code widely used in C programs. Even though it is a cross-breed one can argue it is a C program. It is even plausible OP would recognize it as C code. It is clearly not python, or? –  Sukminder Jan 13 at 13:43
#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;
}
share

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");
    }
}
share
    
Why, it was not obvious to me at all! –  leewangzhong Jan 15 at 22:07

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.

share
    
Negative a, yes, negative b I don't think so. But that's fixable in many creative ways. Simplest would be sign_a ^= sign_b, sign_b = 0. –  MSalters Jan 15 at 12:51
    
@MSalters, tested and works for all sign combinations (with Linux/gcc). –  ugoren Jan 15 at 15:03

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;
}
share
1  
This is exactly the solution I thought of... but coming to the party late I knew it was a matter of scrolling down until I found that someone had already written it. Still, you get a -(-1) from me. –  Floris Jan 15 at 6:49

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.

share
    
I don't think this is trolling... –  Jan Dvorak Jan 13 at 10:54
    
Really ? I thought the pointless, gratuitous and architecture-specific use of SIMD would qualify it for code-trolling ? –  Paul R Jan 13 at 11:55
    
hmm... true. Didn't realise this was architecture-specific. –  Jan Dvorak Jan 13 at 12:13
#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 '*'
share
    
Now waiting for the 'turing machine emulation' solution. –  greggo Jan 13 at 14:56
1  
while strlen(cg) != a is a very trolling method to eliminate the -- (makes it O(N*N)). –  MSalters Jan 15 at 12:57

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;
    }
share
1  
Ungh. This is not trolling. This is an entirely reasonable way to do this. –  Jan Dvorak Jan 13 at 15:49
1  
It's trolly because it's too fast :-) –  Timtech Jan 13 at 16:09

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 $ '|'
share
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.

share

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;
share
1  
My God, it's full of *s ! –  Paul R Jan 14 at 15:42
1  
@PaulR :) but they're not operators. –  SQB Jan 15 at 7:09
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.

share
#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
share

protected by Community Jan 15 at 20:40

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.