-
-
Save kebunit/4fa83273090837fc1157 to your computer and use it in GitHub Desktop.
//============================================================================ | |
// 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 | |
* | |
* 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_ */ |
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.
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.
In line 33, it should be
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 oflong long
. Even you cannot cannot call thatmultiply()
function with an argument2>>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 justa*b
because the latter is calculated in CPU with just one instruction. However the former takes much more instructions to get the result.