graceh@linus.UUCP (Grace L. Hammonds) (07/10/83)
Does anyone have fixes for bugs in the arbitrary precision integer arithmetic package that came with our 4.1bsd system, /usr/src/lib/libmp? I recently found a problem in the division routine, but there may be others I haven't come across yet. I discovered the bug when I tried to divide a 10-digit number into twice that number less one. The remainder should have been the divisor less one, but it was much too low. The trouble seems to start at 1073741825 = 2^30+1 (I haven't been able to get it to fail at numbers smaller than that), where I get the following results: (2 * (2^30+1) - 1) mod (2^30+1) = 2^30-2, instead of 2^30 Using 2^30+3: (2 * (2^30+3) - 1) mod (2^30+3) = 2^30-(2^16), instead of 2^30+2 Actually, any information you have on the package would be appreciated, because it came undocumented.
graceh@linus.UUCP (Grace L. Hammonds) (08/04/83)
The bug in the libmp division routine, mdiv, that I reported earlier has
been solved by changing a declaration in the m_dsb subroutine of the mdiv.c
file. The variable 'u' should be declared short instead of int. My thanks
to watdaisy!dtaylor for this solution.
For those who may have missed the original posting, the problem was
described this way:
----
I discovered the bug when I tried to divide a 10-digit number into twice
that number less one. The remainder should have been the divisor less one,
but it was much too low. The trouble seems to start at 1073741825 = 2^30+1
(I haven't been able to get it to fail at numbers smaller than that), where
I get the following results:
(2 * (2^30+1) - 1) mod (2^30+1) = 2^30-2, instead of 2^30
Using 2^30+3:
(2 * (2^30+3) - 1) mod (2^30+3) = 2^30-(2^16), instead of 2^30+2
--
--Grace Hammonds
{allegra,genrad,ihnp4,utzoo,philabs,uw-beaver}!linus!graceh (UUCP)
linus!graceh@mitre-bedford (ARPA)