# arbitrary big integer divisions

This topic is 1742 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Some time ago I wonder how i would write some small library for arbitrary-big integer arithmetics

probably it would be proper to store such arbitrary big number as a vector of unsigned integers

addition would be simple, substraction would be simpe, multiplication probably could be done through some matrix-like-result multiplications and than sum up things (am i right?)

but what with division - can it calculated in some way close to such multiplication-result-matrix i write above? how could be such division done?

Edited by fir

##### Share on other sites

You would do binary long division. You need to use unsigned numbers since you can't 2's complement an arbitrarily large number... just follow the usual rules for negatives (i.e. -/- = +, +/+ = +, -/+ = -, +/- = -) once you do the unsigned version.

Wikipedia:

Integer division (unsigned) with remainder

The following algorithm, the binary version of the famous long division, will divide N by D, placing the quotient in Q and the remainder in R. All values are treated as unsigned integers.[citation needed]]]

if D == 0 then throw DivisionByZeroException end
Q := 0                 initialize quotient and remainder to zero
R := 0
for i = n-1...0 do     where n is number of bits
R := R << 1          left-shift R by 1 bit
R(0) := N(i)         set the least-significant bit of R equal to bit i of the numerator
if R >= D then
R = R - D
Q(i) := 1
end
end



You can do binary long multiplication for multiplying as well... although there are better algorithms for very large numbers of bits.

##### Share on other sites

You would do binary long division. You need to use

• 22
• 10
• 19
• 15
• 14