Made a "Multiply Two Integers Without *" In C

[act]

My attention was brought to the classic Computer-Science task of multiplying two integers without using the proper multiplication operator. I decided to go out and do it, and I think I've done rather well. The only issue is that if the multiplier (The integer b) is less than 1, the program uses overflows to calculate the answer. It produces the correct result, sure, but it's extremely inefficient. Does anyone have any feedback for it?

Code: Select all

#include <stdio.h>

int main()
{

        int a, b, c; //A is multiplied. B is mutliplied by. C is original A.
        printf("First number? \n");
        scanf("%d", &a);
        c = a;
        printf("\nSecond number? \n");
        scanf("%d", &b);
        b = b - 1;
        do{
                b = b - 1;
                a = a + c;
        }while(b != 0);
        printf("%d", a);
        return 0;
}

[dave0808]

• Sticking with your loop solution: Rather than a do/while loop, I would use a for loop and control 'b' there.
• Use increment/decrement rather than x=x+1 or x=x-1
• You could test if 'b' is negative, make it positive, and then remember to make the result negative, after doing your calculation.
• If 'a' or 'b' is zero, then your result is known. No need to do any other work.

[rene]

You could test if 'b' is negative, make it positive, and then remember to make the result negative, after doing your calculation.

Quite -- or just do it in advance:

Code: Select all

if (b < 0) {
	a = -a;
	b = -b;
}
for (result = a; b > 1; b--)
	result += a;

[xenopeek]

Would it be allowable to use bitwise operations? You know, shift left once to multiply by 2 and so on.

[rene]

Would it be allowable to use bitwise operations? You know, shift left once to multiply by 2 and so on.

Added bonus, doesn't need to special-case 0 for either a or b. Does still also need the above if (b < 0) for negative numbers.

Code: Select all

for (result = 0; b; b >>= 1) {    
	if (b & 1)
		result += a;
	a  += a;
}       

Of course only works until overflow...

[Flemur]

multiplying two integers without using the proper multiplication operator.

How about

Code: Select all

answer = exp(log(a) + log(b))

[rene]

Sure.

This is actually sort of a nice addendum to the previous thread in here; viewtopic.php?f=120&t=357104&p=2127885#p2127885. I.e, the original simple plussing algorithm loops b times; the bit-shifting one above at most n times if b is an n-bits integer. That is, a Python version of latter would be faster than a C version of former relatively quickly as a function of b. exp()/log() is supposedly relatively expensive generally --- but we're not looping at all even.

[act]

Welp, months later I've decided I would get off my butt and make a little passion project video about the task, since I understand the theory and logic behind the program itself. I'd like you guys to see it, you can find it at https://odysee.com/@act:a/03-05-22:4
And if you ask, I want to make sure another YouTube-competitor doesn't end up like princess or Vid.me, and that starts by making content for it and making people aware of it.

[rene]

Seems you haven't payed any mind to the requested feedback though. I really just shouldn't, but...

Your algorithm is quite literally the definition of multiplication:

Code: Select all

a * b = a + ... + a {b times}

The as such most obvious implementation is

Code: Select all

for (result = 0; b > 0; b--)
	result += a;

or with the tiny optimization of starting at result = a instead, your algorithm (although written a bit more C-like),

Code: Select all

for (result = a; b > 1; b--)
	result += a

In the video you say to still not know what to do with negative numbers. As dave commented, you can simply invert both b and the result in that case, since a * b = -(a * (-b)). As I then added, also a * b = (-a) * (-b), i.e.,

Code: Select all

if (b < 0) {
	a = -a;
	b = -b;
}
for (result = a; b > 1; b--)
	result += a

Even with that taken care of this is still however the most basic algorithm possible: if b is say 4 billion you loop 4 billion (minus one...) times to arrive at the answer. If you look at the above bit-shifting one, if b is 4 billion (a 32-bit number) that one loops 32 times -- which is rather significantly less than 4 billion. Flemur added that also a * b = exp(log(a) + log(b)).

Those latter two do need some understanding of binary respectively general mathematics so, sure and all, but this comment still got a bit unavoidable when you said to still not know what do with negative numbers. I.e., why did you ask for feedback?

[act]

Seems you haven't payed any mind to the requested feedback though. I really just shouldn't, but...
Those latter two do need some understanding of binary respectively general mathematics so, sure and all, but this comment still got a bit unavoidable when you said to still not know what do with negative numbers. I.e., why did you ask for feedback?

I written the script on January 21st, and in my pride of successfully completing the - very basic - task, I failed to really consider the feedback that's been given. Sorry about that. I decided to not look into anything as I began to produce the video, but I'll change that with today. Once again, sorry about my ignorance in the matter, and I deeply thank you for your longwinded explanation, it'll help me because I'm not particularly smart with things and need to be slapped in the face with obvious knowledge.
I think that sounds really sarcastic, so in the case that it does come off as sarcastic, it's serious. Sorry about the failure on my end, and thank you for your help.

[rene]

Err. Okay...

I'll just add then that the in the first, "most obvious" above version a = 0 or b = 0 is fine (although former does unnecessary work) but that after the mentioned "tiny optimization" we need to special-case b = 0 -- which is to say that it's in fact a pessimization in practice: an if also takes time. The bit-shifting algorithm doesn't mind 0 for either; the exp/log one needs to special case for either being 0.