Fixed size arithmatics

[Torbjorn Granlund]

Basel Alomair <alomair at u.washington.edu> writes:

  I need to perform fixed size arithmetic (addition and multiplication) on unsigned integers. For example, I want to define three 128-bit integers, a, b, and c. When I do c=a*b, I want multiplication to abort whatever beyond the 128th bit. I know I can use modular operations to get the right result, but efficiency is a factor in my code. The problem with GMP is that when I define a 128-bit integer as
  
   mpz_init2(sum1, 128);
  
  the variable “sum1” will grow automatically, if necessary. But I want the result to always stay within 128 bits, without using the modular operation.
  
  Basically, I want something similar to basic C. When I identify three unsigned long integers a, b, and c; c=a*b will always be a 32-bit integer.
  
GMP cannot do what you want.

If you're on a 64-bit machine (which you should be on if efficiency is
an issue) you should be able to implement someting without too much
headache using some GMP internals.

The key is the longlong.h file (which incidentally is shared among
several GNU programs including GCC).  You will need to define a few
things, described at the beginning of longlong.h before you include it.
Then you will have 64x64->128 bit multiplication, and 128-bit addition
and subtraction.    64x64->128 bit multiplication is a building block
for the multiplication you need.

-- 
Torbjörn