Advertisement Jump to content
Sign in to follow this  

arbitrary big integer divisions

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

If you intended to correct an error in the post then please contact us.

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 this post

Link to post
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.



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

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

Share this post

Link to post
Share on other sites

You would do binary long division. You need to use 


Much Tnx, I didn't know about this. I will take my time tu munch (crunch/digest) it..

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!