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

[noreply at github.com]

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