Binary Multiplication in C

Question:Write an algorithm in C to do integer multiplication without using multiplication nor division operators.

Could I get a critique of the doMultiplication function? I know the rest of the code has some dumb stuff in it (like using scanf), but I'm looking for feedback on my multiplication implementation. Are there any cases it won't handle? Is there anything I could possibly have done to optimize it? And lastly, is there anything that would make it more readable?

#include <stdio.h>
#include <math.h>
/*
Write an algorithm/code in C to do integer multiplication  without using multiplication nor division operators.
*/
void main()
{
int n;
int m;
int result;
printf("Please enter numbers to multiplye\n");
printf("First number\n");
int multiple1 = getNumberFromUser();
printf("\nSecond number\n");
int multiple2 = getNumberFromUser();
result = doMultiplication(multiple1,multiple2);
printf("Result of multiplication = %d\n", result);
}

int getNumberFromUser()
{
char arg1[10];
int retry = 0;
int multiple;
while(retry == 0)
{
printf("Please enter a number:");
scanf("%s", arg1);
if(isNumericInput(arg1) != 0)
{
char * strEnd;
multiple = strtol(arg1,&strEnd, 10);
retry = 1;
} else {
printf("Bzzz wrong answer genius try a number \n");
}
}

return multiple;

}

int isNumericInput(char arg[]){
char * strEnd;
int userInput = strtol(arg, &strEnd, 10);
return userInput;
}

int doMultiplication(int n, int m)
{
int result = 0;
while(m != 0)
{
if((m & 1) != 0)
{
result = result + n;
}
n = n << 1;
m = m >> 1;
}
return result;
}

-

Basically your algorithm looks correct, however:

1. You should use unsigned ints or have some treatment for the signs, otherwise I guess (didn't check it though) that your results for negative numbers will be wrong
2. Don't test for 0 explicitly, i.e. just write while(m) and if(m & 1)
-

Your algorithm is optimal for numbers that fit into a int, but a lot of multiplication algorithms exist for large inputs. By the way, is bit-shifting authorized? It looks a lot like a multiplication.

1. strtol(3) returns a long int, not an int.
2. Tell scanf you only want 9 characters (+ \0): scanf("%9s", arg1); if you want to avoid a buffer overflow.
3. You should test the return of scanf.
4. Calling strtol(3) twice is surprising. Why don't you store the return value of isNumericInput?
5. You could print errors on the standard error stream: fprintf(stderr, "Bzzz wrong!\n");
6. ((m & 1) != 0) -> (m & 1 != 0) -> (m % 2 != 0) -> (m % 2).
7. Typo: it's multiply, not multiplye.
-
#6 would be better to be just m & 1, since bit-fiddling will be faster than a full modulus operation (although GCC seems to compile them to the same code) and testing != 0 is pointless in C (any non-zero value is already considered "true"). –  huon-dbaupp Mar 14 '12 at 9:44
Yes, GCC and any reasonable compiler will optimize it, so it's pointless to use bit-shifting. It's the same for / 2, but since he can't do "multiplication/division"... Thanks for the != 0, I'll edit. –  Quentin Pradet Mar 14 '12 at 9:48
void main()


== inf. pain.

I die a little every time I see that... It's int main(), thank you very much!

if(isNumericInput(arg1) != 0)

The name isNumericInput() is poorly chosen, as the function doesn't really return what the name implies, i.e. a true/false value. I think that's why you made a small logical bug here.

The return value of isNumericInput() is the actual parsed number, which can be 0, if either arg1 isn't a number at all or if arg1 is "0", a perfectly fine number contrary to what your program claims.

If you did make a proper isNumericInput(), I would suggest re-writing the check as

if(!isNumericInput(arg1))


as that can more easily be read as "if not numeric, ..." compared to your version, which reads more like "if numeric NOT!, ..." or "if numeric not false, ...".

Instead of first reading a string and then parsing that string (twice), I think it would be better to just let scanf() read an integer.

Maybe something like this:

int getNumberFromUser()
{
int number;  /*
* You call it "multiple", but at this point in the code,
* it's just a number. This function doesn't care what you
* use the number for later on.
*/

int items;

do
{
printf("Please enter a number:");

items=scanf("%d",&number);  /* Return number of items read. */

if(items!=1)  /* If we didn't read a number... */
fprintf(stderr,"Bzzz wrong answer genius try a number \n");
}
while(items!=1);  /* Loop until we get a number */

/*
* In this case, "items" will always be either 0 or 1, so here the two
* checks could have been replaced with either (items==0) or (!items),
* but IMHO it feels more logical to compare against 1 in this case.
*/

return(number);
}


and drop isNumericInput() as it isn't used anymore.

-

While others have mentioned that your code is technically correct, it could be made much simpler to understand and read. Don't try to be too clever, let the complier optimize. As someone else mentioned, using bitshifting could be construed as multiplication because, well, it kind of is.

int doMultiplication(int n, int m)
{
int result = 0;
while(m)
{
result += n;
m--;
}
return result;
}


One thing yours (and mine) doesn't support is negative numbers. If you need to support negative numbers, here's one solution:

int doMultiplication(int n, int m)
{
/* This first part is if you need to handle negative numbers */
int n_is_negative = (n < 0);
int m_is_negative = (m < 0);
int result_is_negative = (n_is_negative != m_is_negative); /* Only if the signs are different is the result negative */
n = (n < 0 ? -n : n); /* use abs() if you can for readability sake */
m = (m < 0 ? -m : m);

int result = 0;
while(m)
{
result += n;
m--;
}
if(result_is_negative)
result = -result;
return result;
}


Granted, this uses the negation operator (-), which is itself a form of multiplication, but it is the simplest way to negate a number.

-