// Karatsuba multiplication LE+BE (+undef)
#include <stdlib.h>
#include <iostream>
using namespace std;
// Determine Little-Endian or Big-Endian
#define CURRENT_BYTE_ORDER (*(int *)"\x01\x02\x03\x04")
#define LITTLE_ENDIAN_BYTE_ORDER 0x04030201
#define BIG_ENDIAN_BYTE_ORDER 0x01020304
#define PDP_ENDIAN_BYTE_ORDER 0x02010403
#define IS_LITTLE_ENDIAN (CURRENT_BYTE_ORDER == LITTLE_ENDIAN_BYTE_ORDER)
#define IS_BIG_ENDIAN (CURRENT_BYTE_ORDER == BIG_ENDIAN_BYTE_ORDER)
#define IS_PDP_ENDIAN (CURRENT_BYTE_ORDER == PDP_ENDIAN_BYTE_ORDER)
//
// Karatsuba multiplication algorithm
//
// +------+------+
// | x1 | x0 |
// +------+------+
// *
// +------+------+
// | y1 | y0 |
// +------+------+
// =
// +-------------+-------------+
// + | x1*y1 | x0*y0 |
// +----+-+------+------+------+
// . . .
// . . .
// +-+------+------+
// + | x0*y1 + x1*y0 |
// +-+------+------+
//
//
// Params:
// T - is type of x0, x1, y0 and y1 halves
// T2 - is type of x, y and half of res
//
template<typename T, typename T2>
inline void Karatsuba_multiply(const T * x, const T * y, T2 * res)
{
if (IS_LITTLE_ENDIAN)
return Karatsuba_multiply_little_endian(x,y,res);
if (IS_BIG_ENDIAN)
return Karatsuba_multiply_big_endian(x,y,res);
}
template<typename T, typename T2>
inline void Karatsuba_multiply_little_endian(const T * x, const T * y, T2 * res)
{
// Define vars (differs from byte order)
#define ptrRes ((T*)res)
T2 & lowWord = (T2&)(ptrRes[0]);
T2 & midWord = (T2&)(ptrRes[1]);
T2 & highWord = (T2&)(ptrRes[2]);
T & highByte = (T &)(ptrRes[3]);
#undef ptrRes
const T & x0 = x[0];
const T & x1 = x[1];
const T & y0 = y[0];
const T & y1 = y[1];
// Multiply action
lowWord = x0 * y0;
highWord = x1 * y1;
T2 m1 = x0 * y1;
T2 m2 = x1 * y0;
midWord += m1;
if (midWord < m1) highByte++;
midWord += m2;
if (midWord < m2) highByte++;
}
template<typename T, typename T2>
inline void Karatsuba_multiply_big_endian(const T * x, const T * y, T2 * res)
{
// Define vars (differs from byte order)
#define ptrRes ((T*)res)
T2 & highWord = *(T2*)(ptrRes+0);
T2 & midWord = *(T2*)(ptrRes+1);
T2 & lowWord = *(T2*)(ptrRes+2);
T & highByte = *(T *)(ptrRes+0);
const T & x0 = x[1];
const T & x1 = x[0];
const T & y0 = y[1];
const T & y1 = y[0];
// Multiply action
lowWord = x0 * y0;
highWord = x1 * y1;
T m1 = x0 * y1;
T m2 = x1 * y0;
midWord += m1;
if (midWord < m1) highByte++;
midWord += m2;
if (midWord < m2) highByte++;
}
int main()
{
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned int u32;
u16 a = 1000;
u16 b = 2000;
u32 r = 0;
u8 * a_ptr = (u8*)&a;
u8 * b_ptr = (u8*)&b;
u16 * r_ptr = (u16*)(void*)&r;
Karatsuba_multiply(a_ptr, b_ptr, r_ptr);
cout << r;
}