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

68

35

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.

s3lph

Posted 2014-01-11T16:49:07.000

Reputation: 1 598

1Please be more specific about "numbers". – Paul R – 2014-01-11T17:03:15.303

2@PaulR use your fantasy – John Dvorak – 2014-01-11T17:03:42.697

I guess the original Q meant any numbers... – s3lph – 2014-01-11T17:04:51.520

The given example doesn't work with integers so I'm guessing it may be a floating point task? – Paul R – 2014-01-11T17:05:18.637

Why doesn't it work with ints? (except 0) – s3lph – 2014-01-11T17:10:33.420

1/n is 0 for n > 1 when n is an int. – Paul R – 2014-01-11T17:19:21.093

oh.. yes, you're right... doesn't matter for the question – s3lph – 2014-01-11T17:22:24.220

26Code-golf.SE should not be a place for you to mock questions you've seen on StackOverflow. – Gareth – 2014-01-11T19:40:05.483

17

@Gareth, are you sure? The first line of this suggests this may be quite appropriate.

– Darren Stone – 2014-01-11T20:27:17.590

@DarrenStone I've enjoyed being a member of this site for a couple of years now and I'm seriously concerned that questions like this are mean and unpleasant. I don't want to see this site become reddit-like. – Gareth – 2014-01-11T22:42:55.727

1@Gareth, I certainly didn't intend to be mean with my comment. I wrestle with the spirit and noise that [tag:code-trolling] questions bring, but OP has tagged the question correctly and code-trolling is based on jest and mockery of real questions. – Darren Stone – 2014-01-11T22:50:37.057

1@DarrenStone I think you misunderstood me, I think this type of question which mocks an SO user is a bit mean. Your comment was a reasonable one (as they usually are). – Gareth – 2014-01-12T01:15:21.473

5I´m waiting for someone write an algorithm based on sleep – kb_sou – 2014-01-12T02:11:21.180

21This 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 – 2014-01-12T06:12:24.757

1@Gabe yeah, but the O(bits^2) solution is inappropriate for a code-trolling challenge :-) – John Dvorak – 2014-01-12T07:47:36.880

@Gareth - I don't see that the OP is in any way being mean or "mocking" the SO user. – Kevin Fegan – 2014-01-13T03:02:02.097

@JanDvorak: Multiplying is O(digits^2). If your computer can do it faster than that, it's because it has O(digits^2) transistors that all operate simultaneously. – Gabe – 2014-01-13T06:43:03.070

last week I had an interview I was asked to multiply a number with 7 without using + and * I answered result = (number << 3) - number. – Grijesh Chauhan – 2014-01-13T06:54:35.290

@GrijeshChauhan: your solution does not work for the full valid range of possible input values (it overflows for part of the range). – Paul R – 2014-01-13T07:56:45.257

@PaulR Yes. You are correct, in-fact it can cause undefined behavior if left-shit sets sign-bit(msb). But fortunately interviewer was happy :) I guess because he asked question in Puzzle section(not in programming). Btw I now like @ MarkLakata trick. – Grijesh Chauhan – 2014-01-13T08:09:37.453

@GrijeshChauhan: I think you're confused between left shift and right shift of signed values - the only problem with the left shift in your solution is the potential for overflow in the intermediate result - otherwise it's fine. – Paul R – 2014-01-13T08:11:46.197

Since all computers are essentially adding machines, with flow control, comparators, and about every other operation including incrementing the program counter dependent on addition then no, in the strictest sense this program can't be written, at least not for any non-analogue computer. – user289251 – 2014-01-12T03:35:20.040

@GrijeshChauhan: To avoid overflow of the intermediate result, set result = (number<<2) + (number <<1) + number – Pieter Geerkens – 2014-01-13T11:57:29.233

@PieterGeerkens yup, this kind of technique can be helpful, but you are using +!! – Grijesh Chauhan – 2014-01-13T12:19:46.267

2@GrijeshChauhan: Oops! Time for a coffee I think. – Pieter Geerkens – 2014-01-13T12:21:53.123

