FAST C/C++ Implementation of the Karatsuba Multiplication algorithm. This is the only C++ implementation that I found online that uses straight C++ primitives to store data instead of std::vector or std::string objects. Because of this, it's pretty speedy. You can use this file in your program

KaratsubaMultiplication.cpp

//============================================================================
// Name        : KaratsubaMultiplication.cpp
// Author      : Evin Ugur (http://evinugur.com)
// Version     : 1.0
// Copyright   : Copyright 2015. You can use this code however and wherever you want no strings attached
// Description : C++ Functions to Perform Karatsbuba Multiplications
//============================================================================

#include <iostream>
#include <math.h>
#include "KaratsubaMultiplication.h"
using namespace std;



int getLength(long long value) {
	int counter = 0;
	while (value != 0) {
		counter++;
		value /= 10;
	}
	return counter;
}

long long multiply(long long x, long long y) {
	int xLength = getLength(x);
	int yLength = getLength(y);

	// the bigger of the two lengths
	int N = (int)(fmax(xLength, yLength));

	// if the max length is small it's faster to just flat out multiply the two nums
	if (N < 10)
		return x * y;

	//max length divided and rounded up
	N = (N/2) + (N%2);

	long long multiplier = pow(10, N);

	long long b = x/multiplier;
	long long a = x - (b * multiplier);
	long long d = y / multiplier;
	long long c = y - (d * N);

	long long z0 = multiply(a,c);
	long long z1 = multiply(a + b, c + d);
	long long z2 = multiply(b, d);


    return z0 + ((z1 - z0 - z2) * multiplier) + (z2 * (long long)(pow(10, 2 * N)));

}


// C++ example (uses cout...)
// (this code works in straight C too though if you use a different main function)
int main() {
	// two numbers
	long long a = 2406994;
	long long b = 2328563;
	cout << multiply(a,b) << endl;
	return 0;
}

KaratsubaMultiplication.h

/*
 * KaratsubaMultiplication.h
 *
 *  Created on: Feb 4, 2015
 *      Author: Evin Ugur (http://evinugur.com)
 */

#ifndef KARATSUBAMULTIPLICATION_H_
#define KARATSUBAMULTIPLICATION_H_

int getLength(long long value); // returns the number of digits a number has
long long multiply(long long x, long long y); // Karatsuba multiplication of two numbers



#endif /* KARATSUBAMULTIPLICATION_H_ */

What a ridiculous implementation! How did the author came up with the idea that let's implement it in built-in type long long.
This implementation can never deliver the result of 2^65 * 2^65 because it returns type of long long. Even you cannot cannot call that multiply() function with an argument 2>>65 since there will be an overflow. (compiler will complain as well.)

By the way, even you multiply the numbers that fit in long long, that function (multiply()) will be rather slower than just a*b because the latter is calculated in CPU with just one instruction. However the former takes much more instructions to get the result.

Could you please generalize it for the general numbers of base n.
@OrkhanAlikhanov,Although this multiplication may not be the best, but it serves it purpose, KaratsubaMultiplication.cpp

@orkhan
I think the intent here is to show a implementation so that can people can craft their own long number multiplication routine. Also C++ Language do not assume multiplication is possible with 1 instruction, so theorically on certain CPU architectures this code can (not necessarily) be faster than generated compiler assembly.

@ketankr9

http://code.geeksforgeeks.org/LwO51C

I have just tried to make the above code to general algorithm for base n

Is it possible to use this code to multiply x = 499; y = 123? Once I change if (N < 10) to if (N < 2) it goes into infinite recursion.

Hi kebunit,
It has been a long time since this great code has been written!
Thank you! It is the best KARA code I found on the google.

There is a little comment:
On the 44th line:
long long c = y - (d * N);

It maybe should be like:
long long c = y - (d * multiplier);

Hey I didn't understand the 33rd line. Why is it N<10? Isn't it just multiplying it directly because 2406994 has N=7 digits and N<10 so it just directly multiplies and returns 2406994 * 2328563 without actually going through the whole process.

By necessity you need integer arrays to perform multiplications large enough to obtain any optimization from using Karatsuba. How people think this code is fast (or actually does anything) is beyond me. It's theorectically impossible to write karatsuba algorithm faster than naive multiplication with only two 64-bit numbers; it requires at least two numbers of 5 radix_n length, any less requires more operations than long multiplication. Because multiplication of 64bit is executable as single instruction you can treat it as the radix instead of using ten or any other smaller (and therefore wasteful) number.

This Code would not Work for 64 Digit Value, as it would return 19 instead of 64.

In line 33, it should be $N==1$. Because you have got the length of value $x$.