CODEWITHSUNDEEP
assembly32-bitbigintriscv
Erick
Erick

Reputation: 73

Arbitrary-precision integer division, how to deal with 32-bit remainders?

I need to divide a number N by another number D, both bigger than my word length which is 32 bits

Currently i'm using the algorithm found in here: http://justinparrtech.com/JustinParr-Tech/an-algorithm-for-arbitrary-precision-integer-division/

I'm implementing my solution for the RISC-V ISA

But in the third step when Q = N / A, I don't know what to do in the case the remainder is also a 32-bit number, because usually i would use this remainder for the division of the next word but if it is the size of the register its impossible to take it into account.

I've been thinking how to solve this but every solution i come up with i feel its not the best way to do it.

Upvotes: 0

Views: 1726

Answers (1)

Brendan
Brendan

Reputation: 37232

That algorithm is horrible.

The first step should be to determine the sign of the result (from the sign of the numerator and divisor); then find the magnitude of the numerator and divisor (and have short-cuts for the "numerator is 0" and "abs(divisor) is 0 or 1" cases where actually doing a division is avoidable or impossible) so that the code that does the actual division only ever deals with positive numbers.

The second step should be to determine if the divisor is small enough to fit in a single digit (with digits that are in whatever base is the largest that your language/environment supports - e.g. for C with 32-bit integers it might be "base 65536", and for 64-bit 80x86 assembly language (where you can use 128-bit numerators) it might be "base 18446744073709551616"). At this point you branch to one of 2 completely different algorithms.

Small Divisor

This is a relatively trivial "for each digit in numerator { divide digit by divisor to find the digit in the result}" loop (followed by fixing up the sign of the result that you determined at the start).

Large Divisor

For this I'd use binary division. The idea is to shift the numerator and divisor left/right so that divisor becomes as large as possible without being larger than the numerator. Then you subtract divisor from numerator and set the bit in the result that corresponds to how much you shifted left/right; and repeat this, so that (after the initial shifting) it ends up being "shift whatever remains of the numerator left; then compare to divisor, and if numerator is larger than divisor subtract divisor from numerator and set bit in result" in a loop that terminates when there's nothing remaining of the numerator).

Off-Topic Alternative

For most cases where you need arbitrary-precision division; it's better to use rational numbers where each number is stored as three (arbitrary sized) integers - numerator, divisor and exponent (like number = numerator/divisor * (1 << exponent)). In this case you never need to divide - you only multiply by the reciprocal. This makes it better for performance, but also significantly better for precision (e.g. you can calculate (1/3) * 6 and guarantee that there will be no precision loss).

Upvotes: 6

Related Questions