< Summary

Information
Class: Renci.SshNet.Common.BigInteger
Assembly: Renci.SshNet
File(s): \home\appveyor\projects\ssh-net\src\Renci.SshNet\Common\BigInteger.cs
Line coverage
85%
Covered lines: 2166
Uncovered lines: 353
Coverable lines: 2519
Total lines: 4969
Line coverage: 85.9%
Branch coverage
82%
Covered branches: 959
Total branches: 1156
Branch coverage: 82.9%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.cctor()100%1100%
get_BitLength()50%658.33%
ModInverse(...)75%885.71%
PositiveMod(...)100%2100%
Random(...)50%2100%
.ctor(...)100%1100%
.ctor(...)100%4100%
.ctor(...)50%263.63%
.ctor(...)100%12100%
.ctor(...)100%6100%
.ctor(...)50%1457.14%
.ctor(...)100%10%
.ctor(...)100%12100%
.ctor(...)97.22%3697.93%
Negative(...)100%1100%
Exponent(...)100%1100%
Mantissa(...)100%1100%
get_IsEven()100%2100%
get_IsOne()100%4100%
PopulationCount(...)100%1100%
PopulationCount(...)100%1100%
LeadingZeroCount(...)100%1100%
LeadingZeroCount(...)100%1100%
BuildDouble(...)66.66%1880%
get_IsPowerOfTwo()100%8100%
get_IsZero()100%1100%
get_Sign()100%1100%
get_MinusOne()100%1100%
get_One()100%1100%
get_Zero()100%1100%
op_Explicit(...)91.66%1295.45%
op_Explicit(...)66.66%677.77%
op_Explicit(...)66.66%671.42%
op_Explicit(...)0%20%
op_Explicit(...)0%20%
op_Explicit(...)0%60%
op_Explicit(...)100%14100%
op_Explicit(...)12.5%835.71%
op_Explicit(...)100%8100%
op_Explicit(...)100%10%
op_Explicit(...)100%10100%
op_Implicit(...)100%1100%
op_Implicit(...)100%1100%
op_Implicit(...)100%10%
op_Implicit(...)100%10%
op_Implicit(...)100%1100%
op_Implicit(...)100%10%
op_Implicit(...)100%1100%
op_Implicit(...)100%1100%
op_Explicit(...)100%10%
op_Explicit(...)100%10%
op_Explicit(...)100%10%
op_Addition(...)100%10100%
op_Subtraction(...)100%10100%
op_Multiply(...)96.42%28100%
op_Division(...)66.66%1270%
op_Modulus(...)66.66%1270%
op_UnaryNegation(...)100%2100%
op_UnaryPlus(...)100%10%
op_Increment(...)91.66%1288.88%
op_Decrement(...)91.66%1288.88%
op_BitwiseAnd(...)100%28100%
op_BitwiseOr(...)92.85%2896.61%
op_ExclusiveOr(...)100%26100%
op_OnesComplement(...)94.44%1892.3%
BitScanBackward(...)75%490%
op_LeftShift(...)100%16100%
op_RightShift(...)91.17%3496.96%
op_LessThan(...)100%1100%
op_LessThan(...)100%1100%
op_LessThan(...)100%1100%
op_LessThan(...)100%1100%
op_LessThan(...)100%1100%
op_LessThanOrEqual(...)100%1100%
op_LessThanOrEqual(...)100%1100%
op_LessThanOrEqual(...)100%1100%
op_LessThanOrEqual(...)100%1100%
op_LessThanOrEqual(...)100%1100%
op_GreaterThan(...)100%1100%
op_GreaterThan(...)100%1100%
op_GreaterThan(...)100%1100%
op_GreaterThan(...)100%1100%
op_GreaterThan(...)100%1100%
op_GreaterThanOrEqual(...)100%1100%
op_GreaterThanOrEqual(...)100%1100%
op_GreaterThanOrEqual(...)100%1100%
op_GreaterThanOrEqual(...)100%1100%
op_GreaterThanOrEqual(...)100%1100%
op_Equality(...)100%1100%
op_Equality(...)100%1100%
op_Equality(...)100%1100%
op_Equality(...)100%1100%
op_Equality(...)100%1100%
op_Inequality(...)100%1100%
op_Inequality(...)100%1100%
op_Inequality(...)100%1100%
op_Inequality(...)100%1100%
op_Inequality(...)100%1100%
Equals(...)0%40%
Equals(...)83.33%1276.47%
Equals(...)100%10%
Equals(...)100%10%
ToString()100%1100%
ToString(...)100%1100%
ToString(...)100%1100%
ToString(...)70.83%2488.88%
ToStringWithPadding(...)83.33%693.33%
MakeTwoComplement(...)75%485.71%
ToString(...)88.88%3693.1%
Parse(...)100%2100%
Parse(...)100%1100%
Parse(...)100%10%
Parse(...)100%2100%
TryParse(...)100%1100%
TryParse(...)100%2100%
Parse(...)70.55%18067.05%
CheckStyle(...)42.85%1435.48%
JumpOverWhitespace(...)70%1057.14%
FindSign(...)87.5%868.75%
FindCurrency(...)75%4100%
FindExponent(...)50%3867.39%
FindOther(...)75%4100%
ValidDigit(...)60%10100%
GetFormatException()100%1100%
ProcessTrailingWhitespace(...)87.5%8100%
Parse(...)94.11%3492.2%
Min(...)100%8100%
Max(...)100%8100%
Abs(...)100%1100%
DivRem(...)100%20100%
Pow(...)100%12100%
ModPow(...)100%10100%
GreatestCommonDivisor(...)93.33%3087.03%
Log(...)96.66%3090.24%
Log(...)100%1100%
Log10(...)100%10%
GetHashCode()25%445.45%
Add(...)100%1100%
Subtract(...)100%1100%
Multiply(...)100%10%
Divide(...)100%10%
Remainder(...)100%10%
Negate(...)100%1100%
CompareTo(...)16.66%655.55%
CompareTo(...)100%1100%
CompareTo(...)87.5%885.71%
CompareTo(...)100%12100%
LongCompare(...)100%10100%
Compare(...)100%6100%
TopByte(...)100%6100%
FirstNonFfByte(...)100%6100%
ToByteArray()96.15%2690.69%
CoreAdd(...)100%8100%
CoreAdd(...)75%476.47%
CoreSub(...)70%1080.76%
CoreSub(...)62.5%873.68%
CoreCompare(...)100%14100%
GetNormalizeShift(...)100%10100%
Normalize(...)100%10100%
Unnormalize(...)100%6100%
DivModUnsigned(...)80%2084.21%

File(s)

\home\appveyor\projects\ssh-net\src\Renci.SshNet\Common\BigInteger.cs

