OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 // Copyright 2009 The Go Authors. All rights reserved. | 5 // Copyright 2009 The Go Authors. All rights reserved. |
6 // Use of this source code is governed by a BSD-style | 6 // Use of this source code is governed by a BSD-style |
7 // license that can be found in the LICENSE file. | 7 // license that can be found in the LICENSE file. |
8 | 8 |
9 /* | 9 /* |
10 * Copyright (c) 2003-2005 Tom Wu | 10 * Copyright (c) 2003-2005 Tom Wu |
(...skipping 1024 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1035 var i = r_used + (r_used & 1); | 1035 var i = r_used + (r_used & 1); |
1036 var j = i - y_used; | 1036 var j = i - y_used; |
1037 // t_digits is a temporary array of i digits. | 1037 // t_digits is a temporary array of i digits. |
1038 var t_digits = new Uint32List(i); | 1038 var t_digits = new Uint32List(i); |
1039 var t_used = _dlShiftDigits(y_digits, y_used, j, t_digits); | 1039 var t_used = _dlShiftDigits(y_digits, y_used, j, t_digits); |
1040 // Explicit first division step in case normalized dividend is larger or | 1040 // Explicit first division step in case normalized dividend is larger or |
1041 // equal to shifted normalized divisor. | 1041 // equal to shifted normalized divisor. |
1042 if (_compareDigits(r_digits, r_used, t_digits, t_used) >= 0) { | 1042 if (_compareDigits(r_digits, r_used, t_digits, t_used) >= 0) { |
1043 assert(i == r_used); | 1043 assert(i == r_used); |
1044 r_digits[r_used++] = 1; // Quotient = 1. | 1044 r_digits[r_used++] = 1; // Quotient = 1. |
1045 r_digits[r_used] = 0; // Leading zero. | |
1046 // Subtract divisor from remainder. | 1045 // Subtract divisor from remainder. |
1047 _absSub(r_digits, r_used, t_digits, t_used, r_digits); | 1046 _absSub(r_digits, r_used, t_digits, t_used, r_digits); |
| 1047 } else { |
| 1048 // Account for possible carry in _mulAdd step. |
| 1049 r_digits[r_used++] = 0; |
1048 } | 1050 } |
| 1051 r_digits[r_used] = 0; // Leading zero for 64-bit processing. |
1049 // Negate y so we can later use _mulAdd instead of non-existent _mulSub. | 1052 // Negate y so we can later use _mulAdd instead of non-existent _mulSub. |
1050 var ny_digits = new Uint32List(y_used + 2); | 1053 var ny_digits = new Uint32List(y_used + 2); |
1051 ny_digits[y_used] = 1; | 1054 ny_digits[y_used] = 1; |
1052 _absSub(ny_digits, y_used + 1, y_digits, y_used, ny_digits); | 1055 _absSub(ny_digits, y_used + 1, y_digits, y_used, ny_digits); |
1053 // ny_digits is read-only and has y_used digits (possibly including several | 1056 // ny_digits is read-only and has y_used digits (possibly including several |
1054 // leading zeros) plus a leading zero for 64-bit processing. | 1057 // leading zeros) plus a leading zero for 64-bit processing. |
1055 // r_digits is modified during iteration. | 1058 // r_digits is modified during iteration. |
1056 // r_digits[0..y_used-1] is the current remainder. | 1059 // r_digits[0..y_used-1] is the current remainder. |
1057 // r_digits[y_used..r_used-1] is the current quotient. | 1060 // r_digits[y_used..r_used-1] is the current quotient. |
1058 --i; | 1061 --i; |
(...skipping 71 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1130 // For 64-bit processing, make sure y_used, i, and j are even. | 1133 // For 64-bit processing, make sure y_used, i, and j are even. |
1131 assert(y_used.isEven); | 1134 assert(y_used.isEven); |
1132 var i = r_used + (r_used & 1); | 1135 var i = r_used + (r_used & 1); |
1133 var j = i - y_used; | 1136 var j = i - y_used; |
1134 var t_used = _dlShiftDigits(y_digits, y_used, j, t_digits); | 1137 var t_used = _dlShiftDigits(y_digits, y_used, j, t_digits); |
1135 // Explicit first division step in case normalized dividend is larger or | 1138 // Explicit first division step in case normalized dividend is larger or |
1136 // equal to shifted normalized divisor. | 1139 // equal to shifted normalized divisor. |
1137 if (_compareDigits(r_digits, r_used, t_digits, t_used) >= 0) { | 1140 if (_compareDigits(r_digits, r_used, t_digits, t_used) >= 0) { |
1138 assert(i == r_used); | 1141 assert(i == r_used); |
1139 r_digits[r_used++] = 1; // Quotient = 1. | 1142 r_digits[r_used++] = 1; // Quotient = 1. |
1140 r_digits[r_used] = 0; // Leading zero. | |
1141 // Subtract divisor from remainder. | 1143 // Subtract divisor from remainder. |
1142 _absSub(r_digits, r_used, t_digits, t_used, r_digits); | 1144 _absSub(r_digits, r_used, t_digits, t_used, r_digits); |
| 1145 } else { |
| 1146 // Account for possible carry in _mulAdd step. |
| 1147 r_digits[r_used++] = 0; |
1143 } | 1148 } |
| 1149 r_digits[r_used] = 0; // Leading zero for 64-bit processing. |
1144 // Negated y_digits passed in ny_digits allow the use of _mulAdd instead of | 1150 // Negated y_digits passed in ny_digits allow the use of _mulAdd instead of |
1145 // unimplemented _mulSub. | 1151 // unimplemented _mulSub. |
1146 // ny_digits is read-only and has y_used digits (possibly including several | 1152 // ny_digits is read-only and has y_used digits (possibly including several |
1147 // leading zeros) plus a leading zero for 64-bit processing. | 1153 // leading zeros) plus a leading zero for 64-bit processing. |
1148 // r_digits is modified during iteration. | 1154 // r_digits is modified during iteration. |
1149 // r_digits[0..y_used-1] is the current remainder. | 1155 // r_digits[0..y_used-1] is the current remainder. |
1150 // r_digits[y_used..r_used-1] is the current quotient. | 1156 // r_digits[y_used..r_used-1] is the current quotient. |
1151 --i; | 1157 --i; |
1152 while (j > 0) { | 1158 while (j > 0) { |
1153 var d0 = _estQuotientDigit(yt_qd, r_digits, i); | 1159 var d0 = _estQuotientDigit(yt_qd, r_digits, i); |
(...skipping 643 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1797 | 1803 |
1798 int _mul(Uint32List x_digits, int x_used, | 1804 int _mul(Uint32List x_digits, int x_used, |
1799 Uint32List y_digits, int y_used, | 1805 Uint32List y_digits, int y_used, |
1800 Uint32List r_digits) { | 1806 Uint32List r_digits) { |
1801 var r_used = _Bigint._mulDigits(x_digits, x_used, | 1807 var r_used = _Bigint._mulDigits(x_digits, x_used, |
1802 y_digits, y_used, | 1808 y_digits, y_used, |
1803 r_digits); | 1809 r_digits); |
1804 return _reduce(r_digits, r_used); | 1810 return _reduce(r_digits, r_used); |
1805 } | 1811 } |
1806 } | 1812 } |
OLD | NEW |