CODEWITHSUNDEEP
c++algorithmmath
Mohsen Rasouli
Mohsen Rasouli

Reputation: 352

Multiplying integers the long way

I'm trying to create long int multiplication function. In math for multiplying 2 numbers for example 123 X 456, I do:

(12 * 10^1 + 3)( 45 * 10^1 + 6) = 
(540 * 10^2) + (72 * 10^1) + (135 * 10^1) + 18 = 15129

I created a small program for this algorithm but it didn't work right.

I don't know where my problem is. Can you help me to understand and correct that?

Tnx

int digits(int n) {
    int digit = 0;
    while (n>0){
        n/=10;
        digit++;
    }
    return digit;
}

long int longMult(long int a, long int b) {
    long int x,y,w,z;
    int digitA = digits(a);
    int digitB = digits(b);

    if((a==0) || (b==0)) {
        return 0;
    } else if (digitA < 2 || digitB < 2) {
        return a*b;
    } else {
        int powA = digitA / 2;
        int powB = digitB / 2;

        //for first number
        x = a/(10^powA);
        y = a%(10^powA);

        //for second number
        w = b/(10^powB);
        z = b%(10^powB);

        return ( longMult(x,w)*(10^(powA*powB)) + longMult(x,z) +
                 longMult(w,y)*(10^(powA*powB)) + longMult(y,z));
    }
}

int main()
{
    cout << digits(23) << endl; // for test
    cout << longMult(24,24); // must be 576 but output is 96
    return 0;
}

Upvotes: 1

Views: 139

Answers (1)

sj0h
sj0h

Reputation: 912

The expression

10^powA

does a bitwise exclusive or, and doesn't raise 10 to the power of powA, as you appear to expect.

You may want to define something like

long powli(int b, long e) {return e?b*powli(b,e-1):1;}

Then instead you can use

powli(10,powA)

Edit: There is also a problem with the way the values are combined:

    return ( longMult(x,w)*(10^(powA*powB)) + longMult(x,z) +
             longMult(w,y)*(10^(powA*powB)) + longMult(y,z));

Look into the maths, because multiplying the exponents makes little sense.

Also the combinations of adjustments to values is wrong, eg (10*a + b)(10*c + d) = 10*10*a*c + 10*a*d + 10*b*d +b*d. So check on your algebra.

Upvotes: 4

Related Questions