4

I am working in a system which only supports 32bit integers, in order to have a 64bit (unsigned) integer I decided to simply use two 32bit integers with one being the upper 32 bits (hi), and the other being the lower 32 bits (lo).

I also needed to create arithmetic for this [hi, lo] structure, but I found it near impossible to search for already existing arithmetic on such structures. The only useful thing I could find is the arithmetic written in openSUSE: https://github.com/openSUSE/checkmedia/blob/master/u64.h

Is there a name for what I'm trying to do? (Simulating a double-wide integer with a [hi, lo] structure and implementing arithmetic using bitwise operations)

'Arbitrary-precision arithmetic' is close, however I'm not working with infinite precision.

6
  • 1
    Searching for "64bit arithmetic with 32bit ints" on google gives a lot of relevant results.
    – Mat
    Dec 8 '19 at 7:16
  • 1
    Since the openSUSE code does seem to not contain multiplication and division code, I guess that is what you are after? Googling for "64 32 bit arithmetic source code" brought me this and this
    – Doc Brown
    Dec 8 '19 at 7:25
  • Thank you, that's actually what I was looking for. It makes sense to me now to split the 32-bit integers into 16-bit integers and multiply those. I'd still like to know if there's an actual name for this kind of arithmetic though, or if it has no name and is just a general concept of math/programming.
    – AlphaDelta
    Dec 8 '19 at 9:30
  • Look up how 8 bit microcontrollers do 16 bit arithmetic, the lessons and considerations will be the same. Dec 8 '19 at 16:37
  • 1
    @AlphaDelta: I don't think there is a more specific name than "32 bit arithmetic" or "base 2^32 arithmetic" (as in base-10 arithmetic). According to Wikipedia, the multiplication algorithm is called long multiplication, or grade-school multiplication or "standard" algorithm (to the base 2^32 instead of base 10, of course.) The division method is called long division.
    – Doc Brown
    Dec 8 '19 at 18:19
5

Given any system which supports standard math operations -- add, subtract, multiply, divide -- on n bits, you first need to keep in mind some rules. If you are using sign-magnitude representation you lose a bit of potential value, but the math is simpler. If you are only handling unsigned, it simplifies even more. The rules below presume you are using twos-complement number representation.

  1. The max absolute value you can store is 2^(n-1) in any n-bit location. The total range is -2^(n-1)...0...+(2^(n-1)-1), e.g. -32768...0...+32767 for 16-bit twos-complement numbers.
  2. Addition of two numbers with the same sign can generate an answer with n+1 bits required to represent the result: 2^(n-1) + 2^(n-1) == 2 * 2^(n-1) == 2^(n-1+1) == 2^(n)
  3. Subtraction of two numbers with opposite sign can also generate an answer with n+1 bits required to represent the result.
  4. Multiplication of two numbers can generate an answer with 2n-2 bits required to represent the result: 2^(n-1) * 2^(n-1) == 2^(n-1+n-1) == 2^(2n-2)
  5. Division is always hardest! You must somehow handle zero-divisor, and you have to consider whether to round or not for integer division, and floating-point? Well, implementing floating-point standards -- IEEE 754 -- is not trivial, but I have done it. Intel botched accuracy of the first Pentium Floating-point implementation with a small bug.

All modern processors support addition/subtraction. Floating-point units are still the exception rather than the norm, but are becoming more widely used.

For the system you describe, you have two 32-bit values, which you can further subdivide into four 16-bit values or eight 8-bit values. The algorithms are the same, you just have to iterate more. This page describes the basic rules for two's-complement arithmetic.

I will presume you have access to register-level processor access so you can get at status bits like carry, overflow, etc.

Given two 64-bit numbers, X = ab and Y = cd and Result = KL, where a, b, c, d, K, and L are "32-bit digits" in your numberland the following approaches work:

Addition:

  • L = b + d. Set Cl to the carry value after the addition.
  • K = a + c + Cl. (If more than two 'digits', track the carry and move up the chain to higher-order digits.)
  • Use the addition rule to check for overflow in KL.

Subtraction:

  • L = b - d. Set Cl to the underflow (same as carry on a lot of processors) value after the addition.
  • K = a - c - Cl. (If more than two 'digits', track the underflow/carry and move up the chain.)
  • Use the subtraction rule to check for overflow in KL.

As described in the link above, multiplication and division can be performed by addition and subtraction, but you must account for a possible 128-bit result.

 subterm bits:    64       96           96         128
=========================================================
X * Y = ab * cd = b*d + b*c << 32 + a*d << 32 + a*c << 64

i.e. 4 multiplies and 3 adds.

...however, you must account for the intermediate terms which can be larger than your 64-bit numberland.

Represent the result as 2 of your 64-bit numbers, either as an array of two, or as a struct with 4 32-bit values. The following shows use of an array, because it is extensible to arbitrary precision by making the array larger.

Let result = R[2], where each entry in R is one of your 64-bit numbers:

Initialize result (simplifies the algorithm a bit.)

R[0].lo = 0;    // call this L, lowest-order result "digit"
R[0].hi = 0;    // call this K
R[1].lo = 0;    // call this J
R[1].hi = 0;    // call this I, highest-order result "digit"

If X.hi is a, X.lo is b, Y.hi is c, and Y.lo is d, this becomes

(KL)  = X.lo * Y.lo;      // 62-bits max, rule #4.
                          // Note no carry possible from K.
                          // Carry from L handled by Addition, above.
(JK) += X.lo * Y.hi;      // 63-bits max, rule #4, #2.
                          // Note that K contains the value from the
                          // previous step, hence the "+=" operator.
                          // Also note no carry possible from J.
                          // Carry from K handled by Addition, above.
(JK) += X.hi * Y.lo;      // 64-bits max, rule #4, #2.
                          // Note that JK contains the value from the
                          // previous step, hence the "+=" operator.
                          // Also note no carry possible from J.
                          // Carry from K handled by Addition, above.
(IJ) += X.hi * Y.hi;      // 62-bits max, rule #4, #2.
                          // Note that J contains the value from the
                          // previous step, hence the "+=" operator.
                          // Also note no carry possible from I
                          // because we kept a 128-bit result.
                          //  If we only wanted a 64-bit result,
                          // the overflow tests would be by testing K.

Now apply the addition rules from the link above to determine if you overflowed 64 bits.

For subtraction you do the same, subtracting instead of adding, and tracking underflow for Rc. Then you apply the subtraction rules from the link to determine if you overflowed 64 bits.

Once you have multi-precision working for addition/subtraction for two "digits" of arbitrary bit width, extending it to three, four, etc., is very straightforward.

Then, for simplicity, you use the multiply/divide approach used in the above link to multiply and divide in your two-digit system or any higher-precision system.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.