1Unless you are compiling with -Ofast (which is gcc mode that doesn't calculate accurately, like C standard says), a/(1/((float)b)) is not identical to a*b. This is because floating point math is special, and most optimizations cannot be done. – Konrad Borowski – 2014-01-13T19:37:06.643

1What about solutions that use a - -b to substitute for a + b? – Joe Z. – 2014-01-13T20:25:43.987

2"c = a * b" doesn't use "the * and + operators", it only uses one of them :p (how do you make 35 cents with two coins, where one of them isn't a quarter?) – neminem – 2014-01-13T21:13:07.343

(oops, it hates left-arrows so I replaced it with {) Note that on some level, logic gates are in fact related to addition, comparison, and tables. You can state (2 inputs) XOR as 0{A+B{2 or that the sum is equal to 1. A 3-input NAND gate can be stated as A+B+C=3 and so on. On some level, a (stateless) logic device is just asking "Does the sum of these inputs equal to some value in the following table?" and combining the answers recursively for many groups of inputs into yet more tables. This is in fact the idea behind Programmable Array Logic devices. This is getting into major number theory t – None – 2014-01-14T09:18:53.757

No one applied the seemingly obvious properties of natural logarithms? For shame? Oh someone did mention exp(x) though. In (roughly) algebraic form: ab=exp(log(a)+log(b)) So what to do since we can't use addition? I'll not cheat and assume "direct addition" is the only kind forbidden. You could use a table or slide rule (which is just an analog computer version of the table). You'd be imitating addition, though. Hmm, thinking of another angle of attack... OK, multiplying complex numbers adds the angles. angleof((1@ angle A)(1@ angle B)) = (A+B) mod 2Pi. LOL, going around in circles unless A= – None – 2014-01-14T09:14:46.367

1@GrijeshChauhan @PieterGeerkens Regarding result = (number << 3) - number : it does not have an overflow problem. It does overflow, of course, but the result is correct anyway, because (on all normal C machines) both the << and the '-' overflow as in modular arithmetic. So does number*7. So you get the proper result, overflow or not. It's common for C compilers to do such transforms when the shift/add is smaller than the multiply-by-constant. – greggo – 2014-01-20T02:52:56.890

@greggo so I am pass :) – Grijesh Chauhan – 2014-01-20T04:54:14.950

Code-trolling is in the process of being removed, as per the official stance. This question receieved almost 50% "keep" votes on the poll, and is an outlier in that it has an extreme amount of votes, votes on the answers, and amount of answers, so I am locking it.

– Doorknob – 2014-05-10T16:49:17.210

Answers

147

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

Oberon

Posted 2014-01-11T16:49:07.000

Reputation: 2 881

8I 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 ;) – yo' – 2014-01-11T22:52:26.233

1The sheer elegance of this has dissuaded me from posting my ripple carry adder based solution. Bit-wise addition by recursion. Wow. – Julie in Austin – 2014-01-12T01:21:59.543

Wow. Nice increment operator, more readable than mine :-) – John Dvorak – 2014-01-12T05:36:03.863

10If Picasso was a programmer... – R Hughes – 2014-01-12T06:29:19.967

+ can be made of two -s, so add is not necessary (only if you must deal with unsigned integers) – Display Name – 2014-01-12T08:28:33.797

4@SargeBorsch But where'd the fun be in that? – Oberon – 2014-01-12T16:06:48.250

Could someone explain one of these functions to a relatively novice programmer? ^^ – HC_ – 2014-01-13T17:48:31.600

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 – 2014-01-13T18:28:20.147

1Always use recursion? Isn't that only true for Haskell? – NoBugs – 2014-01-14T05:42:34.167

1

It is kind of funny that this kind of an approach would one day cause this...

– mostruash – 2014-01-14T21:53:31.627

2Doesn't the increment function go into an infinite loop for -1? (0xFFFF) ideone shows (-1 >> 1) == -1. – Destrictor – 2014-01-15T09:33:57.150

What would this look like for floats? – gerrit – 2014-01-15T10:08:23.717

