470,830 Members | 1,815 Online

# division problem

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 ?

Dec 22 '06 #1
13 6755 "ja********@gmail.com" <ja********@gmail.comwrote:
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 ?
Long division.

HTH; HAND; DYODH.

Richard
Dec 22 '06 #2
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,

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
<ja********@gmail.comwrote in message
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 ?
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.

The key issue -- and it is the same situation for addition, subtraction, and
multiplication -- is that the processor inherently has integer addition,
subtraction, multiplication and division instructions; but they handle
operands smaller than you are interested in.

The key question is whether it is possible to use these "small" instructions
multiple times to deal with larger operands.

In the case of addition and subtraction, the answer is clearly YES. Even if
one is programming in 'C' and doesn't have direct access to the CARRY bit of
the processor, if the result of an addition is smaller than either of the
input arguments (which must be unsigned), then a carry occurred. With a
little thought, one can code multi-precision integer addition that doesn't
perform badly (although it won't be as efficient as assembly-language).

For example:

unsigned int input1; /* LSI first for all of these */
unsigned int input2;
unsigned int output; /* Result has one more int to hold carry out. */
unsigned int carryout;

output = input1 + input2;

if ((output < input1) || (output < input2))
carryout = 1;
else
carryout = 0;

output = input1 + input2;

if ((output < input1) || (output < input2))
output = 1;
else
output = 0;

/* Now, process the carry out of the LSI */
if (carryout)
{
output ++;
if (! output)
output ++;
}

I don't claim that I didn't make some kind of mistake in the above (I'm
doing this from scratch). The bottom line is that one can do addition and
subtraction of large integers in 'C' fairly effectively.

Note that the solution above uses the inherent ability of the processor to

The solution suggested by Richard Heathfield is just as crude as doing
addition one bit at a time (compared to the technique above).

I won't get into multiplication ... but there is a way to do that using the
processor's multiplication ability, too. You'll figure it out quickly if

And finally, division ... which is the toughest case.

If you try to do the algebra and figure out if you can use "small" machine
division instructions to accomplish a larger division, you'll rapidly come
to the conculsion that you can't. (Fortunately, Donald Knuth and his peers
are just a bit more experienced than you or I. It ends up there is a way to
do it.)

The process is very similar to the way people do longhand division. In
longhand division, people estimate one digit at a time, then multiply and
subtract, then go on to the next digit. Occasionally, one guesses wrong and
has to increase or decrease the quotient digit and re-do that digit.

In the algorithm, a "digit" is 16-32 bits; and the result of estimation may
be off by as much as 2 counts in one direction only (there is a simple and
cheap correction procedure).

The classic algorithm assumes that the machine has a division instruction
that takes a dividend of bitsize 2w, divides it by a divisor of bitsize w,
and produces a quotient of bitsize w and a remainder of bitsize w, with the
possibility of overflow (which is deliberately avoided by the algorithm).

For a typical desktop processor, w is 32 bits, so that in one machine
instruction you can do a 64/32 division. However, typically compilers will
only allow you to do a 32/32 division, so you have to use w=16 and apply the
standard algorithm.

The algorithm essentially will produce 16 bits of the result at a time
(versus 1 bit at a time from the bit-shifting approach).

If you have access to the assembly-language of the machine, normally you can
get [at least] 32 bits at a time.

The standard integer division algorithm is a bit awkward to code in 'C', but
when the data sizes are known in advance (as they are in your case), it gets
less awkward.

I won't include the code here (too much thought would be required).

Here are the resources you should look up.

a)Knuth covers this in Volume 2 of his classic work:

http://www.amazon.com/Art-Computer-P...e=UTF8&s=books

b)The GMP has some division code that is compiled in the event
assembly-language isn't available for the specific processor. This will use
the "digit estimation" technique I described.

c)Also, this URL should be helpful. It also cites Knuth.
http://en.wikipedia.org/wiki/Arbitra...ion_arithmetic

Heathfield's suggestion will work just fine. However, in the general case,
you don't want to do that.

Dave.

Dec 23 '06 #4
David T. Ashley said:

<snip>
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. :-)

<good stuff snipped>

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

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
"Richard Heathfield" <rj*@see.sig.invalidwrote in message
news:0b*********************@bt.com...
David T. Ashley said:

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

David T. Ashley wrote:
"Richard Heathfield" <rj*@see.sig.invalidwrote in message
news:0b*********************@bt.com...
David T. Ashley said:

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

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;
int i=0;
int j = 0;

i = pos / BITS_PER_INTEGER ;
j = pos % BITS_PER_INTEGER ;

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;
int i, j;
if (divisor == 0)
return 0;

for (i= num_bits-1; i>= 0; i--){
/* one round handle a bit */
bit = get_bit(dividend,i);
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
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
ja********@gmail.com said:

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

According to Richard Heathfield 's suggestion , i write a fuction .
however, its efficiency is poor when integer grow larger.
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.

<snip>
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
<dc*****@connx.comwrote in message
>
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

David T. Ashley wrote:
<dc*****@connx.comwrote in message

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.
They are not comparing Newton's method to classic method.
See:
http://swox.com/gmp/devel/
in the section: "New division code"

If you use the floating point hardware to approximate the answer, and
then use the approximation given (it will be good to about 15 digits on
most machines) then one iteration of Newton's method would give you 30
digits of precision, two iterations of Newton's method would give you
60 digits, three iterations 120 digits, etc.

Dec 27 '06 #13

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

 19 posts views Thread by Imbaud Pierre | last post: by 15 posts views Thread by joel | last post: by 6 posts views Thread by bart van deun | last post: by 8 posts views Thread by nineteen | last post: by 17 posts views Thread by seb.haase | last post: by 22 posts views Thread by jamestuck21 | last post: by 2 posts views Thread by kermit | last post: by 1 post views Thread by youjay | last post: by 16 posts views Thread by spl | last post: by reply views Thread by ryjfgjl | last post: by reply views Thread by prepawan | last post: by 1 post views Thread by DANILIN | last post: by reply views Thread by tracyyun | last post: by reply views Thread by mihailmihai484 | last post: by reply views Thread by patriciajames | last post: by 1 post views Thread by Stoney L | last post: by 2 posts views Thread by Dönerbude | last post: by reply views Thread by milkinvl | last post: by