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 performs Gauss' trick (complex multiplication algorithm).
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();
}
AD_plus_BCis introduced in the code. \$\endgroup\$