@Destrictor, that's because I'm stupid and I used signed ints. Problem is, GCC (and most compilers) treat shifts on signed types as arithmetic shifts instad of logical ones. – Oberon – 2014-01-15T13:25:40.937

87

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

Mark Lakata

Posted 2014-01-11T16:49:07.000

Reputation: 1 631

4Put it inside a structure and you don't need memory. – Ben Jackson – 2014-01-12T00:54:45.273

Inside a structure definition. A structure might still allocate space in the BSS segment. – Julie in Austin – 2014-01-12T01:42:33.870

I updated my answer to use a typedef. A struct would use memory too. I think @BenJackson was thinking of a named struct without a variable allocated, ie struct a { char buffer[a][b];} and sizeof(struct a). – Mark Lakata – 2014-01-12T05:35:42.863

4Hahahah great!! – Almo – 2014-01-12T08:26:14.240

byte padding may screw up the results, but good idea :) – BЈовић – 2014-01-13T07:08:52.050

1use "%zu" format string. – Grijesh Chauhan – 2014-01-13T07:30:11.130

5just 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 – 2014-01-13T14:59:25.583

1Delete the first two lines and compile with -DA=45 -DB=315 to avoid having to edit the source file for each multiplication you want to do. – David Richerby – 2014-01-13T22:03:43.703

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 – 2014-01-13T22:48:46.957

Quite an intelligent implementation, I must say. Doesn't cover all cases but gets the job done most of the time. +1 – javatarz – 2014-01-17T06:49:46.270

47

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

Petr Pudlák

Posted 2014-01-11T16:49:07.000

Reputation: 4 272

3You 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 – 2014-01-11T18:28:41.880

1@DarrenStone -= -1 – Timtech – 2014-01-11T20:06:49.740

20@Timtech |= 1 (will work on 50% of numbers, 100% of the time) – Darren Stone – 2014-01-11T20:20:28.340

2+1, but noting that it could be too slow, and you could add multi-thread support, carefully locking the 'count++' :-) – greggo – 2014-01-13T15:01:45.327

1There'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 – 2014-01-15T12:44:36.983

45

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

Cel Skeggs

Posted 2014-01-11T16:49:07.000

Reputation: 901

8Nice. A deliberate misinterpretation of the question :-) – John Dvorak – 2014-01-12T05:59:08.420

6You can optimize this to return a && b;. It’s shorter, so it’s faster. – Ry- – 2014-01-12T18:10:24.630

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;. – Cel Skeggs – 2014-01-12T20:11:19.917

You should have made it return a&b, since this is code golf - the shortest solution wins :) – BЈовић – 2014-01-13T07:17:25.693

@BЈовић Tags on the question: popularity-contest code-trolling - I don't see the code-golf tag. – Cel Skeggs – 2014-01-13T07:25:42.200

Ok, I see. Either ways - a very good solution! – BЈовић – 2014-01-13T07:31:56.817

@minitech !!(a&&b), the recasting will convert it back to 0 or 1 no matter the integer inputs to the function. – recursion.ninja – 2014-01-14T17:25:21.237

Maybe return true and return false for more apparent redundancy. – leewz – 2014-01-15T00:22:02.857

@leewangzhong I don't think that C has true and false, but I'll think about including #defines. – Cel Skeggs – 2014-01-15T01:05:50.083

1C has #include<stdbool.h> to define true and false. – leewz – 2014-01-15T02:10:46.920

@leewangzhong Well, you learn something new every day! Added. – Cel Skeggs – 2014-01-15T04:38:43.583

1Yeah, #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. – leewz – 2014-01-15T15:19:51.993

Though I think stdbool and implicit int are not in the same version of C. – leewz – 2014-01-15T15:25:17.747

@leewangzhong Who said they had to be in the same version of C? Added. – Cel Skeggs – 2014-01-15T16:08:59.730

Aaaand the smart ass of the week goes to.. :) +1 on a good interpretation of the question. – javatarz – 2014-01-17T06:49:03.937

31

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)

Vroo

Posted 2014-01-11T16:49:07.000

