Tukukkk

My implementation of Karatsuba multiplication from Tim Roughgarden's Algorithms course. I've made a Integer class that holds an integer in string format. I've added operations to this class to add, subtract and multiply numbers. Karatsuba.cpp perform's the Gauss trick.

Integer.hpp

#pragma once

#include <string>

#include <functional>



class Integer{

    public:

        Integer();

        Integer(const std::string& input);

        ~Integer();

        Integer operator+(const Integer& other) const;

        Integer operator-(const Integer& other) const;

        Integer operator*(const Integer& other) const;

        size_t size() const{return fString.size();}

        void padRight(size_t num);

        void padLeft(size_t num);

        Integer substr(size_t pos, size_t length) const;

        void print() const;

        void stripLeadingZeros();

    private:

        std::string fString;

};

void equalizeLengthsPadLeft(Integer& first, 

                            Integer& second);

void equalizeLengthsPadRight(std::string& first, std::string& second);

Integer.cpp

#include "Integer.hpp"

#include <assert.h>

#include <string>

#include <algorithm>

#include <iostream>



namespace {

    int char2int(char c){

        return c - '0';

    }

}

Integer::Integer()

:

fString()

{

}



Integer::Integer(const std::string& input)

:

fString(input)

{

}



Integer::~Integer(){}



Integer Integer::substr(size_t pos, size_t len) const{

    return fString.substr(pos, len);

}



void equalizeLengthsPadLeft(Integer& first, 

                            Integer& second){

    if (first.size() < second.size()){

        first.padLeft(second.size()-first.size());

    }

    else if(first.size() > second.size()){

        second.padLeft(first.size() - second.size());

    }

}

void equalizeLengthsPadRight(std::string& first, std::string& second){

    if (first.size() < second.size()){

        first += std::string(second.size()-first.size(), '0');

    }

    else if(first.size() > second.size()){

        second += std::string(first.size() - second.size(), '0');

    }

}



Integer Integer::operator+(const Integer& other) const{

    // For the time being, just conver to integer and return

    std::string first = fString;



    std::reverse(first.begin(), first.end());

    std::string second = other.fString;

    std::reverse(second.begin(), second.end());

    equalizeLengthsPadRight(first,second);



    std::string::iterator first_it = first.begin();

    std::string::iterator second_it = second.begin();

    std::string resultStr;

    int carry = 0;

    while(first_it != first.end()){

        int sum = char2int(*first_it) + char2int(*second_it) + carry;

        carry = 0;

        if (sum >= 10){

            sum = sum%10;

            carry = 1;

        }

        resultStr += std::to_string(sum);        

        first_it++;second_it++;    

    }

    if (carry){

        resultStr += '1'; 

    }

    std::reverse(resultStr.begin(), resultStr.end());

    return resultStr;

}



Integer Integer::operator-(const Integer& other) const{



    std::string first = fString;

    std::reverse(first.begin(), first.end());

    std::string second = other.fString;

    std::reverse(second.begin(), second.end());



    // Equalize

    equalizeLengthsPadRight(first,second);



    std::string::iterator first_it = first.begin();

    std::string::iterator second_it = second.begin();

    std::string resultStr;

     while(first_it != first.end()){

         int up = char2int(*first_it);

         int down = char2int(*second_it);

         int localResult;

         if (up >= down){

            localResult = up-down;

         }

         else{

             // Keep searching forward until you get a non-zero value

            auto next_it = first_it+1;

            while(true){

                if (char2int(*next_it) > 0){

                    // Found the first non-zero number

                    break;

                }

                next_it++;

            }

            *next_it = std::to_string(char2int(*next_it)-1)[0];

            // Now chase back to first_it setting 9's 

            // on the way. Make sure everything was 0 

            // beforehand

            next_it--;

            while(next_it != first_it){

                assert(char2int(*next_it) == 0);

                *next_it = std::to_string(9)[0];

                next_it--;

            }



            localResult = up+10 -down;

         }

         assert(localResult>=0);

         resultStr += std::to_string(localResult);

        first_it++;

        second_it++;

    }

    std::reverse(resultStr.begin(), resultStr.end());

    return resultStr;



}



Integer Integer::operator*(const Integer& other) const {

    // Only allow multiplication when size is 1

    assert(size() == other.size() == 1);

    return std::to_string(std::stoi(fString)*std::stoi(other.fString));

}   



void Integer::padRight(size_t num){

    fString += std::string(num, '0');

}



void Integer::padLeft(size_t num){

    fString.insert(0,num,'0');

}



void Integer::print() const{

    std::cout << fString << std::endl;

}



void Integer::stripLeadingZeros(){

    // Don't strip if all are zeros - this will lead to an empty string

    if (std::all_of(fString.cbegin(), fString.cend(), (char c){return ('0'== c); })){

        return;

    }



    fString.erase(0, fString.find_first_not_of('0'));

}

Karatsuba multiplication

#include <string>

#include <assert.h>

#include <cmath>

#include "Integer.hpp"



Integer multiply(const Integer& inp1, const Integer& inp2){

    Integer first = inp1;

    Integer second = inp2;



    equalizeLengthsPadLeft(first, second);



    assert(first.size()==second.size());

    size_t sz = first.size();



    // Base case 

    if (sz == 1){

        return first*second;

    }



    int n = sz/2;

    Integer A = first.substr(0,n);

    Integer B = first.substr(n, sz-n);

    Integer C = second.substr(0,n);

    Integer D = second.substr(n, sz-n);



    Integer AC = multiply(A, C);

    Integer BD = multiply(B, D);



    Integer A_plus_B = A+B;

    Integer C_plus_D = C+D;

    Integer sum =  multiply(A_plus_B, C_plus_D);

    Integer AD_plus_BC = sum - AC - BD;



    AC.padRight(2*(sz-n));

    AD_plus_BC.padRight(sz-n);



    Integer result = AC+ AD_plus_BC + BD;

    result.stripLeadingZeros();



    return result;



}



int main(){

    Integer first("3141592653589793238462643383279502884197169399375105820974944592");

    Integer second("2718281828459045235360287471352662497757247093699959574966967627");



    Integer ans = multiply(first, second);



    ans.print();

}