// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
-using System;\r
-using System.Collections.Generic;\r
-using System.Diagnostics;\r
-using System.Diagnostics.CodeAnalysis;\r
-using System.Globalization;\r
-using System.Text;\r
+// A big chuck of code comes the DLR (as hosted in http://ironpython.codeplex.com),
+// which has the following License:
+//
+/* ****************************************************************************
+ *
+ * Copyright (c) Microsoft Corporation.
+ *
+ * This source code is subject to terms and conditions of the Microsoft Public License. A
+ * copy of the license can be found in the License.html file at the root of this distribution. If
+ * you cannot locate the Microsoft Public License, please send an email to
+ * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
+ * by the terms of the Microsoft Public License.
+ *
+ * You must not remove this notice, or any other, from this software.
+ *
+ *
+ * ***************************************************************************/
+
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Diagnostics.CodeAnalysis;
+using System.Globalization;
+using System.Text;
+using System.Threading;
/*
Optimization
Use unsafe ops to avoid bounds check
CoreAdd could avoid some resizes by checking for equal sized array that top overflow
For bitwise operators, hoist the conditionals out of their main loop
-*/\r
-namespace System.Numerics {\r
- public struct BigInteger : IComparable, IComparable<BigInteger>, IEquatable<BigInteger>
+ Optimize BitScanBackward
+ Use a carry variable to make shift opts do half the number of array ops.
+ Schoolbook multiply is O(n^2), use Karatsuba /Toom-3 for large numbers
+*/
+namespace System.Numerics {
+ public struct BigInteger : IComparable, IFormattable, IComparable<BigInteger>, IEquatable<BigInteger>
{
//LSB on [0]
readonly uint[] data;
}
}
+
+ static bool Negative (byte[] v)
+ {
+ return ((v[7] & 0x80) != 0);
+ }
+
+ static ushort Exponent (byte[] v)
+ {
+ return (ushort)((((ushort)(v[7] & 0x7F)) << (ushort)4) | (((ushort)(v[6] & 0xF0)) >> 4));
+ }
+
+ static ulong Mantissa(byte[] v)
+ {
+ uint i1 = ((uint)v[0] | ((uint)v[1] << 8) | ((uint)v[2] << 16) | ((uint)v[3] << 24));
+ uint i2 = ((uint)v[4] | ((uint)v[5] << 8) | ((uint)(v[6] & 0xF) << 16));
+
+ return (ulong)((ulong)i1 | ((ulong)i2 << 32));
+ }
+
+ const int bias = 1075;
+ public BigInteger (double value)
+ {
+ if (double.IsNaN (value) || Double.IsInfinity (value))
+ throw new OverflowException ();
+
+ byte[] bytes = BitConverter.GetBytes (value);
+ ulong mantissa = Mantissa (bytes);
+ if (mantissa == 0) {
+ // 1.0 * 2**exp, we have a power of 2
+ int exponent = Exponent (bytes);
+ if (exponent == 0) {
+ sign = 0;
+ data = ZERO;
+ return;
+ }
+
+ BigInteger res = Negative (bytes) ? MinusOne : One;
+ res = res << (exponent - 0x3ff);
+ this.sign = res.sign;
+ this.data = res.data;
+ } else {
+ // 1.mantissa * 2**exp
+ int exponent = Exponent(bytes);
+ mantissa |= 0x10000000000000ul;
+ BigInteger res = mantissa;
+ res = exponent > bias ? res << (exponent - bias) : res >> (bias - exponent);
+
+ this.sign = (short) (Negative (bytes) ? -1 : 1);
+ this.data = res.data;
+ }
+ }
+
+ public BigInteger (float value) : this ((double)value)
+ {
+ }
+
+ const Int32 DecimalScaleFactorMask = 0x00FF0000;
+ const Int32 DecimalSignMask = unchecked((Int32)0x80000000);
+
+ public BigInteger (decimal value)
+ {
+ // First truncate to get scale to 0 and extract bits
+ int[] bits = Decimal.GetBits(Decimal.Truncate(value));
+
+ int size = 3;
+ while (size > 0 && bits[size - 1] == 0) size--;
+
+ if (size == 0) {
+ sign = 0;
+ data = ZERO;
+ return;
+ }
+
+ sign = (short) ((bits [3] & DecimalSignMask) != 0 ? -1 : 1);
+
+ data = new uint [size];
+ data [0] = (uint)bits [0];
+ if (size > 1)
+ data [1] = (uint)bits [1];
+ if (size > 2)
+ data [2] = (uint)bits [2];
+ }
+
[CLSCompliantAttribute (false)]
public BigInteger (byte[] value)
{
sign = 1;
if (sign == 1) {
- while (value [len - 1] == 0)
- --len;
+ while (value [len - 1] == 0) {
+ if (--len == 0) {
+ sign = 0;
+ data = ZERO;
+ return;
+ }
+ }
int full_words, size;
full_words = size = len / 4;
}
public bool IsEven {
- get { return (data [0] & 0x1) == 0; }
+ get { return sign == 0 || (data [0] & 0x1) == 0; }
}
public bool IsOne {
public static explicit operator int (BigInteger value)
{
+ if (value.sign == 0)
+ return 0;
if (value.data.Length > 1)
throw new OverflowException ();
uint data = value.data [0];
[CLSCompliantAttribute (false)]
public static explicit operator uint (BigInteger value)
{
+ if (value.sign == 0)
+ return 0;
if (value.data.Length > 1 || value.sign == -1)
throw new OverflowException ();
return value.data [0];
}
+ public static explicit operator short (BigInteger value)
+ {
+ int val = (int)value;
+ if (val < short.MinValue || val > short.MaxValue)
+ throw new OverflowException ();
+ return (short)val;
+ }
+
+ [CLSCompliantAttribute (false)]
+ public static explicit operator ushort (BigInteger value)
+ {
+ uint val = (uint)value;
+ if (val > ushort.MaxValue)
+ throw new OverflowException ();
+ return (ushort)val;
+ }
+
+ public static explicit operator byte (BigInteger value)
+ {
+ uint val = (uint)value;
+ if (val > byte.MaxValue)
+ throw new OverflowException ();
+ return (byte)val;
+ }
+
+ [CLSCompliantAttribute (false)]
+ public static explicit operator sbyte (BigInteger value)
+ {
+ int val = (int)value;
+ if (val < sbyte.MinValue || val > sbyte.MaxValue)
+ throw new OverflowException ();
+ return (sbyte)val;
+ }
+
+
public static explicit operator long (BigInteger value)
{
if (value.sign == 0)
return (((long)high) << 32) | low;
}
- if (high > 0x80000000u)
- throw new OverflowException ();
+ /*
+ We cannot represent negative numbers smaller than long.MinValue.
+ Those values are encoded into what look negative numbers, so negating
+ them produces a positive value, that's why it's safe to check for that
+ condition.
- return - ((((long)high) << 32) | (long)low);
+ long.MinValue works fine since it's bigint encoding looks like a negative
+ number, but since long.MinValue == -long.MinValue, we're good.
+ */
+
+ long result = - ((((long)high) << 32) | (long)low);
+ if (result > 0)
+ throw new OverflowException ();
+ return result;
}
[CLSCompliantAttribute (false)]
public static explicit operator ulong (BigInteger value)
{
+ if (value.sign == 0)
+ return 0;
if (value.data.Length > 2 || value.sign == -1)
throw new OverflowException ();
return (((ulong)high) << 32) | low;
}
+ public static explicit operator double (BigInteger value)
+ {
+ //FIXME
+ try {
+ return double.Parse (value.ToString (),
+ System.Globalization.CultureInfo.InvariantCulture.NumberFormat);
+ } catch (OverflowException) {
+ return value.sign == -1 ? double.NegativeInfinity : double.PositiveInfinity;
+ }
+ }
+
+ public static explicit operator float (BigInteger value)
+ {
+ //FIXME
+ try {
+ return float.Parse (value.ToString (),
+ System.Globalization.CultureInfo.InvariantCulture.NumberFormat);
+ } catch (OverflowException) {
+ return value.sign == -1 ? float.NegativeInfinity : float.PositiveInfinity;
+ }
+ }
+
+ public static explicit operator decimal (BigInteger value)
+ {
+ if (value.sign == 0)
+ return Decimal.Zero;
+
+ uint[] data = value.data;
+ if (data.Length > 3)
+ throw new OverflowException ();
+
+ int lo = 0, mi = 0, hi = 0;
+ if (data.Length > 2)
+ hi = (Int32)data [2];
+ if (data.Length > 1)
+ mi = (Int32)data [1];
+ if (data.Length > 0)
+ lo = (Int32)data [0];
+
+ return new Decimal(lo, mi, hi, value.sign < 0, 0);
+ }
public static implicit operator BigInteger (int value)
{
return new BigInteger (value);
}
+ public static implicit operator BigInteger (short value)
+ {
+ return new BigInteger (value);
+ }
+
+ [CLSCompliantAttribute (false)]
+ public static implicit operator BigInteger (ushort value)
+ {
+ return new BigInteger (value);
+ }
+
+ public static implicit operator BigInteger (byte value)
+ {
+ return new BigInteger (value);
+ }
+
+ [CLSCompliantAttribute (false)]
+ public static implicit operator BigInteger (sbyte value)
+ {
+ return new BigInteger (value);
+ }
+
public static implicit operator BigInteger (long value)
{
return new BigInteger (value);
return new BigInteger (value);
}
+ public static explicit operator BigInteger (double value)
+ {
+ return new BigInteger (value);
+ }
+
+ public static explicit operator BigInteger (float value)
+ {
+ return new BigInteger (value);
+ }
+
+ public static explicit operator BigInteger (decimal value)
+ {
+ return new BigInteger (value);
+ }
+
public static BigInteger operator+ (BigInteger left, BigInteger right)
{
if (left.sign == 0)
return new BigInteger (left.sign, CoreAdd (left.data, right.data));
}
+ public static BigInteger operator* (BigInteger left, BigInteger right)
+ {
+ if (left.sign == 0 || right.sign == 0)
+ return new BigInteger (0, ZERO);
+
+ if (left.data [0] == 1 && left.data.Length == 1) {
+ if (left.sign == 1)
+ return right;
+ return new BigInteger ((short)-right.sign, right.data);
+ }
+
+ if (right.data [0] == 1 && right.data.Length == 1) {
+ if (right.sign == 1)
+ return left;
+ return new BigInteger ((short)-left.sign, left.data);
+ }
+
+ uint[] a = left.data;
+ uint[] b = right.data;
+
+ uint[] res = new uint [a.Length + b.Length];
+
+ for (int i = 0; i < a.Length; ++i) {
+ uint ai = a [i];
+ int k = i;
+
+ ulong carry = 0;
+ for (int j = 0; j < b.Length; ++j) {
+ carry = carry + ((ulong)ai) * b [j] + res [k];
+ res[k++] = (uint)carry;
+ carry >>= 32;
+ }
+
+ while (carry != 0) {
+ carry += res [k];
+ res[k++] = (uint)carry;
+ carry >>= 32;
+ }
+ }
+
+ int m;
+ for (m = res.Length - 1; m >= 0 && res [m] == 0; --m) ;
+ if (m < res.Length - 1)
+ res = Resize (res, m + 1);
+
+ return new BigInteger ((short)(left.sign * right.sign), res);
+ }
+
+ public static BigInteger operator/ (BigInteger dividend, BigInteger divisor)
+ {
+ if (divisor.sign == 0)
+ throw new DivideByZeroException ();
+
+ if (dividend.sign == 0)
+ return dividend;
+
+ uint[] quotient;
+ uint[] remainder_value;
+
+ DivModUnsigned (dividend.data, divisor.data, out quotient, out remainder_value);
+
+ int i;
+ for (i = quotient.Length - 1; i >= 0 && quotient [i] == 0; --i) ;
+ if (i == -1)
+ return new BigInteger (0, ZERO);
+ if (i < quotient.Length - 1)
+ quotient = Resize (quotient, i + 1);
+
+ return new BigInteger ((short)(dividend.sign * divisor.sign), quotient);
+ }
+
+ public static BigInteger operator% (BigInteger dividend, BigInteger divisor)
+ {
+ if (divisor.sign == 0)
+ throw new DivideByZeroException ();
+
+ if (dividend.sign == 0)
+ return dividend;
+
+ uint[] quotient;
+ uint[] remainder_value;
+
+ DivModUnsigned (dividend.data, divisor.data, out quotient, out remainder_value);
+
+ int i;
+ for (i = remainder_value.Length - 1; i >= 0 && remainder_value [i] == 0; --i) ;
+ if (i == -1)
+ return new BigInteger (0, ZERO);
+
+ if (i < remainder_value.Length - 1)
+ remainder_value = Resize (remainder_value, i + 1);
+ return new BigInteger (dividend.sign, remainder_value);
+ }
+
public static BigInteger operator- (BigInteger value)
{
if (value.sign == 0)
public static BigInteger operator++ (BigInteger value)
{
+ if (value.sign == 0)
+ return One;
+
short sign = value.sign;
uint[] data = value.data;
if (data.Length == 1) {
public static BigInteger operator-- (BigInteger value)
{
+ if (value.sign == 0)
+ return MinusOne;
+
short sign = value.sign;
uint[] data = value.data;
if (data.Length == 1) {
return new BigInteger (neg_res ? (short)-1 : (short)1, result);
}
+ //returns the 0-based index of the most significant set bit
+ //returns 0 if no bit is set, so extra care when using it
+ static int BitScanBackward (uint word)
+ {
+ for (int i = 31; i >= 0; --i) {
+ uint mask = 1u << i;
+ if ((word & mask) == mask)
+ return i;
+ }
+ return 0;
+ }
+
+ public static BigInteger operator<< (BigInteger value, int shift)
+ {
+ if (shift == 0 || value.sign == 0)
+ return value;
+ if (shift < 0)
+ return value >> -shift;
+
+ uint[] data = value.data;
+ int sign = value.sign;
+
+ int topMostIdx = BitScanBackward (data [data.Length - 1]);
+ int bits = shift - (31 - topMostIdx);
+ int extra_words = (bits >> 5) + ((bits & 0x1F) != 0 ? 1 : 0);
+
+ uint[] res = new uint [data.Length + extra_words];
+
+ int idx_shift = shift >> 5;
+ int bit_shift = shift & 0x1F;
+ int carry_shift = 32 - bit_shift;
+
+ if (carry_shift == 32) {
+ for (int i = 0; i < data.Length; ++i) {
+ uint word = data [i];
+ res [i + idx_shift] |= word << bit_shift;
+ }
+ } else {
+ for (int i = 0; i < data.Length; ++i) {
+ uint word = data [i];
+ res [i + idx_shift] |= word << bit_shift;
+ if (i + idx_shift + 1 < res.Length)
+ res [i + idx_shift + 1] = word >> carry_shift;
+ }
+ }
+
+ return new BigInteger ((short)sign, res);
+ }
+
+ public static BigInteger operator>> (BigInteger value, int shift)
+ {
+ if (shift == 0 || value.sign == 0)
+ return value;
+ if (shift < 0)
+ return value << -shift;
+
+ uint[] data = value.data;
+ int sign = value.sign;
+
+ int topMostIdx = BitScanBackward (data [data.Length - 1]);
+ int idx_shift = shift >> 5;
+ int bit_shift = shift & 0x1F;
+
+ int extra_words = idx_shift;
+ if (bit_shift > topMostIdx)
+ ++extra_words;
+ int size = data.Length - extra_words;
+
+ if (size <= 0) {
+ if (sign == 1)
+ return new BigInteger (0, ZERO);
+ return new BigInteger (-1, ONE);
+ }
+
+ uint[] res = new uint [size];
+ int carry_shift = 32 - bit_shift;
+
+ if (carry_shift == 32) {
+ for (int i = data.Length - 1; i >= idx_shift; --i) {
+ uint word = data [i];
+
+ if (i - idx_shift < res.Length)
+ res [i - idx_shift] |= word >> bit_shift;
+ }
+ } else {
+ for (int i = data.Length - 1; i >= idx_shift; --i) {
+ uint word = data [i];
+
+ if (i - idx_shift < res.Length)
+ res [i - idx_shift] |= word >> bit_shift;
+ if (i - idx_shift - 1 >= 0)
+ res [i - idx_shift - 1] = word << carry_shift;
+ }
+
+ }
+
+ //Round down instead of toward zero
+ if (sign == -1) {
+ for (int i = 0; i < idx_shift; i++) {
+ if (data [i] != 0u) {
+ var tmp = new BigInteger ((short)sign, res);
+ --tmp;
+ return tmp;
+ }
+ }
+ if (bit_shift > 0 && (data [idx_shift] << carry_shift) != 0u) {
+ var tmp = new BigInteger ((short)sign, res);
+ --tmp;
+ return tmp;
+ }
+ }
+ return new BigInteger ((short)sign, res);
+ }
+
public static bool operator< (BigInteger left, BigInteger right)
{
return Compare (left, right) < 0;
{
if (sign != other.sign)
return false;
- if (data.Length != other.data.Length)
+
+ int alen = data != null ? data.Length : 0;
+ int blen = other.data != null ? other.data.Length : 0;
+
+ if (alen != blen)
return false;
- for (int i = 0; i < data.Length; ++i) {
+ for (int i = 0; i < alen; ++i) {
if (data [i] != other.data [i])
return false;
}
return CompareTo (other) == 0;
}
- public static BigInteger Min (BigInteger left, BigInteger right)
+ public override string ToString ()
{
- int ls = left.sign;
- int rs = right.sign;
+ return ToString (10, null);
+ }
- if (ls < rs)
- return left;
- if (rs < ls)
- return right;
+ string ToStringWithPadding (string format, uint radix, IFormatProvider provider)
+ {
+ if (format.Length > 1) {
+ int precision = Convert.ToInt32(format.Substring (1), CultureInfo.InvariantCulture.NumberFormat);
+ string baseStr = ToString (radix, provider);
+ if (baseStr.Length < precision) {
+ string additional = new String ('0', precision - baseStr.Length);
+ if (baseStr[0] != '-') {
+ return additional + baseStr;
+ } else {
+ return "-" + additional + baseStr.Substring (1);
+ }
+ }
+ return baseStr;
+ }
+ return ToString (radix, provider);
+ }
- int r = CoreCompare (left.data, right.data);
- if (ls == -1)
- r = -r;
+ public string ToString (string format)
+ {
+ return ToString (format, null);
+ }
- if (r <= 0)
- return left;
- return right;
+ public string ToString (IFormatProvider provider)
+ {
+ return ToString (null, provider);
}
- public static BigInteger Max (BigInteger left, BigInteger right)
+ public string ToString (string format, IFormatProvider provider)
{
- int ls = left.sign;
- int rs = right.sign;
+ if (format == null || format == "")
+ return ToString (10, provider);
- if (ls > rs)
- return left;
- if (rs > ls)
- return right;
+ switch (format[0]) {
+ case 'd':
+ case 'D':
+ case 'g':
+ case 'G':
+ case 'r':
+ case 'R':
+ return ToStringWithPadding (format, 10, provider);
+ case 'x':
+ case 'X':
+ return ToStringWithPadding (format, 16, null);
+ default:
+ throw new FormatException (string.Format ("format '{0}' not implemented", format));
+ }
+ }
- int r = CoreCompare (left.data, right.data);
- if (ls == -1)
- r = -r;
+ static uint[] MakeTwoComplement (uint[] v)
+ {
+ uint[] res = new uint [v.Length];
- if (r >= 0)
- return left;
- return right;
+ ulong carry = 1;
+ for (int i = 0; i < v.Length; ++i) {
+ uint word = v [i];
+ carry = (ulong)~word + carry;
+ word = (uint)carry;
+ carry = (uint)(carry >> 32);
+ res [i] = word;
+ }
+
+ uint last = res [res.Length - 1];
+ int idx = FirstNonFFByte (last);
+ uint mask = 0xFF;
+ for (int i = 1; i < idx; ++i)
+ mask = (mask << 8) | 0xFF;
+
+ res [res.Length - 1] = last & mask;
+ return res;
}
- public static BigInteger Abs (BigInteger value)
+ string ToString (uint radix, IFormatProvider provider)
+ {
+ const string characterSet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+
+ if (characterSet.Length < radix)
+ throw new ArgumentException ("charSet length less than radix", "characterSet");
+ if (radix == 1)
+ throw new ArgumentException ("There is no such thing as radix one notation", "radix");
+
+ if (sign == 0)
+ return "0";
+ if (data.Length == 1 && data [0] == 1)
+ return sign == 1 ? "1" : "-1";
+
+ List<char> digits = new List<char> (1 + data.Length * 3 / 10);
+
+ BigInteger a;
+ if (sign == 1)
+ a = this;
+ else {
+ uint[] dt = data;
+ if (radix > 10)
+ dt = MakeTwoComplement (dt);
+ a = new BigInteger (1, dt);
+ }
+
+ while (a != 0) {
+ BigInteger rem;
+ a = DivRem (a, radix, out rem);
+ digits.Add (characterSet [(int) rem]);
+ }
+
+ if (sign == -1 && radix == 10) {
+ NumberFormatInfo info = null;
+ if (provider != null)
+ info = provider.GetFormat (typeof (NumberFormatInfo)) as NumberFormatInfo;
+ if (info != null) {
+ string str = info.NegativeSign;
+ for (int i = str.Length - 1; i >= 0; --i)
+ digits.Add (str [i]);
+ } else {
+ digits.Add ('-');
+ }
+ }
+
+ char last = digits [digits.Count - 1];
+ if (sign == 1 && radix > 10 && (last < '0' || last > '9'))
+ digits.Add ('0');
+
+ digits.Reverse ();
+
+ return new String (digits.ToArray ());
+ }
+
+ public static BigInteger Parse (string value)
+ {
+ Exception ex;
+ BigInteger result;
+
+ if (!Parse (value, false, out result, out ex))
+ throw ex;
+ return result;
+ }
+
+ public static bool TryParse (string value, out BigInteger result)
+ {
+ Exception ex;
+ return Parse (value, true, out result, out ex);
+ }
+
+ public static BigInteger Parse (string value, NumberStyles style)
+ {
+ return Parse (value, style, null);
+ }
+
+ public static BigInteger Parse (string value, IFormatProvider provider)
+ {
+ return Parse (value, NumberStyles.Integer, provider);
+ }
+
+ public static BigInteger Parse (
+ string value, NumberStyles style, IFormatProvider provider)
+ {
+ Exception exc;
+ BigInteger res;
+
+ if (!Parse (value, style, provider, false, out res, out exc))
+ throw exc;
+
+ return res;
+ }
+
+ public static bool TryParse (
+ string value, NumberStyles style, IFormatProvider provider,
+ out BigInteger result)
+ {
+ Exception exc;
+ if (!Parse (value, style, provider, true, out result, out exc)) {
+ result = Zero;
+ return false;
+ }
+
+ return true;
+ }
+
+ internal static bool Parse (string s, NumberStyles style, IFormatProvider fp, bool tryParse, out BigInteger result, out Exception exc)
+ {
+ result = Zero;
+ exc = null;
+
+ if (s == null) {
+ if (!tryParse)
+ exc = new ArgumentNullException ("s");
+ return false;
+ }
+
+ if (s.Length == 0) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ NumberFormatInfo nfi = null;
+ if (fp != null) {
+ Type typeNFI = typeof(System.Globalization.NumberFormatInfo);
+ nfi = (NumberFormatInfo)fp.GetFormat (typeNFI);
+ }
+ if (nfi == null)
+ nfi = Thread.CurrentThread.CurrentCulture.NumberFormat;
+
+ if (!CheckStyle (style, tryParse, ref exc))
+ return false;
+
+ bool AllowCurrencySymbol = (style & NumberStyles.AllowCurrencySymbol) != 0;
+ bool AllowHexSpecifier = (style & NumberStyles.AllowHexSpecifier) != 0;
+ bool AllowThousands = (style & NumberStyles.AllowThousands) != 0;
+ bool AllowDecimalPoint = (style & NumberStyles.AllowDecimalPoint) != 0;
+ bool AllowParentheses = (style & NumberStyles.AllowParentheses) != 0;
+ bool AllowTrailingSign = (style & NumberStyles.AllowTrailingSign) != 0;
+ bool AllowLeadingSign = (style & NumberStyles.AllowLeadingSign) != 0;
+ bool AllowTrailingWhite = (style & NumberStyles.AllowTrailingWhite) != 0;
+ bool AllowLeadingWhite = (style & NumberStyles.AllowLeadingWhite) != 0;
+ bool AllowExponent = (style & NumberStyles.AllowExponent) != 0;
+
+ int pos = 0;
+
+ if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+
+ bool foundOpenParentheses = false;
+ bool negative = false;
+ bool foundSign = false;
+ bool foundCurrency = false;
+
+ // Pre-number stuff
+ if (AllowParentheses && s [pos] == '(') {
+ foundOpenParentheses = true;
+ foundSign = true;
+ negative = true; // MS always make the number negative when there parentheses
+ // even when NumberFormatInfo.NumberNegativePattern != 0!!!
+ pos++;
+ if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+
+ if (s.Substring (pos, nfi.NegativeSign.Length) == nfi.NegativeSign) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ if (s.Substring (pos, nfi.PositiveSign.Length) == nfi.PositiveSign) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+ }
+
+ if (AllowLeadingSign && !foundSign) {
+ // Sign + Currency
+ FindSign (ref pos, s, nfi, ref foundSign, ref negative);
+ if (foundSign) {
+ if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+ if (AllowCurrencySymbol) {
+ FindCurrency (ref pos, s, nfi,
+ ref foundCurrency);
+ if (foundCurrency && AllowLeadingWhite &&
+ !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+ }
+ }
+ }
+
+ if (AllowCurrencySymbol && !foundCurrency) {
+ // Currency + sign
+ FindCurrency (ref pos, s, nfi, ref foundCurrency);
+ if (foundCurrency) {
+ if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+ if (foundCurrency) {
+ if (!foundSign && AllowLeadingSign) {
+ FindSign (ref pos, s, nfi, ref foundSign,
+ ref negative);
+ if (foundSign && AllowLeadingWhite &&
+ !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+ }
+ }
+ }
+ }
+
+ BigInteger number = Zero;
+ int nDigits = 0;
+ int decimalPointPos = -1;
+ byte digitValue;
+ char hexDigit;
+ bool firstHexDigit = true;
+
+ // Number stuff
+ while (pos < s.Length) {
+
+ if (!ValidDigit (s [pos], AllowHexSpecifier)) {
+ if (AllowThousands &&
+ (FindOther (ref pos, s, nfi.NumberGroupSeparator)
+ || FindOther (ref pos, s, nfi.CurrencyGroupSeparator)))
+ continue;
+
+ if (AllowDecimalPoint && decimalPointPos < 0 &&
+ (FindOther (ref pos, s, nfi.NumberDecimalSeparator)
+ || FindOther (ref pos, s, nfi.CurrencyDecimalSeparator))) {
+ decimalPointPos = nDigits;
+ continue;
+ }
+
+ break;
+ }
+
+ nDigits++;
+
+ if (AllowHexSpecifier) {
+ hexDigit = s [pos++];
+ if (Char.IsDigit (hexDigit))
+ digitValue = (byte)(hexDigit - '0');
+ else if (Char.IsLower (hexDigit))
+ digitValue = (byte)(hexDigit - 'a' + 10);
+ else
+ digitValue = (byte)(hexDigit - 'A' + 10);
+
+ if (firstHexDigit && (byte)digitValue >= 8)
+ negative = true;
+
+ number = number * 16 + digitValue;
+ firstHexDigit = false;
+ continue;
+ }
+
+ number = number * 10 + (byte)(s [pos++] - '0');
+ }
+
+ // Post number stuff
+ if (nDigits == 0) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ //Signed hex value (Two's Complement)
+ if (AllowHexSpecifier && negative) {
+ BigInteger mask = BigInteger.Pow(16, nDigits) - 1;
+ number = (number ^ mask) + 1;
+ }
+
+ int exponent = 0;
+ if (AllowExponent)
+ if (FindExponent (ref pos, s, ref exponent, tryParse, ref exc) && exc != null)
+ return false;
+
+ if (AllowTrailingSign && !foundSign) {
+ // Sign + Currency
+ FindSign (ref pos, s, nfi, ref foundSign, ref negative);
+ if (foundSign && pos < s.Length) {
+ if (AllowTrailingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+ }
+ }
+
+ if (AllowCurrencySymbol && !foundCurrency) {
+ if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
+ return false;
+
+ // Currency + sign
+ FindCurrency (ref pos, s, nfi, ref foundCurrency);
+ if (foundCurrency && pos < s.Length) {
+ if (AllowTrailingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+ if (!foundSign && AllowTrailingSign)
+ FindSign (ref pos, s, nfi, ref foundSign,
+ ref negative);
+ }
+ }
+
+ if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
+ return false;
+
+ if (foundOpenParentheses) {
+ if (pos >= s.Length || s [pos++] != ')') {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+ if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
+ return false;
+ }
+
+ if (pos < s.Length && s [pos] != '\u0000') {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ if (decimalPointPos >= 0)
+ exponent = exponent - nDigits + decimalPointPos;
+
+ if (exponent < 0) {
+ //
+ // Any non-zero values after decimal point are not allowed
+ //
+ BigInteger remainder;
+ number = BigInteger.DivRem(number, BigInteger.Pow(10, -exponent), out remainder);
+
+ if (!remainder.IsZero) {
+ if (!tryParse)
+ exc = new OverflowException ("Value too large or too small. exp="+exponent+" rem = " + remainder + " pow = " + BigInteger.Pow(10, -exponent));
+ return false;
+ }
+ } else if (exponent > 0) {
+ number = BigInteger.Pow(10, exponent) * number;
+ }
+
+ if (number.sign == 0)
+ result = number;
+ else if (negative)
+ result = new BigInteger (-1, number.data);
+ else
+ result = new BigInteger (1, number.data);
+
+ return true;
+ }
+
+ internal static bool CheckStyle (NumberStyles style, bool tryParse, ref Exception exc)
+ {
+ if ((style & NumberStyles.AllowHexSpecifier) != 0) {
+ NumberStyles ne = style ^ NumberStyles.AllowHexSpecifier;
+ if ((ne & NumberStyles.AllowLeadingWhite) != 0)
+ ne ^= NumberStyles.AllowLeadingWhite;
+ if ((ne & NumberStyles.AllowTrailingWhite) != 0)
+ ne ^= NumberStyles.AllowTrailingWhite;
+ if (ne != 0) {
+ if (!tryParse)
+ exc = new ArgumentException (
+ "With AllowHexSpecifier only " +
+ "AllowLeadingWhite and AllowTrailingWhite " +
+ "are permitted.");
+ return false;
+ }
+ } else if ((uint) style > (uint) NumberStyles.Any){
+ if (!tryParse)
+ exc = new ArgumentException ("Not a valid number style");
+ return false;
+ }
+
+ return true;
+ }
+
+ internal static bool JumpOverWhite (ref int pos, string s, bool reportError, bool tryParse, ref Exception exc)
+ {
+ while (pos < s.Length && Char.IsWhiteSpace (s [pos]))
+ pos++;
+
+ if (reportError && pos >= s.Length) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ return true;
+ }
+
+ internal static void FindSign (ref int pos, string s, NumberFormatInfo nfi,
+ ref bool foundSign, ref bool negative)
+ {
+ if ((pos + nfi.NegativeSign.Length) <= s.Length &&
+ string.CompareOrdinal(s, pos, nfi.NegativeSign, 0, nfi.NegativeSign.Length) == 0) {
+ negative = true;
+ foundSign = true;
+ pos += nfi.NegativeSign.Length;
+ } else if ((pos + nfi.PositiveSign.Length) <= s.Length &&
+ string.CompareOrdinal(s, pos, nfi.PositiveSign, 0, nfi.PositiveSign.Length) == 0) {
+ negative = false;
+ pos += nfi.PositiveSign.Length;
+ foundSign = true;
+ }
+ }
+
+ internal static void FindCurrency (ref int pos,
+ string s,
+ NumberFormatInfo nfi,
+ ref bool foundCurrency)
+ {
+ if ((pos + nfi.CurrencySymbol.Length) <= s.Length &&
+ s.Substring (pos, nfi.CurrencySymbol.Length) == nfi.CurrencySymbol) {
+ foundCurrency = true;
+ pos += nfi.CurrencySymbol.Length;
+ }
+ }
+
+ internal static bool FindExponent (ref int pos, string s, ref int exponent, bool tryParse, ref Exception exc)
+ {
+ exponent = 0;
+
+ if (pos >= s.Length || (s [pos] != 'e' && s[pos] != 'E')) {
+ exc = null;
+ return false;
+ }
+
+ var i = pos + 1;
+ if (i == s.Length) {
+ exc = tryParse ? null : GetFormatException ();
+ return true;
+ }
+
+ bool negative = false;
+ if (s [i] == '-') {
+ negative = true;
+ if(++i == s.Length){
+ exc = tryParse ? null : GetFormatException ();
+ return true;
+ }
+ }
+
+ if (s [i] == '+' && ++i == s.Length) {
+ exc = tryParse ? null : GetFormatException ();
+ return true;
+ }
+
+ long exp = 0; // temp long value
+ for (; i < s.Length; i++) {
+ if (!Char.IsDigit (s [i])) {
+ exc = tryParse ? null : GetFormatException ();
+ return true;
+ }
+
+ // Reduce the risk of throwing an overflow exc
+ exp = checked (exp * 10 - (int) (s [i] - '0'));
+ if (exp < Int32.MinValue || exp > Int32.MaxValue) {
+ exc = tryParse ? null : new OverflowException ("Value too large or too small.");
+ return true;
+ }
+ }
+
+ // exp value saved as negative
+ if(!negative)
+ exp = -exp;
+
+ exc = null;
+ exponent = (int)exp;
+ pos = i;
+ return true;
+ }
+
+ internal static bool FindOther (ref int pos, string s, string other)
+ {
+ if ((pos + other.Length) <= s.Length &&
+ s.Substring (pos, other.Length) == other) {
+ pos += other.Length;
+ return true;
+ }
+
+ return false;
+ }
+
+ internal static bool ValidDigit (char e, bool allowHex)
+ {
+ if (allowHex)
+ return Char.IsDigit (e) || (e >= 'A' && e <= 'F') || (e >= 'a' && e <= 'f');
+
+ return Char.IsDigit (e);
+ }
+
+ static Exception GetFormatException ()
+ {
+ return new FormatException ("Input string was not in the correct format");
+ }
+
+ static bool ProcessTrailingWhitespace (bool tryParse, string s, int position, ref Exception exc)
+ {
+ int len = s.Length;
+
+ for (int i = position; i < len; i++){
+ char c = s [i];
+
+ if (c != 0 && !Char.IsWhiteSpace (c)){
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+ }
+ return true;
+ }
+
+ static bool Parse (string s, bool tryParse, out BigInteger result, out Exception exc)
+ {
+ int len;
+ int i, sign = 1;
+ bool digits_seen = false;
+
+ result = Zero;
+ exc = null;
+
+ if (s == null) {
+ if (!tryParse)
+ exc = new ArgumentNullException ("value");
+ return false;
+ }
+
+ len = s.Length;
+
+ char c;
+ for (i = 0; i < len; i++){
+ c = s [i];
+ if (!Char.IsWhiteSpace (c))
+ break;
+ }
+
+ if (i == len) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ var info = Thread.CurrentThread.CurrentCulture.NumberFormat;
+
+ string negative = info.NegativeSign;
+ string positive = info.PositiveSign;
+
+ if (string.CompareOrdinal (s, i, positive, 0, positive.Length) == 0)
+ i += positive.Length;
+ else if (string.CompareOrdinal (s, i, negative, 0, negative.Length) == 0) {
+ sign = -1;
+ i += negative.Length;
+ }
+
+ BigInteger val = Zero;
+ for (; i < len; i++){
+ c = s [i];
+
+ if (c == '\0') {
+ i = len;
+ continue;
+ }
+
+ if (c >= '0' && c <= '9'){
+ byte d = (byte) (c - '0');
+
+ val = val * 10 + d;
+
+ digits_seen = true;
+ } else if (!ProcessTrailingWhitespace (tryParse, s, i, ref exc))
+ return false;
+ }
+
+ if (!digits_seen) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ if (val.sign == 0)
+ result = val;
+ else if (sign == -1)
+ result = new BigInteger (-1, val.data);
+ else
+ result = new BigInteger (1, val.data);
+
+ return true;
+ }
+
+ public static BigInteger Min (BigInteger left, BigInteger right)
+ {
+ int ls = left.sign;
+ int rs = right.sign;
+
+ if (ls < rs)
+ return left;
+ if (rs < ls)
+ return right;
+
+ int r = CoreCompare (left.data, right.data);
+ if (ls == -1)
+ r = -r;
+
+ if (r <= 0)
+ return left;
+ return right;
+ }
+
+
+ public static BigInteger Max (BigInteger left, BigInteger right)
+ {
+ int ls = left.sign;
+ int rs = right.sign;
+
+ if (ls > rs)
+ return left;
+ if (rs > ls)
+ return right;
+
+ int r = CoreCompare (left.data, right.data);
+ if (ls == -1)
+ r = -r;
+
+ if (r >= 0)
+ return left;
+ return right;
+ }
+
+ public static BigInteger Abs (BigInteger value)
{
return new BigInteger ((short)Math.Abs (value.sign), value.data);
}
+
+ public static BigInteger DivRem (BigInteger dividend, BigInteger divisor, out BigInteger remainder)
+ {
+ if (divisor.sign == 0)
+ throw new DivideByZeroException ();
+
+ if (dividend.sign == 0) {
+ remainder = dividend;
+ return dividend;
+ }
+
+ uint[] quotient;
+ uint[] remainder_value;
+
+ DivModUnsigned (dividend.data, divisor.data, out quotient, out remainder_value);
+
+ int i;
+ for (i = remainder_value.Length - 1; i >= 0 && remainder_value [i] == 0; --i) ;
+ if (i == -1) {
+ remainder = new BigInteger (0, ZERO);
+ } else {
+ if (i < remainder_value.Length - 1)
+ remainder_value = Resize (remainder_value, i + 1);
+ remainder = new BigInteger (dividend.sign, remainder_value);
+ }
+
+ for (i = quotient.Length - 1; i >= 0 && quotient [i] == 0; --i) ;
+ if (i == -1)
+ return new BigInteger (0, ZERO);
+ if (i < quotient.Length - 1)
+ quotient = Resize (quotient, i + 1);
+
+ return new BigInteger ((short)(dividend.sign * divisor.sign), quotient);
+ }
+
+ public static BigInteger Pow (BigInteger value, int exponent)
+ {
+ if (exponent < 0)
+ throw new ArgumentOutOfRangeException("exponent", "exp must be >= 0");
+ if (exponent == 0)
+ return One;
+ if (exponent == 1)
+ return value;
+
+ BigInteger result = One;
+ while (exponent != 0) {
+ if ((exponent & 1) != 0)
+ result = result * value;
+ if (exponent == 1)
+ break;
+
+ value = value * value;
+ exponent >>= 1;
+ }
+ return result;
+ }
+
+ public static BigInteger ModPow (BigInteger value, BigInteger exponent, BigInteger modulus) {
+ if (exponent.sign == -1)
+ throw new ArgumentOutOfRangeException("exponent", "power must be >= 0");
+ if (modulus.sign == 0)
+ throw new DivideByZeroException ();
+
+ BigInteger result = One % modulus;
+ while (exponent.sign != 0) {
+ if (!exponent.IsEven) {
+ result = result * value;
+ result = result % modulus;
+ }
+ if (exponent.IsOne)
+ break;
+ value = value * value;
+ value = value % modulus;
+ exponent >>= 1;
+ }
+ return result;
+ }
+
+ public static BigInteger GreatestCommonDivisor (BigInteger left, BigInteger right)
+ {
+ if (left.sign != 0 && left.data.Length == 1 && left.data [0] == 1)
+ return new BigInteger (1, ONE);
+ if (right.sign != 0 && right.data.Length == 1 && right.data [0] == 1)
+ return new BigInteger (1, ONE);
+ if (left.IsZero)
+ return Abs(right);
+ if (right.IsZero)
+ return Abs(left);
+
+ BigInteger x = new BigInteger (1, left.data);
+ BigInteger y = new BigInteger (1, right.data);
+
+ BigInteger g = y;
+
+ while (x.data.Length > 1) {
+ g = x;
+ x = y % x;
+ y = g;
+
+ }
+ if (x.IsZero) return g;
+
+ // TODO: should we have something here if we can convert to long?
+
+ //
+ // Now we can just do it with single precision. I am using the binary gcd method,
+ // as it should be faster.
+ //
+
+ uint yy = x.data [0];
+ uint xx = (uint)(y % yy);
+
+ int t = 0;
+
+ while (((xx | yy) & 1) == 0) {
+ xx >>= 1; yy >>= 1; t++;
+ }
+ while (xx != 0) {
+ while ((xx & 1) == 0) xx >>= 1;
+ while ((yy & 1) == 0) yy >>= 1;
+ if (xx >= yy)
+ xx = (xx - yy) >> 1;
+ else
+ yy = (yy - xx) >> 1;
+ }
+
+ return yy << t;
+ }
+
+ /*LAMESPEC Log doesn't specify to how many ulp is has to be precise
+ We are equilavent to MS with about 2 ULP
+ */
+ public static double Log (BigInteger value, Double baseValue)
+ {
+ if (value.sign == -1 || baseValue == 1.0d || baseValue == -1.0d ||
+ baseValue == Double.NegativeInfinity || double.IsNaN (baseValue))
+ return double.NaN;
+
+ if (baseValue == 0.0d || baseValue == Double.PositiveInfinity)
+ return value.IsOne ? 0 : double.NaN;
+
+ if (value.sign == 0)
+ return double.NegativeInfinity;
+
+ int length = value.data.Length - 1;
+ int bitCount = -1;
+ for (int curBit = 31; curBit >= 0; curBit--) {
+ if ((value.data [length] & (1 << curBit)) != 0) {
+ bitCount = curBit + length * 32;
+ break;
+ }
+ }
+
+ long bitlen = bitCount;
+ Double c = 0, d = 1;
+
+ BigInteger testBit = One;
+ long tempBitlen = bitlen;
+ while (tempBitlen > Int32.MaxValue) {
+ testBit = testBit << Int32.MaxValue;
+ tempBitlen -= Int32.MaxValue;
+ }
+ testBit = testBit << (int)tempBitlen;
+
+ for (long curbit = bitlen; curbit >= 0; --curbit) {
+ if ((value & testBit).sign != 0)
+ c += d;
+ d *= 0.5;
+ testBit = testBit >> 1;
+ }
+ return (System.Math.Log (c) + System.Math.Log (2) * bitlen) / System.Math.Log (baseValue);
+ }
+
+
+ public static double Log (BigInteger value)
+ {
+ return Log (value, Math.E);
+ }
+
+
+ public static double Log10 (BigInteger value)
+ {
+ return Log (value, 10);
+ }
+
[CLSCompliantAttribute (false)]
public bool Equals (ulong other)
{
public override int GetHashCode ()
{
uint hash = (uint)(sign * 0x01010101u);
+ int len = data != null ? data.Length : 0;
- for (int i = 0; i < data.Length; ++i)
+ for (int i = 0; i < len; ++i)
hash ^= data [i];
return (int)hash;
}
return left - right;
}
+ public static BigInteger Multiply (BigInteger left, BigInteger right)
+ {
+ return left * right;
+ }
+
+ public static BigInteger Divide (BigInteger dividend, BigInteger divisor)
+ {
+ return dividend / divisor;
+ }
+
+ public static BigInteger Remainder (BigInteger dividend, BigInteger divisor)
+ {
+ return dividend % divisor;
+ }
+
public static BigInteger Negate (BigInteger value)
{
return - value;
return 0;
if (data.Length > 2)
- return -sign;
+ return sign;
if (other < 0)
other = -other;
}
static byte[] Resize (byte[] v, int len)
- {\r
- byte[] res = new byte [len];\r
- Array.Copy (v, res, Math.Min (v.Length, len));\r
- return res;\r
+ {
+ byte[] res = new byte [len];
+ Array.Copy (v, res, Math.Min (v.Length, len));
+ return res;
}
static uint[] Resize (uint[] v, int len)
{
- uint[] res = new uint [len];\r
- Array.Copy (v, res, Math.Min (v.Length, len));\r
- return res;\r
+ uint[] res = new uint [len];
+ Array.Copy (v, res, Math.Min (v.Length, len));
+ return res;
}
static uint[] CoreAdd (uint[] a, uint[] b)
static int CoreCompare (uint[] a, uint[] b)
{
- int al = a.Length;
- int bl = b.Length;
+ int al = a != null ? a.Length : 0;
+ int bl = b != null ? b.Length : 0;
if (al > bl)
return 1;
return 0;
}
+ static int GetNormalizeShift(uint value) {
+ int shift = 0;
+
+ if ((value & 0xFFFF0000) == 0) { value <<= 16; shift += 16; }
+ if ((value & 0xFF000000) == 0) { value <<= 8; shift += 8; }
+ if ((value & 0xF0000000) == 0) { value <<= 4; shift += 4; }
+ if ((value & 0xC0000000) == 0) { value <<= 2; shift += 2; }
+ if ((value & 0x80000000) == 0) { value <<= 1; shift += 1; }
+
+ return shift;
+ }
+
+ static void Normalize (uint[] u, int l, uint[] un, int shift)
+ {
+ uint carry = 0;
+ int i;
+ if (shift > 0) {
+ int rshift = 32 - shift;
+ for (i = 0; i < l; i++) {
+ uint ui = u [i];
+ un [i] = (ui << shift) | carry;
+ carry = ui >> rshift;
+ }
+ } else {
+ for (i = 0; i < l; i++) {
+ un [i] = u [i];
+ }
+ }
+
+ while (i < un.Length) {
+ un [i++] = 0;
+ }
+
+ if (carry != 0) {
+ un [l] = carry;
+ }
+ }
+
+ static void Unnormalize (uint[] un, out uint[] r, int shift)
+ {
+ int length = un.Length;
+ r = new uint [length];
+
+ if (shift > 0) {
+ int lshift = 32 - shift;
+ uint carry = 0;
+ for (int i = length - 1; i >= 0; i--) {
+ uint uni = un [i];
+ r [i] = (uni >> shift) | carry;
+ carry = (uni << lshift);
+ }
+ } else {
+ for (int i = 0; i < length; i++) {
+ r [i] = un [i];
+ }
+ }
+ }
+
+ const ulong Base = 0x100000000;
+ static void DivModUnsigned (uint[] u, uint[] v, out uint[] q, out uint[] r)
+ {
+ int m = u.Length;
+ int n = v.Length;
+
+ if (n <= 1) {
+ // Divide by single digit
+ //
+ ulong rem = 0;
+ uint v0 = v [0];
+ q = new uint[m];
+ r = new uint [1];
+
+ for (int j = m - 1; j >= 0; j--) {
+ rem *= Base;
+ rem += u[j];
+
+ ulong div = rem / v0;
+ rem -= div * v0;
+ q[j] = (uint)div;
+ }
+ r [0] = (uint)rem;
+ } else if (m >= n) {
+ int shift = GetNormalizeShift (v [n - 1]);
+
+ uint[] un = new uint [m + 1];
+ uint[] vn = new uint [n];
+
+ Normalize (u, m, un, shift);
+ Normalize (v, n, vn, shift);
+
+ q = new uint [m - n + 1];
+ r = null;
+
+ // Main division loop
+ //
+ for (int j = m - n; j >= 0; j--) {
+ ulong rr, qq;
+ int i;
+
+ rr = Base * un [j + n] + un [j + n - 1];
+ qq = rr / vn [n - 1];
+ rr -= qq * vn [n - 1];
+
+ for (; ; ) {
+ // Estimate too big ?
+ //
+ if ((qq >= Base) || (qq * vn [n - 2] > (rr * Base + un [j + n - 2]))) {
+ qq--;
+ rr += (ulong)vn [n - 1];
+ if (rr < Base)
+ continue;
+ }
+ break;
+ }
+
+
+ // Multiply and subtract
+ //
+ long b = 0;
+ long t = 0;
+ for (i = 0; i < n; i++) {
+ ulong p = vn [i] * qq;
+ t = (long)un [i + j] - (long)(uint)p - b;
+ un [i + j] = (uint)t;
+ p >>= 32;
+ t >>= 32;
+ b = (long)p - t;
+ }
+ t = (long)un [j + n] - b;
+ un [j + n] = (uint)t;
+
+ // Store the calculated value
+ //
+ q [j] = (uint)qq;
+
+ // Add back vn[0..n] to un[j..j+n]
+ //
+ if (t < 0) {
+ q [j]--;
+ ulong c = 0;
+ for (i = 0; i < n; i++) {
+ c = (ulong)vn [i] + un [j + i] + c;
+ un [j + i] = (uint)c;
+ c >>= 32;
+ }
+ c += (ulong)un [j + n];
+ un [j + n] = (uint)c;
+ }
+ }
+
+ Unnormalize (un, out r, shift);
+ } else {
+ q = new uint [] { 0 };
+ r = u;
+ }
+ }
}
-}\r
+}
projects / mono.git / blobdiff