Your Try GMP! page
tonybrown at cox.net
tonybrown at cox.net
Thu Jan 11 06:43:08 CET 2007
I am attempting to write my own library, which processes large numbers for various purposes. I am working on my division function. I was using your Try GMP! page for testing (for which I thank you very much!) and discovered the following situation:
As a test case for my program, I wanted to perform the following division:
7295002640174 / 83729
GMP, as well as my program, gives
87126355
as the answer. All well and dandy.
However, I also want my program to have sign correctness.
So, I tried my program as follows:
-7295002640174 / 83729
and got the answer:
-87126356
Notice the 6 on the end now. So I tried GMP and it gave the same answer!
So, I reverted back to my basic number theory, any number should be expressible as
n = qk + r where q=quotient and r=remainder.
When I divide with your GMP, you don't provide the remainder of the division. However, taking simpler numbers, lets say we want to divide 7/4. My take on this is as follows, using n=qk+r:
the sign of the quotient is the XOR of the signs of the dividend and divisor, so for example,
-7/4 : quotient is -1 and if -7 = -1(k) + r , then k must be 4 and r must be -3
7/-4 : quotient is -1 and if 7 = -1(k) + r , then k must be -4 and r must be 3
-7/-4 : quotient is 1 and if -7 = 1(k) + r , then k must be -4 and r must be -3
7/4 : quotient is 1 and if 7 = 1(k) + r , then k must be 4 and r must be 3
GMP also gives an answer of -87126356 for
-7295002640174 / 83729
However, if both dividend and divisor are the same sign GMP always gives:
87126355
Now, I had this same issue in my program and resolved it by running the algorithm as if both dividend and divisor were positive. I calculated the signs independently. I have not yet root caused the issue, but my current solution works, (even if not optimally!)
My program now gives the following results:
Operation: DIVISION
Dividend: 7295002640174
Divisor: 83729
Quotient: 87126355
Remainder: 62379
Operation: DIVISION
Dividend: -7295002640174
Divisor: 83729
Quotient: -87126355
Remainder: -62379
Operation: DIVISION
Dividend: 7295002640174
Divisor: -83729
Quotient: -87126355
Remainder: 62379
Operation: DIVISION
Dividend: -7295002640174
Divisor: -83729
Quotient: 87126355
Remainder: -62379
So, only the signs of the quotient and remainder are affected by the signs of the dividend and divisor, not the values. Although the value of my remainder was never affected.
Please let me know what you think about this issue. Again, thanks for helping me test my program as well as my understanding of basic numerical operations.
Tony
More information about the gmp-discuss
mailing list