I'm implementing karatsuba's multiplication algorithm in C and while debugging I found this error I can't explain: In every step I split the numbers to multiply in halves, which I do by assigning the appropriate pointers to my data type. When I output my values I get this:
a->l: 8 a->u: 4 a->v: 0x51fc270 a: 4072
b->l: 8 b->u: 4 b->v: 0x51fc278 b: 6718
which turns into (for a)
a->l: 2 a->u: 2 a->v: 0x51fc272 a: 00
b->l: 2 b->u: 2 b->v: 0x51fc270 b: 00
and (for b)
a->l: 2 a->u: 2 a->v: 0x51fc27a a: 00
b->l: 2 b->u: 2 b->v: 0x51fc278 b: 00
There are no write accesses in between those two outputs and the first two structures always produce the same output.
Could anybody explain this behavior? Cause I am truly lost..
The structs holding the data look like this
struct mp_type
{
int l, u; //length of v and places used (length of number stored)
char* v; //array which stores the value (the number)
};
typedef struct mp_type mp_int;
the last value is the number stored in the array v.
// high has lower address as low order digits are stored at the end of the array
mp_int low1, low2, high1, high2;
high1.l = high1.u = a->u / 2;
low1.l = low1.u = a->u - high1.u;
low1.v = a->v + low1.u;
high1.v = a->v;
high2.l = high2.u = b->u / 2;
low2.l = low2.u = b->u - high2.u;
low2.v = (b->v + low2.u);
high2.v = b->v;
That's how I split the numbers. a->u and b->u are always even numbers.
Here1 you find a slimmer version of the project, that reproduces the error.