[ create a new paste ] login | about

Link: http://codepad.org/1OTeGqhA    [ raw code | output | fork ]

k06a - C++, pasted on Jun 15:
// Karatsuba multiplication example

#include <stdlib.h>
#include <iostream>

using namespace std;

//
// 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(T * const x, T * const y, T2 * res)
{
    // Define vars (depending 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]);

    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++;
}

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;
}


Output:
1
2000000


Create a new paste based on this one


Comments: