> Thanks very much !!! :D

> > >I'm currently doing a university assignment and I need to be able to

> > >implement 64 bit multiplication. As such I need to hold a 128 bit

> > >number. I know that I need to use long long to store the 64 bit

> > >numbers, but as a newbie to this I am not sure how to do the

> > >multiplication. Can anyone help me with this either pointing me to a

> > >tutorial, or just some general help?

> > Assuming that (ULONG_MAX+1) ** 2 == (ULLONG_MAX+1), a *naive* analysis

> > of the problem goes like this:

> > a = ah * (ULONG_MAX+1) + al

> > b = bh * (ULONG_MAX+1) + bl

> > a * b = ah * bh * (ULONG_MAX+1)**2 + (ah * bl + al * bh) * (ULONG_MAX+1) +

> > + al * bl

> > This means that the lower part of the result consists of al * bl + the

> > lower half of (ah * bl + al * bh) multiplied by (ULONG_MAX+1).

> > The higher half of the result consists from ah * bh +

> > the upper half of (ah * bl + al * bh) + the carry generated when

> > computing the lower half of the result.

> > A C program that implements this "algorithm" looks like this. For

> > simplicity reasons, an unsigned long long is assumed to be a 64-bit type.

> > fangorn:~/tmp 312> cat test.c

> > #include <stdio.h>

> > #include <limits.h>

> > int main()

> > {

> > unsigned long long a = ULLONG_MAX, b = ULLONG_MAX;

> > unsigned long long ah = a >> 32, al = a & 0xffffffff;

> > unsigned long long bh = b >> 32, bl = b & 0xffffffff;

> > unsigned long long rl, rh;

> > unsigned long long ahbh, ahbl, albh, albl;

> > unsigned long long ahbl_upper, ahbl_lower, albh_upper, albh_lower;

> > unsigned long long carry = 0;

> > ahbh = ah * bh;

> > ahbl = ah * bl;

> > albh = al * bh;

> > albl = al * bl;

> > ahbl_lower = ahbl << 32;

> > ahbl_upper = ahbl >> 32;

> > albh_lower = albh << 32;

> > albh_upper = albh >> 32;

> > rl = albl;

> > if ((rl += ahbl_lower) < ahbl_lower) carry++;

> > if ((rl += albh_lower) < albh_lower) carry++;

> > rh = ahbh + ahbl_upper + albh_upper + carry;

> > printf ("%016llx%016llx %llx\n", rh, rl, (1ull*ULONG_MAX)*ULONG_MAX);

> > return 0;

> > }

> > fangorn:~/tmp 313> gcc -std=c99 test.c

> > fangorn:~/tmp 314> ./a.out

> > fffffffffffffffe0000000000000001 fffffffe00000001

> > For comparison, the program also displays the result of

> > ULONG_MAX * ULONG_MAX computed using unsigned long long arithmetic.

> > The purists can add the following macros to eliminate most of the "magic"

> > constants used in the code:

> > #define OFFSET ((sizeof(long long) * CHAR_BIT) / 2)

> > #define MASK ((1ull << OFFSET) - 1)

> > The remaining assumption is that unsigned long long has an even number

> > of value bits and no padding bits.

> > Dan

Hi,