Reputation: 411

41I 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 – 2014-01-12T01:40:39.190

5Thanks 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 – 2014-01-12T05:34:39.987

Also, you're still using the multiplication operator; disguising it as %2A doesn't help. – abarnert – 2014-01-13T10:46:53.890

2@abarnert hmm... does Bing understand "times"? Wolfram Alpha might, though. – John Dvorak – 2014-01-13T10:57:36.263

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 – 2014-01-13T12:48:37.207

@abarnert the output is embedded directly in the response page in javascript. Plus there's a dev API (free registration) for Wolfram Alpha. – John Dvorak – 2014-01-13T12:51:43.097

3@JanDvorak: That's no fun. I was looking forward to someone writing a simple OCR library with no addition or multiplication… – abarnert – 2014-01-13T12:54:30.057

1@abarnert now that would be cool. – John Dvorak – 2014-01-13T12:56:29.780

@AmeliaBR Here's a C solution: wrap the entire thing in a system() call. – Braden Best – 2014-02-12T18:33:15.433

27

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

treamur

Posted 2014-01-11T16:49:07.000

Reputation: 581

18

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.

John Dvorak

Posted 2014-01-11T16:49:07.000

Reputation: 9 048

+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 – 2014-01-11T22:26:46.287

1It'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 – 2014-01-12T01:25:26.570

@JulieinAustin yep. The algorithm is even more inefficient than it needs to be. Should I amend the troll list? :-) – John Dvorak – 2014-01-12T05:31:08.850

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 – 2014-01-12T06:10:03.423

@hobbs solution: instead of ORing, add them recursively if carry is non-zero. – John Dvorak – 2014-01-12T07:29:17.743

@JulieinAustin it's possible to make an efficient multiplier using bitwise operators (and shifts) only. O(bits^2) is quite easy. – John Dvorak – 2014-01-12T07:37:51.667

@hobbs - It's a single bit adder. For wider adders, you have to make a ripple-carry adder and iteratively re-add the carry back into the (x ^ y) result. If you let (carry = (x & y) << 1), and (partial = (x ^ y)), the result is a while() loop where x is the first addend, y is the second, and (x = partial; y = carry;) is the result of each step. That means the control loop is then while(y) and the result of the "no addition operators" ripple carry adder is left in x. – Julie in Austin – 2014-01-29T17:16:18.247

14

Works for floating point numbers as well:

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

nbubis

Posted 2014-01-11T16:49:07.000

Reputation: 1 019

11

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

abarnert

Posted 2014-01-11T16:49:07.000

Reputation: 467

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

greggo

Posted 2014-01-11T16:49:07.000

Reputation: 231

Oops, there is * char (although it's not multiplication) – Display Name – 2014-01-12T08:37:57.490

Uh, table lookup uses addition -- (a[i]) is the same as (*(a + i)). – Julie in Austin – 2014-01-29T17:18:39.363

@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 – 2014-03-02T02:23:08.980

10

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?

abarnert

Posted 2014-01-11T16:49:07.000

Reputation: 467

1Wow. You're even slower than me. – John Dvorak – 2014-01-13T10:50:48.617

8

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

Matthias

Posted 2014-01-11T16:49:07.000

Reputation: 189

1+1 Nice implementation of carry evaluation. I like your code :) – yo' – 2014-01-12T12:49:23.590

@BЈовић: My fault, I thought trolling is not about understandig. Changed names and added comments. – Matthias – 2014-01-13T10:57:05.160

sorry. I misunderstood what that tag is, and what the Q really is about. You should revert it – BЈовић – 2014-01-13T12:07:50.840

@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 – 2014-01-13T14:48:21.513

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 – 2014-01-13T15:18:11.393

8

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

Mark Lakata

Posted 2014-01-11T16:49:07.000

Reputation: 1 631

7

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.

millinon

Posted 2014-01-11T16:49:07.000

Reputation: 590

2Why 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 – 2014-01-13T11:06:20.450

2Might as well use OpenMPI to run it on a few machines in parallel. – millinon – 2014-01-13T11:22:14.420

