Clarification of Answer by
maniac-ga
on
09 Feb 2003 15:29 PST
Hello Amirehsans,
As the separate comment says, base 10 (or 10^n) division can be
considered in the way you learned long division. Generate each digit
of the result from either repeated subtraction or by some other
method.
I can't directly convert the example to base 10^n arithmetic, so let
me take another approach to understand the code that I referred to. I
built a version where the "digits" were 8 bits in size (zero to 256)
and have added several print statements to display intermediate
values. The sample I used was
500678 / 1000 = 500, remainder 678
The values are displayed in hexidecimal (for intermediate values) or
decimal (loop indicies). I will comment on the results to help relate
them to the code.
BnnDivide: nn (4) = 0007A3C6, dd (2) = 03E8, entry
[for reference, nn == 500678, the digits are 00, 07, A3, C6; dd ==
500, 03, E8]
BnnDivide: nn (4) = 01E8F180, dd (2) = FA00, nshift = 6
[after normalization, both values shifted left six positions]
divide: nn (3) = E8F180, dd (2) = FA00
[same values, now at entry of divide function]
divide: BaseMinus1 = FF
divide: DDigit = FA
divide: dd (2) = 0600
[D was replaced by Base-D]
[Now in the loop of divide, the first pass - the second half of the if
statement was taken.]
BDivDigit: nn (2) = 01E8, d = FA, entry
[first two digits of nn - 01, E8 = 488; d - FA = 250; result should be
Q=1, rem=238 - EE]
BDivDigit: so(BNP)>so(BND)
[size of BigNumberProduct is more than the size of BigNumberDigit.
This is the then part of the if statement. As the comment mentions,
having smaller chunks make the arithmetic simpler.]
BDivDigit: nl=1, qq=B0, quad=1, before loop
BDivDigit: nl=0, qq=01, quad=ee, in loop
BDivDigit: quad=ee, return
divide: QApp = 01, digits not equal
[note - return value from BnnDivDigit of Quotient=01, remainder=EE,
check]
divide: nn+ni (3) = 01EEF1, dd (2) = 0600, QApp = 01, compute
remainder
[second time through the divide loop, second half of the if taken]
BDivDigit: nn (2) = EEF1, d = FA, entry
[first two digits of nn - EE, F1 = 61169; d - FA = 250; result should
be Q=244 - F4, rem=169 - A9]
BDivDigit: so(BNP)>so(BND)
BDivDigit: nl=1, qq=EE, quad=ee, before loop
BDivDigit: nl=0, qq=F4, quad=a9, in loop
BDivDigit: quad=a9, return
divide: QApp = F4, digits not equal
[note - correct result again, Quotient is F4=244, remainder A9=169]
divide: nn+ni (3) = F4A980, dd (2) = 0600, QApp = F4, compute
remainder
divide: nn (4) = 01F4A980, dd (2) = FA00, returning
BnnDivide: nn (4) = 01F4A980, dd (2) = FA00
[just prior to the normalization step]
BnnDivide: nn (4) = 01F402A6, dd (2) = 03E8
[values in nn are 01, F4 = 500 (result); 02, A6 = 678; dd are 03, E8 =
1000]
Watching the example run, we did not run all the code. However, the
remaining code works in a similar manner. It might also be easier to
understand if the code did not overwrite some of the variables used -
that would certainly be something to consider as you write your
version. The other thing to remember is the methods that work in this
example for 2^8 (base 256) works in the same way for 2^16, 2^32, and
so on. I made no changes to the algorithms - just changed a few
constants and declarations in the header file (to use 8 bit signed /
unsigned characters as the "digits").
In putting together this example, I ended up using the "bz" package as
well to call the functions in the bn directory. The main program was
about a dozen lines of code (to convert two strings to "BigZ"'s, do
the division, and print the result). I am including the test program
for reference below.
#include <stdio.h>
#include "BigZ.h"
int main () {
BigZ A, B, C;
A = BzFromString("500678", 10);
B = BzFromString("1000", 10);
C = BzDiv(A, B);
printf("500678/1000 is %s\n", BzToString(C, 10));
return 0;
}
If there are still some unclear parts - let me know. Indicate
specifically which steps you are having trouble with so I can focus on
those steps.
--Maniac
