Unsigned 128-bit division on 64-bit machine

Question

I have a 128-bit number stored as 2 64-bit numbers ("Hi" and "Lo"). I need only to divide it by a 32-bit number. How could I do it, using the native 64-bit operations from CPU?

(Please, note that I DO NOT need an arbitrary precision library. Just need to know how to make this simple division using native operations. Thank you).

Answer 1

64t hi, lo;
32t div;

64t rhi = hi/div;
64t rlo = hi % div + lo/div;

Right?

(A+B)/C = A/C + B/C. Then take the remainder bits from the high order division and add it on to the low order bits.

Answer 2

Some c code here.

Answer 3

If you are storing the value (128-bits) using the largest possible native representation your architecture can handle (64-bits) you will have problems handling the intermediate results of the division (as you already found :) ).

But you always can use a SMALLER representation. What about FOUR numbers of 32-bits? This way you could use the native 64-bits operations without overflow problems.

A simple implementation (in Delphi) can be found here.