0

I've read many blogs and examples of code but I'm trying to implement the Karatsuba multiplication through a way that is currently not logically working. Only single digit number multiplications are working, but any digits longer than 1 are displaying completely wrong answers. It should be able to take in long numbers of input, but I'm not allowed to use long int storage type. Also, it's meant to be able to multiply numbers of different base (1-10) however I'm unsure on how to do that so initially I'm just attempting base 10. This is my code so far:

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <sstream> 
int compareSize(string integer1, string integer2)
{
    int length = 0;
    if (integer1.length() > integer2.length())
    {
        //allocating int 1's length as final length if bigger than int 2
        length = integer1.length();
    }
    else if (integer2.length() > integer1.length())
    {
        //allocating int 2's length as final length if bigger than int 1
        length = integer2.length();
    }
    else
    {
        length = integer1.length();
    }

    return length;
}

int multiplication( string I1, string I2, int B){
    
    int length = compareSize(I1, I2);

    //converting the strings into integers
    stringstream numberOne(I1);
    int digitOne = 0;
    numberOne >> digitOne;

    stringstream numberTwo(I2);
    int digitTwo = 0;
    numberTwo >> digitTwo;

    //checking if numbers are single digits
    if ( (10 > digitOne) || (10 > digitTwo) ) {
        //cout<<(digitOne * digitTwo)<<endl;
        return (digitOne * digitTwo);
    }

    int size = ( length % 2) + (length / 2);

    int power = pow(10, size);

    int a = digitOne / power;   
    int c = digitTwo / power;   
    int b = digitOne - (a * power);  
    int d = digitTwo - (c * power);  

    int p2 = b * d;   
    int p0 = a * c;   
    int p1 = (b + a) * (d + c);
    //int final = p1 - p2 - p0;
    int sum = ((a*d) + (b*c)) ;

    int p = (p0*(pow(10,length))) + (sum * (pow(10,length)) + p2);
    //int p = ( p2 * (pow(10,size*2)) + ( p1 - (p2+p0)) * pow(10,size) + p0 ) * 100;
    // int p = (p2 * (long long)(pow(10, 2 * size))) + p0 + ((p1 - p0 - p2) * power);
    return p; 
}

int main(){

    string int1, int2;
    int base;
    cout<<"Enter I1, I2 and B: ";
        cin>> int1 >> int2 >> base;
    
    cout<<" "<<multiplication(int1, int2, base)<<endl;

    return 0;
    
}
hi_it'sme
  • 49
  • 6
  • Is `numberOne >> digitOne;` supposed to read just one digit? – Lukas-T Aug 12 '20 at 14:32
  • Can you provide an [MWE](https://stackoverflow.com/help/minimal-reproducible-example)? – bitmask Aug 12 '20 at 14:33
  • @churill it's meant to read whatever string (amount of digits entered together without a space) is inputted in – hi_it'sme Aug 12 '20 at 14:36
  • Another, unrelated, maybe wrong, note: Since you return an `int` anyway there is no real point in using such an algorithm. If the result is small enough to fit into an `int` you can use builtin multiplication. If the result is too big for `int` you get an overflow anyway. Maybe I'm missing something, but it looks like returning a string would be better. – Lukas-T Aug 12 '20 at 14:37
  • @hi_it'sme Ok, understood. It's just strange they are called `digitOne`/`digitTwo`. Anyway if the input is too large for `int` this might cause an error. You could check how long the string is instead. – Lukas-T Aug 12 '20 at 14:39
  • @churill I'm meant to use the karatsuba algorithm for this, I'm unsure on how to split the string format equally and multiply and perform the other operations such as `(pow(10,size))` on strings – hi_it'sme Aug 12 '20 at 14:40
  • @churill you're right it could, but I tested for basic numbers first and even inputs such as 12 and 11, are displaying wrong answers – hi_it'sme Aug 12 '20 at 14:41
  • @bitmask sorry I'm not sure I can do that, as I don't know how I can minimise the code displayed even further as I don't know where the error could be – hi_it'sme Aug 12 '20 at 14:42
  • @hi_it'sme It's not about minimizing the code further. It's about the reproducible part. A [mre] can be copied and executed as is. In this code some includes and `compareSize` are missing. Adding them would make it a real mre and help us to debug it better/easier :) – Lukas-T Aug 12 '20 at 14:46
  • @churill i understaand, i added those now :) – hi_it'sme Aug 12 '20 at 14:49
  • 1
    It's not a fix but looking for a bug it usually helps me to remove unneeded code. You can completely remove `compareSize` and replace `int length = compareSize(I1, I2);` with `int length = std::max(I1.length(), I2.length());` – Thomas Sablik Aug 12 '20 at 14:56

1 Answers1

2

The main problem is

int p = (p0*(pow(10,length))) + (sum * (pow(10,length)) + p2);

It should be

int p = (p0*(pow(10,length))) + (sum * (pow(10,length - 1)) + p2);

You shouldn't use std::pow for integers GCC C++ pow accuracy. I replaced it with my own version:

#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>

int pow(int b, int e) {
    if (e == 0) return 1;
    if (e == 1) return b;
    if (e % 2 == 0) return pow(b * b, e / 2);
    return b * pow(b * b, e / 2);
}

int multiplication(std::string I1, std::string I2) {
    
    int length = std::max(I1.length(), I2.length());
    int digitOne = std::stoi(I1);
    int digitTwo = std::stoi(I2);
    
    if ( (10 > digitOne) || (10 > digitTwo) ) {
        return (digitOne * digitTwo);
    }

    int size = ( length % 2) + (length / 2);

    int power = pow(10, size);

    int a = digitOne / power;   
    int c = digitTwo / power;   
    int b = digitOne - (a * power);  
    int d = digitTwo - (c * power);  

    int p2 = b * d;   
    int p0 = a * c;   
    int sum = ((a*d) + (b*c)) ;

    int p = (p0*(pow(10,length))) + (sum * (pow(10,length - 1)) + p2);
    return p; 
}

int main(){

    std::string int1, int2;
    std::cout<<"Enter I1 and I2: ";
    std::cin>> int1 >> int2;
    
    std::cout<<" "<<multiplication(int1, int2)<<'\n';

    return 0;
    
}
Thomas Sablik
  • 16,127
  • 7
  • 34
  • 62