449,315 Members | 1,672 Online Need help? Post your question and get tips & solutions from a community of 449,315 IT Pros & Developers. It's quick & easy.

# division problem

 P: n/a Supposed unsigned int(32 bits) is the largest number that computer can represent with a single variable. Now, i have a big integer ( less than 64 bit, but great than 32 bit) . i represent it by this way: unsigned int dividend : divident store low 32 bits of big integer, dividend store high 32 bits of big integer. my problem is how make a division, like this quotient = big integer/ divisor, remainder = big integer mod divisor (divisor is 32 bit unsigned integer); how can i get quotient, and remainder ? thanks your help! Dec 22 '06 #1
13 Replies

 P: n/a "ja********@gmail.com"

 P: n/a ja********@gmail.com said: Supposed unsigned int(32 bits) is the largest number that computer can represent with a single variable. Now, i have a big integer ( less than 64 bit, but great than 32 bit) . i represent it by this way: unsigned int dividend : divident store low 32 bits of big integer, dividend store high 32 bits of big integer. my problem is how make a division, like this quotient = big integer/ divisor, remainder = big integer mod divisor (divisor is 32 bit unsigned integer); how can i get quotient, and remainder ? Let the big number be N: 11001110100111111001101001001010111010110101101010 11010110101010 Let the divisor be D: 10111011101100111101010101010101 Let S0 be the difference between the top bits of N and the whole of D. Q: 1 ------------------------------------------------------------------- N: 11001110100111111001101001001010111010110101101010 11010110101010 D: 10111011101100111101010101010101 ----------------------------------- S0:00010010111010111100010011110101 Get the next bit from N: Q: 10 ------------------------------------------------------------------- N: 11001110100111111001101001001010111010110101101010 11010110101010 D: 10111011101100111101010101010101 ----------------------------------- 00100101110101111000100111101011 D: 10111011101100111101010101010101 Get the next bit from N: Q: 100 ------------------------------------------------------------------- N: 11001110100111111001101001001010111010110101101010 11010110101010 D: 10111011101100111101010101010101 ----------------------------------- 01001011101011110001001111010111 D: 10111011101100111101010101010101 Get the next bit from N: Q: 1000 ------------------------------------------------------------------- N: 11001110100111111001101001001010111010110101101010 11010110101010 D: 10111011101100111101010101010101 ----------------------------------- 10010111010111100010011110101111 D: 10111011101100111101010101010101 Get the next bit from N: Q: 10001 ------------------------------------------------------------------- N: 11001110100111111001101001001010111010110101101010 11010110101010 D: 10111011101100111101010101010101 ----------------------------------- 100101110101111000100111101011110 D: 10111011101100111101010101010101 ------------------------------- S1: 1110011000010000111101000001000 Get the next bit from N: Q: 100011 ------------------------------------------------------------------- N: 11001110100111111001101001001010111010110101101010 11010110101010 D: 10111011101100111101010101010101 ----------------------------------- 100101110101111000100111101011110 D: 10111011101100111101010101010101 ------------------------------- 11100110000100001111010000010001 D: 10111011101100111101010101010101 etc etc etc. (I might have got some of the bits mixed up because I did this by hand, but you'll be doing this automatically.) When you run out of bits, Q is your quotient and whatever is left over is, strangely enough, your remainder. Division is much simpler in binary than in any other number base, since your program only has to know your 1-times table. Either D is greater than the set of bits you're currently comparing with (in which case the Q-bit is 0), or it isn't (in which case the Q-bit is 1). Subtract and move on. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Dec 22 '06 #3

 P: n/a

 P: n/a David T. Ashley said: Richard Heathfield suggested bit-shifting, and for your problem this will work just fine. However, it is [very!] suboptimal, even in the case you proposed. I agree. I was about to suggest TAOCP 2 to him (which is what I used), but at the last minute I figured he'd prefer simple. :-) -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Dec 23 '06 #5

 P: n/a Thanks very much. Richard Heathfield suggest to make a divsion bit-one-bit ( divison is replaced by many substract )£¬ it works. thanks. however i guess this method can work better in hardware than software implementent. Also thank you ,David T.Ashely. i will turn to TAOCP 2 for more help. Dec 24 '06 #6

 P: n/a "Richard Heathfield" >Richard Heathfield suggested bit-shifting, and for your problem this willwork just fine. However, it is [very!] suboptimal, even in the case youproposed. I agree. I was about to suggest TAOCP 2 to him (which is what I used), but at the last minute I figured he'd prefer simple. :-) My natural assumption was that you were unaware of the classic division algorithm (which was apparently not the case). I agree that simpler is better for someone doing it the first time. I've had this same discussion multiple times with people who _should_ know the best algorithms. In one case a compiler vendor was not aware of the existence of the better algorithm (their 32/32 divide routine was suboptimal on a small micro that has a 16/8=8 division instruction). It seems to be the norm that about 99% of people know the classic ADD/ADC algorithms for addition and subtraction, 85% know or can figure out how to use the processor's MUL instruction to handle long integer multiplication, but only about 25% are aware of the classic division algorithm. 75% bit-shift. It is logically correct -- just depends how efficient you need to be. Dec 25 '06 #7

 P: n/a David T. Ashley wrote: "Richard Heathfield" Richard Heathfield suggested bit-shifting, and for your problem this will work just fine. However, it is [very!] suboptimal, even in the case you proposed. I agree. I was about to suggest TAOCP 2 to him (which is what I used), but at the last minute I figured he'd prefer simple. :-) My natural assumption was that you were unaware of the classic division algorithm (which was apparently not the case). I agree that simpler is better for someone doing it the first time. I've had this same discussion multiple times with people who _should_ know the best algorithms. In one case a compiler vendor was not aware of the existence of the better algorithm (their 32/32 divide routine was suboptimal on a small micro that has a 16/8=8 division instruction). It seems to be the norm that about 99% of people know the classic ADD/ADC algorithms for addition and subtraction, 85% know or can figure out how to use the processor's MUL instruction to handle long integer multiplication, but only about 25% are aware of the classic division algorithm. 75% bit-shift. It is logically correct -- just depends how efficient you need to be. To do division efficently, the classical solution is to use Newton's methd. http://en.wikipedia.org/wiki/Division_(digital) It might be a bit crunchy to use it on integers, so why not just perform a double division and then assign it? I guess that it is a lot faster than emulating hardware. The IBM Jikes Compiler has a 64 bit number class for 32 bit machines. It is C++ but it would not be too hard to convert it to be C function calls. Dec 26 '06 #8

 P: n/a On 12ÔÂ26ÈÕ, ÏÂÎç11Ê±24·Ö, dcor...@connx.com wrote: >To do division efficently, the classical solution is to use Newton's methd.http://en.wikipedia.org/wiki/Division_(digital) It might be a bit crunchy to use it on integers, so why not just perform a double division and then assign it? I guess that it is a lot faster than emulating hardware. The IBM Jikes Compiler has a 64 bit number class for 32 bit machines. It is C++ but it would not be too hard to convert it to be C function calls. I want to know the general method to do division. if the divident is 1024 bits , and divisor 256 bit, division instructions of computer hardly do the job directly. According to Richard Heathfield 's suggestion , i write a fuction . however, its efficiency is poor when integer grow larger. ================================================== ========== #define BITS_PER_INTEGER 32 /* a help fuction , fetch a bit from a integer */ unsigned int get_bit(unsigned int dividend[], int pos) /* pos : position of requested bit, start from 0 */ { unsigned int bit; unsigned int mask = 0; int i=0; int j = 0; i = pos / BITS_PER_INTEGER ; j = pos % BITS_PER_INTEGER ; mask = (1U) << j; bit = (dividend[i] & mask) >j ; return bit ; } unsigned int div_binary( unsigned int dividend[], unsigned int divisor, unsigned int quotient[]) /* 64 bits integer dividend div 32 bits integer divsior * quotient[] is quotient , return value is remainder */ { unsigned int bit, shifted_out; unsigned int num_bits = 64; unsigned int part = 0; unsigned int mask; int i, j; if (divisor == 0) return 0; mask = (1U)<< (BITS_PER_INTEGER-1) ; for (i= num_bits-1; i>= 0; i--){ /* one round handle a bit */ bit = get_bit(dividend,i); shifted_out = (part&mask)>>(BITS_PER_INTEGER-1); part = (part << 1)|bit ; if (part >= divisor) { part = part - divisor; j = i / BITS_PER_INTEGER; quotient[j] = (quotient[j] << 1)| (1U); } else { if (shifted_out == 1) { part = divisor - part ; j = i / BITS_PER_INTEGER; quotient[j] = (quotient[j] << 1)| (1U); } else { j = i / BITS_PER_INTEGER; quotient[j] = (quotient[j] << 1)| (0U); } } } return part ; } ================================================== ========== i'm reading TAOCP 2 , Knuth method is very attractive and powerful. I want to write a divison function that can handle divison between any size of integer according Knuth method (as an exercise). As soon as i finish , i will post here. Dec 26 '06 #9

 P: n/a ja********@gmail.com wrote: [snip] I want to know the general method to do division. if the divident is 1024 bits , and divisor 256 bit, division instructions of computer hardly do the job directly. [snip] The answer is Newton's method. If you use a binary schoolbook method, it's going to suck eggs. You might need extended precision number functions like GMP http://www.swox.com/gmp/ Or HPALIB: http://www.nongnu.org/hpalib/ Or NTL: http://www.cnr.berkeley.edu/~casterln/ntl/tour.html etc. This also might be worth a look: http://www.mindspring.com/~pate/ P.S. This problem has already been solved by the above mentioned software sets. But if you want to do it yourself it will be a worthwhile exercise. Dec 26 '06 #10

 P: n/a ja********@gmail.com said: I want to know the general method to do division. if the divident is 1024 bits , and divisor 256 bit, division instructions of computer hardly do the job directly. According to Richard Heathfield 's suggestion , i write a fuction . however, its efficiency is poor when integer grow larger. You specifically asked in your original article for advice on the case where your largest value had fewer than 64 bits but more than 32, and so you were using an array of exactly two 32-bit values (low-32 in one element, and the remaining high bits in the other) as your dividend. Under those circumstances, the simple algorithm I described works reasonably well. When you change the spec, do not be surprised if the advice you were given for the simpler case is no longer reasonable. i'm reading TAOCP 2 , Knuth method is very attractive and powerful. Good. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Dec 26 '06 #11

 P: n/a To do division efficently, the classical solution is to use Newton's methd. http://en.wikipedia.org/wiki/Division_(digital) It might be a bit crunchy to use it on integers, so why not just perform a double division and then assign it? I guess that it is a lot faster than emulating hardware. The IBM Jikes Compiler has a 64 bit number class for 32 bit machines. It is C++ but it would not be too hard to convert it to be C function calls. It appears that the method won't pay off over classic division until the operands are fairly large: http://www.swox.com/list-archives/gm...er/002549.html For the kind of work I do, 64 bits is a HUGE integer (eight bytes, wow!). I need to read up on this. Dec 26 '06 #12

 P: n/a David T. Ashley wrote:

 P: n/a See also: http://www.azillionmonkeys.com/qed/adiv.html http://www.cse.ucsc.edu/research/kes...apers/new2.pdf http://www.cs.uiowa.edu/~jones/bcd/divide.html ftp://arith.stanford.edu/tr/oberman.jul95.tr675.ps.Z Alverson, Robert. "Integer Division Using Reciprocals." In Proceedings IEEE 10th Symposium on Computer Arithmetic, June 26-28, 1991, Grenoble, France, 186-190 http://www.cs.princeton.edu/~wayne/k...05multiply.pdf http://209.85.165.104/search?q=cache...&ct=clnk&cd=12 http://www.dsprelated.com/showmessage/48180/1.php http://books.elsevier.com/companions...appendix-h.pdf Dec 27 '06 #14

### This discussion thread is closed

Replies have been disabled for this discussion. 