src/share/classes/java/math/MutableBigInteger.java

Print this page 
rev 8880 : 8029501: BigInteger division algorithm selection heuristic is incorrect
Summary: Change Burnikel-Ziegler division heuristic to require that the dividend int-length exceed that of the divisor by a minimum amount.
Reviewed-by: TBD


1131         }
1132 
1133         quotient.normalize();
1134         // Unnormalize
1135         if (shift > 0)
1136             return rem % divisor;
1137         else
1138             return rem;
1139     }
1140 
1141     /**
1142      * Calculates the quotient of this div b and places the quotient in the
1143      * provided MutableBigInteger objects and the remainder object is returned.
1144      *
1145      */
1146     MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient) {
1147         return divide(b,quotient,true);
1148     }
1149 
1150     MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient, boolean needRemainder) {
1151         if (intLen < BigInteger.BURNIKEL_ZIEGLER_THRESHOLD ||
1152                 b.intLen < BigInteger.BURNIKEL_ZIEGLER_THRESHOLD) {
1153             return divideKnuth(b, quotient, needRemainder);
1154         } else {
1155             return divideAndRemainderBurnikelZiegler(b, quotient);
1156         }
1157     }
1158 
1159     /**
1160      * @see #divideKnuth(MutableBigInteger, MutableBigInteger, boolean)
1161      */
1162     MutableBigInteger divideKnuth(MutableBigInteger b, MutableBigInteger quotient) {
1163         return divideKnuth(b,quotient,true);
1164     }
1165 
1166     /**
1167      * Calculates the quotient of this div b and places the quotient in the
1168      * provided MutableBigInteger objects and the remainder object is returned.
1169      *
1170      * Uses Algorithm D in Knuth section 4.3.1.
1171      * Many optimizations to that algorithm have been adapted from the Colin
1172      * Plumb C library.




1131         }
1132 
1133         quotient.normalize();
1134         // Unnormalize
1135         if (shift > 0)
1136             return rem % divisor;
1137         else
1138             return rem;
1139     }
1140 
1141     /**
1142      * Calculates the quotient of this div b and places the quotient in the
1143      * provided MutableBigInteger objects and the remainder object is returned.
1144      *
1145      */
1146     MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient) {
1147         return divide(b,quotient,true);
1148     }
1149 
1150     MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient, boolean needRemainder) {
1151         if (b.intLen < BigInteger.BURNIKEL_ZIEGLER_THRESHOLD ||
1152                 intLen - b.intLen < BigInteger.BURNIKEL_ZIEGLER_OFFSET) {
1153             return divideKnuth(b, quotient, needRemainder);
1154         } else {
1155             return divideAndRemainderBurnikelZiegler(b, quotient);
1156         }
1157     }
1158 
1159     /**
1160      * @see #divideKnuth(MutableBigInteger, MutableBigInteger, boolean)
1161      */
1162     MutableBigInteger divideKnuth(MutableBigInteger b, MutableBigInteger quotient) {
1163         return divideKnuth(b,quotient,true);
1164     }
1165 
1166     /**
1167      * Calculates the quotient of this div b and places the quotient in the
1168      * provided MutableBigInteger objects and the remainder object is returned.
1169      *
1170      * Uses Algorithm D in Knuth section 4.3.1.
1171      * Many optimizations to that algorithm have been adapted from the Colin
1172      * Plumb C library.