[phobos] [D-Programming-Language/phobos] 9ecf94: 5568 A problem with BigInt modulus

Brad Roberts braddr at puremagic.com
Wed Feb 23 13:41:27 PST 2011


Looks like the biguintcore unit tests are pissed off, across the board (well, I'm assuming freebsd will eventually show
the same problem, it's not caught up yet).

On 2/23/2011 1:14 PM, noreply at github.com wrote:
> Branch: refs/heads/master Home:   https://github.com/D-Programming-Language/phobos
> 
> Commit: 9ecf947290f1149e1b062a75dafd30326697fe00 
> https://github.com/D-Programming-Language/phobos/commit/9ecf947290f1149e1b062a75dafd30326697fe00 Author: Don Clugston
> <dclugston at googlemail.com> Date:   2011-02-23 (Wed, 23 Feb 2011)
> 
> Changed paths: M std/bigint.d M std/internal/math/biguintcore.d
> 
> Log Message: ----------- 5568 A problem with BigInt modulus
> 
> This is quite subtle. The recursive division algorithm has a possibility of one bit of overflow in the second
> recursive call, in cases where the top quarter of the dividend is identical to the top half of the divisor. The
> description of the recursive division algorithm in "Modern Computer Arithmetic" 0.5.9 is rather vague about this
> (which is why I missed it originally, though the test case does cause assert failure in biguint). Unfortunately it
> requires fairly substantial changes to the function, which makes the algorithm a lot less elegant. But I have managed
> to implement it without any change to the basic division algorithm (which is very fast).
> 
> 
> Commit: 9fa7393417015257342401860ea4a2fa4f55db41 
> https://github.com/D-Programming-Language/phobos/commit/9fa7393417015257342401860ea4a2fa4f55db41 Author: Walter
> Bright <walter at walterbright.com> Date:   2011-02-23 (Wed, 23 Feb 2011)
> 
> Changed paths: M std/bigint.d M std/internal/math/biguintcore.d
> 
> Log Message: ----------- Merge branch 'bigint5568' of https://github.com/donc/phobos into donc-bigint5568
> 
> 
> _______________________________________________ phobos mailing list phobos at puremagic.com 
> http://lists.puremagic.com/mailman/listinfo/phobos



More information about the phobos mailing list