Почему реализация карацубы дает неверный результат - PullRequest
Новая
       107

Почему реализация карацубы дает неверный результат

0 голосов
/ 12 июля 2020

Я сделал программу для BigInteger, в которой реализовал сложение и вычитание, но она дает неправильный результат. После нескольких дебютов я не могу понять проблему. Вот мой код: - 

//
// Created by bothra on 09/07/20.
//

#include <sstream>
#include"BigInteger.h++"

BigInteger::BigInteger(std::string a) {
    digits = a;
}

BigInteger BigInteger::operator+(BigInteger othr) {
    return add(othr);
}

BigInteger BigInteger::operator-(BigInteger othr) {
    return Subtract(othr);
}

bool BigInteger::operator>(BigInteger othr) {
    if(digits.size() > othr.digits.size()){
        return true;
    }
    else if(digits.size() < othr.digits.size()){
        return false;
    }
    else{
        for(int i = digits.size() - 1;i >= 0;i--){
            if(digits[i] < othr.digits[i]){
                return false;
            }
        }
        return true;
    }
}

bool BigInteger::operator==(BigInteger othr) {
    if(digits.size() == othr.digits.size()){
        int flag = 0;
        for(int i = digits.size() - 1;i >= 0;i--){
            if(digits[i] < othr.digits[i]){
                return false;
            }
            if(digits[i] > othr.digits[i]){
                flag = 1;
            }
        }
        if(flag == 0){
            return true;
        }
    }
    return false;
}

BigInteger::BigInteger(int a) {

}

BigInteger BigInteger::add(BigInteger other) {
    if(sign == other.sign) {
        int base = 10;
        BigInteger ans("0");
        std::string a = digits;
        std::string b = other.digits;
        std::string result = "";
        int s = 0;

        int i = a.size() - 1;
        int j = b.size() - 1;
        while (i >= 0 || j >= 0 || s == 1) {
            s += ((i >= 0) ? a[i] - '0' : 0);
            s += ((j >= 0) ? b[j] - '0' : 0);

            result = char(s % base + '0') + result;

            s /= base;

            i--;
            j--;
        }
        ans.sign = sign;
        ans.digits = result;
        return ans;
    }
    else{
        return Subtract(other);
    }
}

BigInteger BigInteger::MakeShifting(BigInteger a,int stepnum){
    std::string shifted = a.digits;
    for (int i = 0 ; i < stepnum ; i++)
        shifted = shifted + '0';
    return shifted;
}

int makeEqualLength(std::string &str1, std::string &str2)
{
    int len1 = str1.size();
    int len2 = str2.size();
    if (len1 < len2)
    {
        for (int i = 0 ; i < len2 - len1 ; i++)
            str1 = '0' + str1;
        return len2;
    }
    else if (len1 > len2)
    {
        for (int i = 0 ; i < len1 - len2 ; i++)
            str2 = '0' + str2;
    }
    return len1; // If len1 >= len2
}

std::string getString(char x)
{
    std::string s(1, x);
    return s;
}

std::string DecimalToBinary(long long int number)
{
    std::string result = "";
    int base = 10;
    if (number <= 0){
        return "0";
    }
    else{
        int i = 0;
        char temp;
        while (number > 0){

            long long int num= number % base;
            temp = num + '0';
            result = getString(temp) + result;
            number = number / base;
            i++;
        }
        return result;
    }
}

BigInteger BigInteger::Subtract(BigInteger a)
{
    if(a.sign != sign){
        a.sign = sign;
        BigInteger ans = add(a);
        ans.sign = sign;
        return ans;
    }
    if(*this > a) {
        BigInteger ans("0");
        std::string rhs = a.digits;
        std::string lhs = digits;
        int length = makeEqualLength(lhs, rhs);
        int diff;
        std::string result;
        int base = 10;
        for (int i = length - 1; i >= 0; i--) {
            diff = (lhs[i] - '0') - (rhs[i] - '0');
            if (diff >= 0) {
                result = DecimalToBinary(diff) + result;
            } else {
                for (int j = i - 1; j >= 0; j--) {
                    lhs[j] = ((lhs[j] - '0') - 1) % 10 + '0';
                    if (lhs[j] != '1') {
                        break;
                    }
                }
                result = DecimalToBinary(diff + base) + result;
            }
        }
        ans.sign = sign;
        ans.digits = result;
        return ans;
    }
    if(*this == a){
        return BigInteger("0");
    }
    else{
        BigInteger ans("0");
        std::string rhs = digits;
        std::string lhs = a.digits;
        int length = makeEqualLength(lhs, rhs);
        int diff;
        std::string result;
        int base = 79;
        for (int i = length - 1; i >= 0; i--) {
            diff = (lhs[i] - '0') - (rhs[i] - '0');
            if (diff >= 0) {
                result = DecimalToBinary(diff) + result;
            } else {
                for (int j = i - 1; j >= 0; j--) {
                    lhs[j] = ((lhs[j] - '0') - 1) % 10 + '0';
                    if (lhs[j] != '1') {
                        break;
                    }
                }
                result = DecimalToBinary(diff + base) + result;
            }
        }
        ans.sign = a.sign;
        ans.digits = result;
        return ans;
    }
}

BigInteger BigInteger::Multiply(BigInteger other)
{
    std::string X = digits;
    std::string Y = other.digits;
    int n = makeEqualLength(X, Y);

    if (n == 1) return BigInteger(DecimalToBinary((X[0] - '0') * (Y[0] - '0')));

    int fh = n/2;   // First half of string, floor(n/2)
    int sh = (n-fh); // Second half of string, ceil(n/2)

    // Find the first half and second half of first string.
    std::string Xl = X.substr(0, fh);
    std::string Xr = X.substr(fh, sh);

    // Find the first half and second half of second string
    std::string Yl = Y.substr(0, fh);
    std::string Yr = Y.substr(fh, sh);

    // Recursively calculate the three products of inputs of size n/2
    BigInteger P1 = BigInteger(Xl).Multiply(BigInteger(Yl));
    BigInteger P2 = BigInteger(Xr).Multiply(BigInteger(Yr));
    BigInteger P3 = (BigInteger(Xl)+BigInteger(Xr)).Multiply(BigInteger(Yl) + BigInteger(Yr));

    // return added string version
    return  (P2 + MakeShifting(P1,2*(n - n/2))) + (MakeShifting(P3 - (P1 + P2) , n - n/2));
}

и заголовок: 

//
// Created by bothra on 09/07/20.
//

#ifndef BIGINTEGER_BIGINTEGER_H
#define BIGINTEGER_BIGINTEGER_H
#include<iostream>

class BigInteger{
public:
    std::string digits;
    bool sign = false;//false indicates positive

    BigInteger(int a);

    BigInteger(std::string a);

    BigInteger operator + (BigInteger othr);

    BigInteger operator - (BigInteger othr);

    bool operator > (BigInteger othr);

    bool operator ==(BigInteger othr);

    BigInteger add(BigInteger other);

    BigInteger MakeShifting(BigInteger a,int stepnum);

    BigInteger Subtract(BigInteger other);

    BigInteger Multiply(BigInteger other);

};
#endif //BIGINTEGER_BIGINTEGER_H

Но умножение этого кода не работает. Он продолжает давать неправильный ответ.

Например, вот код драйвера: - 

#include <iostream>
#include "BigInteger.h++"

int main() {
    BigInteger a("429");
    BigInteger b("429");
    a = a.Multiply(b);
    std::cout << a.digits;
    return 0;
}

Здесь 429 * 429: 

Output : 1397541
Output should have been : 184041

Пожалуйста, помогите меня. Заранее спасибо

...