How to do manage 65bits allocation when doing 64 bits unsigned integer divison?

Question

I am now implementing 64bits unsigned integer division on 32bit machine.

I can represent 64bits unsigned integer with

struct { 
    unsigned int a, 
    unsigned int b
}

I am trying to implement this with restoring algorithm.

https://www.geeksforgeeks.org/restoring-division-algorithm-unsigned-integer/

I have to store 65bits for the accumulator and M, but how can I manage this..?

There must be millions of examples on how to do 64-bit arithmetic using 32-bit values (or 32-bit arithmetic using 16-bit values) if you just search around a little. — Some programmer dude, Sep 14 '19 at 08:39
A division function would take two struct as arguments and return one struct as a result. Use local variable in your function to store the accumulator and M. — AugustinLopez, Sep 14 '19 at 08:55
Why not just use the already existing 64bit type? Which probably is ”long long” — Fredrik, Sep 14 '19 at 09:23
besides, if there are already 32-bit divide instruction then that can also be used for accelerating the division [How can I perform 64-bit division with a 32-bit divide instruction?](https://stackoverflow.com/q/3572409/995714) — phuclv, Sep 14 '19 at 10:13
@Someprogrammerdude: The question does not ask for an algorithm to perform 64-bit arithmetic using 32-bit values. It asks about a specific problem OP believes they have with the algorithm they identified, namely managing a 65-bit during the algorithm. — Eric Postpischil, Sep 14 '19 at 11:44
@Fredik: How do you imagine a 64-bit type would hold 65 bits? And what makes you think their C implementation has a 64-bit integer type? — Eric Postpischil, Sep 14 '19 at 11:45
@Eric you don’t need to implement 64 bit division, just let the compiler handle it if you have a 64bit type. — Fredrik, Sep 14 '19 at 12:18
Why don't you `#include ` and simply use `int64_t` and `uint64_t`? Compiler would handle the division for you. Apart from that, it seems you basically need 64 bits and an additional bit. If your question is how to pack this single bit into a struct, the answer is you can't, since your struct will be padded to the next size multiple of its largest field anways. So if a `struct { int32_t a; uint8_t b; }`, it will still take (at least) 8 bytes. — vgru, Sep 14 '19 at 12:19
@Fredrik: So you are not answering the question OP asks. You might want to be clear about that; say you are proposing an alternative (which we do not know will work, since their C implementation may not support 64-bit types) that avoids the problem they asked about. — Eric Postpischil, Sep 14 '19 at 12:46

score 1 · Accepted Answer · answered Sep 14 '19 at 13:37

Although the article you link to appears to show using five bits for each of M and A when the dividend width is four bits, it fails to explicitly state what width to use or why. Nonetheless, the shift of A and Q as a single register can be readily accomplished:

Identify the top bit of Q.
Shift A left one bit and insert the top bit from Q as the low bit of A.
Shift Q left one bit, letting the top bit be shifted out (and lost).

This uses a shift of 33 bits for A, if it is 33 bits when you are using a basic width of 32 bits, and a shift of 32 bits for Q. No 65-bit shift or register is needed.

How to do manage 65bits allocation when doing 64 bits unsigned integer divison?

1 Answers1