• Advertisement
Sign in to follow this  

arbitrary big integer divisions

This topic is 1649 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
Advertisement

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