6

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

user3175123

Posted 2014-01-11T16:49:07.000

Reputation: 81

6

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

hobbs

Posted 2014-01-11T16:49:07.000

Reputation: 2 403

4The asker didn't troll. You are supposed to troll. – John Dvorak – 2014-01-12T05:56:31.360

2It's a stealth troll! The secret failure is on a==INT_MIN. – Jander – 2014-01-13T06:17:34.360

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 – 2014-01-13T06:22:22.563

@hobbs Yeah, that sounds right to me. Otherwise a very pretty answer. – Jander – 2014-01-13T06:30:26.743

6

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.

Runium

Posted 2014-01-11T16:49:07.000

Reputation: 1 878

2"without using the multiplication and addition operators". Nice bending of the rules - this will be absolutely useless to the asker :-) – John Dvorak – 2014-01-12T09:36:27.780

2This isn't really a C solution. Plus, it fails to compile on my ARM9. – abarnert – 2014-01-13T10:51:44.973

1@abarnert: Fail to recognize your statement as a relevant argument. – Runium – 2014-01-13T11:35:04.333

@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 – 2014-01-13T12:43:49.127

@abarnet: And thus it is completely useless. Thought that was part of the point. – Runium – 2014-01-13T12:57:34.200

@Sukminder: Answering "No, I don't want to" or "fnord" is even more completely useless, but it's not completely useless C code, which is the point. – abarnert – 2014-01-13T13:00:01.797

And assembly is not "a language that the lazy OP might think acceptable" if he specifically asked for C. Look at the bold sentence starting the bullet point you quoted. – abarnert – 2014-01-13T13:17:01.880

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? – Runium – 2014-01-13T13:43:59.827

@abarnert: Obviously you need to use a cross-compiler for x86 if you want to compile this on ARM9 :) Compiles just fine on this ARM machine. – Janus Troelsen – 2014-01-14T22:07:52.380

6

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

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

    }
    return C;
}

Chengarda

Posted 2014-01-11T16:49:07.000

Reputation: 69

1This will fail horribly if the result overflows. Nice! I guess you shouldn't print, though. – John Dvorak – 2014-01-13T06:35:19.777

2fails for a=2, b=2, c=5 – BЈовић – 2014-01-13T07:12:12.007

@BЈовић: while(C/A != B || C%A)? – abarnert – 2014-01-13T11:08:29.397

2Note 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 – 2014-01-13T13:10:33.900

1Needs multiple threads. You know, to make it efficient. – greggo – 2014-01-13T14:54:06.840

@BЈовић That's intentional, it's a Monte Carlo AND Las Vegas Bogo-Multiplier. Best of Both Worlds. – Chengarda – 2014-01-13T23:46:33.470

5

#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;
}

jaybers

Posted 2014-01-11T16:49:07.000

Reputation: 151

5

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

abarnert

Posted 2014-01-11T16:49:07.000

Reputation: 467

Why, it was not obvious to me at all! – leewz – 2014-01-15T22:07:30.250

4

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.

ugoren

Posted 2014-01-11T16:49:07.000

Reputation: 16 527

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 – 2014-01-15T12:51:52.780

@MSalters, tested and works for all sign combinations (with Linux/gcc). – ugoren – 2014-01-15T15:03:27.270

3

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

thepirat000

Posted 2014-01-11T16:49:07.000

Reputation: 588

1This 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 – 2014-01-15T06:49:52.500

3

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.

Paul R

Posted 2014-01-11T16:49:07.000

Reputation: 2 893

I don't think this is trolling... – John Dvorak – 2014-01-13T10:54:29.513

Really ? I thought the pointless, gratuitous and architecture-specific use of SIMD would qualify it for code-trolling ? – Paul R – 2014-01-13T11:55:34.823

hmm... true. Didn't realise this was architecture-specific. – John Dvorak – 2014-01-13T12:13:59.813

3

#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 '*'

marol

Posted 2014-01-11T16:49:07.000

Reputation: 131