#LineLine coverage
 1#pragma warning disable SA1028 // Code should not contain trailing whitespace
 2#pragma warning disable SA1515 // Single-line comment should be preceded by blank line
 3//
 4// System.Numerics.BigInteger
 5//
 6// Authors:
 7// Rodrigo Kumpera (rkumpera@novell.com)
 8// Marek Safar  <marek.safar@gmail.com>
 9//
 10// Copyright (C) 2010 Novell, Inc (http://www.novell.com)
 11// Copyright (C) 2014 Xamarin Inc (http://www.xamarin.com)
 12//
 13// Permission is hereby granted, free of charge, to any person obtaining
 14// a copy of this software and associated documentation files (the
 15// "Software"), to deal in the Software without restriction, including
 16// without limitation the rights to use, copy, modify, merge, publish,
 17// distribute, sublicense, and/or sell copies of the Software, and to
 18// permit persons to whom the Software is furnished to do so, subject to
 19// the following conditions:
 20//
 21// The above copyright notice and this permission notice shall be
 22// included in all copies or substantial portions of the Software.
 23//
 24// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 25// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 26// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 27// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 28// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 29// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 30// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 31//
 32// A big chuck of code comes the DLR (as hosted in http://ironpython.codeplex.com),
 33// which has the following License:
 34//
 35/* ****************************************************************************
 36*
 37* Copyright (c) Microsoft Corporation.
 38*
 39* This source code is subject to terms and conditions of the Microsoft Public License. A
 40* copy of the license can be found in the License.html file at the root of this distribution. If
 41* you cannot locate the Microsoft Public License, please send an email to
 42* dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
 43* by the terms of the Microsoft Public License.
 44*
 45* You must not remove this notice, or any other, from this software.
 46*
 47*
 48* ***************************************************************************/
 49#pragma warning restore SA1515 // Single-line comment should be preceded by blank line
 50#pragma warning restore SA1028 // Code should not contain trailing whitespace
 51
 52using System;
 53using System.Collections.Generic;
 54using System.Globalization;
 55
 56using Renci.SshNet.Abstractions;
 57
 58/*
 59 * Optimization:
 60 * - Have proper popcount function for IsPowerOfTwo
 61 * - Use unsafe ops to avoid bounds check
 62 * - CoreAdd could avoid some resizes by checking for equal sized array that top overflow
 63 * - For bitwise operators, hoist the conditionals out of their main loop
 64 * - Optimize BitScanBackward
 65 * - Use a carry variable to make shift opts do half the number of array ops.
 66 * -Schoolbook multiply is O(n^2), use Karatsuba /Toom-3 for large numbers
 67 */
 68namespace Renci.SshNet.Common
 69{
 70    /// <summary>
 71    /// Represents an arbitrarily large signed integer.
 72    /// </summary>
 73    public struct BigInteger : IComparable, IFormattable, IComparable<BigInteger>, IEquatable<BigInteger>
 74    {
 75        private const ulong Base = 0x100000000;
 76        private const int Bias = 1075;
 77        private const int DecimalSignMask = unchecked((int)0x80000000);
 78
 479        private static readonly BigInteger ZeroSingleton = new BigInteger(0);
 480        private static readonly BigInteger OneSingleton = new BigInteger(1);
 481        private static readonly BigInteger MinusOneSingleton = new BigInteger(-1);
 82
 83        // LSB on [0]
 84        private readonly uint[] _data;
 85        private readonly short _sign;
 86
 87        #region SSH.NET additions
 88
 89        /// <summary>
 90        /// Gets number of bits used by the number.
 91        /// </summary>
 92        /// <value>
 93        /// The number of the bit used.
 94        /// </value>
 95        public readonly int BitLength
 96        {
 97            get
 261998            {
 261999                if (_sign == 0)
 0100                {
 0101                    return 0;
 102                }
 103
 2619104                var msbIndex = _data.Length - 1;
 105
 2619106                while (_data[msbIndex] == 0)
 0107                {
 0108                    msbIndex--;
 0109                }
 110
 2619111                var msbBitCount = BitScanBackward(_data[msbIndex]) + 1;
 112
 2619113                return (msbIndex * 4 * 8) + msbBitCount + ((_sign > 0) ? 0 : 1);
 2619114            }
 115        }
 116
 117        /// <summary>
 118        /// Mods the inverse.
 119        /// </summary>
 120        /// <param name="bi">The bi.</param>
 121        /// <param name="modulus">The modulus.</param>
 122        /// <returns>
 123        /// Modulus inverted number.
 124        /// </returns>
 125        public static BigInteger ModInverse(BigInteger bi, BigInteger modulus)
 700126        {
 1400127            BigInteger a = modulus, b = bi % modulus;
 1400128            BigInteger p0 = 0, p1 = 1;
 129
 416538130            while (!b.IsZero)
 416538131            {
 416538132                if (b.IsOne)
 373133                {
 373134                    return p1;
 135                }
 136
 416165137                p0 += (a / b) * p1;
 416165138                a %= b;
 139
 416165140                if (a.IsZero)
 0141                {
 0142                    break;
 143                }
 144
 416165145                if (a.IsOne)
 327146                {
 327147                    return modulus - p0;
 148                }
 149
 415838150                p1 += (b / a) * p0;
 415838151                b %= a;
 415838152            }
 153
 0154            return 0;
 700155        }
 156
 157        /// <summary>
 158        /// Returns positive remainder that results from division with two specified <see cref="BigInteger"/> values.
 159        /// </summary>
 160        /// <param name="dividend">The value to be divided.</param>
 161        /// <param name="divisor">The value to divide by.</param>
 162        /// <returns>
 163        /// Positive remainder that results from the division.
 164        /// </returns>
 165        public static BigInteger PositiveMod(BigInteger dividend, BigInteger divisor)
 2088166        {
 2088167            var result = dividend % divisor;
 168
 2088169            if (result < 0)
 291170            {
 291171                result += divisor;
 291172            }
 173
 2088174            return result;
 2088175        }
 176
 177        /// <summary>
 178        /// Generates a new, random <see cref="BigInteger"/> of the specified length.
 179        /// </summary>
 180        /// <param name="bitLength">The number of bits for the new number.</param>
 181        /// <returns>A random number of the specified length.</returns>
 182        public static BigInteger Random(int bitLength)
 727183        {
 727184            var bytesArray = new byte[(bitLength / 8) + (((bitLength % 8) > 0) ? 1 : 0)];
 727185            CryptoAbstraction.GenerateRandom(bytesArray);
 727186            bytesArray[bytesArray.Length - 1] = (byte) (bytesArray[bytesArray.Length - 1] & 0x7F); // Ensure not a negat
 727187            return new BigInteger(bytesArray);
 727188        }
 189
 190        #endregion SSH.NET additions
 191
 192        private BigInteger(short sign, uint[] data)
 9009700193        {
 9009700194            _sign = sign;
 9009700195            _data = data;
 9009700196        }
 197
 198        /// <summary>
 199        /// Initializes a new instance of the <see cref="BigInteger"/> structure using a 32-bit signed integer value.
 200        /// </summary>
 201        /// <param name="value">A 32-bit signed integer.</param>
 202        public BigInteger(int value)
 27644203        {
 27644204            if (value == 0)
 1874205            {
 1874206                _sign = 0;
 1874207                _data = null;
 1874208            }
 25770209            else if (value > 0)
 25616210            {
 25616211                _sign = 1;
 25616212                _data = new[] { (uint) value };
 25616213            }
 214            else
 154215            {
 154216                _sign = -1;
 217#pragma warning disable SA1021 // Negative signs should be spaced correctly
 154218                _data = new[] { (uint) -value };
 219#pragma warning restore SA1021 // Negative signs should be spaced correctly
 154220            }
 27644221        }
 222
 223        /// <summary>
 224        /// Initializes a new instance of the <see cref="BigInteger"/> structure using an unsigned 32-bit integer value.
 225        /// </summary>
 226        /// <param name="value">An unsigned 32-bit integer value.</param>
 227        [CLSCompliant(false)]
 228        public BigInteger(uint value)
 18201229        {
 18201230            if (value == 0)
 0231            {
 0232                _sign = 0;
 0233                _data = null;
 0234            }
 235            else
 18201236            {
 18201237                _sign = 1;
 18201238                _data = new[] { value };
 18201239            }
 18201240        }
 241
 242        /// <summary>
 243        /// Initializes a new instance of the <see cref="BigInteger"/> structure using a 64-bit signed integer value.
 244        /// </summary>
 245        /// <param name="value">A 64-bit signed integer.</param>
 246        public BigInteger(long value)
 3645247        {
 3645248            if (value == 0)
 426249            {
 426250                _sign = 0;
 426251                _data = null;
 426252            }
 3219253            else if (value > 0)
 1737254            {
 1737255                _sign = 1;
 1737256                var low = (uint)value;
 1737257                var high = (uint)(value >> 32);
 258
 1737259                _data = new uint[high != 0 ? 2 : 1];
 1737260                _data[0] = low;
 1737261                if (high != 0)
 657262                {
 657263                    _data[1] = high;
 657264                }
 1737265            }
 266            else
 1482267            {
 1482268                _sign = -1;
 1482269                value = -value;
 1482270                var low = (uint)value;
 1482271                var high = (uint)((ulong)value >> 32);
 272
 1482273                _data = new uint[high != 0 ? 2 : 1];
 1482274                _data[0] = low;
 1482275                if (high != 0)
 507276                {
 507277                    _data[1] = high;
 507278                }
 1482279            }
 3645280        }
 281
 282        /// <summary>
 283        /// Initializes a new instance of the <see cref="BigInteger"/> structure with an unsigned 64-bit integer value.
 284        /// </summary>
 285        /// <param name="value">An unsigned 64-bit integer.</param>
 286        [CLSCompliant(false)]
 287        public BigInteger(ulong value)
 210288        {
 210289            if (value == 0)
 24290            {
 24291                _sign = 0;
 24292                _data = null;
 24293            }
 294            else
 186295            {
 186296                _sign = 1;
 186297                var low = (uint) value;
 186298                var high = (uint) (value >> 32);
 299
 186300                _data = new uint[high != 0 ? 2 : 1];
 186301                _data[0] = low;
 186302                if (high != 0)
 114303                {
 114304                    _data[1] = high;
 114305                }
 186306            }
 210307        }
 308
 309        /// <summary>
 310        /// Initializes a new instance of the <see cref="BigInteger"/> structure using a double-precision floating-point
 311        /// </summary>
 312        /// <param name="value">A double-precision floating-point value.</param>
 313        public BigInteger(double value)
 24314        {
 24315            if (double.IsNaN(value) || double.IsInfinity(value))
 9316            {
 9317                throw new OverflowException();
 318            }
 319
 15320            var bytes = BitConverter.GetBytes(value);
 15321            var mantissa = Mantissa(bytes);
 15322            if (mantissa == 0)
 0323            {
 324                // 1.0 * 2**exp, we have a power of 2
 0325                int exponent = Exponent(bytes);
 0326                if (exponent == 0)
 0327                {
 0328                    _sign = 0;
 0329                    _data = null;
 0330                    return;
 331                }
 332
 0333                var res = Negative(bytes) ? MinusOne : One;
 0334                res <<= exponent - 0x3ff;
 0335                _sign = res._sign;
 0336                _data = res._data;
 0337            }
 338            else
 15339            {
 340                // 1.mantissa * 2**exp
 15341                int exponent = Exponent(bytes);
 15342                mantissa |= 0x10000000000000ul;
 15343                BigInteger res = mantissa;
 15344                res = exponent > Bias ? res << (exponent - Bias) : res >> (Bias - exponent);
 345
 15346                _sign = (short) (Negative(bytes) ? -1 : 1);
 15347                _data = res._data;
 15348            }
 15349        }
 350
 351        /// <summary>
 352        /// Initializes a new instance of the <see cref="BigInteger"/> structure using a single-precision floating-point
 353        /// </summary>
 354        /// <param name="value">A single-precision floating-point value.</param>
 355        public BigInteger(float value)
 0356            : this((double) value)
 0357        {
 0358        }
 359
 360        /// <summary>
 361        /// Initializes a new instance of the <see cref="BigInteger"/> structure using a <see cref="decimal"/> value.
 362        /// </summary>
 363        /// <param name="value">A decimal number.</param>
 364        public BigInteger(decimal value)
 12365        {
 366            // First truncate to get scale to 0 and extract bits
 12367            var bits = decimal.GetBits(decimal.Truncate(value));
 368
 12369            var size = 3;
 33370            while (size > 0 && bits[size - 1] == 0)
 21371            {
 21372                size--;
 21373            }
 374
 12375            if (size == 0)
 3376            {
 3377                _sign = 0;
 3378                _data = null;
 3379                return;
 380            }
 381
 9382            _sign = (short) ((bits[3] & DecimalSignMask) != 0 ? -1 : 1);
 383
 9384            _data = new uint[size];
 9385            _data[0] = (uint) bits[0];
 9386            if (size > 1)
 3387            {
 3388                _data[1] = (uint) bits[1];
 3389            }
 390
 9391            if (size > 2)
 3392            {
 3393                _data[2] = (uint) bits[2];
 3394            }
 12395        }
 396
 397        /// <summary>
 398        /// Initializes a new instance of the <see cref="BigInteger"/> structure using the values in a byte array.
 399        /// </summary>
 400        /// <param name="value">An array of <see cref="byte"/> values in little-endian order.</param>
 401        /// <exception cref="ArgumentNullException"><paramref name="value"/> is <see langword="null"/>.</exception>
 402        [CLSCompliant(false)]
 403        public BigInteger(byte[] value)
 11224404        {
 11224405            if (value is null)
 3406            {
 3407                throw new ArgumentNullException(nameof(value));
 408            }
 409
 11221410            var len = value.Length;
 411
 11221412            if (len == 0 || (len == 1 && value[0] == 0))
 517413            {
 517414                _sign = 0;
 517415                _data = null;
 517416                return;
 417            }
 418
 10704419            if ((value[len - 1] & 0x80) != 0)
 90420            {
 90421                _sign = -1;
 90422            }
 423            else
 10614424            {
 10614425                _sign = 1;
 10614426            }
 427
 428#pragma warning disable CA1508 // Avoid dead conditional code | this is the following bug in the analyzer rule: https://
 10704429            if (_sign == 1)
 430#pragma warning restore CA1508 // Avoid dead conditional code
 10614431            {
 16623432                while (value[len - 1] == 0)
 6012433                {
 6012434                    if (--len == 0)
 3435                    {
 3436                        _sign = 0;
 3437                        _data = null;
 3438                        return;
 439                    }
 6009440                }
 441
 442                int size;
 10611443                var fullWords = size = len / 4;
 10611444                if ((len & 0x3) != 0)
 2579445                {
 2579446                    ++size;
 2579447                }
 448
 10611449                _data = new uint[size];
 10611450                var j = 0;
 985608451                for (var i = 0; i < fullWords; ++i)
 482193452                {
 482193453                    _data[i] = (uint) value[j++] |
 482193454                               (uint) (value[j++] << 8) |
 482193455                               (uint) (value[j++] << 16) |
 482193456                               (uint) (value[j++] << 24);
 482193457                }
 458
 10611459                size = len & 0x3;
 10611460                if (size > 0)
 2579461                {
 2579462                    var idx = _data.Length - 1;
 18300463                    for (var i = 0; i < size; ++i)
 6571464                    {
 6571465                        _data[idx] |= (uint) (value[j++] << (i * 8));
 6571466                    }
 2579467                }
 10611468            }
 469            else
 90470            {
 471                int size;
 90472                var fullWords = size = len / 4;
 90473                if ((len & 0x3) != 0)
 60474                {
 60475                    ++size;
 60476                }
 477
 90478                _data = new uint[size];
 479
 90480                uint word, borrow = 1;
 481                ulong sub;
 90482                var j = 0;
 483
 1362484                for (var i = 0; i < fullWords; ++i)
 591485                {
 591486                    word = (uint) value[j++] |
 591487                           (uint) (value[j++] << 8) |
 591488                           (uint) (value[j++] << 16) |
 591489                           (uint) (value[j++] << 24);
 490
 591491                    sub = (ulong) word - borrow;
 591492                    word = (uint) sub;
 591493                    borrow = (uint) (sub >> 32) & 0x1u;
 591494                    _data[i] = ~word;
 591495                }
 496
 90497                size = len & 0x3;
 498
 90499                if (size > 0)
 60500                {
 60501                    word = 0;
 60502                    uint storeMask = 0;
 336503                    for (var i = 0; i < size; ++i)
 108504                    {
 108505                        word |= (uint) (value[j++] << (i * 8));
 108506                        storeMask = (storeMask << 8) | 0xFF;
 108507                    }
 508
 60509                    sub = word - borrow;
 60510                    word = (uint) sub;
 60511                    borrow = (uint) (sub >> 32) & 0x1u;
 512
 60513                    if ((~word & storeMask) == 0)
 12514                    {
 12515                        Array.Resize(ref _data, _data.Length - 1);
 12516                    }
 517                    else
 48518                    {
 48519                        _data[_data.Length - 1] = ~word & storeMask;
 48520                    }
 60521                }
 522
 90523                if (borrow != 0)
 0524                {
 525#pragma warning disable CA2201 // Do not raise reserved exception types
 0526                    throw new Exception("non zero final carry");
 527#pragma warning restore CA2201 // Do not raise reserved exception types
 528                }
 90529            }
 11221530        }
 531
 532        private static bool Negative(byte[] v)
 15533        {
 15534            return (v[7] & 0x80) != 0;
 15535        }
 536
 537        private static ushort Exponent(byte[] v)
 15538        {
 15539            return (ushort)((((ushort)(v[7] & 0x7F)) << (ushort)4) | (((ushort)(v[6] & 0xF0)) >> 4));
 15540        }
 541
 542        private static ulong Mantissa(byte[] v)
 15543        {
 15544            var i1 = (uint)v[0] | ((uint)v[1] << 8) | ((uint)v[2] << 16) | ((uint)v[3] << 24);
 15545            var i2 = (uint)v[4] | ((uint)v[5] << 8) | ((uint)(v[6] & 0xF) << 16);
 546
 15547            return (ulong) i1 | ((ulong) i2 << 32);
 15548        }
 549
 550        /// <summary>
 551        /// Gets a value indicating whether the value of the current <see cref="BigInteger"/> object is an even number.
 552        /// </summary>
 553        /// <value>
 554        /// <see langword="true"/> if the value of the <see cref="BigInteger"/> object is an even number; otherwise, <se
 555        /// </value>
 556        public readonly bool IsEven
 557        {
 4453422558            get { return _sign == 0 || (_data[0] & 0x1) == 0; }
 559        }
 560
 561        /// <summary>
 562        /// Gets a value indicating whether the value of the current <see cref="BigInteger"/> object is <see cref="One"/
 563        /// </summary>
 564        /// <value>
 565        /// <see langword="true"/> if the value of the <see cref="BigInteger"/> object is <see cref="One"/>;
 566        /// otherwise, <see langword="false"/>.
 567        /// </value>
 568        public readonly bool IsOne
 569        {
 6951558570            get { return _sign == 1 && _data.Length == 1 && _data[0] == 1; }
 571        }
 572
 573        // Gem from Hacker's Delight
 574        // Returns the number of bits set in @x
 575        private static int PopulationCount(uint x)
 51576        {
 51577            x -= (x >> 1) & 0x55555555;
 51578            x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
 51579            x = (x + (x >> 4)) & 0x0F0F0F0F;
 51580            x += x >> 8;
 51581            x += x >> 16;
 51582            return (int) (x & 0x0000003F);
 51583        }
 584
 585        /// <summary>
 586        /// Returns the number of bits set in <paramref name="x"/>.
 587        /// </summary>
 588        /// <returns>
 589        /// The number of bits set in <paramref name="x"/>.
 590        /// </returns>
 591        /// <remarks>
 592        /// Based on code by Zilong Tan on Ulib released under MIT license.
 593        /// </remarks>
 594        private static int PopulationCount(ulong x)
 54595        {
 54596            x -= (x >> 1) & 0x5555555555555555UL;
 54597            x = (x & 0x3333333333333333UL) + ((x >> 2) & 0x3333333333333333UL);
 54598            x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fUL;
 54599            return (int)((x * 0x0101010101010101UL) >> 56);
 54600        }
 601
 602        private static int LeadingZeroCount(uint value)
 39603        {
 39604            value |= value >> 1;
 39605            value |= value >> 2;
 39606            value |= value >> 4;
 39607            value |= value >> 8;
 39608            value |= value >> 16;
 39609            return 32 - PopulationCount(value); // 32 = bits in uint
 39610        }
 611
 612        private static int LeadingZeroCount(ulong value)
 54613        {
 54614            value |= value >> 1;
 54615            value |= value >> 2;
 54616            value |= value >> 4;
 54617            value |= value >> 8;
 54618            value |= value >> 16;
 54619            value |= value >> 32;
 54620            return 64 - PopulationCount(value); // 64 = bits in ulong
 54621        }
 622
 623        private static double BuildDouble(int sign, ulong mantissa, int exponent)
 54624        {
 625            const int exponentBias = 1023;
 626            const int mantissaLength = 52;
 627            const int exponentLength = 11;
 628            const int maxExponent = 2046;
 629            const long mantissaMask = 0xfffffffffffffL;
 630            const long exponentMask = 0x7ffL;
 631            const ulong negativeMark = 0x8000000000000000uL;
 632
 54633            if (sign == 0 || mantissa == 0)
 0634            {
 0635                return 0.0;
 636            }
 637
 54638            exponent += exponentBias + mantissaLength;
 54639            var offset = LeadingZeroCount(mantissa) - exponentLength;
 54640            if (exponent - offset > maxExponent)
 9641            {
 9642                return sign > 0 ? double.PositiveInfinity : double.NegativeInfinity;
 643            }
 644
 45645            if (offset < 0)
 6646            {
 6647                mantissa >>= -offset;
 6648                exponent += -offset;
 6649            }
 39650            else if (offset >= exponent)
 0651            {
 0652                mantissa <<= exponent - 1;
 0653                exponent = 0;
 0654            }
 655            else
 39656            {
 39657                mantissa <<= offset;
 39658                exponent -= offset;
 39659            }
 660
 45661            mantissa &= mantissaMask;
 662
 45663            if ((exponent & exponentMask) == exponent)
 45664            {
 665                unchecked
 45666                {
 45667                    var bits = mantissa | ((ulong)exponent << mantissaLength);
 45668                    if (sign < 0)
 12669                    {
 12670                        bits |= negativeMark;
 12671                    }
 672
 45673                    return BitConverter.Int64BitsToDouble((long)bits);
 674                }
 675            }
 676
 0677            return sign > 0 ? double.PositiveInfinity : double.NegativeInfinity;
 54678        }
 679
 680        /// <summary>
 681        /// Gets a value Indicating whether the value of the current <see cref="BigInteger"/> object is a power of two.
 682        /// </summary>
 683        /// <value>
 684        /// <see langword="true"/> if the value of the <see cref="BigInteger"/> object is a power of two;
 685        /// otherwise, <see langword="false"/>.
 686        /// </value>
 687        public readonly bool IsPowerOfTwo
 688        {
 689            get
 27690            {
 27691                if (_sign != 1)
 15692                {
 15693                    return false;
 694                }
 695
 12696                var foundBit = false;
 697
 698                // This function is pop count == 1 for positive numbers
 57699                foreach (var bit in _data)
 12700                {
 12701                    var p = PopulationCount(bit);
 12702                    if (p > 0)
 12703                    {
 12704                        if (p > 1 || foundBit)
 3705                        {
 3706                            return false;
 707                        }
 708
 9709                        foundBit = true;
 9710                    }
 9711                }
 712
 9713                return foundBit;
 27714            }
 715        }
 716
 717        /// <summary>
 718        /// Gets a value indicating whether the value of the current <see cref="BigInteger"/> object is <see cref="Zero"
 719        /// </summary>
 720        /// <value>
 721        /// <see langword="true"/> if the value of the <see cref="BigInteger"/> object is <see cref="Zero"/>;
 722        /// otherwise, <see langword="false"/>.
 723        /// </value>
 724        public readonly bool IsZero
 725        {
 2504220726            get { return _sign == 0; }
 727        }
 728
 729        /// <summary>
 730        /// Gets a number that indicates the sign (negative, positive, or zero) of the current <see cref="BigInteger"/> 
 731        /// </summary>
 732        /// <value>
 733        /// A number that indicates the sign of the <see cref="BigInteger"/> object.
 734        /// </value>
 735        public readonly int Sign
 736        {
 54737            get { return _sign; }
 738        }
 739
 740        /// <summary>
 741        /// Gets a value that represents the number negative one (-1).
 742        /// </summary>
 743        /// <value>
 744        /// An integer whose value is negative one (-1).
 745        /// </value>
 746        public static BigInteger MinusOne
 747        {
 144748            get { return MinusOneSingleton; }
 749        }
 750
 751        /// <summary>
 752        /// Gets a value that represents the number one (1).
 753        /// </summary>
 754        /// <value>
 755        /// An object whose value is one (1).
 756        /// </value>
 757        public static BigInteger One
 758        {
 18771759            get { return OneSingleton; }
 760        }
 761
 762        /// <summary>
 763        /// Gets a value that represents the number 0 (zero).
 764        /// </summary>
 765        /// <value>
 766        /// An integer whose value is 0 (zero).
 767        /// </value>
 768        public static BigInteger Zero
 769        {
 14625770            get { return ZeroSingleton; }
 771        }
 772
 773        /// <summary>
 774        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a 32-bit signed integer value.
 775        /// </summary>
 776        /// <param name="value">The value to convert to a 32-bit signed integer.</param>
 777        /// <returns>
 778        /// An object that contains the value of the <paramref name="value"/> parameter.
 779        /// </returns>
 780#pragma warning disable CA2225 // Operator overloads have named alternates
 781        public static explicit operator int(BigInteger value)
 782#pragma warning restore CA2225 // Operator overloads have named alternates
 18462783        {
 18462784            if (value._data is null)
 2187785            {
 2187786                return 0;
 787            }
 788
 16275789            if (value._data.Length > 1)
 3790            {
 3791                throw new OverflowException();
 792            }
 793
 16272794            var data = value._data[0];
 795
 16272796            if (value._sign == 1)
 16194797            {
 16194798                if (data > (uint) int.MaxValue)
 3799                {
 3800                    throw new OverflowException();
 801                }
 802
 16191803                return (int)data;
 804            }
 805
 78806            if (value._sign == -1)
 78807            {
 78808                if (data > 0x80000000u)
 3809                {
 3810                    throw new OverflowException();
 811                }
 812
 75813                return -(int)data;
 814            }
 815
 0816            return 0;
 18453817        }
 818
 819        /// <summary>
 820        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to an unsigned 32-bit integer value.
 821        /// </summary>
 822        /// <param name="value">The value to convert to an unsigned 32-bit integer.</param>
 823        /// <returns>
 824        /// An object that contains the value of the <paramref name="value"/> parameter.
 825        /// </returns>
 826        [CLSCompliant(false)]
 827#pragma warning disable CA2225 // Operator overloads have named alternates
 828        public static explicit operator uint(BigInteger value)
 829#pragma warning restore CA2225 // Operator overloads have named alternates
 18830        {
 18831            if (value._data is null)
 3832            {
 3833                return 0;
 834            }
 835
 15836            if (value._data.Length > 1 || value._sign == -1)
 0837            {
 0838                throw new OverflowException();
 839            }
 840
 15841            return value._data[0];
 18842        }
 843
 844        /// <summary>
 845        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a 16-bit signed integer value.
 846        /// </summary>
 847        /// <param name="value">The value to convert to a 16-bit signed integer.</param>
 848        /// <returns>
 849        /// An object that contains the value of the <paramref name="value"/> parameter.
 850        /// </returns>
 851#pragma warning disable CA2225 // Operator overloads have named alternates
 852        public static explicit operator short(BigInteger value)
 853#pragma warning restore CA2225 // Operator overloads have named alternates
 6854        {
 6855            var val = (int) value;
 6856            if (val is < short.MinValue or > short.MaxValue)
 6857            {
 6858                throw new OverflowException();
 859            }
 860
 0861            return (short) val;
 0862        }
 863
 864        /// <summary>
 865        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a 16-bit unsigned integer value.
 866        /// </summary>
 867        /// <param name="value">The value to convert to a 16-bit unsigned integer.</param>
 868        /// <returns>
 869        /// An object that contains the value of the <paramref name="value"/> parameter.
 870        /// </returns>
 871        [CLSCompliant(false)]
 872#pragma warning disable CA2225 // Operator overloads have named alternates
 873        public static explicit operator ushort(BigInteger value)
 874#pragma warning restore CA2225 // Operator overloads have named alternates
 0875        {
 0876            var val = (uint) value;
 0877            if (val > ushort.MaxValue)
 0878            {
 0879                throw new OverflowException();
 880            }
 881
 0882            return (ushort) val;
 0883        }
 884
 885        /// <summary>
 886        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to an unsigned byte value.
 887        /// </summary>
 888        /// <param name="value">The value to convert to a <see cref="byte"/>.</param>
 889        /// <returns>
 890        /// An object that contains the value of the <paramref name="value"/> parameter.
 891        /// </returns>
 892#pragma warning disable CA2225 // Operator overloads have named alternates
 893        public static explicit operator byte(BigInteger value)
 894#pragma warning restore CA2225 // Operator overloads have named alternates
 0895        {
 0896            var val = (uint) value;
 0897            if (val > byte.MaxValue)
 0898            {
 0899                throw new OverflowException();
 900            }
 901
 0902            return (byte) val;
 0903        }
 904
 905        /// <summary>
 906        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a signed 8-bit value.
 907        /// </summary>
 908        /// <param name="value">The value to convert to a signed 8-bit value.</param>
 909        /// <returns>
 910        /// An object that contains the value of the <paramref name="value"/> parameter.
 911        /// </returns>
 912        [CLSCompliant(false)]
 913#pragma warning disable CA2225 // Operator overloads have named alternates
 914        public static explicit operator sbyte(BigInteger value)
 915#pragma warning restore CA2225 // Operator overloads have named alternates
 0916        {
 0917            var val = (int) value;
 0918            if (val is < sbyte.MinValue or > sbyte.MaxValue)
 0919            {
 0920                throw new OverflowException();
 921            }
 922
 0923            return (sbyte) val;
 0924        }
 925
 926        /// <summary>
 927        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a 64-bit signed integer value.
 928        /// </summary>
 929        /// <param name="value">The value to convert to a 64-bit signed integer.</param>
 930        /// <returns>
 931        /// An object that contains the value of the <paramref name="value"/> parameter.
 932        /// </returns>
 933#pragma warning disable CA2225 // Operator overloads have named alternates
 934        public static explicit operator long(BigInteger value)
 935#pragma warning restore CA2225 // Operator overloads have named alternates
 2238936        {
 2238937            if (value._data is null)
 471938            {
 471939                return 0;
 940            }
 941
 1767942            if (value._data.Length > 2)
 3943            {
 3944                throw new OverflowException();
 945            }
 946
 1764947            var low = value._data[0];
 948
 1764949            if (value._data.Length == 1)
 1023950            {
 1023951                if (value._sign == 1)
 474952                {
 474953                    return (long) low;
 954                }
 955
 549956                var res = (long)low;
 549957                return -res;
 958            }
 959
 741960            var high = value._data[1];
 961
 741962            if (value._sign == 1)
 390963            {
 390964                if (high >= 0x80000000u)
 3965                {
 3966                    throw new OverflowException();
 967                }
 968
 387969                return (((long)high) << 32) | low;
 970            }
 971
 972            /*
 973            We cannot represent negative numbers smaller than long.MinValue.
 974            Those values are encoded into what look negative numbers, so negating
 975            them produces a positive value, that's why it's safe to check for that
 976            condition.
 977
 978            long.MinValue works fine since it's bigint encoding looks like a negative
 979            number, but since long.MinValue == -long.MinValue, we're good.
 980            */
 981
 351982            var result = -((((long)high) << 32) | (long)low);
 351983            if (result > 0)
 6984            {
 6985                throw new OverflowException();
 986            }
 987
 345988            return result;
 2226989        }
 990
 991        /// <summary>
 992        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to an unsigned 64-bit integer value.
 993        /// </summary>
 994        /// <param name="value">The value to convert to an unsigned 64-bit integer.</param>
 995        /// <returns>
 996        /// An object that contains the value of the <paramref name="value"/> parameter.
 997        /// </returns>
 998        [CLSCompliant(false)]
 999#pragma warning disable CA2225 // Operator overloads have named alternates
 1000        public static explicit operator ulong(BigInteger value)
 1001#pragma warning restore CA2225 // Operator overloads have named alternates
 31002        {
 31003            if (value._data is null)
 31004            {
 31005                return 0;
 1006            }
 1007
 01008            if (value._data.Length > 2 || value._sign == -1)
 01009            {
 01010                throw new OverflowException();
 1011            }
 1012
 01013            var low = value._data[0];
 01014            if (value._data.Length == 1)
 01015            {
 01016                return low;
 1017            }
 1018
 01019            var high = value._data[1];
 01020            return (((ulong)high) << 32) | low;
 31021        }
 1022
 1023        /// <summary>
 1024        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a <see cref="double"/> value.
 1025        /// </summary>
 1026        /// <param name="value">The value to convert to a <see cref="double"/>.</param>
 1027        /// <returns>
 1028        /// An object that contains the value of the <paramref name="value"/> parameter.
 1029        /// </returns>
 1030#pragma warning disable CA2225 // Operator overloads have named alternates
 1031        public static explicit operator double(BigInteger value)
 1032#pragma warning restore CA2225 // Operator overloads have named alternates
 571033        {
 571034            if (value._data is null)
 31035            {
 31036                return 0.0;
 1037            }
 1038
 541039            switch (value._data.Length)
 1040            {
 1041                case 1:
 91042                    return BuildDouble(value._sign, value._data[0], 0);
 1043                case 2:
 61044                    return BuildDouble(value._sign, (ulong) value._data[1] << 32 | (ulong) value._data[0], 0);
 1045                default:
 391046                    var index = value._data.Length - 1;
 391047                    var word = value._data[index];
 391048                    var mantissa = ((ulong)word << 32) | value._data[index - 1];
 391049                    var missing = LeadingZeroCount(word) - 11; // 11 = bits in exponent
 391050                    if (missing > 0)
 91051                    {
 1052                        // add the missing bits from the next word
 91053                        mantissa = (mantissa << missing) | (value._data[index - 2] >> (32 - missing));
 91054                    }
 1055                    else
 301056                    {
 301057                        mantissa >>= -missing;
 301058                    }
 1059
 391060                    return BuildDouble(value._sign, mantissa, ((value._data.Length - 2) * 32) - missing);
 1061            }
 571062        }
 1063
 1064        /// <summary>
 1065        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a single-precision floating-point val
 1066        /// </summary>
 1067        /// <param name="value">The value to convert to a single-precision floating-point value.</param>
 1068        /// <returns>
 1069        /// An object that contains the value of the <paramref name="value"/> parameter.
 1070        /// </returns>
 1071#pragma warning disable CA2225 // Operator overloads have named alternates
 1072        public static explicit operator float(BigInteger value)
 1073#pragma warning restore CA2225 // Operator overloads have named alternates
 01074        {
 01075            return (float) (double) value;
 01076        }
 1077
 1078        /// <summary>
 1079        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a <see cref="decimal"/> value.
 1080        /// </summary>
 1081        /// <param name="value">The value to convert to a <see cref="decimal"/>.</param>
 1082        /// <returns>
 1083        /// An object that contains the value of the <paramref name="value"/> parameter.
 1084        /// </returns>
 1085#pragma warning disable CA2225 // Operator overloads have named alternates
 1086        public static explicit operator decimal(BigInteger value)
 1087#pragma warning restore CA2225 // Operator overloads have named alternates
 241088        {
 241089            if (value._data is null)
 61090            {
 61091                return decimal.Zero;
 1092            }
 1093
 181094            var data = value._data;
 181095            if (data.Length > 3)
 61096            {
 61097                throw new OverflowException();
 1098            }
 1099
 361100            int lo = 0, mi = 0, hi = 0;
 121101            if (data.Length > 2)
 31102            {
 31103                hi = (int) data[2];
 31104            }
 1105
 121106            if (data.Length > 1)
 31107            {
 31108                mi = (int) data[1];
 31109            }
 1110
 121111            if (data.Length > 0)
 121112            {
 121113                lo = (int) data[0];
 121114            }
 1115
 121116            return new decimal(lo, mi, hi, value._sign < 0, 0);
 181117        }
 1118
 1119        /// <summary>
 1120        /// Defines an implicit conversion of a signed 32-bit integer to a <see cref="BigInteger"/> value.
 1121        /// </summary>
 1122        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
 1123        /// <returns>
 1124        /// An object that contains the value of the <paramref name="value"/> parameter.
 1125        /// </returns>
 1126#pragma warning disable CA2225 // Operator overloads have named alternates
 1127        public static implicit operator BigInteger(int value)
 1128#pragma warning restore CA2225 // Operator overloads have named alternates
 149511129        {
 149511130            return new BigInteger(value);
 149511131        }
 1132
 1133        /// <summary>
 1134        /// Defines an implicit conversion of a 32-bit unsigned integer to a <see cref="BigInteger"/> value.
 1135        /// </summary>
 1136        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
 1137        /// <returns>
 1138        /// An object that contains the value of the <paramref name="value"/> parameter.
 1139        /// </returns>
 1140        [CLSCompliant(false)]
 1141#pragma warning disable CA2225 // Operator overloads have named alternates
 1142        public static implicit operator BigInteger(uint value)
 1143#pragma warning restore CA2225 // Operator overloads have named alternates
 182011144        {
 182011145            return new BigInteger(value);
 182011146        }
 1147
 1148        /// <summary>
 1149        /// Defines an implicit conversion of a signed 16-bit integer to a BigInteger value.
 1150        /// </summary>
 1151        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
 1152        /// <returns>
 1153        /// An object that contains the value of the <paramref name="value"/> parameter.
 1154        /// </returns>
 1155#pragma warning disable CA2225 // Operator overloads have named alternates
 1156        public static implicit operator BigInteger(short value)
 1157#pragma warning restore CA2225 // Operator overloads have named alternates
 01158        {
 01159            return new BigInteger(value);
 01160        }
 1161
 1162        /// <summary>
 1163        /// Defines an implicit conversion of a 16-bit unsigned integer to a <see cref="BigInteger"/> value.
 1164        /// </summary>
 1165        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
 1166        /// <returns>
 1167        /// An object that contains the value of the <paramref name="value"/> parameter.
 1168        /// </returns>
 1169        [CLSCompliant(false)]
 1170#pragma warning disable CA2225 // Operator overloads have named alternates
 1171        public static implicit operator BigInteger(ushort value)
 1172#pragma warning restore CA2225 // Operator overloads have named alternates
 01173        {
 01174            return new BigInteger(value);
 01175        }
 1176
 1177        /// <summary>
 1178        /// Defines an implicit conversion of an unsigned byte to a <see cref="BigInteger"/> value.
 1179        /// </summary>
 1180        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
 1181        /// <returns>
 1182        /// An object that contains the value of the <paramref name="value"/> parameter.
 1183        /// </returns>
 1184#pragma warning disable CA2225 // Operator overloads have named alternates
 1185        public static implicit operator BigInteger(byte value)
 1186#pragma warning restore CA2225 // Operator overloads have named alternates
 124051187        {
 124051188            return new BigInteger(value);
 124051189        }
 1190
 1191        /// <summary>
 1192        /// Defines an implicit conversion of a signed byte to a <see cref="BigInteger"/> value.
 1193        /// </summary>
 1194        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
 1195        /// <returns>
 1196        /// An object that contains the value of the <paramref name="value"/> parameter.
 1197        /// </returns>
 1198        [CLSCompliant(false)]
 1199#pragma warning disable CA2225 // Operator overloads have named alternates
 1200        public static implicit operator BigInteger(sbyte value)
 1201#pragma warning restore CA2225 // Operator overloads have named alternates
 01202        {
 01203            return new BigInteger(value);
 01204        }
 1205
 1206        /// <summary>
 1207        /// Defines an implicit conversion of a signed 64-bit integer to a <see cref="BigInteger"/> value.
 1208        /// </summary>
 1209        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
 1210        /// <returns>
 1211        /// An object that contains the value of the <paramref name="value"/> parameter.
 1212        /// </returns>
 1213#pragma warning disable CA2225 // Operator overloads have named alternates
 1214        public static implicit operator BigInteger(long value)
 1215#pragma warning restore CA2225 // Operator overloads have named alternates
 61216        {
 61217            return new BigInteger(value);
 61218        }
 1219
 1220        /// <summary>
 1221        /// Defines an implicit conversion of a 64-bit unsigned integer to a <see cref="BigInteger"/> value.
 1222        /// </summary>
 1223        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
 1224        /// <returns>
 1225        /// An object that contains the value of the <paramref name="value"/> parameter.
 1226        /// </returns>
 1227        [CLSCompliant(false)]
 1228#pragma warning disable CA2225 // Operator overloads have named alternates
 1229        public static implicit operator BigInteger(ulong value)
 1230#pragma warning restore CA2225 // Operator overloads have named alternates
 151231        {
 151232            return new BigInteger(value);
 151233        }
 1234
 1235        /// <summary>
 1236        /// Defines an explicit conversion of a <see cref="double"/> value to a <see cref="BigInteger"/> value.
 1237        /// </summary>
 1238        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
 1239        /// <returns>
 1240        /// An object that contains the value of the <paramref name="value"/> parameter.
 1241        /// </returns>
 1242#pragma warning disable CA2225 // Operator overloads have named alternates
 1243        public static explicit operator BigInteger(double value)
 1244#pragma warning restore CA2225 // Operator overloads have named alternates
 01245        {
 01246            return new BigInteger(value);
 01247        }
 1248
 1249        /// <summary>
 1250        /// Defines an explicit conversion of a <see cref="float"/> object to a <see cref="BigInteger"/> value.
 1251        /// </summary>
 1252        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
 1253        /// <returns>
 1254        /// An object that contains the value of the <paramref name="value"/> parameter.
 1255        /// </returns>
 1256#pragma warning disable CA2225 // Operator overloads have named alternates
 1257        public static explicit operator BigInteger(float value)
 1258#pragma warning restore CA2225 // Operator overloads have named alternates
 01259        {
 01260            return new BigInteger(value);
 01261        }
 1262
 1263        /// <summary>
 1264        /// Defines an explicit conversion of a <see cref="decimal"/> object to a <see cref="BigInteger"/> value.
 1265        /// </summary>
 1266        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
 1267        /// <returns>
 1268        /// An object that contains the value of the <paramref name="value"/> parameter.
 1269        /// </returns>
 1270#pragma warning disable CA2225 // Operator overloads have named alternates
 1271        public static explicit operator BigInteger(decimal value)
 1272#pragma warning restore CA2225 // Operator overloads have named alternates
 01273        {
 01274            return new BigInteger(value);
 01275        }
 1276
 1277        /// <summary>
 1278        /// Adds the values of two specified <see cref="BigInteger"/> objects.
 1279        /// </summary>
 1280        /// <param name="left">The first value to add.</param>
 1281        /// <param name="right">The second value to add.</param>
 1282        /// <returns>
 1283        /// The sum of <paramref name="left"/> and <paramref name="right"/>.
 1284        /// </returns>
 1285        public static BigInteger operator +(BigInteger left, BigInteger right)
 8456361286        {
 8456361287            if (left._sign == 0)
 8801288            {
 8801289                return right;
 1290            }
 1291
 8447561292            if (right._sign == 0)
 11071293            {
 11071294                return left;
 1295            }
 1296
 8436491297            if (left._sign == right._sign)
 8432921298            {
 8432921299                return new BigInteger(left._sign, CoreAdd(left._data, right._data));
 1300            }
 1301
 3571302            var r = CoreCompare(left._data, right._data);
 1303
 3571304            if (r == 0)
 301305            {
 301306                return Zero;
 1307            }
 1308
 3271309            if (r > 0)
 181310            {
 1311                // left > right
 181312                return new BigInteger(left._sign, CoreSub(left._data, right._data));
 1313            }
 1314
 3091315            return new BigInteger(right._sign, CoreSub(right._data, left._data));
 8456361316        }
 1317
 1318        /// <summary>
 1319        /// Subtracts a <see cref="BigInteger"/> value from another <see cref="BigInteger"/> value.
 1320        /// </summary>
 1321        /// <param name="left">The value to subtract from (the minuend).</param>
 1322        /// <param name="right">The value to subtract (the subtrahend).</param>
 1323        /// <returns>
 1324        /// The result of subtracting <paramref name="right"/> from <paramref name="left"/>.
 1325        /// </returns>
 1326        public static BigInteger operator -(BigInteger left, BigInteger right)
 20821327        {
 20821328            if (right._sign == 0)
 421329            {
 421330                return left;
 1331            }
 1332
 20401333            if (left._sign == 0)
 361334            {
 1335#pragma warning disable SA1021 // Negative signs should be spaced correctly
 361336                return new BigInteger((short) -right._sign, right._data);
 1337#pragma warning restore SA1021 // Negative signs should be spaced correctly
 1338            }
 1339
 20041340            if (left._sign == right._sign)
 18931341            {
 18931342                var r = CoreCompare(left._data, right._data);
 1343
 18931344                if (r == 0)
 361345                {
 361346                    return Zero;
 1347                }
 1348
 18571349                if (r > 0)
 15271350                {
 1351                    // left > right
 15271352                    return new BigInteger(left._sign, CoreSub(left._data, right._data));
 1353                }
 1354
 3301355                return new BigInteger((short)-right._sign, CoreSub(right._data, left._data));
 1356            }
 1357
 1111358            return new BigInteger(left._sign, CoreAdd(left._data, right._data));
 20821359        }
 1360
 1361        /// <summary>
 1362        /// Multiplies two specified <see cref="BigInteger"/> values.
 1363        /// </summary>
 1364        /// <param name="left">The first value to multiply.</param>
 1365        /// <param name="right">The second value to multiply.</param>
 1366        /// <returns>
 1367        /// The product of left and right.
 1368        /// </returns>
 1369        public static BigInteger operator *(BigInteger left, BigInteger right)
 30869021370        {
 30869021371            if (left._sign == 0 || right._sign == 0)
 1921372            {
 1921373                return Zero;
 1374            }
 1375
 30867101376            if (left._data[0] == 1 && left._data.Length == 1)
 3490631377            {
 3490631378                if (left._sign == 1)
 3490451379                {
 3490451380                    return right;
 1381                }
 1382
 181383                return new BigInteger((short)-right._sign, right._data);
 1384            }
 1385
 27376471386            if (right._data[0] == 1 && right._data.Length == 1)
 5781387            {
 5781388                if (right._sign == 1)
 5631389                {
 5631390                    return left;
 1391                }
 1392
 151393                return new BigInteger((short)-left._sign, left._data);
 1394            }
 1395
 27370691396            var a = left._data;
 27370691397            var b = right._data;
 1398
 27370691399            var res = new uint[a.Length + b.Length];
 1400
 1590320981401            for (var i = 0; i < a.Length; ++i)
 767789801402            {
 767789801403                var ai = a[i];
 767789801404                var k = i;
 1405
 767789801406                ulong carry = 0;
 968236241407                for (var j = 0; j < b.Length; ++j)
 462847141408                {
 462847141409                    carry = carry + (((ulong) ai) * b[j]) + res[k];
 462847141410                    res[k++] = (uint)carry;
 462847141411                    carry >>= 32;
 462847141412                }
 1413
 1529903881414                while (carry != 0)
 762114081415                {
 762114081416                    carry += res[k];
 762114081417                    res[k++] = (uint)carry;
 762114081418                    carry >>= 32;
 762114081419                }
 767789801420            }
 1421
 1422            int m;
 63961861423            for (m = res.Length - 1; m >= 0 && res[m] == 0; --m)
 4610241424            {
 1425                // Intentionally empty block
 4610241426            }
 1427
 27370691428            if (m < res.Length - 1)
 4610241429            {
 4610241430                Array.Resize(ref res, m + 1);
 4610241431            }
 1432
 27370691433            return new BigInteger((short) (left._sign*right._sign), res);
 30869021434        }
 1435
 1436        /// <summary>
 1437        /// Divides a specified <see cref="BigInteger"/> value by another specified <see cref="BigInteger"/> value by us
 1438        /// integer division.
 1439        /// </summary>
 1440        /// <param name="dividend">The value to be divided.</param>
 1441        /// <param name="divisor">The value to divide by.</param>
 1442        /// <returns>
 1443        /// The integral result of the division.
 1444        /// </returns>
 1445        public static BigInteger operator /(BigInteger dividend, BigInteger divisor)
 8320061446        {
 8320061447            if (divisor._sign == 0)
 01448            {
 01449                throw new DivideByZeroException();
 1450            }
 1451
 8320061452            if (dividend._sign == 0)
 01453            {
 01454                return dividend;
 1455            }
 1456
 8320061457            DivModUnsigned(dividend._data, divisor._data, out var quotient, out _);
 1458
 1459            int i;
 17517401460            for (i = quotient.Length - 1; i >= 0 && quotient[i] == 0; --i)
 438641461            {
 1462                // Intentionally empty block
 438641463            }
 1464
 8320061465            if (i == -1)
 01466            {
 01467                return Zero;
 1468            }
 1469
 8320061470            if (i < quotient.Length - 1)
 438641471            {
 438641472                Array.Resize(ref quotient, i + 1);
 438641473            }
 1474
 8320061475            return new BigInteger((short)(dividend._sign * divisor._sign), quotient);
 8320061476        }
 1477
 1478        /// <summary>
 1479        /// Returns the remainder that results from division with two specified <see cref="BigInteger"/> values.
 1480        /// </summary>
 1481        /// <param name="dividend">The value to be divided.</param>
 1482        /// <param name="divisor">The value to divide by.</param>
 1483        /// <returns>
 1484        /// The remainder that results from the division.
 1485        /// </returns>
 1486        public static BigInteger operator %(BigInteger dividend, BigInteger divisor)
 30786251487        {
 30786251488            if (divisor._sign == 0)
 01489            {
 01490                throw new DivideByZeroException();
 1491            }
 1492
 30786251493            if (dividend._sign == 0)
 01494            {
 01495                return dividend;
 1496            }
 1497
 30786251498            DivModUnsigned(dividend._data, divisor._data, out _, out var remainderValue);
 1499
 1500            int i;
 1629337581501            for (i = remainderValue.Length - 1; i >= 0 && remainderValue[i] == 0; --i)
 783882541502            {
 1503                // Intentionally empty block
 783882541504            }
 1505
 30786251506            if (i == -1)
 01507            {
 01508                return Zero;
 1509            }
 1510
 30786251511            if (i < remainderValue.Length - 1)
 30621061512            {
 30621061513                Array.Resize(ref remainderValue, i + 1);
 30621061514            }
 1515
 30786251516            return new BigInteger(dividend._sign, remainderValue);
 30786251517        }
 1518
 1519        /// <summary>
 1520        /// Negates a specified <see cref="BigInteger"/> value.
 1521        /// </summary>
 1522        /// <param name="value">The value to negate.</param>
 1523        /// <returns>
 1524        /// The result of the <paramref name="value"/> parameter multiplied by negative one (-1).
 1525        /// </returns>
 1526        public static BigInteger operator -(BigInteger value)
 421527        {
 421528            if (value._data is null)
 61529            {
 61530                return value;
 1531            }
 1532
 1533#pragma warning disable SA1021 // Negative signs should be spaced correctly
 361534            return new BigInteger((short) -value._sign, value._data);
 1535#pragma warning restore SA1021 // Negative signs should be spaced correctly
 421536        }
 1537
 1538        /// <summary>
 1539        /// Returns the value of the <see cref="BigInteger"/> operand.
 1540        /// </summary>
 1541        /// <param name="value">An integer value.</param>
 1542        /// <returns>
 1543        /// The value of the <paramref name="value"/> operand.
 1544        /// </returns>
 1545        /// <remarks>
 1546        /// The sign of the operand is unchanged.
 1547        /// </remarks>
 1548#pragma warning disable CA2225 // Operator overloads have named alternates
 1549        public static BigInteger operator +(BigInteger value)
 1550#pragma warning restore CA2225 // Operator overloads have named alternates
 01551        {
 01552            return value;
 01553        }
 1554
 1555        /// <summary>
 1556        /// Increments a <see cref="BigInteger"/> value by 1.
 1557        /// </summary>
 1558        /// <param name="value">The value to increment.</param>
 1559        /// <returns>
 1560        /// The value of the <paramref name="value"/> parameter incremented by 1.
 1561        /// </returns>
 1562#pragma warning disable CA2225 // Operator overloads have named alternates
 1563        public static BigInteger operator ++(BigInteger value)
 1564#pragma warning restore CA2225 // Operator overloads have named alternates
 241565        {
 241566            if (value._data is null)
 61567            {
 61568                return One;
 1569            }
 1570
 181571            var sign = value._sign;
 181572            var data = value._data;
 181573            if (data.Length == 1)
 121574            {
 121575                if (sign == -1 && data[0] == 1)
 31576                {
 31577                    return Zero;
 1578                }
 1579
 91580                if (sign == 0)
 01581                {
 01582                    return One;
 1583                }
 91584            }
 1585
 151586            data = sign == -1 ? CoreSub(data, 1) : CoreAdd(data, 1);
 1587
 151588            return new BigInteger(sign, data);
 241589        }
 1590
 1591        /// <summary>
 1592        /// Decrements a <see cref="BigInteger"/> value by 1.
 1593        /// </summary>
 1594        /// <param name="value">The value to decrement.</param>
 1595        /// <returns>
 1596        /// The value of the <paramref name="value"/> parameter decremented by 1.
 1597        /// </returns>
 1598#pragma warning disable CA2225 // Operator overloads have named alternates
 1599        public static BigInteger operator --(BigInteger value)
 1600#pragma warning restore CA2225 // Operator overloads have named alternates
 331601        {
 331602            if (value._data is null)
 61603            {
 61604                return MinusOne;
 1605            }
 1606
 271607            var sign = value._sign;
 271608            var data = value._data;
 271609            if (data.Length == 1)
 211610            {
 211611                if (sign == 1 && data[0] == 1)
 31612                {
 31613                    return Zero;
 1614                }
 1615
 181616                if (sign == 0)
 01617                {
 01618                    return MinusOne;
 1619                }
 181620            }
 1621
 241622            data = sign == -1 ? CoreAdd(data, 1) : CoreSub(data, 1);
 1623
 241624            return new BigInteger(sign, data);
 331625        }
 1626
 1627        /// <summary>
 1628        /// Performs a bitwise <c>And</c> operation on two <see cref="BigInteger"/> values.
 1629        /// </summary>
 1630        /// <param name="left">The first value.</param>
 1631        /// <param name="right">The second value.</param>
 1632        /// <returns>
 1633        /// The result of the bitwise <c>And</c> operation.
 1634        /// </returns>
 1635#pragma warning disable CA2225 // Operator overloads have named alternates
 1636        public static BigInteger operator &(BigInteger left, BigInteger right)
 1637#pragma warning restore CA2225 // Operator overloads have named alternates
 2491638        {
 2491639            if (left._sign == 0)
 241640            {
 241641                return left;
 1642            }
 1643
 2251644            if (right._sign == 0)
 211645            {
 211646                return right;
 1647            }
 1648
 2041649            var a = left._data;
 2041650            var b = right._data;
 2041651            int ls = left._sign;
 2041652            int rs = right._sign;
 1653
 2041654            var negRes = (ls == rs) && (ls == -1);
 1655
 2041656            var result = new uint[Math.Max(a.Length, b.Length)];
 1657
 6121658            ulong ac = 1, bc = 1, borrow = 1;
 1659
 1660            int i;
 10141661            for (i = 0; i < result.Length; ++i)
 3031662            {
 3031663                uint va = 0;
 3031664                if (i < a.Length)
 2671665                {
 2671666                    va = a[i];
 2671667                }
 1668
 3031669                if (ls == -1)
 1021670                {
 1021671                    ac = ~va + ac;
 1021672                    va = (uint)ac;
 1021673                    ac = (uint)(ac >> 32);
 1021674                }
 1675
 3031676                uint vb = 0;
 3031677                if (i < b.Length)
 2671678                {
 2671679                    vb = b[i];
 2671680                }
 1681
 3031682                if (rs == -1)
 1021683                {
 1021684                    bc = ~vb + bc;
 1021685                    vb = (uint)bc;
 1021686                    bc = (uint)(bc >> 32);
 1021687                }
 1688
 3031689                var word = va & vb;
 1690
 3031691                if (negRes)
 421692                {
 421693                    borrow = word - borrow;
 421694                    word = ~(uint)borrow;
 421695                    borrow = (uint)(borrow >> 32) & 0x1u;
 421696                }
 1697
 3031698                result[i] = word;
 3031699            }
 1700
 6361701            for (i = result.Length - 1; i >= 0 && result[i] == 0; --i)
 1141702            {
 1703                // Intentionally empty block
 1141704            }
 1705
 2041706            if (i == -1)
 721707            {
 721708                return Zero;
 1709            }
 1710
 1321711            if (i < result.Length - 1)
 61712            {
 61713                Array.Resize(ref result, i + 1);
 61714            }
 1715
 1321716            return new BigInteger(negRes ? (short)-1 : (short)1, result);
 2491717        }
 1718
 1719        /// <summary>
 1720        /// Performs a bitwise <c>Or</c> operation on two <see cref="BigInteger"/> values.
 1721        /// </summary>
 1722        /// <param name="left">The first value.</param>
 1723        /// <param name="right">The second value.</param>
 1724        /// <returns>
 1725        /// The result of the bitwise <c>Or</c> operation.
 1726        /// </returns>
 1727#pragma warning disable CA2225 // Operator overloads have named alternates
 1728        public static BigInteger operator |(BigInteger left, BigInteger right)
 1729#pragma warning restore CA2225 // Operator overloads have named alternates
 1921730        {
 1921731            if (left._sign == 0)
 241732            {
 241733                return right;
 1734            }
 1735
 1681736            if (right._sign == 0)
 211737            {
 211738                return left;
 1739            }
 1740
 1471741            var a = left._data;
 1471742            var b = right._data;
 1471743            int ls = left._sign;
 1471744            int rs = right._sign;
 1745
 1471746            var negRes = (ls == -1) || (rs == -1);
 1747
 1471748            var result = new uint[Math.Max(a.Length, b.Length)];
 1749
 4411750            ulong ac = 1, bc = 1, borrow = 1;
 1751
 1752            int i;
 7861753            for (i = 0; i < result.Length; ++i)
 2461754            {
 2461755                uint va = 0;
 2461756                if (i < a.Length)
 2101757                {
 2101758                    va = a[i];
 2101759                }
 1760
 2461761                if (ls == -1)
 1021762                {
 1021763                    ac = ~va + ac;
 1021764                    va = (uint)ac;
 1021765                    ac = (uint)(ac >> 32);
 1021766                }
 1767
 2461768                uint vb = 0;
 2461769                if (i < b.Length)
 2101770                {
 2101771                    vb = b[i];
 2101772                }
 1773
 2461774                if (rs == -1)
 1021775                {
 1021776                    bc = ~vb + bc;
 1021777                    vb = (uint)bc;
 1021778                    bc = (uint)(bc >> 32);
 1021779                }
 1780
 2461781                var word = va | vb;
 1782
 2461783                if (negRes)
 1621784                {
 1621785                    borrow = word - borrow;
 1621786                    word = ~(uint)borrow;
 1621787                    borrow = (uint)(borrow >> 32) & 0x1u;
 1621788                }
 1789
 2461790                result[i] = word;
 2461791            }
 1792
 3901793            for (i = result.Length - 1; i >= 0 && result[i] == 0; --i)
 481794            {
 1795                // Intentionally empty block
 481796            }
 1797
 1471798            if (i == -1)
 01799            {
 01800                return Zero;
 1801            }
 1802
 1471803            if (i < result.Length - 1)
 481804            {
 481805                Array.Resize(ref result, i + 1);
 481806            }
 1807
 1471808            return new BigInteger(negRes ? (short)-1 : (short)1, result);
 1921809        }
 1810
 1811        /// <summary>
 1812        /// Performs a bitwise exclusive <c>Or</c> (<c>XOr</c>) operation on two <see cref="BigInteger"/> values.
 1813        /// </summary>
 1814        /// <param name="left">The first value.</param>
 1815        /// <param name="right">The second value.</param>
 1816        /// <returns>
 1817        /// The result of the bitwise <c>Or</c> operation.
 1818        /// </returns>
 1819#pragma warning disable CA2225 // Operator overloads have named alternates
 1820        public static BigInteger operator ^(BigInteger left, BigInteger right)
 1821#pragma warning restore CA2225 // Operator overloads have named alternates
 2101822        {
 2101823            if (left._sign == 0)
 241824            {
 241825                return right;
 1826            }
 1827
 1861828            if (right._sign == 0)
 211829            {
 211830                return left;
 1831            }
 1832
 1651833            var a = left._data;
 1651834            var b = right._data;
 1651835            int ls = left._sign;
 1651836            int rs = right._sign;
 1837
 1651838            var negRes = (ls == -1) ^ (rs == -1);
 1839
 1651840            var result = new uint[Math.Max(a.Length, b.Length)];
 1841
 4951842            ulong ac = 1, bc = 1, borrow = 1;
 1843
 1844            int i;
 29521845            for (i = 0; i < result.Length; ++i)
 13111846            {
 13111847                uint va = 0;
 13111848                if (i < a.Length)
 2281849                {
 2281850                    va = a[i];
 2281851                }
 1852
 13111853                if (ls == -1)
 1021854                {
 1021855                    ac = ~va + ac;
 1021856                    va = (uint)ac;
 1021857                    ac = (uint)(ac >> 32);
 1021858                }
 1859
 13111860                uint vb = 0;
 13111861                if (i < b.Length)
 12751862                {
 12751863                    vb = b[i];
 12751864                }
 1865
 13111866                if (rs == -1)
 1021867                {
 1021868                    bc = ~vb + bc;
 1021869                    vb = (uint)bc;
 1021870                    bc = (uint)(bc >> 32);
 1021871                }
 1872
 13111873                var word = va ^ vb;
 1874
 13111875                if (negRes)
 1201876                {
 1201877                    borrow = word - borrow;
 1201878                    word = ~(uint)borrow;
 1201879                    borrow = (uint)(borrow >> 32) & 0x1u;
 1201880                }
 1881
 13111882                result[i] = word;
 13111883            }
 1884
 4141885            for (i = result.Length - 1; i >= 0 && result[i] == 0; --i)
 421886            {
 1887                // Intentionally empty block
 421888            }
 1889
 1651890            if (i == -1)
 271891            {
 271892                return Zero;
 1893            }
 1894
 1381895            if (i < result.Length - 1)
 61896            {
 61897                Array.Resize(ref result, i + 1);
 61898            }
 1899
 1381900            return new BigInteger(negRes ? (short)-1 : (short)1, result);
 2101901        }
 1902
 1903        /// <summary>
 1904        /// Returns the bitwise one's complement of a <see cref="BigInteger"/> value.
 1905        /// </summary>
 1906        /// <param name="value">An integer value.</param>
 1907        /// <returns>
 1908        /// The bitwise one's complement of <paramref name="value"/>.
 1909        /// </returns>
 1910#pragma warning disable CA2225 // Operator overloads have named alternates
 1911        public static BigInteger operator ~(BigInteger value)
 1912#pragma warning restore CA2225 // Operator overloads have named alternates
 1951913        {
 1951914            if (value._data is null)
 271915            {
 271916                return MinusOne;
 1917            }
 1918
 1681919            var data = value._data;
 1681920            int sign = value._sign;
 1921
 1681922            var negRes = sign == 1;
 1923
 1681924            var result = new uint[data.Length];
 1925
 3361926            ulong carry = 1, borrow = 1;
 1927
 1928            int i;
 8161929            for (i = 0; i < result.Length; ++i)
 2401930            {
 2401931                var word = data[i];
 2401932                if (sign == -1)
 961933                {
 961934                    carry = ~word + carry;
 961935                    word = (uint)carry;
 961936                    carry = (uint)(carry >> 32);
 961937                }
 1938
 2401939                word = ~word;
 1940
 2401941                if (negRes)
 1441942                {
 1441943                    borrow = word - borrow;
 1441944                    word = ~(uint)borrow;
 1441945                    borrow = (uint)(borrow >> 32) & 0x1u;
 1441946                }
 1947
 2401948                result[i] = word;
 2401949            }
 1950
 3841951            for (i = result.Length - 1; i >= 0 && result[i] == 0; --i)
 241952            {
 1953                // Intentionally empty block
 241954            }
 1955
 1681956            if (i == -1)
 241957            {
 241958                return Zero;
 1959            }
 1960
 1441961            if (i < result.Length - 1)
 01962            {
 01963                Array.Resize(ref result, i + 1);
 01964            }
 1965
 1441966            return new BigInteger(negRes ? (short)-1 : (short)1, result);
 1951967        }
 1968
 1969        /// <summary>
 1970        /// Returns the zero-based index of the most significant set bit.
 1971        /// </summary>
 1972        /// <param name="word">The value to scan.</param>
 1973        /// <returns>
 1974        /// The zero-based index of the most significant set bit, or zero if no bit is set.
 1975        /// </returns>
 1976        private static int BitScanBackward(uint word)
 14842771977        {
 493275741978            for (var i = 31; i >= 0; --i)
 246637871979            {
 246637871980                var mask = 1u << i;
 246637871981                if ((word & mask) == mask)
 14842771982                {
 14842771983                    return i;
 1984                }
 231795101985            }
 1986
 01987            return 0;
 14842771988        }
 1989
 1990        /// <summary>
 1991        /// Shifts a <see cref="BigInteger"/> value a specified number of bits to the left.
 1992        /// </summary>
 1993        /// <param name="value">The value whose bits are to be shifted.</param>
 1994        /// <param name="shift">The number of bits to shift value to the left.</param>
 1995        /// <returns>
 1996        /// A value that has been shifted to the left by the specified number of bits.
 1997        /// </returns>
 1998#pragma warning disable CA2225 // Operator overloads have named alternates
 1999        public static BigInteger operator <<(BigInteger value, int shift)
 2000#pragma warning restore CA2225 // Operator overloads have named alternates
 2552001        {
 2552002            if (shift == 0 || value._data is null)
 62003            {
 62004                return value;
 2005            }
 2006
 2492007            if (shift < 0)
 32008            {
 32009                return value >> -shift;
 2010            }
 2011
 2462012            var data = value._data;
 2462013            int sign = value._sign;
 2014
 2462015            var topMostIdx = BitScanBackward(data[data.Length - 1]);
 2462016            var bits = shift - (31 - topMostIdx);
 2462017            var extraWords = (bits >> 5) + ((bits & 0x1F) != 0 ? 1 : 0);
 2018
 2462019            var res = new uint[data.Length + extraWords];
 2020
 2462021            var idxShift = shift >> 5;
 2462022            var bitShift = shift & 0x1F;
 2462023            var carryShift = 32 - bitShift;
 2024
 2462025            if (carryShift == 32)
 92026            {
 902027                for (var i = 0; i < data.Length; ++i)
 362028                {
 362029                    var word = data[i];
 362030                    res[i + idxShift] |= word << bitShift;
 362031                }
 92032            }
 2033            else
 2372034            {
 21542035                for (var i = 0; i < data.Length; ++i)
 8402036                {
 8402037                    var word = data[i];
 8402038                    res[i + idxShift] |= word << bitShift;
 8402039                    if (i + idxShift + 1 < res.Length)
 6092040                    {
 6092041                        res[i + idxShift + 1] = word >> carryShift;
 6092042                    }
 8402043                }
 2372044            }
 2045
 2462046            return new BigInteger((short)sign, res);
 2552047        }
 2048
 2049        /// <summary>
 2050        /// Shifts a <see cref="BigInteger"/> value a specified number of bits to the right.
 2051        /// </summary>
 2052        /// <param name="value">The value whose bits are to be shifted.</param>
 2053        /// <param name="shift">The number of bits to shift value to the right.</param>
 2054        /// <returns>
 2055        /// A value that has been shifted to the right by the specified number of bits.
 2056        /// </returns>
 2057#pragma warning disable CA2225 // Operator overloads have named alternates
 2058        public static BigInteger operator >>(BigInteger value, int shift)
 2059#pragma warning restore CA2225 // Operator overloads have named alternates
 14814182060        {
 14814182061            if (shift == 0 || value._sign == 0)
 32062            {
 32063                return value;
 2064            }
 2065
 14814152066            if (shift < 0)
 32067            {
 32068                return value << -shift;
 2069            }
 2070
 14814122071            var data = value._data;
 14814122072            int sign = value._sign;
 2073
 14814122074            var topMostIdx = BitScanBackward(data[data.Length - 1]);
 14814122075            var idxShift = shift >> 5;
 14814122076            var bitShift = shift & 0x1F;
 2077
 14814122078            var extraWords = idxShift;
 14814122079            if (bitShift > topMostIdx)
 444582080            {
 444582081                ++extraWords;
 444582082            }
 2083
 14814122084            var size = data.Length - extraWords;
 2085
 14814122086            if (size <= 0)
 212087            {
 212088                return sign == 1 ? Zero : MinusOne;
 2089            }
 2090
 14813912091            var res = new uint[size];
 14813912092            var carryShift = 32 - bitShift;
 2093
 14813912094            if (carryShift == 32)
 92095            {
 962096                for (var i = data.Length - 1; i >= idxShift; --i)
 392097                {
 392098                    var word = data[i];
 2099
 392100                    if (i - idxShift < res.Length)
 392101                    {
 392102                        res[i - idxShift] |= word >> bitShift;
 392103                    }
 392104                }
 92105            }
 2106            else
 14813822107            {
 510435102108                for (var i = data.Length - 1; i >= idxShift; --i)
 240403732109                {
 240403732110                    var word = data[i];
 2111
 240403732112                    if (i - idxShift < res.Length)
 239959332113                    {
 239959332114                        res[i - idxShift] |= word >> bitShift;
 239959332115                    }
 2116
 240403732117                    if (i - idxShift - 1 >= 0)
 225589912118                    {
 225589912119                        res[i - idxShift - 1] = word << carryShift;
 225589912120                    }
 240403732121                }
 14813822122            }
 2123
 2124            // Round down instead of toward zero
 14813912125            if (sign == -1)
 92126            {
 182127                for (var i = 0; i < idxShift; i++)
 32128                {
 32129                    if (data[i] != 0u)
 32130                    {
 32131                        var tmp = new BigInteger((short)sign, res);
 32132                        --tmp;
 32133                        return tmp;
 2134                    }
 02135                }
 2136
 62137                if (bitShift > 0 && (data[idxShift] << carryShift) != 0u)
 62138                {
 62139                    var tmp = new BigInteger((short)sign, res);
 62140                    --tmp;
 62141                    return tmp;
 2142                }
 02143            }
 2144
 14813822145            return new BigInteger((short)sign, res);
 14814182146        }
 2147
 2148        /// <summary>
 2149        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is less than another
 2150        /// <see cref="BigInteger"/> value.
 2151        /// </summary>
 2152        /// <param name="left">The first value to compare.</param>
 2153        /// <param name="right">The second value to compare.</param>
 2154        /// <returns>
 2155        /// <see langword="true"/> if <paramref name="left"/> is less than <paramref name="right"/>; otherwise, <see lan
 2156        /// </returns>
 2157        public static bool operator <(BigInteger left, BigInteger right)
 19602158        {
 19602159            return Compare(left, right) < 0;
 19602160        }
 2161
 2162        /// <summary>
 2163        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is less than a 64-bit signed integer
 2164        /// </summary>
 2165        /// <param name="left">The first value to compare.</param>
 2166        /// <param name="right">The second value to compare.</param>
 2167        /// <returns>
 2168        /// <see langword="true"/> if left is <paramref name="left"/> than <paramref name="right"/>; otherwise, <see lan
 2169        /// </returns>
 2170        public static bool operator <(BigInteger left, long right)
 24812171        {
 24812172            return left.CompareTo(right) < 0;
 24812173        }
 2174
 2175        /// <summary>
 2176        /// Returns a value that indicates whether a 64-bit signed integer is less than a <see cref="BigInteger"/> value
 2177        /// </summary>
 2178        /// <param name="left">The first value to compare.</param>
 2179        /// <param name="right">The second value to compare.</param>
 2180        /// <returns>
 2181        /// <see langword="true"/> if <paramref name="left"/> is less than <paramref name="right"/>;
 2182        /// otherwise, <see langword="false"/>.
 2183        /// </returns>
 2184        public static bool operator <(long left, BigInteger right)
 3632185        {
 3632186            return right.CompareTo(left) > 0;
 3632187        }
 2188
 2189        /// <summary>
 2190        /// Returns a value that indicates whether a 64-bit signed integer is less than a <see cref="BigInteger"/> value
 2191        /// </summary>
 2192        /// <param name="left">The first value to compare.</param>
 2193        /// <param name="right">The second value to compare.</param>
 2194        /// <returns>
 2195        /// <see langword="true"/> if <paramref name="left"/> is less than <paramref name="right"/>; otherwise, <see lan
 2196        /// </returns>
 2197        [CLSCompliant(false)]
 2198        public static bool operator <(BigInteger left, ulong right)
 1922199        {
 1922200            return left.CompareTo(right) < 0;
 1922201        }
 2202
 2203        /// <summary>
 2204        /// Returns a value that indicates whether a 64-bit unsigned integer is less than a <see cref="BigInteger"/> val
 2205        /// </summary>
 2206        /// <param name="left">The first value to compare.</param>
 2207        /// <param name="right">The second value to compare.</param>
 2208        /// <returns>
 2209        /// <see langword="true"/> if <paramref name="left"/> is less than <paramref name="right"/>; otherwise, <see lan
 2210        /// </returns>
 2211        [CLSCompliant(false)]
 2212        public static bool operator <(ulong left, BigInteger right)
 1922213        {
 1922214            return right.CompareTo(left) > 0;
 1922215        }
 2216
 2217        /// <summary>
 2218        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is less than or equal
 2219        /// to another <see cref="BigInteger"/> value.
 2220        /// </summary>
 2221        /// <param name="left">The first value to compare.</param>
 2222        /// <param name="right">The second value to compare.</param>
 2223        /// <returns>
 2224        /// <see langword="true"/> if <paramref name="left"/> is less than or equal to <paramref name="right"/>;
 2225        /// otherwise, <see langword="false"/>.
 2226        /// </returns>
 2227        public static bool operator <=(BigInteger left, BigInteger right)
 26582228        {
 26582229            return Compare(left, right) <= 0;
 26582230        }
 2231
 2232        /// <summary>
 2233        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is less than or equal
 2234        /// to a 64-bit signed integer.
 2235        /// </summary>
 2236        /// <param name="left">The first value to compare.</param>
 2237        /// <param name="right">The second value to compare.</param>
 2238        /// <returns>
 2239        /// <see langword="true"/> if <paramref name="left"/> is less than or equal to <paramref name="right"/>;
 2240        /// otherwise, <see langword="false"/>.
 2241        /// </returns>
 2242        public static bool operator <=(BigInteger left, long right)
 3712243        {
 3712244            return left.CompareTo(right) <= 0;
 3712245        }
 2246
 2247        /// <summary>
 2248        /// Returns a value that indicates whether a 64-bit signed integer is less than or equal to a <see cref="BigInte
 2249        /// </summary>
 2250        /// <param name="left">The first value to compare.</param>
 2251        /// <param name="right">The second value to compare.</param>
 2252        /// <returns>
 2253        /// <see langword="true"/> if <paramref name="left"/> is less than or equal to <paramref name="right"/>;
 2254        /// otherwise, <see langword="false"/>.
 2255        /// </returns>
 2256        public static bool operator <=(long left, BigInteger right)
 3632257        {
 3632258            return right.CompareTo(left) >= 0;
 3632259        }
 2260
 2261        /// <summary>
 2262        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is less than or equal to
 2263        /// a 64-bit unsigned integer.
 2264        /// </summary>
 2265        /// <param name="left">The first value to compare.</param>
 2266        /// <param name="right">The second value to compare.</param>
 2267        /// <returns>
 2268        /// <see langword="true"/> if <paramref name="left"/> is less than or equal to <paramref name="right"/>;
 2269        /// otherwise, <see langword="false"/>.
 2270        /// </returns>
 2271        [CLSCompliant(false)]
 2272        public static bool operator <=(BigInteger left, ulong right)
 1922273        {
 1922274            return left.CompareTo(right) <= 0;
 1922275        }
 2276
 2277        /// <summary>
 2278        /// Returns a value that indicates whether a 64-bit unsigned integer is less than or equal to a
 2279        /// <see cref="BigInteger"/> value.
 2280        /// </summary>
 2281        /// <param name="left">The first value to compare.</param>
 2282        /// <param name="right">The second value to compare.</param>
 2283        /// <returns>
 2284        /// <see langword="true"/> if <paramref name="left"/> is less than or equal to <paramref name="right"/>;
 2285        /// otherwise, <see langword="false"/>.
 2286        /// </returns>
 2287        [CLSCompliant(false)]
 2288        public static bool operator <=(ulong left, BigInteger right)
 1922289        {
 1922290            return right.CompareTo(left) >= 0;
 1922291        }
 2292
 2293        /// <summary>
 2294        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is greater than another
 2295        /// <see cref="BigInteger"/> value.
 2296        /// </summary>
 2297        /// <param name="left">The first value to compare.</param>
 2298        /// <param name="right">The second value to compare.</param>
 2299        /// <returns>
 2300        /// <see langword="true"/> if <paramref name="left"/> is greater than <paramref name="right"/>;
 2301        /// otherwise, <see langword="false"/>.
 2302        /// </returns>
 2303        public static bool operator >(BigInteger left, BigInteger right)
 12842304        {
 12842305            return Compare(left, right) > 0;
 12842306        }
 2307
 2308        /// <summary>
 2309        /// Returns a value that indicates whether a <see cref="BigInteger"/> is greater than a 64-bit signed integer va
 2310        /// </summary>
 2311        /// <param name="left">The first value to compare.</param>
 2312        /// <param name="right">The second value to compare.</param>
 2313        /// <returns>
 2314        /// <see langword="true"/> if <paramref name="left"/> is greater than <paramref name="right"/>;
 2315        /// otherwise, <see langword="false"/>.
 2316        /// </returns>
 2317        public static bool operator >(BigInteger left, long right)
 3632318        {
 3632319            return left.CompareTo(right) > 0;
 3632320        }
 2321
 2322        /// <summary>
 2323        /// Returns a value that indicates whether a 64-bit signed integer is greater than a <see cref="BigInteger"/> va
 2324        /// </summary>
 2325        /// <param name="left">The first value to compare.</param>
 2326        /// <param name="right">The second value to compare.</param>
 2327        /// <returns>
 2328        /// <see langword="true"/> if <paramref name="left"/> is greater than <paramref name="right"/>;
 2329        /// otherwise, <see langword="false"/>.
 2330        /// </returns>
 2331        public static bool operator >(long left, BigInteger right)
 3632332        {
 3632333            return right.CompareTo(left) < 0;
 3632334        }
 2335
 2336        /// <summary>
 2337        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is greater than a 64-bit unsigned in
 2338        /// </summary>
 2339        /// <param name="left">The first value to compare.</param>
 2340        /// <param name="right">The second value to compare.</param>
 2341        /// <returns>
 2342        /// <see langword="true"/> if <paramref name="left"/> is greater than <paramref name="right"/>;
 2343        /// otherwise, <see langword="false"/>.
 2344        /// </returns>
 2345        [CLSCompliant(false)]
 2346        public static bool operator >(BigInteger left, ulong right)
 1922347        {
 1922348            return left.CompareTo(right) > 0;
 1922349        }
 2350
 2351        /// <summary>
 2352        /// Returns a value that indicates whether a 64-bit unsigned integer is greater than a <see cref="BigInteger"/> 
 2353        /// </summary>
 2354        /// <param name="left">The first value to compare.</param>
 2355        /// <param name="right">The second value to compare.</param>
 2356        /// <returns>
 2357        /// <see langword="true"/> if <paramref name="left"/> is greater than <paramref name="right"/>;
 2358        /// otherwise, <see langword="false"/>.
 2359        /// </returns>
 2360        [CLSCompliant(false)]
 2361        public static bool operator >(ulong left, BigInteger right)
 1922362        {
 1922363            return right.CompareTo(left) < 0;
 1922364        }
 2365
 2366        /// <summary>
 2367        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is greater than or equal
 2368        /// to another <see cref="BigInteger"/> value.
 2369        /// </summary>
 2370        /// <param name="left">The first value to compare.</param>
 2371        /// <param name="right">The second value to compare.</param>
 2372        /// <returns>
 2373        /// <see langword="true"/> if <paramref name="left"/> is greater than <paramref name="right"/>;
 2374        /// otherwise, <see langword="false"/>.
 2375        /// </returns>
 2376        public static bool operator >=(BigInteger left, BigInteger right)
 19692377        {
 19692378            return Compare(left, right) >= 0;
 19692379        }
 2380
 2381        /// <summary>
 2382        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is greater than or equal
 2383        /// to a 64-bit signed integer value.
 2384        /// </summary>
 2385        /// <param name="left">The first value to compare.</param>
 2386        /// <param name="right">The second value to compare.</param>
 2387        /// <returns>
 2388        /// <see langword="true"/> if <paramref name="left"/> is greater than <paramref name="right"/>;
 2389        /// otherwise, <see langword="false"/>.
 2390        /// </returns>
 2391        public static bool operator >=(BigInteger left, long right)
 3632392        {
 3632393            return left.CompareTo(right) >= 0;
 3632394        }
 2395
 2396        /// <summary>
 2397        /// Returns a value that indicates whether a 64-bit signed integer is greater than or equal to a
 2398        /// <see cref="BigInteger"/> value.
 2399        /// </summary>
 2400        /// <param name="left">The first value to compare.</param>
 2401        /// <param name="right">The second value to compare.</param>
 2402        /// <returns>
 2403        /// <see langword="true"/> if <paramref name="left"/> is greater than <paramref name="right"/>;
 2404        /// otherwise, <see langword="false"/>.
 2405        /// </returns>
 2406        public static bool operator >=(long left, BigInteger right)
 3632407        {
 3632408            return right.CompareTo(left) <= 0;
 3632409        }
 2410
 2411        /// <summary>
 2412        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is greater than or equal to a
 2413        /// 64-bit unsigned integer value.
 2414        /// </summary>
 2415        /// <param name="left">The first value to compare.</param>
 2416        /// <param name="right">The second value to compare.</param>
 2417        /// <returns>
 2418        /// <see langword="true"/> if <paramref name="left"/> is greater than <paramref name="right"/>;
 2419        /// otherwise, <see langword="false"/>.
 2420        /// </returns>
 2421        [CLSCompliant(false)]
 2422        public static bool operator >=(BigInteger left, ulong right)
 1922423        {
 1922424            return left.CompareTo(right) >= 0;
 1922425        }
 2426
 2427        /// <summary>
 2428        /// Returns a value that indicates whether a 64-bit unsigned integer is greater than or equal to a
 2429        /// <see cref="BigInteger"/> value.
 2430        /// </summary>
 2431        /// <param name="left">The first value to compare.</param>
 2432        /// <param name="right">The second value to compare.</param>
 2433        /// <returns>
 2434        /// <see langword="true"/> if <paramref name="left"/> is greater than <paramref name="right"/>;
 2435        /// otherwise, <see langword="false"/>.
 2436        /// </returns>
 2437        [CLSCompliant(false)]
 2438        public static bool operator >=(ulong left, BigInteger right)
 1922439        {
 1922440            return right.CompareTo(left) <= 0;
 1922441        }
 2442
 2443        /// <summary>
 2444        /// Returns a value that indicates whether the values of two <see cref="BigInteger"/> objects are equal.
 2445        /// </summary>
 2446        /// <param name="left">The first value to compare.</param>
 2447        /// <param name="right">The second value to compare.</param>
 2448        /// <returns>
 2449        /// <see langword="true"/> if the <paramref name="left"/> and <paramref name="right"/> parameters have the same 
 2450        /// otherwise, <see langword="false"/>.
 2451        /// </returns>
 2452        public static bool operator ==(BigInteger left, BigInteger right)
 12632453        {
 12632454            return Compare(left, right) == 0;
 12632455        }
 2456
 2457        /// <summary>
 2458        /// Returns a value that indicates whether a <see cref="BigInteger"/> value and a signed long integer value are 
 2459        /// </summary>
 2460        /// <param name="left">The first value to compare.</param>
 2461        /// <param name="right">The second value to compare.</param>
 2462        /// <returns>
 2463        /// <see langword="true"/> if the <paramref name="left"/> and <paramref name="right"/> parameters have the same 
 2464        /// otherwise, <see langword="false"/>.
 2465        /// </returns>
 2466        public static bool operator ==(BigInteger left, long right)
 3632467        {
 3632468            return left.CompareTo(right) == 0;
 3632469        }
 2470
 2471        /// <summary>
 2472        /// Returns a value that indicates whether a signed long integer value and a <see cref="BigInteger"/> value are 
 2473        /// </summary>
 2474        /// <param name="left">The first value to compare.</param>
 2475        /// <param name="right">The second value to compare.</param>
 2476        /// <returns>
 2477        /// <see langword="true"/> if the <paramref name="left"/> and <paramref name="right"/> parameters have the same 
 2478        /// otherwise, <see langword="false"/>.
 2479        /// </returns>
 2480        public static bool operator ==(long left, BigInteger right)
 3632481        {
 3632482            return right.CompareTo(left) == 0;
 3632483        }
 2484
 2485        /// <summary>
 2486        /// Returns a value that indicates whether a <see cref="BigInteger"/> value and an unsigned long integer value a
 2487        /// </summary>
 2488        /// <param name="left">The first value to compare.</param>
 2489        /// <param name="right">The second value to compare.</param>
 2490        /// <returns>
 2491        /// <see langword="true"/> if the <paramref name="left"/> and <paramref name="right"/> parameters have the same 
 2492        /// otherwise, <see langword="false"/>.
 2493        /// </returns>
 2494        [CLSCompliant(false)]
 2495        public static bool operator ==(BigInteger left, ulong right)
 1922496        {
 1922497            return left.CompareTo(right) == 0;
 1922498        }
 2499
 2500        /// <summary>
 2501        /// Returns a value that indicates whether an unsigned long integer value and a <see cref="BigInteger"/> value a
 2502        /// </summary>
 2503        /// <param name="left">The first value to compare.</param>
 2504        /// <param name="right">The second value to compare.</param>
 2505        /// <returns>
 2506        /// <see langword="true"/> if the <paramref name="left"/> and <paramref name="right"/> parameters have the same 
 2507        /// otherwise, <see langword="false"/>.
 2508        /// </returns>
 2509        [CLSCompliant(false)]
 2510        public static bool operator ==(ulong left, BigInteger right)
 1922511        {
 1922512            return right.CompareTo(left) == 0;
 1922513        }
 2514
 2515        /// <summary>
 2516        /// Returns a value that indicates whether two <see cref="BigInteger"/> objects have different values.
 2517        /// </summary>
 2518        /// <param name="left">The first value to compare.</param>
 2519        /// <param name="right">The second value to compare.</param>
 2520        /// <returns>
 2521        /// <see langword="true"/> if <paramref name="left"/> and <paramref name="right"/> are not equal;
 2522        /// otherwise, <see langword="false"/>.
 2523        /// </returns>
 2524        public static bool operator !=(BigInteger left, BigInteger right)
 12572525        {
 12572526            return Compare(left, right) != 0;
 12572527        }
 2528
 2529        /// <summary>
 2530        /// Returns a value that indicates whether a <see cref="BigInteger"/> value and a 64-bit signed integer are not 
 2531        /// </summary>
 2532        /// <param name="left">The first value to compare.</param>
 2533        /// <param name="right">The second value to compare.</param>
 2534        /// <returns>
 2535        /// <see langword="true"/> if <paramref name="left"/> and <paramref name="right"/> are not equal;
 2536        /// otherwise, <see langword="false"/>.
 2537        /// </returns>
 2538        public static bool operator !=(BigInteger left, long right)
 190442539        {
 190442540            return left.CompareTo(right) != 0;
 190442541        }
 2542
 2543        /// <summary>
 2544        /// Returns a value that indicates whether a 64-bit signed integer and a <see cref="BigInteger"/> value are not 
 2545        /// </summary>
 2546        /// <param name="left">The first value to compare.</param>
 2547        /// <param name="right">The second value to compare.</param>
 2548        /// <returns>
 2549        /// <see langword="true"/> if <paramref name="left"/> and <paramref name="right"/> are not equal;
 2550        /// otherwise, <see langword="false"/>.
 2551        /// </returns>
 2552        public static bool operator !=(long left, BigInteger right)
 3632553        {
 3632554            return right.CompareTo(left) != 0;
 3632555        }
 2556
 2557        /// <summary>
 2558        /// Returns a value that indicates whether a <see cref="BigInteger"/> value and a 64-bit unsigned integer are no
 2559        /// </summary>
 2560        /// <param name="left">The first value to compare.</param>
 2561        /// <param name="right">The second value to compare.</param>
 2562        /// <returns>
 2563        /// <see langword="true"/> if <paramref name="left"/> and <paramref name="right"/> are not equal;
 2564        /// otherwise, <see langword="false"/>.
 2565        /// </returns>
 2566        [CLSCompliant(false)]
 2567        public static bool operator !=(BigInteger left, ulong right)
 1922568        {
 1922569            return left.CompareTo(right) != 0;
 1922570        }
 2571
 2572        /// <summary>
 2573        /// Returns a value that indicates whether a 64-bit unsigned integer and a <see cref="BigInteger"/> value are no
 2574        /// </summary>
 2575        /// <param name="left">The first value to compare.</param>
 2576        /// <param name="right">The second value to compare.</param>
 2577        /// <returns>
 2578        /// <see langword="true"/> if <paramref name="left"/> and <paramref name="right"/> are not equal;
 2579        /// otherwise, <see langword="false"/>.
 2580        /// </returns>
 2581        [CLSCompliant(false)]
 2582        public static bool operator !=(ulong left, BigInteger right)
 1922583        {
 1922584            return right.CompareTo(left) != 0;
 1922585        }
 2586
 2587        /// <summary>
 2588        /// Returns a value that indicates whether the current instance and a specified object have the same value.
 2589        /// </summary>
 2590        /// <param name="obj">The object to compare.</param>
 2591        /// <returns>
 2592        /// <see langword="true"/> if the <paramref name="obj"/> parameter is a <see cref="BigInteger"/> object or a typ
 2593        /// of implicit conversion to a <see cref="BigInteger"/> value, and its value is equal to the value of the
 2594        /// current <see cref="BigInteger"/> object; otherwise, <see langword="false"/>.
 2595        /// </returns>
 2596        public override readonly bool Equals(object obj)
 02597        {
 02598            if (obj is not BigInteger other)
 02599            {
 02600                return false;
 2601            }
 2602
 02603            return Equals(other);
 02604        }
 2605
 2606        /// <summary>
 2607        /// Returns a value that indicates whether the current instance and a specified <see cref="BigInteger"/> object
 2608        /// have the same value.
 2609        /// </summary>
 2610        /// <param name="other">The object to compare.</param>
 2611        /// <returns>
 2612        /// <see langword="true"/> if this <see cref="BigInteger"/> object and <paramref name="other"/> have the same va
 2613        /// otherwise, <see langword="false"/>.
 2614        /// </returns>
 2615        public readonly bool Equals(BigInteger other)
 1652616        {
 1652617            if (_sign != other._sign)
 32618            {
 32619                return false;
 2620            }
 2621
 1622622            var alen = _data != null ? _data.Length : 0;
 1622623            var blen = other._data != null ? other._data.Length : 0;
 2624
 1622625            if (alen != blen)
 02626            {
 02627                return false;
 2628            }
 2629
 8282630            for (var i = 0; i < alen; ++i)
 2522631            {
 2522632                if (_data[i] != other._data[i])
 02633                {
 02634                    return false;
 2635                }
 2522636            }
 2637
 1622638            return true;
 1652639        }
 2640
 2641        /// <summary>
 2642        /// Returns a value that indicates whether the current instance and a signed 64-bit integer have the same value.
 2643        /// </summary>
 2644        /// <param name="other">The signed 64-bit integer value to compare.</param>
 2645        /// <returns>
 2646        /// <see langword="true"/> if the signed 64-bit integer and the current instance have the same value; otherwise,
 2647        /// </returns>
 2648        public readonly bool Equals(long other)
 02649        {
 02650            return CompareTo(other) == 0;
 02651        }
 2652
 2653        /// <summary>
 2654        /// Returns a value that indicates whether the current instance and an unsigned 64-bit integer have the same val
 2655        /// </summary>
 2656        /// <param name="other">The unsigned 64-bit integer to compare.</param>
 2657        /// <returns>
 2658        /// <see langword="true"/> if the current instance and the unsigned 64-bit integer have the same value; otherwis
 2659        /// </returns>
 2660        [CLSCompliant(false)]
 2661        public readonly bool Equals(ulong other)
 02662        {
 02663            return CompareTo(other) == 0;
 02664        }
 2665
 2666        /// <summary>
 2667        /// Converts the numeric value of the current <see cref="BigInteger"/> object to its equivalent string represent
 2668        /// </summary>
 2669        /// <returns>
 2670        /// The string representation of the current <see cref="BigInteger"/> value.
 2671        /// </returns>
 2672        public override readonly string ToString()
 4472673        {
 4472674            return ToString(10, provider: null);
 4472675        }
 2676
 2677        /// <summary>
 2678        /// Converts the numeric value of the current <see cref="BigInteger"/> object to its equivalent string represent
 2679        /// by using the specified format.
 2680        /// </summary>
 2681        /// <param name="format">A standard or custom numeric format string.</param>
 2682        /// <returns>
 2683        /// The string representation of the current <see cref="BigInteger"/> value in the format specified by the
 2684        /// <paramref name="format"/> parameter.
 2685        /// </returns>
 2686        /// <exception cref="FormatException"><paramref name="format"/> is not a valid format string.</exception>
 2687        public readonly string ToString(string format)
 362688        {
 362689            return ToString(format, formatProvider: null);
 362690        }
 2691
 2692        /// <summary>
 2693        /// Converts the numeric value of the current <see cref="BigInteger"/> object to its equivalent string represent
 2694        /// by using the specified culture-specific formatting information.
 2695        /// </summary>
 2696        /// <param name="provider">An object that supplies culture-specific formatting information.</param>
 2697        /// <returns>
 2698        /// The string representation of the current <see cref="BigInteger"/> value in the format specified by the
 2699        /// <paramref name="provider"/> parameter.
 2700        /// </returns>
 2701        public readonly string ToString(IFormatProvider provider)
 122702        {
 122703            return ToString(format: null, provider);
 122704        }
 2705
 2706        /// <summary>
 2707        /// Converts the numeric value of the current <see cref="BigInteger"/> object to its equivalent string represent
 2708        /// by using the specified format and culture-specific format information.
 2709        /// </summary>
 2710        /// <param name="format">A standard or custom numeric format string.</param>
 2711        /// <param name="formatProvider">An object that supplies culture-specific formatting information.</param>
 2712        /// <returns>
 2713        /// The string representation of the current <see cref="BigInteger"/> value as specified by the <paramref name="
 2714        /// and <paramref name="formatProvider"/> parameters.
 2715        /// </returns>
 2716        public readonly string ToString(string format, IFormatProvider formatProvider)
 752717        {
 752718            if (string.IsNullOrEmpty(format))
 152719            {
 152720                return ToString(10, formatProvider);
 2721            }
 2722
 602723            switch (format[0])
 2724            {
 2725                case 'd':
 2726                case 'D':
 2727                case 'g':
 2728                case 'G':
 2729                case 'r':
 2730                case 'R':
 332731                    return ToStringWithPadding(format, 10, formatProvider);
 2732                case 'x':
 2733                case 'X':
 272734                    return ToStringWithPadding(format, 16, provider: null);
 2735                default:
 02736                    throw new FormatException(string.Format("format '{0}' not implemented", format));
 2737            }
 752738        }
 2739
 2740        private readonly string ToStringWithPadding(string format, uint radix, IFormatProvider provider)
 602741        {
 602742            if (format.Length > 1)
 122743            {
 122744                var precision = Convert.ToInt32(format.Substring(1), CultureInfo.InvariantCulture.NumberFormat);
 122745                var baseStr = ToString(radix, provider);
 122746                if (baseStr.Length < precision)
 92747                {
 92748                    var additional = new string('0', precision - baseStr.Length);
 92749                    if (baseStr[0] != '-')
 92750                    {
 92751                        return additional + baseStr;
 2752                    }
 2753
 2754#if NET
 02755                    return string.Concat("-", additional, baseStr.AsSpan(1));
 2756#else
 02757                    return "-" + additional + baseStr.Substring(1);
 2758#endif // NET
 2759                }
 2760
 32761                return baseStr;
 2762            }
 2763
 482764            return ToString(radix, provider);
 602765        }
 2766
 2767        private static uint[] MakeTwoComplement(uint[] v)
 62768        {
 62769            var res = new uint[v.Length];
 2770
 62771            ulong carry = 1;
 242772            for (var i = 0; i < v.Length; ++i)
 62773            {
 62774                var word = v[i];
 62775                carry = (ulong) ~word + carry;
 62776                word = (uint) carry;
 62777                carry = (uint) (carry >> 32);
 62778                res[i] = word;
 62779            }
 2780
 62781            var last = res[res.Length - 1];
 62782            var idx = FirstNonFfByte(last);
 62783            uint mask = 0xFF;
 122784            for (var i = 1; i < idx; ++i)
 02785            {
 02786                mask = (mask << 8) | 0xFF;
 02787            }
 2788
 62789            res[res.Length - 1] = last & mask;
 62790            return res;
 62791        }
 2792
 2793        private readonly string ToString(uint radix, IFormatProvider provider)
 5222794        {
 2795            const string characterSet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 2796
 5222797            if (characterSet.Length < radix)
 02798            {
 02799                throw new ArgumentException("charSet length less than radix", nameof(radix));
 2800            }
 2801
 5222802            if (radix == 1)
 02803            {
 02804                throw new ArgumentException("There is no such thing as radix one notation", nameof(radix));
 2805            }
 2806
 5222807            if (_sign == 0)
 92808            {
 92809                return "0";
 2810            }
 2811
 5132812            if (_data.Length == 1 && _data[0] == 1)
 32813            {
 32814                return _sign == 1 ? "1" : "-1";
 2815            }
 2816
 5102817            var digits = new List<char>(1 + ((_data.Length * 3) / 10));
 2818
 2819            BigInteger a;
 5102820            if (_sign == 1)
 4772821            {
 4772822                a = this;
 4772823            }
 2824            else
 332825            {
 332826                var dt = _data;
 332827                if (radix > 10)
 62828                {
 62829                    dt = MakeTwoComplement(dt);
 62830                }
 2831
 332832                a = new BigInteger(1, dt);
 332833            }
 2834
 186812835            while (a != 0)
 181712836            {
 181712837                a = DivRem(a, radix, out var rem);
 181712838                digits.Add(characterSet[(int) rem]);
 181712839            }
 2840
 5102841            if (_sign == -1 && radix == 10)
 272842            {
 272843                NumberFormatInfo info = null;
 272844                if (provider != null)
 212845                {
 212846                    info = provider.GetFormat(typeof(NumberFormatInfo)) as NumberFormatInfo;
 212847                }
 2848
 272849                if (info != null)
 212850                {
 212851                    var str = info.NegativeSign;
 1082852                    for (var i = str.Length - 1; i >= 0; --i)
 332853                    {
 332854                        digits.Add(str[i]);
 332855                    }
 212856                }
 2857                else
 62858                {
 62859                    digits.Add('-');
 62860                }
 272861            }
 2862
 5102863            var last = digits[digits.Count - 1];
 5102864            if (_sign == 1 && radix > 10 && (last < '0' || last > '9'))
 122865            {
 122866                digits.Add('0');
 122867            }
 2868
 5102869            digits.Reverse();
 2870
 5102871            return new string(digits.ToArray());
 5222872        }
 2873
 2874        /// <summary>
 2875        /// Converts the string representation of a number to its <see cref="BigInteger"/> equivalent.
 2876        /// </summary>
 2877        /// <param name="value">A string that contains the number to convert.</param>
 2878        /// <returns>
 2879        /// A value that is equivalent to the number specified in the <paramref name="value"/> parameter.
 2880        /// </returns>
 2881        /// <exception cref="ArgumentNullException"><paramref name="value"/> is <see langword="null"/>.</exception>
 2882        /// <exception cref="FormatException"><paramref name="value"/> is not in the correct format.</exception>
 2883        public static BigInteger Parse(string value)
 482884        {
 482885            if (!Parse(value, tryParse: false, out var result, out var ex))
 182886            {
 182887                throw ex;
 2888            }
 2889
 302890            return result;
 302891        }
 2892
 2893        /// <summary>
 2894        /// Converts the string representation of a number in a specified style to its <see cref="BigInteger"/> equivale
 2895        /// </summary>
 2896        /// <param name="value">A string that contains a number to convert.</param>
 2897        /// <param name="style">A bitwise combination of the enumeration values that specify the permitted format of <pa
 2898        /// <returns>
 2899        /// A value that is equivalent to the number specified in the <paramref name="value"/> parameter.
 2900        /// </returns>
 2901        /// <exception cref="ArgumentException">
 2902        /// <para><paramref name="style"/> is not a <see cref="NumberStyles"/> value.</para>
 2903        /// <para>-or-</para>
 2904        /// <para><paramref name="style"/> includes the <see cref="NumberStyles.AllowHexSpecifier"/> or <see cref="Numbe
 2905        /// </exception>
 2906        /// <exception cref="ArgumentNullException"><paramref name="value"/> is <see langword="null"/>.</exception>
 2907        /// <exception cref="FormatException"><paramref name="value"/> does not comply with the input pattern specified 
 2908        public static BigInteger Parse(string value, NumberStyles style)
 392909        {
 392910            return Parse(value, style, provider: null);
 362911        }
 2912
 2913        /// <summary>
 2914        /// Converts the string representation of a number in a specified style to its <see cref="BigInteger"/> equivale
 2915        /// </summary>
 2916        /// <param name="value">A string that contains a number to convert.</param>
 2917        /// <param name="provider">An object that provides culture-specific formatting information about <paramref name=
 2918        /// <returns>
 2919        /// A value that is equivalent to the number specified in the <paramref name="value"/> parameter.
 2920        /// </returns>
 2921        /// <exception cref="ArgumentNullException"><paramref name="value"/> is <see langword="null"/>.</exception>
 2922        /// <exception cref="FormatException"><paramref name="value"/> is not in the correct format.</exception>
 2923        public static BigInteger Parse(string value, IFormatProvider provider)
 02924        {
 02925            return Parse(value, NumberStyles.Integer, provider);
 02926        }
 2927
 2928        /// <summary>
 2929        /// Converts the string representation of a number in a specified style and culture-specific format to its <see 
 2930        /// </summary>
 2931        /// <param name="value">A string that contains a number to convert.</param>
 2932        /// <param name="style">A bitwise combination of the enumeration values that specify the permitted format of <pa
 2933        /// <param name="provider">An object that provides culture-specific formatting information about <paramref name=
 2934        /// <returns>
 2935        /// A value that is equivalent to the number specified in the <paramref name="value"/> parameter.
 2936        /// </returns>
 2937        /// <exception cref="ArgumentException">
 2938        /// <para><paramref name="style"/> is not a <see cref="NumberStyles"/> value.</para>
 2939        /// <para>-or-</para>
 2940        /// <para><paramref name="style"/> includes the <see cref="NumberStyles.AllowHexSpecifier"/> or <see cref="Numbe
 2941        /// </exception>
 2942        /// <exception cref="ArgumentNullException"><paramref name="value"/> is <see langword="null"/>.</exception>
 2943        /// <exception cref="FormatException"><paramref name="value"/> does not comply with the input pattern specified 
 2944        public static BigInteger Parse(string value, NumberStyles style, IFormatProvider provider)
 452945        {
 452946            if (!Parse(value, style, provider, tryParse: false, out var res, out var exc))
 32947            {
 32948                throw exc;
 2949            }
 2950
 422951            return res;
 422952        }
 2953
 2954        /// <summary>
 2955        /// Tries to convert the string representation of a number to its <see cref="BigInteger"/> equivalent, and
 2956        /// returns a value that indicates whether the conversion succeeded.
 2957        /// </summary>
 2958        /// <param name="value">The string representation of a number.</param>
 2959        /// <param name="result">When this method returns, contains the <see cref="BigInteger"/> equivalent to the numbe
 2960        /// <returns>
 2961        /// <see langword="true"/> if <paramref name="value"/> was converted successfully; otherwise, <see langword="fal
 2962        /// </returns>
 2963        /// <exception cref="ArgumentNullException"><paramref name="value"/> is <see langword="null"/>.</exception>
 2964        public static bool TryParse(string value, out BigInteger result)
 332965        {
 332966            return Parse(value, tryParse: true, out result, out _);
 332967        }
 2968
 2969        /// <summary>
 2970        /// Tries to convert the string representation of a number in a specified style and culture-specific format to i
 2971        /// <see cref="BigInteger"/> equivalent, and returns a value that indicates whether the conversion succeeded.
 2972        /// </summary>
 2973        /// <param name="value">The string representation of a number.</param>
 2974        /// <param name="style">A bitwise combination of enumeration values that indicates the style elements that can b
 2975        /// <param name="provider">An object that supplies culture-specific formatting information about <paramref name=
 2976        /// <param name="result">When this method returns, contains the <see cref="BigInteger"/> equivalent to the numbe
 2977        /// <returns>
 2978        /// <see langword="true"/> if <paramref name="value"/> was converted successfully; otherwise, <see langword="fal
 2979        /// </returns>
 2980        /// <exception cref="ArgumentException">
 2981        /// <para><paramref name="style"/> is not a <see cref="NumberStyles"/> value.</para>
 2982        /// <para>-or-</para>
 2983        /// <para><paramref name="style"/> includes the <see cref="NumberStyles.AllowHexSpecifier"/> or <see cref="Numbe
 2984        /// </exception>
 2985        public static bool TryParse(string value, NumberStyles style, IFormatProvider provider, out BigInteger result)
 632986        {
 632987            if (!Parse(value, style, provider, tryParse: true, out result, out _))
 332988            {
 332989                result = Zero;
 332990                return false;
 2991            }
 2992
 302993            return true;
 632994        }
 2995
 2996#pragma warning disable S4136 // Method overloads should be grouped together
 2997        private static bool Parse(string value, NumberStyles style, IFormatProvider fp, bool tryParse, out BigInteger re
 2998#pragma warning restore S4136 // Method overloads should be grouped together
 1082999        {
 1083000            result = Zero;
 1083001            exc = null;
 3002
 1083003            if (value is null)
 33004            {
 33005                if (!tryParse)
 03006                {
 03007                    exc = new ArgumentNullException(nameof(value));
 03008                }
 3009
 33010                return false;
 3011            }
 3012
 1053013            if (value.Length == 0)
 03014            {
 03015                if (!tryParse)
 03016                {
 03017                    exc = GetFormatException();
 03018                }
 3019
 03020                return false;
 3021            }
 3022
 1053023            NumberFormatInfo nfi = null;
 1053024            if (fp != null)
 303025            {
 303026                var typeNfi = typeof(NumberFormatInfo);
 303027                nfi = (NumberFormatInfo) fp.GetFormat(typeNfi);
 303028            }
 3029
 1053030            nfi ??= NumberFormatInfo.CurrentInfo;
 3031
 1053032            if (!CheckStyle(style, tryParse, ref exc))
 03033            {
 03034                return false;
 3035            }
 3036
 1053037            var allowCurrencySymbol = (style & NumberStyles.AllowCurrencySymbol) == NumberStyles.AllowCurrencySymbol;
 1053038            var allowHexSpecifier = (style & NumberStyles.AllowHexSpecifier) == NumberStyles.AllowHexSpecifier;
 1053039            var allowThousands = (style & NumberStyles.AllowThousands) == NumberStyles.AllowThousands;
 1053040            var allowDecimalPoint = (style & NumberStyles.AllowDecimalPoint) == NumberStyles.AllowDecimalPoint;
 1053041            var allowParentheses = (style & NumberStyles.AllowParentheses) == NumberStyles.AllowParentheses;
 1053042            var allowTrailingSign = (style & NumberStyles.AllowTrailingSign) == NumberStyles.AllowTrailingSign;
 1053043            var allowLeadingSign = (style & NumberStyles.AllowLeadingSign) == NumberStyles.AllowLeadingSign;
 1053044            var allowTrailingWhite = (style & NumberStyles.AllowTrailingWhite) == NumberStyles.AllowTrailingWhite;
 1053045            var allowLeadingWhite = (style & NumberStyles.AllowLeadingWhite) == NumberStyles.AllowLeadingWhite;
 1053046            var allowExponent = (style & NumberStyles.AllowExponent) == NumberStyles.AllowExponent;
 3047
 1053048            var pos = 0;
 3049
 1053050            if (allowLeadingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
 03051            {
 03052                return false;
 3053            }
 3054
 1053055            var foundOpenParentheses = false;
 1053056            var negative = false;
 1053057            var foundSign = false;
 1053058            var foundCurrency = false;
 3059
 3060            // Pre-number stuff
 1053061            if (allowParentheses && value[pos] == '(')
 63062            {
 63063                foundOpenParentheses = true;
 63064                foundSign = true;
 63065                negative = true; // MS always make the number negative when there parentheses, even when NumberFormatInf
 63066                pos++;
 3067
 63068                if (allowLeadingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
 03069                {
 03070                    return false;
 3071                }
 3072
 63073                if (value.Substring(pos, nfi.NegativeSign.Length) == nfi.NegativeSign)
 03074                {
 03075                    if (!tryParse)
 03076                    {
 03077                        exc = GetFormatException();
 03078                    }
 3079
 03080                    return false;
 3081                }
 3082
 63083                if (value.Substring(pos, nfi.PositiveSign.Length) == nfi.PositiveSign)
 03084                {
 03085                    if (!tryParse)
 03086                    {
 03087                        exc = GetFormatException();
 03088                    }
 3089
 03090                    return false;
 3091                }
 63092            }
 3093
 1053094            if (allowLeadingSign && !foundSign)
 183095            {
 3096                // Sign + Currency
 183097                FindSign(ref pos, value, nfi, ref foundSign, ref negative);
 183098                if (foundSign)
 63099                {
 63100                    if (allowLeadingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
 03101                    {
 03102                        return false;
 3103                    }
 3104
 63105                    if (allowCurrencySymbol)
 03106                    {
 03107                        FindCurrency(ref pos, value, nfi, ref foundCurrency);
 03108                        if (foundCurrency && allowLeadingWhite && !JumpOverWhitespace(ref pos, value, reportError: true,
 03109                        {
 03110                            return false;
 3111                        }
 03112                    }
 63113                }
 183114            }
 3115
 1053116            if (allowCurrencySymbol && !foundCurrency)
 123117            {
 3118                // Currency + sign
 123119                FindCurrency(ref pos, value, nfi, ref foundCurrency);
 123120                if (foundCurrency)
 33121                {
 33122                    if (allowLeadingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
 03123                    {
 03124                        return false;
 3125                    }
 3126
 33127                    if (foundCurrency)
 33128                    {
 33129                        if (!foundSign && allowLeadingSign)
 03130                        {
 03131                            FindSign(ref pos, value, nfi, ref foundSign, ref negative);
 03132                            if (foundSign && allowLeadingWhite && !JumpOverWhitespace(ref pos, value, reportError: true,
 03133                            {
 03134                                return false;
 3135                            }
 03136                        }
 33137                    }
 33138                }
 123139            }
 3140
 1053141            var number = Zero;
 1053142            var nDigits = 0;
 1053143            var decimalPointPos = -1;
 1053144            var firstHexDigit = true;
 3145
 3146            // Number stuff
 120243147            while (pos < value.Length)
 119793148            {
 119793149                if (!ValidDigit(value[pos], allowHexSpecifier))
 813150                {
 813151                    if (allowThousands &&
 813152                        (FindOther(ref pos, value, nfi.NumberGroupSeparator)
 813153                        || FindOther(ref pos, value, nfi.CurrencyGroupSeparator)))
 123154                    {
 123155                        continue;
 3156                    }
 3157
 693158                    if (allowDecimalPoint && decimalPointPos < 0 &&
 693159                        (FindOther(ref pos, value, nfi.NumberDecimalSeparator)
 693160                        || FindOther(ref pos, value, nfi.CurrencyDecimalSeparator)))
 93161                    {
 93162                        decimalPointPos = nDigits;
 93163                        continue;
 3164                    }
 3165
 603166                    break;
 3167                }
 3168
 118983169                nDigits++;
 3170
 118983171                if (allowHexSpecifier)
 23493172                {
 23493173                    var hexDigit = value[pos++];
 3174                    byte digitValue;
 23493175                    if (char.IsDigit(hexDigit))
 13833176                    {
 13833177                        digitValue = (byte) (hexDigit - '0');
 13833178                    }
 9663179                    else if (char.IsLower(hexDigit))
 03180                    {
 03181                        digitValue = (byte) (hexDigit - 'a' + 10);
 03182                    }
 3183                    else
 9663184                    {
 9663185                        digitValue = (byte) (hexDigit - 'A' + 10);
 9663186                    }
 3187
 23493188                    if (firstHexDigit && digitValue >= 8)
 93189                    {
 93190                        negative = true;
 93191                    }
 3192
 23493193                    number = (number * 16) + digitValue;
 23493194                    firstHexDigit = false;
 23493195                    continue;
 3196                }
 3197
 95493198                number = (number * 10) + (byte)(value[pos++] - '0');
 95493199            }
 3200
 3201            // Post number stuff
 1053202            if (nDigits == 0)
 243203            {
 243204                if (!tryParse)
 03205                {
 03206                    exc = GetFormatException();
 03207                }
 3208
 243209                return false;
 3210            }
 3211
 3212            // Signed hex value (Two's Complement)
 813213            if (allowHexSpecifier && negative)
 93214            {
 93215                var mask = Pow(16, nDigits) - 1;
 93216                number = (number ^ mask) + 1;
 93217            }
 3218
 813219            var exponent = 0;
 813220            if (allowExponent)
 123221            {
 123222                if (FindExponent(ref pos, value, ref exponent, tryParse, ref exc) && exc != null)
 33223                {
 33224                    return false;
 3225                }
 93226            }
 3227
 783228            if (allowTrailingSign && !foundSign)
 123229            {
 3230                // Sign + Currency
 123231                FindSign(ref pos, value, nfi, ref foundSign, ref negative);
 123232                if (foundSign && pos < value.Length)
 03233                {
 03234                    if (allowTrailingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
 03235                    {
 03236                        return false;
 3237                    }
 03238                }
 123239            }
 3240
 783241            if (allowCurrencySymbol && !foundCurrency)
 63242            {
 63243                if (allowTrailingWhite && pos < value.Length && !JumpOverWhitespace(ref pos, value, reportError: false, 
 03244                {
 03245                    return false;
 3246                }
 3247
 3248                // Currency + sign
 63249                FindCurrency(ref pos, value, nfi, ref foundCurrency);
 63250                if (foundCurrency && pos < value.Length)
 33251                {
 33252                    if (allowTrailingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
 03253                    {
 03254                        return false;
 3255                    }
 3256
 33257                    if (!foundSign && allowTrailingSign)
 33258                    {
 33259                        FindSign(ref pos, value, nfi, ref foundSign, ref negative);
 33260                    }
 33261                }
 63262            }
 3263
 783264            if (allowTrailingWhite && pos < value.Length && !JumpOverWhitespace(ref pos, value, reportError: false, tryP
 03265            {
 03266                return false;
 3267            }
 3268
 783269            if (foundOpenParentheses)
 63270            {
 63271                if (pos >= value.Length || value[pos++] != ')')
 03272                {
 03273                    if (!tryParse)
 03274                    {
 03275                        exc = GetFormatException();
 03276                    }
 3277
 03278                    return false;
 3279                }
 3280
 63281                if (allowTrailingWhite && pos < value.Length && !JumpOverWhitespace(ref pos, value, reportError: false, 
 03282                {
 03283                    return false;
 3284                }
 63285            }
 3286
 783287            if (pos < value.Length && value[pos] != '\u0000')
 63288            {
 63289                if (!tryParse)
 03290                {
 03291                    exc = GetFormatException();
 03292                }
 3293
 63294                return false;
 3295            }
 3296
 723297            if (decimalPointPos >= 0)
 93298            {
 93299                exponent = exponent - nDigits + decimalPointPos;
 93300            }
 3301
 723302            if (exponent < 0)
 93303            {
 3304                // Any non-zero values after decimal point are not allowed
 93305                number = DivRem(number, Pow(10, -exponent), out var remainder);
 3306
 93307                if (!remainder.IsZero)
 03308                {
 03309                    if (!tryParse)
 03310                    {
 03311                        exc = new OverflowException(string.Format(CultureInfo.InvariantCulture,
 03312                                                                  "Value too large or too small. exp= {0} rem = {1} pow 
 03313                                                                  exponent,
 03314                                                                  remainder,
 03315                                                                  Pow(10, -exponent)));
 03316                    }
 3317
 03318                    return false;
 3319                }
 93320            }
 633321            else if (exponent > 0)
 63322            {
 63323                number = Pow(10, exponent) * number;
 63324            }
 3325
 723326            if (number._sign == 0)
 03327            {
 03328                result = number;
 03329            }
 723330            else if (negative)
 243331            {
 243332                result = new BigInteger(-1, number._data);
 243333            }
 3334            else
 483335            {
 483336                result = new BigInteger(1, number._data);
 483337            }
 3338
 723339            return true;
 1083340        }
 3341
 3342        private static bool CheckStyle(NumberStyles style, bool tryParse, ref Exception exc)
 1053343        {
 1053344            if ((style & NumberStyles.AllowHexSpecifier) == NumberStyles.AllowHexSpecifier)
 243345            {
 243346                var ne = style ^ NumberStyles.AllowHexSpecifier;
 243347                if ((ne & NumberStyles.AllowLeadingWhite) == NumberStyles.AllowLeadingWhite)
 03348                {
 03349                    ne ^= NumberStyles.AllowLeadingWhite;
 03350                }
 3351
 243352                if ((ne & NumberStyles.AllowTrailingWhite) == NumberStyles.AllowTrailingWhite)
 03353                {
 03354                    ne ^= NumberStyles.AllowTrailingWhite;
 03355                }
 3356
 243357                if (ne != NumberStyles.None)
 03358                {
 03359                    if (!tryParse)
 03360                    {
 03361                        exc = new ArgumentException("With AllowHexSpecifier only " +
 03362                                                    "AllowLeadingWhite and AllowTrailingWhite " +
 03363                                                    "are permitted.");
 03364                    }
 3365
 03366                    return false;
 3367                }
 243368            }
 813369            else if ((uint)style > (uint)NumberStyles.Any)
 03370            {
 03371                if (!tryParse)
 03372                {
 03373                    exc = new ArgumentException("Not a valid number style");
 03374                }
 3375
 03376                return false;
 3377            }
 3378
 1053379            return true;
 1053380        }
 3381
 3382        private static bool JumpOverWhitespace(ref int pos, string s, bool reportError, bool tryParse, ref Exception exc
 483383        {
 963384            while (pos < s.Length && char.IsWhiteSpace(s[pos]))
 483385            {
 483386                pos++;
 483387            }
 3388
 483389            if (reportError && pos >= s.Length)
 03390            {
 03391                if (!tryParse)
 03392                {
 03393                    exc = GetFormatException();
 03394                }
 3395
 03396                return false;
 3397            }
 3398
 483399            return true;
 483400        }
 3401
 3402        private static void FindSign(ref int pos, string s, NumberFormatInfo nfi, ref bool foundSign, ref bool negative)
 333403        {
 333404            if ((pos + nfi.NegativeSign.Length) <= s.Length &&
 333405                string.CompareOrdinal(s, pos, nfi.NegativeSign, 0, nfi.NegativeSign.Length) == 0)
 93406            {
 93407                negative = true;
 93408                foundSign = true;
 93409                pos += nfi.NegativeSign.Length;
 93410            }
 243411            else if ((pos + nfi.PositiveSign.Length) <= s.Length &&
 243412              string.CompareOrdinal(s, pos, nfi.PositiveSign, 0, nfi.PositiveSign.Length) == 0)
 03413            {
 03414                negative = false;
 03415                pos += nfi.PositiveSign.Length;
 03416                foundSign = true;
 03417            }
 333418        }
 3419
 3420        private static void FindCurrency(ref int pos, string s, NumberFormatInfo nfi, ref bool foundCurrency)
 183421        {
 183422            if ((pos + nfi.CurrencySymbol.Length) <= s.Length &&
 183423                 s.Substring(pos, nfi.CurrencySymbol.Length) == nfi.CurrencySymbol)
 93424            {
 93425                foundCurrency = true;
 93426                pos += nfi.CurrencySymbol.Length;
 93427            }
 183428        }
 3429
 3430        private static bool FindExponent(ref int pos, string s, ref int exponent, bool tryParse, ref Exception exc)
 123431        {
 123432            exponent = 0;
 3433
 123434            if (pos >= s.Length || (s[pos] != 'e' && s[pos] != 'E'))
 03435            {
 03436                exc = null;
 03437                return false;
 3438            }
 3439
 123440            var i = pos + 1;
 123441            if (i == s.Length)
 03442            {
 03443                exc = tryParse ? null : GetFormatException();
 03444                return true;
 3445            }
 3446
 123447            var negative = false;
 123448            if (s[i] == '-')
 33449            {
 33450                negative = true;
 33451                if (++i == s.Length)
 03452                {
 03453                    exc = tryParse ? null : GetFormatException();
 03454                    return true;
 3455                }
 33456            }
 3457
 123458            if (s[i] == '+' && ++i == s.Length)
 03459            {
 03460                exc = tryParse ? null : GetFormatException();
 03461                return true;
 3462            }
 3463
 123464            long exp = 0; // temp long value
 363465            for (; i < s.Length; i++)
 153466            {
 153467                if (!char.IsDigit(s[i]))
 33468                {
 33469                    exc = tryParse ? null : GetFormatException();
 33470                    return true;
 3471                }
 3472
 3473                // Reduce the risk of throwing an overflow exc
 123474                exp = checked((exp * 10) - (s[i] - '0'));
 123475                if (exp is < int.MinValue or > int.MaxValue)
 03476                {
 03477                    exc = tryParse ? null : new OverflowException("Value too large or too small.");
 03478                    return true;
 3479                }
 123480            }
 3481
 3482            // exp value saved as negative
 93483            if (!negative)
 63484            {
 63485                exp = -exp;
 63486            }
 3487
 93488            exc = null;
 93489            exponent = (int) exp;
 93490            pos = i;
 93491            return true;
 123492        }
 3493
 3494        private static bool FindOther(ref int pos, string s, string other)
 633495        {
 633496            if ((pos + other.Length) <= s.Length &&
 633497                 s.Substring(pos, other.Length) == other)
 213498            {
 213499                pos += other.Length;
 213500                return true;
 3501            }
 3502
 423503            return false;
 633504        }
 3505
 3506        private static bool ValidDigit(char e, bool allowHex)
 119793507        {
 119793508            if (allowHex)
 23493509            {
 23493510                return char.IsDigit(e) || (e >= 'A' && e <= 'F') || (e >= 'a' && e <= 'f');
 3511            }
 3512
 96303513            return char.IsDigit(e);
 119793514        }
 3515
 3516        private static FormatException GetFormatException()
 183517        {
 183518            return new FormatException("Input string was not in the correct format");
 183519        }
 3520
 3521        private static bool ProcessTrailingWhitespace(bool tryParse, string s, int position, ref Exception exc)
 213522        {
 213523            var len = s.Length;
 3524
 663525            for (var i = position; i < len; i++)
 213526            {
 213527                var c = s[i];
 3528
 213529                if (c != 0 && !char.IsWhiteSpace(c))
 93530                {
 93531                    if (!tryParse)
 63532                    {
 63533                        exc = GetFormatException();
 63534                    }
 3535
 93536                    return false;
 3537                }
 123538            }
 3539
 123540            return true;
 213541        }
 3542
 3543        private static bool Parse(string value, bool tryParse, out BigInteger result, out Exception exc)
 813544        {
 813545            int i, sign = 1;
 813546            var digitsSeen = false;
 3547
 813548            result = Zero;
 813549            exc = null;
 3550
 813551            if (value is null)
 63552            {
 63553                if (!tryParse)
 33554                {
 33555                    exc = new ArgumentNullException(nameof(value));
 33556                }
 3557
 63558                return false;
 3559            }
 3560
 753561            var len = value.Length;
 3562
 3563            char c;
 2283564            for (i = 0; i < len; i++)
 1023565            {
 1023566                c = value[i];
 1023567                if (!char.IsWhiteSpace(c))
 633568                {
 633569                    break;
 3570                }
 393571            }
 3572
 753573            if (i == len)
 123574            {
 123575                if (!tryParse)
 63576                {
 63577                    exc = GetFormatException();
 63578                }
 3579
 123580                return false;
 3581            }
 3582
 633583            var info = NumberFormatInfo.CurrentInfo;
 3584
 633585            var negative = info.NegativeSign;
 633586            var positive = info.PositiveSign;
 3587
 633588            if (string.CompareOrdinal(value, i, positive, 0, positive.Length) == 0)
 123589            {
 123590                i += positive.Length;
 123591            }
 513592            else if (string.CompareOrdinal(value, i, negative, 0, negative.Length) == 0)
 243593            {
 243594                sign = -1;
 243595                i += negative.Length;
 243596            }
 3597
 633598            var val = Zero;
 11013599            for (; i < len; i++)
 5283600            {
 5283601                c = value[i];
 3602
 5283603                if (c == '\0')
 03604                {
 03605                    i = len;
 03606                    continue;
 3607                }
 3608
 5283609                if (c is >= '0' and <= '9')
 5073610                {
 5073611                    var d = (byte) (c - '0');
 3612
 5073613                    val = (val * 10) + d;
 3614
 5073615                    digitsSeen = true;
 5073616                }
 213617                else if (!ProcessTrailingWhitespace(tryParse, value, i, ref exc))
 93618                {
 93619                    return false;
 3620                }
 5193621            }
 3622
 543623            if (!digitsSeen)
 93624            {
 93625                if (!tryParse)
 33626                {
 33627                    exc = GetFormatException();
 33628                }
 3629
 93630                return false;
 3631            }
 3632
 453633            if (val._sign == 0)
 03634            {
 03635                result = val;
 03636            }
 3637#pragma warning disable CA1508 // Avoid dead conditional code | this is the following bug in the analyzer rule: https://
 453638            else if (sign == -1)
 3639#pragma warning restore CA1508 // Avoid dead conditional code
 153640            {
 153641                result = new BigInteger(-1, val._data);
 153642            }
 3643            else
 303644            {
 303645                result = new BigInteger(1, val._data);
 303646            }
 3647
 453648            return true;
 813649        }
 3650
 3651        /// <summary>
 3652        /// Returns the smaller of two <see cref="BigInteger"/> values.
 3653        /// </summary>
 3654        /// <param name="left">The first value to compare.</param>
 3655        /// <param name="right">The second value to compare.</param>
 3656        /// <returns>
 3657        /// The <paramref name="left"/> or <paramref name="right"/> parameter, whichever is smaller.
 3658        /// </returns>
 3659        public static BigInteger Min(BigInteger left, BigInteger right)
 1503660        {
 1503661            int ls = left._sign;
 1503662            int rs = right._sign;
 3663
 1503664            if (ls < rs)
 453665            {
 453666                return left;
 3667            }
 3668
 1053669            if (rs < ls)
 453670            {
 453671                return right;
 3672            }
 3673
 603674            var r = CoreCompare(left._data, right._data);
 603675            if (ls == -1)
 273676            {
 273677                r = -r;
 273678            }
 3679
 603680            if (r <= 0)
 423681            {
 423682                return left;
 3683            }
 3684
 183685            return right;
 1503686        }
 3687
 3688        /// <summary>
 3689        /// Returns the larger of two <see cref="BigInteger"/> values.
 3690        /// </summary>
 3691        /// <param name="left">The first value to compare.</param>
 3692        /// <param name="right">The second value to compare.</param>
 3693        /// <returns>
 3694        /// The <paramref name="left"/> or <paramref name="right"/> parameter, whichever is larger.
 3695        /// </returns>
 3696        public static BigInteger Max(BigInteger left, BigInteger right)
 1473697        {
 1473698            int ls = left._sign;
 1473699            int rs = right._sign;
 3700
 1473701            if (ls > rs)
 453702            {
 453703                return left;
 3704            }
 3705
 1023706            if (rs > ls)
 453707            {
 453708                return right;
 3709            }
 3710
 573711            var r = CoreCompare(left._data, right._data);
 573712            if (ls == -1)
 273713            {
 273714                r = -r;
 273715            }
 3716
 573717            if (r >= 0)
 393718            {
 393719                return left;
 3720            }
 3721
 183722            return right;
 1473723        }
 3724
 3725        /// <summary>
 3726        /// Gets the absolute value of a <see cref="BigInteger"/> object.
 3727        /// </summary>
 3728        /// <param name="value">A number.</param>
 3729        /// <returns>
 3730        /// The absolute value of <paramref name="value"/>.
 3731        /// </returns>
 3732        public static BigInteger Abs(BigInteger value)
 363733        {
 363734            return new BigInteger(Math.Abs(value._sign), value._data);
 363735        }
 3736
 3737        /// <summary>
 3738        /// Divides one <see cref="BigInteger"/> value by another, returns the result, and returns the remainder in
 3739        /// an output parameter.
 3740        /// </summary>
 3741        /// <param name="dividend">The value to be divided.</param>
 3742        /// <param name="divisor">The value to divide by.</param>
 3743        /// <param name="remainder">When this method returns, contains a <see cref="BigInteger"/> value that represents 
 3744        /// <returns>
 3745        /// The quotient of the division.
 3746        /// </returns>
 3747        public static BigInteger DivRem(BigInteger dividend, BigInteger divisor, out BigInteger remainder)
 183543748        {
 183543749            if (divisor._sign == 0)
 33750            {
 33751                throw new DivideByZeroException();
 3752            }
 3753
 183513754            if (dividend._sign == 0)
 213755            {
 213756                remainder = dividend;
 213757                return dividend;
 3758            }
 3759
 183303760            DivModUnsigned(dividend._data, divisor._data, out var quotient, out var remainderValue);
 3761
 3762            int i;
 411663763            for (i = remainderValue.Length - 1; i >= 0 && remainderValue[i] == 0; --i)
 22533764            {
 3765                // Intentionally empty block
 22533766            }
 3767
 183303768            if (i == -1)
 22323769            {
 22323770                remainder = Zero;
 22323771            }
 3772            else
 160983773            {
 160983774                if (i < remainderValue.Length - 1)
 63775                {
 63776                    Array.Resize(ref remainderValue, i + 1);
 63777                }
 3778
 160983779                remainder = new BigInteger(dividend._sign, remainderValue);
 160983780            }
 3781
 411123782            for (i = quotient.Length - 1; i >= 0 && quotient[i] == 0; --i)
 22263783            {
 3784                // Intentionally empty block
 22263785            }
 3786
 183303787            if (i == -1)
 5733788            {
 5733789                return Zero;
 3790            }
 3791
 177573792            if (i < quotient.Length - 1)
 16533793            {
 16533794                Array.Resize(ref quotient, i + 1);
 16533795            }
 3796
 177573797            return new BigInteger((short)(dividend._sign * divisor._sign), quotient);
 183513798        }
 3799
 3800        /// <summary>
 3801        /// Raises a <see cref="BigInteger"/> value to the power of a specified value.
 3802        /// </summary>
 3803        /// <param name="value">The number to raise to the <paramref name="exponent"/> power.</param>
 3804        /// <param name="exponent">The exponent to raise <paramref name="value"/> by.</param>
 3805        /// <returns>
 3806        /// The result of raising <paramref name="value"/> to the <paramref name="exponent"/> power.
 3807        /// </returns>
 3808        public static BigInteger Pow(BigInteger value, int exponent)
 753809        {
 753810            if (exponent < 0)
 33811            {
 33812                throw new ArgumentOutOfRangeException(nameof(exponent), "exp must be >= 0");
 3813            }
 3814
 723815            if (exponent == 0)
 33816            {
 33817                return One;
 3818            }
 3819
 693820            if (exponent == 1)
 123821            {
 123822                return value;
 3823            }
 3824
 573825            var result = One;
 3513826            while (exponent != 0)
 3513827            {
 3513828                if ((exponent & 1) != 0)
 1593829                {
 1593830                    result *= value;
 1593831                }
 3832
 3513833                if (exponent == 1)
 573834                {
 573835                    break;
 3836                }
 3837
 2943838                value *= value;
 2943839                exponent >>= 1;
 2943840            }
 3841
 573842            return result;
 723843        }
 3844
 3845        /// <summary>
 3846        /// Performs modulus division on a number raised to the power of another number.
 3847        /// </summary>
 3848        /// <param name="value">The number to raise to the <paramref name="exponent"/> power.</param>
 3849        /// <param name="exponent">The exponent to raise <paramref name="value"/> by.</param>
 3850        /// <param name="modulus">The number by which to divide <paramref name="value"/> raised to the <paramref name="e
 3851        /// <returns>
 3852        /// The remainder after dividing <paramref name="value"/> raised by <paramref name="exponent"/> by
 3853        /// <paramref name="modulus"/>.
 3854        /// </returns>
 3855        /// <exception cref="ArgumentOutOfRangeException"><paramref name="exponent"/> is negative.</exception>
 3856        public static BigInteger ModPow(BigInteger value, BigInteger exponent, BigInteger modulus)
 33593857        {
 33593858            if (exponent._sign == -1)
 33859            {
 33860                throw new ArgumentOutOfRangeException(nameof(exponent), "power must be >= 0");
 3861            }
 3862
 33563863            if (modulus._sign == 0)
 33864            {
 33865                throw new DivideByZeroException();
 3866            }
 3867
 33533868            var result = One % modulus;
 14844563869            while (exponent._sign != 0)
 14844563870            {
 14844563871                if (!exponent.IsEven)
 7579243872                {
 7579243873                    result *= value;
 7579243874                    result %= modulus;
 7579243875                }
 3876
 14844563877                if (exponent.IsOne)
 33533878                {
 33533879                    break;
 3880                }
 3881
 14811033882                value *= value;
 14811033883                value %= modulus;
 14811033884                exponent >>= 1;
 14811033885            }
 3886
 33533887            return result;
 33533888        }
 3889
 3890        /// <summary>
 3891        /// Finds the greatest common divisor of two <see cref="BigInteger"/> values.
 3892        /// </summary>
 3893        /// <param name="left">The first value.</param>
 3894        /// <param name="right">The second value.</param>
 3895        /// <returns>
 3896        /// The greatest common divisor of <paramref name="left"/> and <paramref name="right"/>.
 3897        /// </returns>
 3898        public static BigInteger GreatestCommonDivisor(BigInteger left, BigInteger right)
 543899        {
 543900            if (left._sign != 0 && left._data.Length == 1 && left._data[0] == 1)
 123901            {
 123902                return One;
 3903            }
 3904
 423905            if (right._sign != 0 && right._data.Length == 1 && right._data[0] == 1)
 123906            {
 123907                return One;
 3908            }
 3909
 303910            if (left.IsZero)
 93911            {
 93912                return Abs(right);
 3913            }
 3914
 213915            if (right.IsZero)
 63916            {
 63917                return Abs(left);
 3918            }
 3919
 153920            var x = new BigInteger(1, left._data);
 153921            var y = new BigInteger(1, right._data);
 3922
 153923            var g = y;
 3924
 153925            while (x._data.Length > 1)
 03926            {
 03927                g = x;
 03928                x = y % x;
 03929                y = g;
 03930            }
 3931
 153932            if (x.IsZero)
 03933            {
 03934                return g;
 3935            }
 3936
 3937            // TODO: should we have something here if we can convert to long?
 3938
 3939            /*
 3940             * Now we can just do it with single precision. I am using the binary gcd method,
 3941             * as it should be faster.
 3942             */
 3943
 153944            var yy = x._data[0];
 153945            var xx = (uint)(y % yy);
 3946
 153947            var t = 0;
 3948
 363949            while (((xx | yy) & 1) == 0)
 213950            {
 213951                xx >>= 1;
 213952                yy >>= 1;
 213953                t++;
 213954            }
 3955
 2163956            while (xx != 0)
 2013957            {
 3423958                while ((xx & 1) == 0)
 1413959                {
 1413960                    xx >>= 1;
 1413961                }
 3962
 3513963                while ((yy & 1) == 0)
 1503964                {
 1503965                    yy >>= 1;
 1503966                }
 3967
 2013968                if (xx >= yy)
 963969                {
 963970                    xx = (xx - yy) >> 1;
 963971                }
 3972                else
 1053973                {
 1053974                    yy = (yy - xx) >> 1;
 1053975                }
 2013976            }
 3977
 153978            return yy << t;
 543979        }
 3980
 3981        /*
 3982         * LAMESPEC Log doesn't specify to how many ulp is has to be precise
 3983         * We are equilavent to MS with about 2 ULP
 3984         */
 3985
 3986        /// <summary>
 3987        /// Returns the logarithm of a specified number in a specified base.
 3988        /// </summary>
 3989        /// <param name="value">A number whose logarithm is to be found.</param>
 3990        /// <param name="baseValue">The base of the logarithm.</param>
 3991        /// <returns>
 3992        /// The base <paramref name="baseValue"/> logarithm of value.
 3993        /// </returns>
 3994        /// <exception cref="ArgumentOutOfRangeException">The log of <paramref name="value"/> is out of range of the <se
 3995        public static double Log(BigInteger value, double baseValue)
 513996        {
 513997            if (value._sign == -1 || baseValue == 1.0d || baseValue == -1.0d ||
 513998                    baseValue == double.NegativeInfinity || double.IsNaN(baseValue))
 243999            {
 244000                return double.NaN;
 4001            }
 4002
 274003            if (baseValue is 0.0d or double.PositiveInfinity)
 124004            {
 124005                return value.IsOne ? 0 : double.NaN;
 4006            }
 4007
 154008            if (value._data is null)
 34009            {
 34010                return double.NegativeInfinity;
 4011            }
 4012
 124013            var length = value._data.Length - 1;
 124014            var bitCount = -1;
 6784015            for (var curBit = 31; curBit >= 0; curBit--)
 3394016            {
 3394017                if ((value._data[length] & (1 << curBit)) != 0)
 124018                {
 124019                    bitCount = curBit + (length * 32);
 124020                    break;
 4021                }
 3274022            }
 4023
 124024            long bitlen = bitCount;
 244025            double c = 0, d = 1;
 4026
 124027            var testBit = One;
 124028            var tempBitlen = bitlen;
 124029            while (tempBitlen > int.MaxValue)
 04030            {
 04031                testBit <<= int.MaxValue;
 04032                tempBitlen -= int.MaxValue;
 04033            }
 4034
 124035            testBit <<= (int)tempBitlen;
 4036
 1384037            for (var curbit = bitlen; curbit >= 0; --curbit)
 574038            {
 574039                if ((value & testBit)._sign != 0)
 334040                {
 334041                    c += d;
 334042                }
 4043
 574044                d *= 0.5;
 574045                testBit >>= 1;
 574046            }
 4047
 124048            return (Math.Log(c) + (Math.Log(2) * bitlen)) / Math.Log(baseValue);
 514049        }
 4050
 4051        /// <summary>
 4052        /// Returns the natural (base <c>e</c>) logarithm of a specified number.
 4053        /// </summary>
 4054        /// <param name="value">The number whose logarithm is to be found.</param>
 4055        /// <returns>
 4056        /// The natural (base <c>e</c>) logarithm of <paramref name="value"/>.
 4057        /// </returns>
 4058        /// <exception cref="ArgumentOutOfRangeException">The base 10 log of value is out of range of the <see cref="dou
 4059        public static double Log(BigInteger value)
 184060        {
 184061            return Log(value, Math.E);
 184062        }
 4063
 4064        /// <summary>
 4065        /// Returns the base 10 logarithm of a specified number.
 4066        /// </summary>
 4067        /// <param name="value">A number whose logarithm is to be found.</param>
 4068        /// <returns>
 4069        /// The base 10 logarithm of <paramref name="value"/>.
 4070        /// </returns>
 4071        /// <exception cref="ArgumentOutOfRangeException">The base 10 log of value is out of range of the <see cref="dou
 4072        public static double Log10(BigInteger value)
 04073        {
 04074            return Log(value, 10);
 04075        }
 4076
 4077        /// <summary>
 4078        /// Returns the hash code for the current <see cref="BigInteger"/> object.
 4079        /// </summary>
 4080        /// <returns>
 4081        /// A 32-bit signed integer hash code.
 4082        /// </returns>
 4083        public override readonly int GetHashCode()
 64084        {
 64085            var hash = (uint) (_sign * 0x01010101u);
 64086            if (_data != null)
 04087            {
 04088                foreach (var bit in _data)
 04089                {
 04090                    hash ^= bit;
 04091                }
 04092            }
 4093
 64094            return (int) hash;
 64095        }
 4096
 4097        /// <summary>
 4098        /// Adds two <see cref="BigInteger"/> values and returns the result.
 4099        /// </summary>
 4100        /// <param name="left">The first value to add.</param>
 4101        /// <param name="right">The second value to add.</param>
 4102        /// <returns>
 4103        /// The sum of <paramref name="left"/> and <paramref name="right"/>.
 4104        /// </returns>
 4105        public static BigInteger Add(BigInteger left, BigInteger right)
 94106        {
 94107            return left + right;
 94108        }
 4109
 4110        /// <summary>
 4111        /// Subtracts one <see cref="BigInteger"/> value from another and returns the result.
 4112        /// </summary>
 4113        /// <param name="left">The value to subtract from (the minuend).</param>
 4114        /// <param name="right">The value to subtract (the subtrahend).</param>
 4115        /// <returns>
 4116        /// The result of subtracting <paramref name="right"/> from <paramref name="left"/>.
 4117        /// </returns>
 4118        public static BigInteger Subtract(BigInteger left, BigInteger right)
 1474119        {
 1474120            return left - right;
 1474121        }
 4122
 4123        /// <summary>
 4124        /// Returns the product of two <see cref="BigInteger"/> values.
 4125        /// </summary>
 4126        /// <param name="left">The first number to multiply.</param>
 4127        /// <param name="right">The second number to multiply.</param>
 4128        /// <returns>
 4129        /// The product of the <paramref name="left"/> and <paramref name="right"/> parameters.
 4130        /// </returns>
 4131        public static BigInteger Multiply(BigInteger left, BigInteger right)
 04132        {
 04133            return left * right;
 04134        }
 4135
 4136        /// <summary>
 4137        /// Divides one <see cref="BigInteger"/> value by another and returns the result.
 4138        /// </summary>
 4139        /// <param name="dividend">The value to be divided.</param>
 4140        /// <param name="divisor">The value to divide by.</param>
 4141        /// <returns>
 4142        /// The quotient of the division.
 4143        /// </returns>
 4144        public static BigInteger Divide(BigInteger dividend, BigInteger divisor)
 04145        {
 04146            return dividend / divisor;
 04147        }
 4148
 4149        /// <summary>
 4150        /// Performs integer division on two <see cref="BigInteger"/> values and returns the remainder.
 4151        /// </summary>
 4152        /// <param name="dividend">The value to be divided.</param>
 4153        /// <param name="divisor">The value to divide by.</param>
 4154        /// <returns>
 4155        /// The remainder after dividing <paramref name="dividend"/> by <paramref name="divisor"/>.
 4156        /// </returns>
 4157        public static BigInteger Remainder(BigInteger dividend, BigInteger divisor)
 04158        {
 04159            return dividend % divisor;
 04160        }
 4161
 4162        /// <summary>
 4163        /// Negates a specified <see cref="BigInteger"/> value.
 4164        /// </summary>
 4165        /// <param name="value">The value to negate.</param>
 4166        /// <returns>
 4167        /// The result of the <paramref name="value"/> parameter multiplied by negative one (-1).
 4168        /// </returns>
 4169        public static BigInteger Negate(BigInteger value)
 214170        {
 214171            return -value;
 214172        }
 4173
 4174        /// <summary>
 4175        /// Compares this instance to a specified object and returns an integer that indicates whether the value of
 4176        /// this instance is less than, equal to, or greater than the value of the specified object.
 4177        /// </summary>
 4178        /// <param name="obj">The object to compare.</param>
 4179        /// <returns>
 4180        /// A signed integer that indicates the relationship of the current instance to the <paramref name="obj"/> param
 4181        /// as shown in the following table.
 4182        /// <list type="table">
 4183        ///     <listheader>
 4184        ///         <term>Value</term>
 4185        ///         <description>Condition</description>
 4186        ///     </listheader>
 4187        ///     <item>
 4188        ///         <term>Less than zero</term>
 4189        ///         <description>The current instance is less than <paramref name="obj"/>.</description>
 4190        ///     </item>
 4191        ///     <item>
 4192        ///         <term>Zero</term>
 4193        ///         <description>The current instance equals <paramref name="obj"/>.</description>
 4194        ///     </item>
 4195        ///     <item>
 4196        ///         <term>Greater than zero</term>
 4197        ///         <description>The current instance is greater than <paramref name="obj"/>.</description>
 4198        ///     </item>
 4199        /// </list>
 4200        /// </returns>
 4201        /// <exception cref="ArgumentException"><paramref name="obj"/> is not a <see cref="BigInteger"/>.</exception>
 4202        public readonly int CompareTo(object obj)
 34203        {
 34204            if (obj is null)
 34205            {
 34206                return 1;
 4207            }
 4208
 04209            if (obj is not BigInteger other)
 04210            {
 04211                return -1;
 4212            }
 4213
 04214            return Compare(this, other);
 34215        }
 4216
 4217        /// <summary>
 4218        /// Compares this instance to a second <see cref="BigInteger"/> and returns an integer that indicates whether th
 4219        /// value of this instance is less than, equal to, or greater than the value of the specified object.
 4220        /// </summary>
 4221        /// <param name="other">The object to compare.</param>
 4222        /// <returns>
 4223        /// A signed integer value that indicates the relationship of this instance to <paramref name="other"/>, as
 4224        /// shown in the following table.
 4225        /// <list type="table">
 4226        ///     <listheader>
 4227        ///         <term>Value</term>
 4228        ///         <description>Condition</description>
 4229        ///     </listheader>
 4230        ///     <item>
 4231        ///         <term>Less than zero</term>
 4232        ///         <description>The current instance is less than <paramref name="other"/>.</description>
 4233        ///     </item>
 4234        ///     <item>
 4235        ///         <term>Zero</term>
 4236        ///         <description>The current instance equals <paramref name="other"/>.</description>
 4237        ///     </item>
 4238        ///     <item>
 4239        ///         <term>Greater than zero</term>
 4240        ///         <description>The current instance is greater than <paramref name="other"/>.</description>
 4241        ///     </item>
 4242        /// </list>
 4243        /// </returns>
 4244        public readonly int CompareTo(BigInteger other)
 7054245        {
 7054246            return Compare(this, other);
 7054247        }
 4248
 4249        /// <summary>
 4250        /// Compares this instance to an unsigned 64-bit integer and returns an integer that indicates whether the value
 4251        /// instance is less than, equal to, or greater than the value of the unsigned 64-bit integer.
 4252        /// </summary>
 4253        /// <param name="other">The unsigned 64-bit integer to compare.</param>
 4254        /// <returns>
 4255        /// A signed integer that indicates the relative value of this instance and <paramref name="other"/>, as shown
 4256        /// in the following table.
 4257        /// <list type="table">
 4258        ///     <listheader>
 4259        ///         <term>Value</term>
 4260        ///         <description>Condition</description>
 4261        ///     </listheader>
 4262        ///     <item>
 4263        ///         <term>Less than zero</term>
 4264        ///         <description>The current instance is less than <paramref name="other"/>.</description>
 4265        ///     </item>
 4266        ///     <item>
 4267        ///         <term>Zero</term>
 4268        ///         <description>The current instance equals <paramref name="other"/>.</description>
 4269        ///     </item>
 4270        ///     <item>
 4271        ///         <term>Greater than zero</term>
 4272        ///         <description>The current instance is greater than <paramref name="other"/>.</description>
 4273        ///     </item>
 4274        /// </list>
 4275        /// </returns>
 4276        [CLSCompliant(false)]
 4277        public readonly int CompareTo(ulong other)
 24964278        {
 24964279            if (_sign < 0)
 9364280            {
 9364281                return -1;
 4282            }
 4283
 15604284            if (_sign == 0)
 3124285            {
 3124286                return other == 0 ? 0 : -1;
 4287            }
 4288
 12484289            if (_data.Length > 2)
 04290            {
 04291                return 1;
 4292            }
 4293
 12484294            var high = (uint)(other >> 32);
 12484295            var low = (uint)other;
 4296
 12484297            return LongCompare(low, high);
 24964298        }
 4299
 4300        /// <summary>
 4301        /// Compares this instance to a signed 64-bit integer and returns an integer that indicates whether the value of
 4302        /// instance is less than, equal to, or greater than the value of the signed 64-bit integer.
 4303        /// </summary>
 4304        /// <param name="other">The signed 64-bit integer to compare.</param>
 4305        /// <returns>
 4306        /// A signed integer that indicates the relative value of this instance and <paramref name="other"/>, as shown
 4307        /// in the following table.
 4308        /// <list type="table">
 4309        ///     <listheader>
 4310        ///         <term>Value</term>
 4311        ///         <description>Condition</description>
 4312        ///     </listheader>
 4313        ///     <item>
 4314        ///         <term>Less than zero</term>
 4315        ///         <description>The current instance is less than <paramref name="other"/>.</description>
 4316        ///     </item>
 4317        ///     <item>
 4318        ///         <term>Zero</term>
 4319        ///         <description>The current instance equals <paramref name="other"/>.</description>
 4320        ///     </item>
 4321        ///     <item>
 4322        ///         <term>Greater than zero</term>
 4323        ///         <description>The current instance is greater than <paramref name="other"/>.</description>
 4324        ///     </item>
 4325        /// </list>
 4326        /// </returns>
 4327        public readonly int CompareTo(long other)
 255414328        {
 255414329            int ls = _sign;
 255414330            var rs = Math.Sign(other);
 4331
 255414332            if (ls != rs)
 229274333            {
 229274334                return ls > rs ? 1 : -1;
 4335            }
 4336
 26144337            if (ls == 0)
 5504338            {
 5504339                return 0;
 4340            }
 4341
 20644342            if (_data.Length > 2)
 274343            {
 274344                return _sign;
 4345            }
 4346
 20374347            if (other < 0)
 6274348            {
 6274349                other = -other;
 6274350            }
 4351
 20374352            var low = (uint) other;
 20374353            var high = (uint) ((ulong) other >> 32);
 4354
 20374355            var r = LongCompare(low, high);
 20374356            if (ls == -1)
 6274357            {
 6274358                r = -r;
 6274359            }
 4360
 20374361            return r;
 255414362        }
 4363
 4364        private readonly int LongCompare(uint low, uint high)
 32854365        {
 32854366            uint h = 0;
 4367
 32854368            if (_data.Length > 1)
 16444369            {
 16444370                h = _data[1];
 16444371            }
 4372
 32854373            if (h > high)
 10984374            {
 10984375                return 1;
 4376            }
 4377
 21874378            if (h < high)
 10924379            {
 10924380                return -1;
 4381            }
 4382
 10954383            var l = _data[0];
 4384
 10954385            if (l > low)
 2734386            {
 2734387                return 1;
 4388            }
 4389
 8224390            if (l < low)
 2764391            {
 2764392                return -1;
 4393            }
 4394
 5464395            return 0;
 32854396        }
 4397
 4398        /// <summary>
 4399        /// Compares two <see cref="BigInteger"/> values and returns an integer that indicates whether the first value i
 4400        /// </summary>
 4401        /// <param name="left">The first value to compare.</param>
 4402        /// <param name="right">The second value to compare.</param>
 4403        /// <returns>
 4404        /// A signed integer that indicates the relative values of left and right, as shown in the following table.
 4405        /// <list type="table">
 4406        ///     <listheader>
 4407        ///         <term>Value</term>
 4408        ///         <description>Condition</description>
 4409        ///     </listheader>
 4410        ///     <item>
 4411        ///         <term>Less than zero</term>
 4412        ///         <description><paramref name="left"/> is less than <paramref name="right"/>.</description>
 4413        ///     </item>
 4414        ///     <item>
 4415        ///         <term>Zero</term>
 4416        ///         <description><paramref name="left"/> equals <paramref name="right"/>.</description>
 4417        ///     </item>
 4418        ///     <item>
 4419        ///         <term>Greater than zero</term>
 4420        ///         <description><paramref name="left"/> is greater than <paramref name="right"/>.</description>
 4421        ///     </item>
 4422        /// </list>
 4423        /// </returns>
 4424        public static int Compare(BigInteger left, BigInteger right)
 112434425        {
 112434426            int ls = left._sign;
 112434427            int rs = right._sign;
 4428
 112434429            if (ls != rs)
 47384430            {
 47384431                return ls > rs ? 1 : -1;
 4432            }
 4433
 65054434            var r = CoreCompare(left._data, right._data);
 65054435            if (ls < 0)
 8404436            {
 8404437                r = -r;
 8404438            }
 4439
 65054440            return r;
 112434441        }
 4442
 4443        private static int TopByte(uint x)
 86544444        {
 86544445            if ((x & 0xFFFF0000u) != 0)
 71104446            {
 71104447                if ((x & 0xFF000000u) != 0)
 46224448                {
 46224449                    return 4;
 4450                }
 4451
 24884452                return 3;
 4453            }
 4454
 15444455            if ((x & 0xFF00u) != 0)
 594456            {
 594457                return 2;
 4458            }
 4459
 14854460            return 1;
 86544461        }
 4462
 4463        private static int FirstNonFfByte(uint word)
 1294464        {
 1294465            if ((word & 0xFF000000u) != 0xFF000000u)
 394466            {
 394467                return 4;
 4468            }
 4469
 904470            if ((word & 0xFF0000u) != 0xFF0000u)
 274471            {
 274472                return 3;
 4473            }
 4474
 634475            if ((word & 0xFF00u) != 0xFF00u)
 274476            {
 274477                return 2;
 4478            }
 4479
 364480            return 1;
 1294481        }
 4482
 4483        /// <summary>
 4484        /// Converts a <see cref="BigInteger"/> value to a byte array.
 4485        /// </summary>
 4486        /// <returns>
 4487        /// The value of the current <see cref="BigInteger"/> object converted to an array of bytes.
 4488        /// </returns>
 4489        public readonly byte[] ToByteArray()
 86784490        {
 86784491            if (_sign == 0)
 244492            {
 244493                return new byte[1];
 4494            }
 4495
 4496            // number of bytes not counting upper word
 86544497            var bytes = (_data.Length - 1) * 4;
 86544498            var needExtraZero = false;
 4499
 86544500            var topWord = _data[_data.Length - 1];
 4501            int extra;
 4502
 4503            // if the topmost bit is set we need an extra
 86544504            if (_sign == 1)
 85314505            {
 85314506                extra = TopByte(topWord);
 85314507                var mask = 0x80u << ((extra - 1) * 8);
 85314508                if ((topWord & mask) != 0)
 35174509                {
 35174510                    needExtraZero = true;
 35174511                }
 85314512            }
 4513            else
 1234514            {
 1234515                extra = TopByte(topWord);
 1234516            }
 4517
 86544518            var res = new byte[bytes + extra + (needExtraZero ? 1 : 0)];
 86544519            if (_sign == 1)
 85314520            {
 85314521                var j = 0;
 85314522                var end = _data.Length - 1;
 7618404523                for (var i = 0; i < end; ++i)
 3723894524                {
 3723894525                    var word = _data[i];
 4526
 3723894527                    res[j++] = (byte)word;
 3723894528                    res[j++] = (byte)(word >> 8);
 3723894529                    res[j++] = (byte)(word >> 16);
 3723894530                    res[j++] = (byte)(word >> 24);
 3723894531                }
 4532
 357594533                while (extra-- > 0)
 272284534                {
 272284535                    res[j++] = (byte)topWord;
 272284536                    topWord >>= 8;
 272284537                }
 85314538            }
 4539            else
 1234540            {
 1234541                var j = 0;
 1234542                var end = _data.Length - 1;
 4543
 1234544                uint carry = 1, word;
 4545                ulong add;
 6064546                for (var i = 0; i < end; ++i)
 1804547                {
 1804548                    word = _data[i];
 1804549                    add = (ulong)~word + carry;
 1804550                    word = (uint)add;
 1804551                    carry = (uint)(add >> 32);
 4552
 1804553                    res[j++] = (byte)word;
 1804554                    res[j++] = (byte)(word >> 8);
 1804555                    res[j++] = (byte)(word >> 16);
 1804556                    res[j++] = (byte)(word >> 24);
 1804557                }
 4558
 1234559                add = (ulong)~topWord + carry;
 1234560                word = (uint)add;
 1234561                carry = (uint)(add >> 32);
 1234562                if (carry == 0)
 1234563                {
 1234564                    var ex = FirstNonFfByte(word);
 1234565                    var needExtra = (word & (1 << ((ex * 8) - 1))) == 0;
 1234566                    var to = ex + (needExtra ? 1 : 0);
 4567
 1234568                    if (to != extra)
 154569                    {
 154570                        Array.Resize(ref res, bytes + to);
 154571                    }
 4572
 4444573                    while (ex-- > 0)
 3214574                    {
 3214575                        res[j++] = (byte)word;
 3214576                        word >>= 8;
 3214577                    }
 4578
 1234579                    if (needExtra)
 214580                    {
 4581#pragma warning disable S1854 // Unused assignments should be removed
 214582                        res[j++] = 0xFF;
 4583#pragma warning restore S1854 // Unused assignments should be removed
 214584                    }
 1234585                }
 4586                else
 04587                {
 04588                    Array.Resize(ref res, bytes + 5);
 04589                    res[j++] = (byte)word;
 04590                    res[j++] = (byte)(word >> 8);
 04591                    res[j++] = (byte)(word >> 16);
 04592                    res[j++] = (byte)(word >> 24);
 4593#pragma warning disable S1854 // Unused assignments should be removed
 04594                    res[j++] = 0xFF;
 4595#pragma warning restore S1854 // Unused assignments should be removed
 04596                }
 1234597            }
 4598
 86544599            return res;
 86784600        }
 4601
 4602        private static uint[] CoreAdd(uint[] a, uint[] b)
 8434034603        {
 8434034604            if (a.Length < b.Length)
 804394605            {
 804394606                var tmp = a;
 804394607                a = b;
 804394608                b = tmp;
 804394609            }
 4610
 8434034611            var bl = a.Length;
 8434034612            var sl = b.Length;
 4613
 8434034614            var res = new uint[bl];
 4615
 8434034616            ulong sum = 0;
 4617
 8434034618            var i = 0;
 547644974619            for (; i < sl; i++)
 269605474620            {
 269605474621                sum = sum + a[i] + b[i];
 269605474622                res[i] = (uint)sum;
 269605474623                sum >>= 32;
 269605474624            }
 4625
 29743654626            for (; i < bl; i++)
 10654814627            {
 10654814628                sum += a[i];
 10654814629                res[i] = (uint)sum;
 10654814630                sum >>= 32;
 10654814631            }
 4632
 8434034633            if (sum != 0)
 73354634            {
 73354635                Array.Resize(ref res, bl + 1);
 73354636                res[i] = (uint)sum;
 73354637            }
 4638
 8434034639            return res;
 8434034640        }
 4641
 4642        private static uint[] CoreAdd(uint[] a, uint b)
 274643        {
 274644            var len = a.Length;
 274645            var res = new uint[len];
 4646
 274647            ulong sum = b;
 4648            int i;
 1204649            for (i = 0; i < len; i++)
 334650            {
 334651                sum += a[i];
 334652                res[i] = (uint) sum;
 334653                sum >>= 32;
 334654            }
 4655
 274656            if (sum != 0)
 04657            {
 04658                Array.Resize(ref res, len + 1);
 04659                res[i] = (uint) sum;
 04660            }
 4661
 274662            return res;
 274663        }
 4664
 4665        /*invariant a > b*/
 4666        private static uint[] CoreSub(uint[] a, uint[] b)
 21844667        {
 21844668            var bl = a.Length;
 21844669            var sl = b.Length;
 4670
 21844671            var res = new uint[bl];
 4672
 21844673            ulong borrow = 0;
 4674            int i;
 1110404675            for (i = 0; i < sl; ++i)
 533364676            {
 533364677                borrow = (ulong)a[i] - b[i] - borrow;
 4678
 533364679                res[i] = (uint)borrow;
 533364680                borrow = (borrow >> 32) & 0x1;
 533364681            }
 4682
 961024683            for (; i < bl; i++)
 469594684            {
 469594685                borrow = (ulong)a[i] - borrow;
 469594686                res[i] = (uint)borrow;
 469594687                borrow = (borrow >> 32) & 0x1;
 469594688            }
 4689
 4690            // remove extra zeroes
 43684691            for (i = bl - 1; i >= 0 && res[i] == 0; --i)
 04692            {
 4693                // Intentionally empty block
 04694            }
 4695
 21844696            if (i < bl - 1)
 04697            {
 04698                Array.Resize(ref res, i + 1);
 04699            }
 4700
 21844701            return res;
 21844702        }
 4703
 4704        private static uint[] CoreSub(uint[] a, uint b)
 124705        {
 124706            var len = a.Length;
 124707            var res = new uint[len];
 4708
 124709            ulong borrow = b;
 4710            int i;
 604711            for (i = 0; i < len; i++)
 184712            {
 184713                borrow = (ulong)a[i] - borrow;
 184714                res[i] = (uint)borrow;
 184715                borrow = (borrow >> 32) & 0x1;
 184716            }
 4717
 4718            // Remove extra zeroes
 244719            for (i = len - 1; i >= 0 && res[i] == 0; --i)
 04720            {
 4721                // Intentionally empty block
 04722            }
 4723
 124724            if (i < len - 1)
 04725            {
 04726                Array.Resize(ref res, i + 1);
 04727            }
 4728
 124729            return res;
 124730        }
 4731
 4732        private static int CoreCompare(uint[] a, uint[] b)
 88724733        {
 88724734            var al = a != null ? a.Length : 0;
 88724735            var bl = b != null ? b.Length : 0;
 4736
 88724737            if (al > bl)
 30784738            {
 30784739                return 1;
 4740            }
 4741
 57944742            if (bl > al)
 9424743            {
 9424744                return -1;
 4745            }
 4746
 134184747            for (var i = al - 1; i >= 0; --i)
 50984748            {
 50984749                var ai = a[i];
 50984750                var bi = b[i];
 50984751                if (ai > bi)
 13384752                {
 13384753                    return 1;
 4754                }
 4755
 37604756                if (ai < bi)
 19034757                {
 19034758                    return -1;
 4759                }
 18574760            }
 4761
 16114762            return 0;
 88724763        }
 4764
 4765        private static int GetNormalizeShift(uint value)
 38813094766        {
 38813094767            var shift = 0;
 4768
 38813094769            if ((value & 0xFFFF0000) == 0)
 8199334770            {
 8199334771                value <<= 16;
 8199334772                shift += 16;
 8199334773            }
 4774
 38813094775            if ((value & 0xFF000000) == 0)
 8179814776            {
 8179814777                value <<= 8;
 8179814778                shift += 8;
 8179814779            }
 4780
 38813094781            if ((value & 0xF0000000) == 0)
 8193614782            {
 8193614783                value <<= 4;
 8193614784                shift += 4;
 8193614785            }
 4786
 38813094787            if ((value & 0xC0000000) == 0)
 8200974788            {
 8200974789                value <<= 2;
 8200974790                shift += 2;
 8200974791            }
 4792
 38813094793            if ((value & 0x80000000) == 0)
 8177594794            {
 4795#pragma warning disable IDE0059 // Unnecessary assignment of a value
 8177594796                value <<= 1;
 4797#pragma warning restore IDE0059 // Unnecessary assignment of a value
 8177594798                shift += 1;
 8177594799            }
 4800
 38813094801            return shift;
 38813094802        }
 4803
 4804        private static void Normalize(uint[] u, int l, uint[] un, int shift)
 77626184805        {
 77626184806            uint carry = 0;
 4807            int i;
 77626184808            if (shift > 0)
 31757144809            {
 31757144810                var rshift = 32 - shift;
 2159822144811                for (i = 0; i < l; i++)
 1048153934812                {
 1048153934813                    var ui = u[i];
 1048153934814                    un[i] = (ui << shift) | carry;
 1048153934815                    carry = ui >> rshift;
 1048153934816                }
 31757144817            }
 4818            else
 45869044819            {
 4682575324820                for (i = 0; i < l; i++)
 2295418624821                {
 2295418624822                    un[i] = u[i];
 2295418624823                }
 45869044824            }
 4825
 116439274826            while (i < un.Length)
 38813094827            {
 38813094828                un[i++] = 0;
 38813094829            }
 4830
 77626184831            if (carry != 0)
 11884974832            {
 11884974833                un[l] = carry;
 11884974834            }
 77626184835        }
 4836
 4837        private static void Unnormalize(uint[] un, out uint[] r, int shift)
 38813094838        {
 38813094839            var length = un.Length;
 38813094840            r = new uint[length];
 4841
 38813094842            if (shift > 0)
 15878574843            {
 15878574844                var lshift = 32 - shift;
 15878574845                uint carry = 0;
 1112139984846                for (var i = length - 1; i >= 0; i--)
 540191424847                {
 540191424848                    var uni = un[i];
 540191424849                    r[i] = (uni >> shift) | carry;
 540191424850                    carry = uni << lshift;
 540191424851                }
 15878574852            }
 4853            else
 22934524854            {
 3139939264855                for (var i = 0; i < length; i++)
 1547035114856                {
 1547035114857                    r[i] = un[i];
 1547035114858                }
 22934524859            }
 38813094860        }
 4861
 4862        private static void DivModUnsigned(uint[] u, uint[] v, out uint[] q, out uint[] r)
 39289614863        {
 39289614864            var m = u.Length;
 39289614865            var n = v.Length;
 4866
 39289614867            if (n <= 1)
 439964868            {
 4869                // Divide by single digit
 439964870                ulong rem = 0;
 439964871                var v0 = v[0];
 439964872                q = new uint[m];
 439964873                r = new uint[1];
 4874
 2392344875                for (var j = m - 1; j >= 0; j--)
 756214876                {
 756214877                    rem *= Base;
 756214878                    rem += u[j];
 4879
 756214880                    var div = rem / v0;
 756214881                    rem -= div * v0;
 756214882                    q[j] = (uint)div;
 756214883                }
 4884
 439964885                r[0] = (uint) rem;
 439964886            }
 38849654887            else if (m >= n)
 38813094888            {
 38813094889                var shift = GetNormalizeShift(v[n - 1]);
 4890
 38813094891                var un = new uint[m + 1];
 38813094892                var vn = new uint[n];
 4893
 38813094894                Normalize(u, m, un, shift);
 38813094895                Normalize(v, n, vn, shift);
 4896
 38813094897                q = new uint[m - n + 1];
 4898
 4899                // Main division loop
 1661761024900                for (var j = m - n; j >= 0; j--)
 792067424901                {
 4902                    int i;
 4903
 792067424904                    var rr = (Base * un[j + n]) + un[j + n - 1];
 792067424905                    var qq = rr / vn[n - 1];
 792067424906                    rr -= qq * vn[n - 1];
 4907
 4908                    for (; ; )
 907289284909                    {
 4910                        // Estimate too big ?
 907289284911                        if ((qq >= Base) || (qq * vn[n - 2] > ((rr * Base) + un[j + n - 2])))
 359318634912                        {
 359318634913                            qq--;
 359318634914                            rr += (ulong)vn[n - 1];
 359318634915                            if (rr < Base)
 115221864916                            {
 115221864917                                continue;
 4918                            }
 244096774919                        }
 4920
 792067424921                        break;
 4922                    }
 4923
 4924                    // Multiply and subtract
 792067424925                    long b = 0;
 4926                    long t;
 986312804927                    for (i = 0; i < n; i++)
 478355904928                    {
 478355904929                        var p = vn[i] * qq;
 478355904930                        t = (long)un[i + j] - (long)(uint)p - b;
 478355904931                        un[i + j] = (uint)t;
 478355904932                        p >>= 32;
 478355904933                        t >>= 32;
 478355904934                        b = (long)p - t;
 478355904935                    }
 4936
 792067424937                    t = (long)un[j + n] - b;
 792067424938                    un[j + n] = (uint)t;
 4939
 4940                    // Store the calculated value
 792067424941                    q[j] = (uint)qq;
 4942
 4943                    // Add back vn[0..n] to un[j..j+n]
 792067424944                    if (t < 0)
 04945                    {
 04946                        q[j]--;
 04947                        ulong c = 0;
 04948                        for (i = 0; i < n; i++)
 04949                        {
 04950                            c = (ulong)vn[i] + un[j + i] + c;
 04951                            un[j + i] = (uint)c;
 04952                            c >>= 32;
 04953                        }
 4954
 04955                        c += (ulong)un[j + n];
 04956                        un[j + n] = (uint)c;
 04957                    }
 792067424958                }
 4959
 38813094960                Unnormalize(un, out r, shift);
 38813094961            }
 4962            else
 36564963            {
 36564964                q = new uint[] { 0 };
 36564965                r = u;
 36564966            }
 39289614967        }
 4968    }
 4969}
Generated by: ReportGenerator 5.2.0.0
11/29/2023 - 11:22:39 AM
GitHub | reportgenerator.io

Methods/Properties

.cctor()
get_BitLength()
ModInverse(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
PositiveMod(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
Random(System.Int32)
.ctor(System.Int16,System.UInt32[])
.ctor(System.Int32)
.ctor(System.UInt32)
.ctor(System.Int64)
.ctor(System.UInt64)
.ctor(System.Double)
.ctor(System.Single)
.ctor(System.Decimal)
.ctor(System.Byte[])
Negative(System.Byte[])
Exponent(System.Byte[])
Mantissa(System.Byte[])
get_IsEven()
get_IsOne()
PopulationCount(System.UInt32)
PopulationCount(System.UInt64)
LeadingZeroCount(System.UInt32)
LeadingZeroCount(System.UInt64)
BuildDouble(System.Int32,System.UInt64,System.Int32)
get_IsPowerOfTwo()
get_IsZero()
get_Sign()
get_MinusOne()
get_One()
get_Zero()
op_Explicit(Renci.SshNet.Common.BigInteger)
op_Explicit(Renci.SshNet.Common.BigInteger)
op_Explicit(Renci.SshNet.Common.BigInteger)
op_Explicit(Renci.SshNet.Common.BigInteger)
op_Explicit(Renci.SshNet.Common.BigInteger)
op_Explicit(Renci.SshNet.Common.BigInteger)
op_Explicit(Renci.SshNet.Common.BigInteger)
op_Explicit(Renci.SshNet.Common.BigInteger)
op_Explicit(Renci.SshNet.Common.BigInteger)
op_Explicit(Renci.SshNet.Common.BigInteger)
op_Explicit(Renci.SshNet.Common.BigInteger)
op_Implicit(System.Int32)
op_Implicit(System.UInt32)
op_Implicit(System.Int16)
op_Implicit(System.UInt16)
op_Implicit(System.Byte)
op_Implicit(System.SByte)
op_Implicit(System.Int64)
op_Implicit(System.UInt64)
op_Explicit(System.Double)
op_Explicit(System.Single)
op_Explicit(System.Decimal)
op_Addition(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_Subtraction(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_Multiply(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_Division(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_Modulus(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_UnaryNegation(Renci.SshNet.Common.BigInteger)
op_UnaryPlus(Renci.SshNet.Common.BigInteger)
op_Increment(Renci.SshNet.Common.BigInteger)
op_Decrement(Renci.SshNet.Common.BigInteger)
op_BitwiseAnd(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_BitwiseOr(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_ExclusiveOr(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_OnesComplement(Renci.SshNet.Common.BigInteger)
BitScanBackward(System.UInt32)
op_LeftShift(Renci.SshNet.Common.BigInteger,System.Int32)
op_RightShift(Renci.SshNet.Common.BigInteger,System.Int32)
op_LessThan(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_LessThan(Renci.SshNet.Common.BigInteger,System.Int64)
op_LessThan(System.Int64,Renci.SshNet.Common.BigInteger)
op_LessThan(Renci.SshNet.Common.BigInteger,System.UInt64)
op_LessThan(System.UInt64,Renci.SshNet.Common.BigInteger)
op_LessThanOrEqual(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_LessThanOrEqual(Renci.SshNet.Common.BigInteger,System.Int64)
op_LessThanOrEqual(System.Int64,Renci.SshNet.Common.BigInteger)
op_LessThanOrEqual(Renci.SshNet.Common.BigInteger,System.UInt64)
op_LessThanOrEqual(System.UInt64,Renci.SshNet.Common.BigInteger)
op_GreaterThan(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_GreaterThan(Renci.SshNet.Common.BigInteger,System.Int64)
op_GreaterThan(System.Int64,Renci.SshNet.Common.BigInteger)
op_GreaterThan(Renci.SshNet.Common.BigInteger,System.UInt64)
op_GreaterThan(System.UInt64,Renci.SshNet.Common.BigInteger)
op_GreaterThanOrEqual(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_GreaterThanOrEqual(Renci.SshNet.Common.BigInteger,System.Int64)
op_GreaterThanOrEqual(System.Int64,Renci.SshNet.Common.BigInteger)
op_GreaterThanOrEqual(Renci.SshNet.Common.BigInteger,System.UInt64)
op_GreaterThanOrEqual(System.UInt64,Renci.SshNet.Common.BigInteger)
op_Equality(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_Equality(Renci.SshNet.Common.BigInteger,System.Int64)
op_Equality(System.Int64,Renci.SshNet.Common.BigInteger)
op_Equality(Renci.SshNet.Common.BigInteger,System.UInt64)
op_Equality(System.UInt64,Renci.SshNet.Common.BigInteger)
op_Inequality(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
op_Inequality(Renci.SshNet.Common.BigInteger,System.Int64)
op_Inequality(System.Int64,Renci.SshNet.Common.BigInteger)
op_Inequality(Renci.SshNet.Common.BigInteger,System.UInt64)
op_Inequality(System.UInt64,Renci.SshNet.Common.BigInteger)
Equals(System.Object)
Equals(Renci.SshNet.Common.BigInteger)
Equals(System.Int64)
Equals(System.UInt64)
ToString()
ToString(System.String)
ToString(System.IFormatProvider)
ToString(System.String,System.IFormatProvider)
ToStringWithPadding(System.String,System.UInt32,System.IFormatProvider)
MakeTwoComplement(System.UInt32[])
ToString(System.UInt32,System.IFormatProvider)
Parse(System.String)
Parse(System.String,System.Globalization.NumberStyles)
Parse(System.String,System.IFormatProvider)
Parse(System.String,System.Globalization.NumberStyles,System.IFormatProvider)
TryParse(System.String,Renci.SshNet.Common.BigInteger&)
TryParse(System.String,System.Globalization.NumberStyles,System.IFormatProvider,Renci.SshNet.Common.BigInteger&)
Parse(System.String,System.Globalization.NumberStyles,System.IFormatProvider,System.Boolean,Renci.SshNet.Common.BigInteger&,System.Exception&)
CheckStyle(System.Globalization.NumberStyles,System.Boolean,System.Exception&)
JumpOverWhitespace(System.Int32&,System.String,System.Boolean,System.Boolean,System.Exception&)
FindSign(System.Int32&,System.String,System.Globalization.NumberFormatInfo,System.Boolean&,System.Boolean&)
FindCurrency(System.Int32&,System.String,System.Globalization.NumberFormatInfo,System.Boolean&)
FindExponent(System.Int32&,System.String,System.Int32&,System.Boolean,System.Exception&)
FindOther(System.Int32&,System.String,System.String)
ValidDigit(System.Char,System.Boolean)
GetFormatException()
ProcessTrailingWhitespace(System.Boolean,System.String,System.Int32,System.Exception&)
Parse(System.String,System.Boolean,Renci.SshNet.Common.BigInteger&,System.Exception&)
Min(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
Max(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
Abs(Renci.SshNet.Common.BigInteger)
DivRem(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger&)
Pow(Renci.SshNet.Common.BigInteger,System.Int32)
ModPow(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
GreatestCommonDivisor(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
Log(Renci.SshNet.Common.BigInteger,System.Double)
Log(Renci.SshNet.Common.BigInteger)
Log10(Renci.SshNet.Common.BigInteger)
GetHashCode()
Add(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
Subtract(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
Multiply(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
Divide(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
Remainder(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
Negate(Renci.SshNet.Common.BigInteger)
CompareTo(System.Object)
CompareTo(Renci.SshNet.Common.BigInteger)
CompareTo(System.UInt64)
CompareTo(System.Int64)
LongCompare(System.UInt32,System.UInt32)
Compare(Renci.SshNet.Common.BigInteger,Renci.SshNet.Common.BigInteger)
TopByte(System.UInt32)
FirstNonFfByte(System.UInt32)
ToByteArray()
CoreAdd(System.UInt32[],System.UInt32[])
CoreAdd(System.UInt32[],System.UInt32)
CoreSub(System.UInt32[],System.UInt32[])
CoreSub(System.UInt32[],System.UInt32)
CoreCompare(System.UInt32[],System.UInt32[])
GetNormalizeShift(System.UInt32)
Normalize(System.UInt32[],System.Int32,System.UInt32[],System.Int32)
Unnormalize(System.UInt32[],System.UInt32[]&,System.Int32)
DivModUnsigned(System.UInt32[],System.UInt32[],System.UInt32[]&,System.UInt32[]&)