Now waiting for the 'turing machine emulation' solution. – greggo – 2014-01-13T14:56:09.250

1while strlen(cg) != a is a very trolling method to eliminate the -- (makes it O(N*N)). – MSalters – 2014-01-15T12:57:48.387

3

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

David Laight

Posted 2014-01-11T16:49:07.000

Reputation: 31

1Ungh. This is not trolling. This is an entirely reasonable way to do this. – John Dvorak – 2014-01-13T15:49:04.977

1It's trolly because it's too fast :-) – Timtech – 2014-01-13T16:09:20.460

3

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

mhwombat

Posted 2014-01-11T16:49:07.000

Reputation: 131

3

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.

Konrad Borowski

Posted 2014-01-11T16:49:07.000

Reputation: 11 185

3

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;

SQB

Posted 2014-01-11T16:49:07.000

Reputation: 681

1My God, it's full of *s ! – Paul R – 2014-01-14T15:42:13.680

1@PaulR :) but they're not operators. – SQB – 2014-01-15T07:09:49.357

2

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

Quiz

Posted 2014-01-11T16:49:07.000

Reputation: 121

2

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.

Joker_vD

Posted 2014-01-11T16:49:07.000

Reputation: 121

2

#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

Kaz

Posted 2014-01-11T16:49:07.000

Reputation: 372

1

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

Robert Sørlie

Posted 2014-01-11T16:49:07.000

Reputation: 1 036

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… – abarnert – 2014-01-13T12:41:20.303

ugh, i need to to learn to read... Should i delete this? – Robert Sørlie – 2014-01-13T13:03:44.737

1I actually thought that PHP was part of the joke, lol. – Vereos – 2014-01-13T15:49:28.560

1

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

Javier

Posted 2014-01-11T16:49:07.000

Reputation: 119

1"Why don't you do it in scheme?" doesn't seem like an answer to "Is there any C code that…" – abarnert – 2014-01-14T02:45:48.467

1I'm trolling the OP – Javier – 2014-01-14T13:25:20.240

1Many Schemes compile to C, for example Chicken Scheme. – Janus Troelsen – 2014-01-14T22:10:36.460

1

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

abarnert

Posted 2014-01-11T16:49:07.000

Reputation: 467

1

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.

dtldarek

Posted 2014-01-11T16:49:07.000

Reputation: 321

1

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.

Glenn Teitelbaum

Posted 2014-01-11T16:49:07.000

Reputation: 141

nice work :) black magic ftw :P – masterX244 – 2014-02-17T19:46:48.540

0

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

Paul R

Posted 2014-01-11T16:49:07.000

Reputation: 2 893

Looks rather similar to mine, except it's more efficient (boo) and uses the increment operator (double boo). – John Dvorak – 2014-01-13T10:52:20.687

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 ++. – Paul R – 2014-01-13T11:54:36.900

0

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/

JMercer

Posted 2014-01-11T16:49:07.000

Reputation: 101

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. – gnibbler – 2014-02-03T01:05:29.880

0

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

Matteo Italia

Posted 2014-01-11T16:49:07.000

Reputation: 3 669

Note: fails if either a or b is equal to INT_MIN. – Paul R – 2014-01-14T07:54:25.693

0

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

aditsu quit because SE is EVIL

Posted 2014-01-11T16:49:07.000

Reputation: 22 326

0

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

greggo

Posted 2014-01-11T16:49:07.000

Reputation: 231

0

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.

Digital Trauma

Posted 2014-01-11T16:49:07.000

Reputation: 64 644

0

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.

Digital Trauma

Posted 2014-01-11T16:49:07.000

Reputation: 64 644

0

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!

Nowayz

Posted 2014-01-11T16:49:07.000

Reputation: 149

May take small modification depending on instruction set – Nowayz – 2014-02-17T23:44:44.353

0

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

urzeit

Posted 2014-01-11T16:49:07.000

Reputation: 1 297

-2

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

Boris

Posted 2014-01-11T16:49:07.000

Reputation: 1

1This 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" – John Dvorak – 2014-01-13T08:38:30.360