< Summary

Information
Class: FixedMathSharp.WideArithmetic
Assembly: FixedMathSharp
File(s): File 1: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Comparison.cs
File 2: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.cs
File 3: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Magnitude.cs
File 4: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Ratio.cs
File 5: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed192.cs
File 6: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed320.cs
File 7: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed576.cs
File 8: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed704.cs
File 9: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed832.cs
Line coverage
100%
Covered lines: 2384
Uncovered lines: 0
Coverable lines: 2384
Total lines: 3908
Line coverage: 100%
Branch coverage
100%
Covered branches: 643
Total branches: 643
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
File 1: GetRoundedNonNegativeNormalizedDepth(...)100%1818100%
File 1: CompareNonNegativeNormalizedDepths(...)100%22100%
File 1: CompareNormalizedDepthToTwiceRaw(...)100%11100%
File 1: CompareSignedNormalizedMagnitudes(...)100%1414100%
File 1: GetSignedMagnitudeAndSquareRootSign(...)100%2020100%
File 1: CompareRadialProjectionDepths(...)100%11100%
File 1: CompareRadialProjectionDepths(...)100%1414100%
File 1: AddSignedRadicand(...)100%88100%
File 1: BuildSquaredRadialDepthNumerator(...)100%11100%
File 1: BuildRadialDepthCrossRadicand(...)100%66100%
File 1: CompareNonNegativeRadicalPairs(...)100%44100%
File 1: ComparePositiveRadicalPairDifference(...)100%44100%
File 1: CompareNonNegativeRadicalSumToRatio(...)100%1010100%
File 1: CompareNonNegativeRadicalToRatio(...)100%11100%
File 1: CompareSignedLinearRadicalToZero(...)100%1212100%
File 1: CompareNonNegativeRadicalToRatio(...)100%11100%
File 1: CompareRadicalCrossTerm(...)100%44100%
File 2: CompareUnsigned(...)100%1212100%
File 2: CompareUnsigned(...)100%2020100%
File 2: TryGetSigned95Magnitude(...)100%22100%
File 2: MultiplySigned95(...)100%66100%
File 2: MultiplyUnsigned128(...)100%22100%
File 2: MultiplyUnsigned96(...)100%11100%
File 2: Multiply64By32(...)100%11100%
File 2: AddProductAt2(...)100%22100%
File 2: AddProductAt3(...)100%11100%
File 2: AccumulateWord(...)100%22100%
File 2: SubtractWord(...)100%11100%
File 2: AddSignedWord(...)100%44100%
File 2: IsZeroMagnitude(...)100%44100%
File 2: GetLinearRadicalSumSign(...)100%2222100%
File 2: GetMultiquadraticSign(...)100%1212100%
File 2: BuildMultiquadraticSquaredDifference(...)100%11100%
File 2: AddMultiquadraticSquare(...)100%1414100%
File 2: AddSignedMagnitude(...)100%88100%
File 3: GetActiveMagnitudeLength(...)100%44100%
File 3: GetMagnitudeBitLength(...)100%22100%
File 3: MultiplyMagnitudes(...)100%88100%
File 3: AddWord(...)100%44100%
File 3: AddEqualMagnitudes(...)100%22100%
File 3: AddMagnitudeInto(...)100%44100%
File 3: SubtractEqualMagnitudes(...)100%22100%
File 3: CompareMagnitudeEqualLength(...)100%66100%
File 4: GetSignedRatioWith64FractionBits(...)100%1616100%
File 4: GetMassRatioBitLength(...)100%44100%
File 4: ShiftMassRatioLeft(...)100%88100%
File 4: ShiftMassRatioRightOne(...)100%22100%
File 4: ShiftMassRatioLeftOne(...)100%22100%
File 5: GetMagnitude(...)100%66100%
File 5: CompareMagnitude(...)100%11100%
File 5: IsMagnitudeAtMost(...)100%11100%
File 5: AddSigned192(...)100%66100%
File 5: Double(...)100%11100%
File 5: SubtractSigned192(...)100%11100%
File 5: Difference(...)100%11100%
File 5: GetFloorSquareRoot(...)100%1515100%
File 5: Scale(...)100%11100%
File 5: Negate(...)100%11100%
File 5: Absolute(...)100%22100%
File 5: ShiftRightToUInt64(...)100%1010100%
File 5: GetFloorSquareRoot192(...)100%1212100%
File 5: ShiftLeft(...)100%22100%
File 5: ShiftLeftOne(...)100%11100%
File 5: ShiftRightOne(...)100%11100%
File 5: GetBitLength(...)100%44100%
File 5: SubtractUnsigned(...)100%11100%
File 6: GetMagnitude(...)100%2020100%
File 6: MultiplySubtract(...)100%88100%
File 6: AddProducts(...)100%11100%
File 6: AddProducts(...)100%11100%
File 6: GetDotProduct3D(...)100%11100%
File 6: AddSigned320(...)100%1212100%
File 6: SubtractSigned320(...)100%11100%
File 6: CompareMagnitude(...)100%11100%
File 6: MultiplySigned192(...)100%2222100%
File 6: CompareNormalizedComponentToMidpoint(...)100%88100%
File 6: ShiftLeft(...)100%22100%
File 6: ShiftLeftOne(...)100%11100%
File 6: ShiftRightOne(...)100%11100%
File 6: GetBitLength(...)100%88100%
File 6: SubtractUnsigned(...)100%11100%
File 7: GetMagnitude(...)100%44100%
File 7: CompareNonNegative(...)100%3636100%
File 7: AddSigned576(...)100%11100%
File 7: Double(...)100%11100%
File 7: SubtractSigned576(...)100%11100%
File 7: MultiplySigned320(...)100%11100%
File 7: MultiplySigned320(...)100%1010100%
File 7: MultiplySigned576(...)100%22100%
File 7: MultiplySigned576(...)100%1010100%
File 7: MultiplySigned576(...)100%11100%
File 7: MultiplySigned576(...)100%11100%
File 7: MultiplySigned576(...)100%11100%
File 7: GetFloorSquareRootScaledByFixed64(...)100%1212100%
File 7: Negate(...)100%11100%
File 7: Absolute(...)100%22100%
File 7: ClampToNonNegative(...)100%11100%
File 7: GetBitLength(...)100%1010100%
File 7: GetMagnitudeBitLength(...)100%66100%
File 7: MultiplySigned576Word(...)100%11100%
File 7: GetBitPair(...)100%99100%
File 7: ShiftLeft(...)100%22100%
File 7: MultiplyNonNegativeToSigned576(...)100%11100%
File 8: GetMagnitude(...)100%44100%
File 8: MultiplySigned576ToSigned704(...)100%11100%
File 8: MultiplyNonNegative(...)100%11100%
File 8: GetFloorSquareRoot(...)100%66100%
File 8: AddSigned704(...)100%11100%
File 8: SubtractSigned704(...)100%11100%
File 8: CompareNonNegative(...)100%4444100%
File 8: MultiplySigned320(...)100%44100%
File 8: CopyMagnitude(...)100%11100%
File 8: CreateSigned704(...)100%11100%
File 8: ApplySigned704Sign(...)100%44100%
File 8: GetBitLength(...)100%2020100%
File 8: GetBitLength(...)100%22100%
File 8: GetBitPair(...)100%1111100%
File 8: GetBitPair(...)100%11100%
File 8: ShiftLeftMagnitude(...)100%22100%
File 9: GetMagnitude(...)100%44100%
File 9: AddSigned832(...)100%11100%
File 9: CompareNonNegativeSquaredRatios(...)100%11100%
File 9: CompareNonNegativeProducts(...)100%11100%
File 9: MultiplySigned576ToSigned832(...)100%11100%
File 9: MultiplySigned576ToSigned832(...)100%11100%
File 9: MultiplySigned704ToSigned832(...)100%11100%
File 9: MultiplySigned704ToSigned832(...)100%11100%
File 9: MultiplySigned704ToSigned832(...)100%11100%
File 9: MultiplySigned832(...)100%11100%
File 9: SubtractSigned832(...)100%11100%
File 9: GetFloorSquareRootOfProduct(...)100%88100%
File 9: CreateSigned832(...)100%11100%
File 9: ApplySigned832Sign(...)100%44100%
File 9: MultiplyNonNegativeToSigned832(...)100%11100%

File(s)

/home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Comparison.cs

#LineLine coverage
 1//=======================================================================
 2// WideArithmetic.Comparison.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024–present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9
 10namespace FixedMathSharp;
 11
 12/// <content>
 13/// Comparison helpers for wide fixed-point arithmetic, including normalized
 14/// depth rounding and comparisons against wide intermediate representations.
 15/// </content>
 16internal static partial class WideArithmetic
 17{
 18    #region Normalized Depth Comparison
 19
 20    /// <summary>
 21    /// Rounds a nonnegative depth represented as
 22    /// <c>overlap / (commonDenominator * sqrt(squaredAxisLength))</c>
 23    /// to the nearest raw Q32.32 value with ties to even.
 24    /// </summary>
 25    /// <remarks>
 26    /// Squared axis lengths at least <c>(2^31)^2</c> use a constant-time floor
 27    /// root approximation whose error is less than one raw result unit, then
 28    /// one exact midpoint correction. Smaller nonzero axes use an exact binary
 29    /// search over the representable nonnegative raw domain. Both paths apply
 30    /// exact clamping classification and nearest-even midpoint admission.
 31    /// </remarks>
 32    internal static Fixed64 GetRoundedNonNegativeNormalizedDepth(
 33        Signed576 overlap,
 34        Signed576 squaredAxisLength,
 35        Signed320 commonDenominator,
 36        out bool isClamped)
 37    {
 51738        Signed192 maximumTwiceRaw = AddSigned192(
 51739            Signed192.Signed(long.MaxValue),
 51740            Signed192.Signed(long.MaxValue));
 51741        if (CompareNormalizedDepthToTwiceRaw(
 51742                overlap,
 51743                squaredAxisLength,
 51744                commonDenominator,
 51745                maximumTwiceRaw) > 0)
 46        {
 1147            isClamped = true;
 1148            return Fixed64.MaxValue;
 49        }
 50
 50651        Signed576 approximationThreshold = Signed576.ExtendValue(
 50652            Signed320.ExtendValue(Signed192.Signed(1L << 62)));
 50653        if (CompareNonNegative(
 50654                squaredAxisLength,
 50655                approximationThreshold) < 0)
 56        {
 3957            long low = 0L;
 3958            long high = long.MaxValue;
 249659            while (low < high)
 60            {
 245761                long candidate = (long)(
 245762                    ((ulong)low + (ulong)high + 1UL) >> 1);
 245763                Signed192 candidateLowerMidpoint = SubtractSigned192(
 245764                    AddSigned192(
 245765                        Signed192.Signed(candidate),
 245766                        Signed192.Signed(candidate)),
 245767                    Signed192.Signed(1L));
 245768                int candidateComparison = CompareNormalizedDepthToTwiceRaw(
 245769                    overlap,
 245770                    squaredAxisLength,
 245771                    commonDenominator,
 245772                    candidateLowerMidpoint);
 245773                bool roundsAtLeastCandidate = candidateComparison > 0
 245774                    || (candidateComparison == 0
 245775                        && (candidate & 1L) == 0L);
 245776                if (roundsAtLeastCandidate)
 118977                    low = candidate;
 78                else
 126879                    high = candidate - 1L;
 80            }
 81
 3982            isClamped = false;
 3983            return Fixed64.FromRaw(low);
 84        }
 85
 46786        Signed320 scaledAxisLength =
 46787            GetFloorSquareRootScaledByFixed64(squaredAxisLength);
 46788        Signed576 scaledDenominator = MultiplySigned320(
 46789            scaledAxisLength,
 46790            commonDenominator);
 46791        if (!Fixed64.TryGetSignedRawRatio(
 46792                Signed832.ExtendValue(overlap),
 46793                Signed832.ExtendValue(scaledDenominator),
 46794                FixedMath.SHIFT_AMOUNT_I,
 46795                out Fixed64 depth))
 96        {
 97            // The floor root can place a representable exact result one raw
 98            // unit above the scalar domain. The exact midpoint correction
 99            // below distinguishes MaxValue from MaxValue - one raw unit.
 1100            depth = Fixed64.MaxValue;
 101        }
 467102        isClamped = false;
 467103        if (depth == Fixed64.Zero)
 7104            return depth;
 105
 460106        Signed192 lowerMidpoint = SubtractSigned192(
 460107            AddSigned192(
 460108                Signed192.Signed(depth.m_rawValue),
 460109                Signed192.Signed(depth.m_rawValue)),
 460110            Signed192.Signed(1L));
 460111        int comparison = CompareNormalizedDepthToTwiceRaw(
 460112            overlap,
 460113            squaredAxisLength,
 460114            commonDenominator,
 460115            lowerMidpoint);
 460116        if (comparison < (depth.m_rawValue & 1L))
 117        {
 34118            depth = Fixed64.FromRaw(depth.m_rawValue - 1L);
 119        }
 120
 460121        return depth;
 122    }
 123
 124    /// <summary>
 125    /// Compares nonnegative depths represented as
 126    /// <c>overlap / (commonDenominator * sqrt(squaredAxisLength))</c>.
 127    /// </summary>
 128    internal static int CompareNonNegativeNormalizedDepths(
 129        Signed576 leftOverlap,
 130        Signed576 leftSquaredAxisLength,
 131        Signed320 leftCommonDenominator,
 132        Signed576 rightOverlap,
 133        Signed576 rightSquaredAxisLength,
 134        Signed320 rightCommonDenominator)
 135    {
 8984136        Span<ulong> leftOverlapWords = stackalloc ulong[9];
 8984137        Span<ulong> rightOverlapWords = stackalloc ulong[9];
 8984138        Span<ulong> leftAxisWords = stackalloc ulong[9];
 8984139        Span<ulong> rightAxisWords = stackalloc ulong[9];
 8984140        GetMagnitude(leftOverlap, leftOverlapWords);
 8984141        GetMagnitude(rightOverlap, rightOverlapWords);
 8984142        GetMagnitude(leftSquaredAxisLength, leftAxisWords);
 8984143        GetMagnitude(rightSquaredAxisLength, rightAxisWords);
 144
 8984145        if (leftCommonDenominator.Equals(rightCommonDenominator))
 146        {
 8983147            return CompareSignedNormalizedMagnitudes(
 8983148                leftOverlapWords,
 8983149                leftOverlap.Sign,
 8983150                leftAxisWords,
 8983151                rightOverlapWords,
 8983152                rightOverlap.Sign,
 8983153                rightAxisWords);
 154        }
 155
 1156        Span<ulong> leftCommonWords = stackalloc ulong[5];
 1157        Span<ulong> rightCommonWords = stackalloc ulong[5];
 1158        GetMagnitude(
 1159            leftCommonDenominator,
 1160            out leftCommonWords[4],
 1161            out leftCommonWords[3],
 1162            out leftCommonWords[2],
 1163            out leftCommonWords[1],
 1164            out leftCommonWords[0]);
 1165        GetMagnitude(
 1166            rightCommonDenominator,
 1167            out rightCommonWords[4],
 1168            out rightCommonWords[3],
 1169            out rightCommonWords[2],
 1170            out rightCommonWords[1],
 1171            out rightCommonWords[0]);
 172
 1173        Span<ulong> leftOverlapSquared = stackalloc ulong[18];
 1174        Span<ulong> rightOverlapSquared = stackalloc ulong[18];
 1175        Span<ulong> leftCommonSquared = stackalloc ulong[10];
 1176        Span<ulong> rightCommonSquared = stackalloc ulong[10];
 1177        MultiplyMagnitudes(
 1178            leftOverlapWords,
 1179            leftOverlapWords,
 1180            leftOverlapSquared);
 1181        MultiplyMagnitudes(
 1182            rightOverlapWords,
 1183            rightOverlapWords,
 1184            rightOverlapSquared);
 1185        MultiplyMagnitudes(
 1186            leftCommonWords,
 1187            leftCommonWords,
 1188            leftCommonSquared);
 1189        MultiplyMagnitudes(
 1190            rightCommonWords,
 1191            rightCommonWords,
 1192            rightCommonSquared);
 193
 1194        Span<ulong> leftScaledOnce = stackalloc ulong[28];
 1195        Span<ulong> rightScaledOnce = stackalloc ulong[28];
 1196        Span<ulong> leftScaled = stackalloc ulong[40];
 1197        Span<ulong> rightScaled = stackalloc ulong[40];
 1198        MultiplyMagnitudes(
 1199            leftOverlapSquared,
 1200            rightCommonSquared,
 1201            leftScaledOnce);
 1202        MultiplyMagnitudes(
 1203            rightOverlapSquared,
 1204            leftCommonSquared,
 1205            rightScaledOnce);
 1206        MultiplyMagnitudes(
 1207            leftScaledOnce,
 1208            rightAxisWords,
 1209            leftScaled);
 1210        MultiplyMagnitudes(
 1211            rightScaledOnce,
 1212            leftAxisWords,
 1213            rightScaled);
 1214        return CompareMagnitudeEqualLength(leftScaled, rightScaled);
 215    }
 216
 217    private static int CompareNormalizedDepthToTwiceRaw(
 218        Signed576 overlap,
 219        Signed576 squaredAxisLength,
 220        Signed320 commonDenominator,
 221        Signed192 twiceRaw)
 222    {
 3434223        Span<ulong> overlapWords = stackalloc ulong[9];
 3434224        Span<ulong> axisWords = stackalloc ulong[9];
 3434225        Span<ulong> commonWords = stackalloc ulong[5];
 3434226        Span<ulong> twiceRawWords = stackalloc ulong[3];
 3434227        GetMagnitude(overlap, overlapWords);
 3434228        GetMagnitude(squaredAxisLength, axisWords);
 3434229        GetMagnitude(
 3434230            commonDenominator,
 3434231            out commonWords[4],
 3434232            out commonWords[3],
 3434233            out commonWords[2],
 3434234            out commonWords[1],
 3434235            out commonWords[0]);
 3434236        GetMagnitude(
 3434237            twiceRaw,
 3434238            out twiceRawWords[2],
 3434239            out twiceRawWords[1],
 3434240            out twiceRawWords[0]);
 241
 3434242        Span<ulong> left = stackalloc ulong[25];
 3434243        MultiplyMagnitudes(overlapWords, overlapWords, left);
 3434244        ShiftLeftMagnitude(left, 2);
 245
 3434246        Span<ulong> commonSquared = stackalloc ulong[10];
 3434247        Span<ulong> twiceRawSquared = stackalloc ulong[6];
 3434248        Span<ulong> thresholdSquared = stackalloc ulong[16];
 3434249        Span<ulong> right = stackalloc ulong[25];
 3434250        MultiplyMagnitudes(commonWords, commonWords, commonSquared);
 3434251        MultiplyMagnitudes(
 3434252            twiceRawWords,
 3434253            twiceRawWords,
 3434254            twiceRawSquared);
 3434255        MultiplyMagnitudes(
 3434256            commonSquared,
 3434257            twiceRawSquared,
 3434258            thresholdSquared);
 3434259        MultiplyMagnitudes(thresholdSquared, axisWords, right);
 3434260        return CompareMagnitudeEqualLength(left, right);
 261    }
 262
 263    #endregion
 264
 265    #region Normalized Magnitude Comparison
 266
 267    /// <summary>
 268    /// Compares signed ratios of the form
 269    /// <c>numerator / sqrt(squaredAxisLength)</c>.
 270    /// </summary>
 271    internal static int CompareSignedNormalizedMagnitudes(
 272        ReadOnlySpan<ulong> leftNumerator,
 273        int leftSign,
 274        ReadOnlySpan<ulong> leftSquaredAxisLength,
 275        ReadOnlySpan<ulong> rightNumerator,
 276        int rightSign,
 277        ReadOnlySpan<ulong> rightSquaredAxisLength)
 278    {
 49693279        leftSign = leftSign == 0 || IsZeroMagnitude(leftNumerator)
 49693280            ? 0
 49693281            : leftSign;
 49693282        rightSign = rightSign == 0 || IsZeroMagnitude(rightNumerator)
 49693283            ? 0
 49693284            : rightSign;
 49693285        if (leftSign != rightSign)
 1301286            return leftSign.CompareTo(rightSign);
 48392287        if (leftSign == 0)
 53288            return 0;
 289
 48339290        int wordCount = Math.Max(
 48339291            Math.Max(leftNumerator.Length, rightNumerator.Length),
 48339292            Math.Max(
 48339293                leftSquaredAxisLength.Length,
 48339294                rightSquaredAxisLength.Length));
 48339295        int productWordCount = wordCount * 3;
 48339296        Span<ulong> products =
 48339297            stackalloc ulong[productWordCount * 2];
 48339298        Span<ulong> square = stackalloc ulong[wordCount * 2];
 48339299        Span<ulong> paddedNumerator = stackalloc ulong[wordCount];
 48339300        Span<ulong> paddedAxis = stackalloc ulong[wordCount];
 301
 48339302        paddedNumerator.Clear();
 48339303        leftNumerator.CopyTo(paddedNumerator);
 48339304        MultiplyMagnitudes(
 48339305            paddedNumerator,
 48339306            paddedNumerator,
 48339307            square);
 48339308        paddedAxis.Clear();
 48339309        rightSquaredAxisLength.CopyTo(paddedAxis);
 48339310        MultiplyMagnitudes(
 48339311            square,
 48339312            paddedAxis,
 48339313            products.Slice(0, productWordCount));
 314
 48339315        paddedNumerator.Clear();
 48339316        rightNumerator.CopyTo(paddedNumerator);
 48339317        MultiplyMagnitudes(
 48339318            paddedNumerator,
 48339319            paddedNumerator,
 48339320            square);
 48339321        paddedAxis.Clear();
 48339322        leftSquaredAxisLength.CopyTo(paddedAxis);
 48339323        MultiplyMagnitudes(
 48339324            square,
 48339325            paddedAxis,
 48339326            products.Slice(
 48339327                productWordCount,
 48339328                productWordCount));
 329
 48339330        int comparison = CompareMagnitudeEqualLength(
 48339331            products.Slice(0, productWordCount),
 48339332            products.Slice(productWordCount, productWordCount));
 48339333        return leftSign > 0 ? comparison : -comparison;
 334    }
 335
 336    /// <summary>
 337    /// Gets the exact sign of
 338    /// <c>rational + coefficient * sqrt(squaredRadicand)</c>.
 339    /// </summary>
 340    internal static int GetSignedMagnitudeAndSquareRootSign(
 341        ReadOnlySpan<ulong> rational,
 342        int rationalSign,
 343        ReadOnlySpan<ulong> coefficient,
 344        int coefficientSign,
 345        ReadOnlySpan<ulong> squaredRadicand)
 346    {
 4619347        rationalSign = rationalSign == 0 || IsZeroMagnitude(rational)
 4619348            ? 0
 4619349            : rationalSign;
 4619350        coefficientSign =
 4619351            coefficientSign == 0
 4619352            || IsZeroMagnitude(coefficient)
 4619353            || IsZeroMagnitude(squaredRadicand)
 4619354                ? 0
 4619355                : coefficientSign;
 4619356        if (rationalSign == 0)
 357357            return coefficientSign;
 4262358        if (coefficientSign == 0 || rationalSign == coefficientSign)
 1715359            return rationalSign;
 360
 2547361        int wordCount = Math.Max(
 2547362            Math.Max(rational.Length, coefficient.Length),
 2547363            squaredRadicand.Length);
 2547364        int productWordCount = wordCount * 3;
 2547365        Span<ulong> products =
 2547366            stackalloc ulong[productWordCount * 2];
 2547367        products.Clear();
 2547368        Span<ulong> padded = stackalloc ulong[wordCount];
 2547369        Span<ulong> square = stackalloc ulong[wordCount * 2];
 370
 2547371        padded.Clear();
 2547372        rational.CopyTo(padded);
 2547373        MultiplyMagnitudes(padded, padded, square);
 2547374        square.CopyTo(products);
 375
 2547376        padded.Clear();
 2547377        coefficient.CopyTo(padded);
 2547378        MultiplyMagnitudes(padded, padded, square);
 2547379        padded.Clear();
 2547380        squaredRadicand.CopyTo(padded);
 2547381        MultiplyMagnitudes(
 2547382            square,
 2547383            padded,
 2547384            products.Slice(
 2547385                productWordCount,
 2547386                productWordCount));
 387
 2547388        int comparison = CompareMagnitudeEqualLength(
 2547389            products.Slice(0, productWordCount),
 2547390            products.Slice(productWordCount, productWordCount));
 2547391        if (comparison == 0)
 1164392            return 0;
 1383393        return comparison > 0
 1383394            ? rationalSign
 1383395            : coefficientSign;
 396    }
 397
 398    #endregion
 399
 400    #region Radial Projection Comparison
 401
 402    private const int RadialProjectionWordCount = 96;
 403
 404    /// <summary>
 405    /// Compares two nonnegative radial projection depths without materializing
 406    /// either radical.
 407    /// </summary>
 408    /// <remarks>
 409    /// Each depth has the form
 410    /// (rational + common * sqrt(radicandNumerator / radicandDenominator)) /
 411    /// (common * sqrt(axisSquared)). The comparison squares the nonnegative
 412    /// depths and reduces the result to at most two radicals on either side.
 413    /// </remarks>
 414    internal static int CompareRadialProjectionDepths(
 415        Signed576 leftRational,
 416        Signed832 leftRadicandNumerator,
 417        Signed576 leftRadicandDenominator,
 418        Signed576 leftAxisSquared,
 419        Signed576 rightRational,
 420        Signed832 rightRadicandNumerator,
 421        Signed576 rightRadicandDenominator,
 422        Signed576 rightAxisSquared,
 423        Signed192 common)
 424    {
 2161425        Signed320 radialCoefficient = Signed320.ExtendValue(common);
 2161426        return CompareRadialProjectionDepths(
 2161427            Signed704.ExtendValue(leftRational),
 2161428            radialCoefficient,
 2161429            leftRadicandNumerator,
 2161430            leftRadicandDenominator,
 2161431            leftAxisSquared,
 2161432            Signed704.ExtendValue(rightRational),
 2161433            radialCoefficient,
 2161434            rightRadicandNumerator,
 2161435            rightRadicandDenominator,
 2161436            rightAxisSquared);
 437    }
 438
 439    /// <summary>
 440    /// Compares two nonnegative radial projection depths without materializing
 441    /// either radical.
 442    /// </summary>
 443    /// <remarks>
 444    /// Each depth has the form
 445    /// (rational + radialCoefficient *
 446    /// sqrt(radicandNumerator / radicandDenominator)) /
 447    /// sqrt(axisSquared). Any shared positive denominator has already been
 448    /// omitted because it cannot change the ordering.
 449    /// </remarks>
 450    internal static int CompareRadialProjectionDepths(
 451        Signed704 leftRational,
 452        Signed320 leftRadialCoefficient,
 453        Signed832 leftRadicandNumerator,
 454        Signed576 leftRadicandDenominator,
 455        Signed576 leftAxisSquared,
 456        Signed704 rightRational,
 457        Signed320 rightRadialCoefficient,
 458        Signed832 rightRadicandNumerator,
 459        Signed576 rightRadicandDenominator,
 460        Signed576 rightAxisSquared)
 461    {
 6717462        Span<ulong> leftBase =
 6717463            stackalloc ulong[RadialProjectionWordCount];
 6717464        Span<ulong> rightBase =
 6717465            stackalloc ulong[RadialProjectionWordCount];
 6717466        BuildSquaredRadialDepthNumerator(
 6717467            leftRational,
 6717468            leftRadialCoefficient,
 6717469            leftRadicandNumerator,
 6717470            leftRadicandDenominator,
 6717471            rightAxisSquared,
 6717472            rightRadicandDenominator,
 6717473            leftBase);
 6717474        BuildSquaredRadialDepthNumerator(
 6717475            rightRational,
 6717476            rightRadialCoefficient,
 6717477            rightRadicandNumerator,
 6717478            rightRadicandDenominator,
 6717479            leftAxisSquared,
 6717480            leftRadicandDenominator,
 6717481            rightBase);
 482
 6717483        int baseComparison = CompareMagnitudeEqualLength(
 6717484            leftBase,
 6717485            rightBase);
 6717486        Span<ulong> baseMagnitude =
 6717487            stackalloc ulong[RadialProjectionWordCount];
 6717488        if (baseComparison >= 0)
 489        {
 5212490            SubtractEqualMagnitudes(
 5212491                leftBase,
 5212492                rightBase,
 5212493                baseMagnitude);
 494        }
 495        else
 496        {
 1505497            SubtractEqualMagnitudes(
 1505498                rightBase,
 1505499                leftBase,
 1505500                baseMagnitude);
 501        }
 502
 6717503        Span<ulong> baseRadicand =
 6717504            stackalloc ulong[RadialProjectionWordCount];
 6717505        MultiplyMagnitudes(
 6717506            baseMagnitude,
 6717507            baseMagnitude,
 6717508            baseRadicand);
 6717509        Span<ulong> leftRadicand =
 6717510            stackalloc ulong[RadialProjectionWordCount];
 6717511        BuildRadialDepthCrossRadicand(
 6717512            leftRadialCoefficient,
 6717513            rightAxisSquared,
 6717514            rightRadicandDenominator,
 6717515            leftRational,
 6717516            leftRadicandNumerator,
 6717517            leftRadicandDenominator,
 6717518            leftRadicand);
 6717519        Span<ulong> rightRadicand =
 6717520            stackalloc ulong[RadialProjectionWordCount];
 6717521        BuildRadialDepthCrossRadicand(
 6717522            rightRadialCoefficient,
 6717523            leftAxisSquared,
 6717524            leftRadicandDenominator,
 6717525            rightRational,
 6717526            rightRadicandNumerator,
 6717527            rightRadicandDenominator,
 6717528            rightRadicand);
 529
 6717530        int baseSign = IsZeroMagnitude(baseRadicand)
 6717531            ? 0
 6717532            : baseComparison;
 6717533        int leftSign = IsZeroMagnitude(leftRadicand)
 6717534            ? 0
 6717535            : leftRational.Sign;
 6717536        int rightSign = IsZeroMagnitude(rightRadicand)
 6717537            ? 0
 6717538            : -rightRational.Sign;
 6717539        int positiveCount =
 6717540            (baseSign > 0 ? 1 : 0)
 6717541            + (leftSign > 0 ? 1 : 0)
 6717542            + (rightSign > 0 ? 1 : 0);
 6717543        int negativeCount =
 6717544            (baseSign < 0 ? 1 : 0)
 6717545            + (leftSign < 0 ? 1 : 0)
 6717546            + (rightSign < 0 ? 1 : 0);
 6717547        if (positiveCount == 0)
 1896548            return negativeCount == 0 ? 0 : -1;
 4821549        if (negativeCount == 0)
 955550            return 1;
 551
 3866552        Span<ulong> positiveFirst =
 3866553            stackalloc ulong[RadialProjectionWordCount];
 3866554        Span<ulong> positiveSecond =
 3866555            stackalloc ulong[RadialProjectionWordCount];
 3866556        Span<ulong> negativeFirst =
 3866557            stackalloc ulong[RadialProjectionWordCount];
 3866558        Span<ulong> negativeSecond =
 3866559            stackalloc ulong[RadialProjectionWordCount];
 3866560        positiveFirst.Clear();
 3866561        positiveSecond.Clear();
 3866562        negativeFirst.Clear();
 3866563        negativeSecond.Clear();
 3866564        int positiveIndex = 0;
 3866565        int negativeIndex = 0;
 3866566        AddSignedRadicand(
 3866567            baseRadicand,
 3866568            baseSign,
 3866569            positiveFirst,
 3866570            positiveSecond,
 3866571            negativeFirst,
 3866572            negativeSecond,
 3866573            ref positiveIndex,
 3866574            ref negativeIndex);
 3866575        AddSignedRadicand(
 3866576            leftRadicand,
 3866577            leftSign,
 3866578            positiveFirst,
 3866579            positiveSecond,
 3866580            negativeFirst,
 3866581            negativeSecond,
 3866582            ref positiveIndex,
 3866583            ref negativeIndex);
 3866584        AddSignedRadicand(
 3866585            rightRadicand,
 3866586            rightSign,
 3866587            positiveFirst,
 3866588            positiveSecond,
 3866589            negativeFirst,
 3866590            negativeSecond,
 3866591            ref positiveIndex,
 3866592            ref negativeIndex);
 3866593        return CompareNonNegativeRadicalPairs(
 3866594            positiveFirst,
 3866595            positiveSecond,
 3866596            negativeFirst,
 3866597            negativeSecond);
 598    }
 599
 600    private static void AddSignedRadicand(
 601        ReadOnlySpan<ulong> radicand,
 602        int sign,
 603        Span<ulong> positiveFirst,
 604        Span<ulong> positiveSecond,
 605        Span<ulong> negativeFirst,
 606        Span<ulong> negativeSecond,
 607        ref int positiveIndex,
 608        ref int negativeIndex)
 609    {
 11598610        if (sign == 0)
 1937611            return;
 612
 9661613        if (sign > 0)
 614        {
 4816615            radicand.CopyTo(
 4816616                positiveIndex++ == 0
 4816617                    ? positiveFirst
 4816618                    : positiveSecond);
 4816619            return;
 620        }
 621
 4845622        radicand.CopyTo(
 4845623            negativeIndex++ == 0
 4845624                ? negativeFirst
 4845625                : negativeSecond);
 4845626    }
 627
 628    private static void BuildSquaredRadialDepthNumerator(
 629        Signed704 rational,
 630        Signed320 radialCoefficient,
 631        Signed832 radicandNumerator,
 632        Signed576 radicandDenominator,
 633        Signed576 otherAxisSquared,
 634        Signed576 otherRadicandDenominator,
 635        Span<ulong> result)
 636    {
 13434637        result.Clear();
 13434638        Span<ulong> rationalWords = stackalloc ulong[11];
 13434639        Span<ulong> radialCoefficientWords = stackalloc ulong[5];
 13434640        Span<ulong> numeratorWords = stackalloc ulong[13];
 13434641        Span<ulong> denominatorWords = stackalloc ulong[9];
 13434642        Span<ulong> axisWords = stackalloc ulong[9];
 13434643        Span<ulong> otherDenominatorWords = stackalloc ulong[9];
 13434644        GetMagnitude(rational, rationalWords);
 13434645        GetMagnitude(
 13434646            radialCoefficient,
 13434647            out radialCoefficientWords[4],
 13434648            out radialCoefficientWords[3],
 13434649            out radialCoefficientWords[2],
 13434650            out radialCoefficientWords[1],
 13434651            out radialCoefficientWords[0]);
 13434652        GetMagnitude(radicandNumerator, numeratorWords);
 13434653        GetMagnitude(radicandDenominator, denominatorWords);
 13434654        GetMagnitude(otherAxisSquared, axisWords);
 13434655        GetMagnitude(
 13434656            otherRadicandDenominator,
 13434657            otherDenominatorWords);
 658
 13434659        Span<ulong> rationalSquared = stackalloc ulong[22];
 13434660        Span<ulong> rationalTerm = stackalloc ulong[31];
 13434661        MultiplyMagnitudes(
 13434662            rationalWords,
 13434663            rationalWords,
 13434664            rationalSquared);
 13434665        MultiplyMagnitudes(
 13434666            rationalSquared,
 13434667            denominatorWords,
 13434668            rationalTerm);
 669
 13434670        Span<ulong> coefficientSquared = stackalloc ulong[10];
 13434671        Span<ulong> radialTerm = stackalloc ulong[23];
 13434672        MultiplyMagnitudes(
 13434673            radialCoefficientWords,
 13434674            radialCoefficientWords,
 13434675            coefficientSquared);
 13434676        MultiplyMagnitudes(
 13434677            coefficientSquared,
 13434678            numeratorWords,
 13434679            radialTerm);
 680
 13434681        Span<ulong> numerator = stackalloc ulong[32];
 13434682        numerator.Clear();
 13434683        AddMagnitudeInto(rationalTerm, numerator);
 13434684        AddMagnitudeInto(radialTerm, numerator);
 13434685        Span<ulong> axisScaled = stackalloc ulong[41];
 13434686        Span<ulong> fullyScaled = stackalloc ulong[50];
 13434687        MultiplyMagnitudes(
 13434688            numerator,
 13434689            axisWords,
 13434690            axisScaled);
 13434691        MultiplyMagnitudes(
 13434692            axisScaled,
 13434693            otherDenominatorWords,
 13434694            fullyScaled);
 13434695        fullyScaled.CopyTo(result);
 13434696    }
 697
 698    private static void BuildRadialDepthCrossRadicand(
 699        Signed320 radialCoefficient,
 700        Signed576 otherAxisSquared,
 701        Signed576 otherRadicandDenominator,
 702        Signed704 rational,
 703        Signed832 radicandNumerator,
 704        Signed576 radicandDenominator,
 705        Span<ulong> result)
 706    {
 13434707        if (radialCoefficient.IsZero
 13434708            || rational.IsZero
 13434709            || radicandNumerator.IsZero)
 710        {
 4647711            result.Clear();
 4647712            return;
 713        }
 714
 8787715        Span<ulong> radialCoefficientWords = stackalloc ulong[5];
 8787716        Span<ulong> axisWords = stackalloc ulong[9];
 8787717        Span<ulong> otherDenominatorWords = stackalloc ulong[9];
 8787718        Span<ulong> rationalWords = stackalloc ulong[11];
 8787719        Span<ulong> numeratorWords = stackalloc ulong[13];
 8787720        Span<ulong> denominatorWords = stackalloc ulong[9];
 8787721        GetMagnitude(
 8787722            radialCoefficient,
 8787723            out radialCoefficientWords[4],
 8787724            out radialCoefficientWords[3],
 8787725            out radialCoefficientWords[2],
 8787726            out radialCoefficientWords[1],
 8787727            out radialCoefficientWords[0]);
 8787728        GetMagnitude(otherAxisSquared, axisWords);
 8787729        GetMagnitude(
 8787730            otherRadicandDenominator,
 8787731            otherDenominatorWords);
 8787732        GetMagnitude(rational, rationalWords);
 8787733        GetMagnitude(radicandNumerator, numeratorWords);
 8787734        GetMagnitude(radicandDenominator, denominatorWords);
 735
 8787736        Span<ulong> coefficientAndAxis = stackalloc ulong[14];
 8787737        Span<ulong> withRational = stackalloc ulong[25];
 8787738        Span<ulong> completeCoefficient = stackalloc ulong[34];
 8787739        Span<ulong> coefficientSquared = stackalloc ulong[68];
 8787740        Span<ulong> withNumerator = stackalloc ulong[81];
 8787741        MultiplyMagnitudes(
 8787742            radialCoefficientWords,
 8787743            axisWords,
 8787744            coefficientAndAxis);
 8787745        MultiplyMagnitudes(
 8787746            coefficientAndAxis,
 8787747            rationalWords,
 8787748            withRational);
 8787749        MultiplyMagnitudes(
 8787750            withRational,
 8787751            otherDenominatorWords,
 8787752            completeCoefficient);
 8787753        MultiplyMagnitudes(
 8787754            completeCoefficient,
 8787755            completeCoefficient,
 8787756            coefficientSquared);
 8787757        MultiplyMagnitudes(
 8787758            coefficientSquared,
 8787759            numeratorWords,
 8787760            withNumerator);
 8787761        MultiplyMagnitudes(
 8787762            withNumerator,
 8787763            denominatorWords,
 8787764            result);
 8787765        ShiftLeftMagnitude(result, 2);
 8787766    }
 767
 768    private static int CompareNonNegativeRadicalPairs(
 769        ReadOnlySpan<ulong> leftFirst,
 770        ReadOnlySpan<ulong> leftSecond,
 771        ReadOnlySpan<ulong> rightFirst,
 772        ReadOnlySpan<ulong> rightSecond)
 773    {
 3866774        Span<ulong> leftBase =
 3866775            stackalloc ulong[RadialProjectionWordCount];
 3866776        Span<ulong> rightBase =
 3866777            stackalloc ulong[RadialProjectionWordCount];
 3866778        AddEqualMagnitudes(leftFirst, leftSecond, leftBase);
 3866779        AddEqualMagnitudes(rightFirst, rightSecond, rightBase);
 3866780        int baseComparison = CompareMagnitudeEqualLength(
 3866781            leftBase,
 3866782            rightBase);
 3866783        Span<ulong> baseMagnitude =
 3866784            stackalloc ulong[RadialProjectionWordCount];
 3866785        if (baseComparison >= 0)
 786        {
 2966787            SubtractEqualMagnitudes(
 2966788                leftBase,
 2966789                rightBase,
 2966790                baseMagnitude);
 791        }
 792        else
 793        {
 900794            SubtractEqualMagnitudes(
 900795                rightBase,
 900796                leftBase,
 900797                baseMagnitude);
 798        }
 799
 3866800        Span<ulong> leftProduct =
 3866801            stackalloc ulong[RadialProjectionWordCount * 2];
 3866802        Span<ulong> rightProduct =
 3866803            stackalloc ulong[RadialProjectionWordCount * 2];
 3866804        MultiplyMagnitudes(leftFirst, leftSecond, leftProduct);
 3866805        MultiplyMagnitudes(rightFirst, rightSecond, rightProduct);
 3866806        if (baseComparison >= 0)
 807        {
 2966808            return ComparePositiveRadicalPairDifference(
 2966809                baseMagnitude,
 2966810                leftProduct,
 2966811                rightProduct);
 812        }
 813
 900814        return -ComparePositiveRadicalPairDifference(
 900815            baseMagnitude,
 900816            rightProduct,
 900817            leftProduct);
 818    }
 819
 820    private static int ComparePositiveRadicalPairDifference(
 821        ReadOnlySpan<ulong> positiveBase,
 822        ReadOnlySpan<ulong> sameSideProduct,
 823        ReadOnlySpan<ulong> oppositeSideProduct)
 824    {
 3866825        Span<ulong> baseSquared =
 3866826            stackalloc ulong[RadialProjectionWordCount * 2];
 3866827        Span<ulong> fourSame =
 3866828            stackalloc ulong[RadialProjectionWordCount * 2];
 3866829        Span<ulong> fourOpposite =
 3866830            stackalloc ulong[RadialProjectionWordCount * 2];
 3866831        MultiplyMagnitudes(
 3866832            positiveBase,
 3866833            positiveBase,
 3866834            baseSquared);
 3866835        sameSideProduct.CopyTo(fourSame);
 3866836        oppositeSideProduct.CopyTo(fourOpposite);
 3866837        ShiftLeftMagnitude(fourSame, 2);
 3866838        ShiftLeftMagnitude(fourOpposite, 2);
 839
 3866840        Span<ulong> knownLeft =
 3866841            stackalloc ulong[RadialProjectionWordCount * 2];
 3866842        AddEqualMagnitudes(baseSquared, fourSame, knownLeft);
 3866843        int knownComparison = CompareMagnitudeEqualLength(
 3866844            knownLeft,
 3866845            fourOpposite);
 3866846        if (knownComparison > 0)
 2393847            return 1;
 1473848        if (knownComparison == 0)
 849        {
 850            // This reducer partitions three signed radical terms. Therefore
 851            // at least one side has a zero product; equality of the known
 852            // squared terms can only occur when the remaining cross term is
 853            // also zero.
 1424854            return 0;
 855        }
 856
 49857        Span<ulong> remainder =
 49858            stackalloc ulong[RadialProjectionWordCount * 2];
 49859        SubtractEqualMagnitudes(
 49860            fourOpposite,
 49861            knownLeft,
 49862            remainder);
 49863        Span<ulong> crossSquared =
 49864            stackalloc ulong[RadialProjectionWordCount * 4];
 49865        Span<ulong> remainderSquared =
 49866            stackalloc ulong[RadialProjectionWordCount * 4];
 49867        MultiplyMagnitudes(
 49868            baseSquared,
 49869            sameSideProduct,
 49870            crossSquared);
 49871        ShiftLeftMagnitude(crossSquared, 4);
 49872        MultiplyMagnitudes(
 49873            remainder,
 49874            remainder,
 49875            remainderSquared);
 49876        return CompareMagnitudeEqualLength(
 49877            crossSquared,
 49878            remainderSquared);
 879    }
 880
 881    #endregion
 882
 883    #region Radical Comparison
 884
 885
 886    /// <summary>
 887    /// Compares <c>sqrt(firstNumerator / firstDenominator) +
 888    /// sqrt(secondNumerator / secondDenominator)</c> with a nonnegative ratio.
 889    /// </summary>
 890    internal static int CompareNonNegativeRadicalSumToRatio(
 891        Signed576 firstNumerator,
 892        Signed192 firstDenominator,
 893        Signed576 secondNumerator,
 894        Signed192 secondDenominator,
 895        Signed320 ratioNumerator,
 896        Signed192 ratioDenominator)
 897    {
 729898        bool firstZero = firstNumerator.IsZero;
 729899        bool secondZero = secondNumerator.IsZero;
 729900        if (firstZero && secondZero)
 39901            return ratioNumerator.IsZero ? 0 : -1;
 690902        if (firstZero)
 903        {
 238904            return CompareNonNegativeRadicalToRatio(
 238905                secondNumerator,
 238906                secondDenominator,
 238907                ratioNumerator,
 238908                ratioDenominator);
 909        }
 452910        if (secondZero)
 911        {
 165912            return CompareNonNegativeRadicalToRatio(
 165913                firstNumerator,
 165914                firstDenominator,
 165915                ratioNumerator,
 165916                ratioDenominator);
 917        }
 918
 287919        Signed576 ratioSquared = MultiplySigned320(ratioNumerator, ratioNumerator);
 287920        Signed576 denominatorProduct = MultiplySigned320(
 287921            Signed320.ExtendValue(firstDenominator),
 287922            Signed320.ExtendValue(secondDenominator));
 287923        Signed576 squaredRatioTerm = MultiplyNonNegativeToSigned576(
 287924            ratioSquared,
 287925            denominatorProduct);
 287926        Signed576 radicalSquares = AddSigned576(
 287927            MultiplySigned576(firstNumerator, secondDenominator),
 287928            MultiplySigned576(secondNumerator, firstDenominator));
 287929        Signed320 ratioDenominatorSquared = MultiplySigned192(
 287930            ratioDenominator,
 287931            ratioDenominator);
 287932        _ = Signed192.TryNarrowSigned(
 287933            Signed576.ExtendValue(ratioDenominatorSquared),
 287934            out Signed192 narrowRatioDenominatorSquared);
 287935        Signed576 radicalSquareTerm = MultiplySigned576(
 287936            radicalSquares,
 287937            narrowRatioDenominatorSquared);
 287938        Signed576 remainder = SubtractSigned576(
 287939            squaredRatioTerm,
 287940            radicalSquareTerm);
 287941        if (remainder.Sign <= 0)
 47942            return 1;
 943
 240944        return CompareRadicalCrossTerm(
 240945            firstNumerator,
 240946            firstDenominator,
 240947            secondNumerator,
 240948            secondDenominator,
 240949            ratioDenominator,
 240950            remainder);
 951    }
 952
 953    /// <summary>
 954    /// Compares a nonnegative radical with a nonnegative ratio whose
 955    /// denominators require the full five-word geometry range.
 956    /// </summary>
 957    internal static int CompareNonNegativeRadicalToRatio(
 958        Signed576 numerator,
 959        Signed320 denominator,
 960        Signed320 ratioNumerator,
 961        Signed320 ratioDenominator)
 962    {
 147963        Span<ulong> numeratorWords = stackalloc ulong[9];
 147964        Span<ulong> denominatorWords = stackalloc ulong[5];
 147965        Span<ulong> ratioNumeratorWords = stackalloc ulong[5];
 147966        Span<ulong> ratioDenominatorWords = stackalloc ulong[5];
 147967        GetMagnitude(numerator, numeratorWords);
 147968        GetMagnitude(
 147969            denominator,
 147970            out denominatorWords[4],
 147971            out denominatorWords[3],
 147972            out denominatorWords[2],
 147973            out denominatorWords[1],
 147974            out denominatorWords[0]);
 147975        GetMagnitude(
 147976            ratioNumerator,
 147977            out ratioNumeratorWords[4],
 147978            out ratioNumeratorWords[3],
 147979            out ratioNumeratorWords[2],
 147980            out ratioNumeratorWords[1],
 147981            out ratioNumeratorWords[0]);
 147982        GetMagnitude(
 147983            ratioDenominator,
 147984            out ratioDenominatorWords[4],
 147985            out ratioDenominatorWords[3],
 147986            out ratioDenominatorWords[2],
 147987            out ratioDenominatorWords[1],
 147988            out ratioDenominatorWords[0]);
 989
 147990        Span<ulong> ratioNumeratorSquared = stackalloc ulong[10];
 147991        Span<ulong> ratioDenominatorSquared = stackalloc ulong[10];
 147992        Span<ulong> left = stackalloc ulong[19];
 147993        Span<ulong> right = stackalloc ulong[19];
 147994        MultiplyMagnitudes(
 147995            ratioNumeratorWords,
 147996            ratioNumeratorWords,
 147997            ratioNumeratorSquared);
 147998        MultiplyMagnitudes(
 147999            ratioDenominatorWords,
 1471000            ratioDenominatorWords,
 1471001            ratioDenominatorSquared);
 1471002        MultiplyMagnitudes(
 1471003            numeratorWords,
 1471004            ratioDenominatorSquared,
 1471005            left);
 1471006        MultiplyMagnitudes(
 1471007            ratioNumeratorSquared,
 1471008            denominatorWords,
 1471009            right);
 1471010        return CompareMagnitudeEqualLength(left, right);
 1011    }
 1012
 1013    /// <summary>
 1014    /// Returns the sign of a signed rational term plus a signed coefficient
 1015    /// multiplied by one nonnegative radical.
 1016    /// </summary>
 1017    internal static int CompareSignedLinearRadicalToZero(
 1018        Signed832 rational,
 1019        Signed704 radicalCoefficient,
 1020        Signed576 radicandNumerator,
 1021        Signed320 radicandDenominator)
 1022    {
 7401023        int rationalSign = rational.Sign;
 7401024        int coefficientSign = radicandNumerator.IsZero
 7401025            ? 0
 7401026            : radicalCoefficient.Sign;
 7401027        if (rationalSign == 0)
 331028            return coefficientSign;
 7071029        if (coefficientSign == 0 || rationalSign == coefficientSign)
 2501030            return rationalSign;
 1031
 4571032        Span<ulong> rationalWords = stackalloc ulong[13];
 4571033        Span<ulong> coefficientWords = stackalloc ulong[11];
 4571034        Span<ulong> numeratorWords = stackalloc ulong[9];
 4571035        Span<ulong> denominatorWords = stackalloc ulong[5];
 4571036        GetMagnitude(rational, rationalWords);
 4571037        GetMagnitude(radicalCoefficient, coefficientWords);
 4571038        GetMagnitude(radicandNumerator, numeratorWords);
 4571039        GetMagnitude(
 4571040            radicandDenominator,
 4571041            out denominatorWords[4],
 4571042            out denominatorWords[3],
 4571043            out denominatorWords[2],
 4571044            out denominatorWords[1],
 4571045            out denominatorWords[0]);
 1046
 4571047        Span<ulong> rationalSquared = stackalloc ulong[26];
 4571048        Span<ulong> coefficientSquared = stackalloc ulong[22];
 4571049        Span<ulong> rationalScaled = stackalloc ulong[31];
 4571050        Span<ulong> coefficientScaled = stackalloc ulong[31];
 4571051        MultiplyMagnitudes(
 4571052            rationalWords,
 4571053            rationalWords,
 4571054            rationalSquared);
 4571055        MultiplyMagnitudes(
 4571056            coefficientWords,
 4571057            coefficientWords,
 4571058            coefficientSquared);
 4571059        MultiplyMagnitudes(
 4571060            rationalSquared,
 4571061            denominatorWords,
 4571062            rationalScaled);
 4571063        MultiplyMagnitudes(
 4571064            coefficientSquared,
 4571065            numeratorWords,
 4571066            coefficientScaled);
 4571067        int comparison = CompareMagnitudeEqualLength(
 4571068            rationalScaled,
 4571069            coefficientScaled);
 4571070        return comparison == 0
 4571071            ? 0
 4571072            : comparison > 0
 4571073                ? rationalSign
 4571074                : coefficientSign;
 1075    }
 1076
 1077    private static int CompareNonNegativeRadicalToRatio(
 1078        Signed576 numerator,
 1079        Signed192 denominator,
 1080        Signed320 ratioNumerator,
 1081        Signed192 ratioDenominator)
 1082    {
 4031083        Signed320 ratioDenominatorSquared = MultiplySigned192(
 4031084            ratioDenominator,
 4031085            ratioDenominator);
 4031086        _ = Signed192.TryNarrowSigned(
 4031087            Signed576.ExtendValue(ratioDenominatorSquared),
 4031088            out Signed192 narrowRatioDenominatorSquared);
 4031089        Signed576 left = MultiplySigned576(
 4031090            numerator,
 4031091            narrowRatioDenominatorSquared);
 4031092        Signed576 right = MultiplySigned576(
 4031093            MultiplySigned320(ratioNumerator, ratioNumerator),
 4031094            denominator);
 4031095        return CompareNonNegative(left, right);
 1096    }
 1097
 1098    private static int CompareRadicalCrossTerm(
 1099        Signed576 firstNumerator,
 1100        Signed192 firstDenominator,
 1101        Signed576 secondNumerator,
 1102        Signed192 secondDenominator,
 1103        Signed192 ratioDenominator,
 1104        Signed576 remainder)
 1105    {
 2401106        Span<ulong> firstNumeratorWords = stackalloc ulong[9];
 2401107        Span<ulong> secondNumeratorWords = stackalloc ulong[9];
 2401108        Span<ulong> firstDenominatorWords = stackalloc ulong[3];
 2401109        Span<ulong> secondDenominatorWords = stackalloc ulong[3];
 2401110        Span<ulong> ratioDenominatorWords = stackalloc ulong[3];
 2401111        Span<ulong> remainderWords = stackalloc ulong[9];
 2401112        GetMagnitude(firstNumerator, firstNumeratorWords);
 2401113        GetMagnitude(secondNumerator, secondNumeratorWords);
 2401114        GetMagnitude(
 2401115            firstDenominator,
 2401116            out firstDenominatorWords[2],
 2401117            out firstDenominatorWords[1],
 2401118            out firstDenominatorWords[0]);
 2401119        GetMagnitude(
 2401120            secondDenominator,
 2401121            out secondDenominatorWords[2],
 2401122            out secondDenominatorWords[1],
 2401123            out secondDenominatorWords[0]);
 2401124        GetMagnitude(
 2401125            ratioDenominator,
 2401126            out ratioDenominatorWords[2],
 2401127            out ratioDenominatorWords[1],
 2401128            out ratioDenominatorWords[0]);
 2401129        GetMagnitude(remainder, remainderWords);
 1130
 2401131        Span<ulong> numeratorProduct = stackalloc ulong[18];
 2401132        Span<ulong> ratioSquared = stackalloc ulong[6];
 2401133        Span<ulong> ratioFourth = stackalloc ulong[12];
 2401134        Span<ulong> denominatorProduct = stackalloc ulong[6];
 2401135        Span<ulong> numeratorAndRatio = stackalloc ulong[30];
 2401136        Span<ulong> left = stackalloc ulong[36];
 2401137        Span<ulong> right = stackalloc ulong[36];
 2401138        MultiplyMagnitudes(
 2401139            firstNumeratorWords,
 2401140            secondNumeratorWords,
 2401141            numeratorProduct);
 2401142        MultiplyMagnitudes(
 2401143            ratioDenominatorWords,
 2401144            ratioDenominatorWords,
 2401145            ratioSquared);
 2401146        MultiplyMagnitudes(ratioSquared, ratioSquared, ratioFourth);
 2401147        MultiplyMagnitudes(
 2401148            firstDenominatorWords,
 2401149            secondDenominatorWords,
 2401150            denominatorProduct);
 2401151        MultiplyMagnitudes(
 2401152            numeratorProduct,
 2401153            ratioFourth,
 2401154            numeratorAndRatio);
 2401155        MultiplyMagnitudes(
 2401156            numeratorAndRatio,
 2401157            denominatorProduct,
 2401158            left);
 2401159        ShiftLeftMagnitude(left, 2);
 2401160        MultiplyMagnitudes(remainderWords, remainderWords, right);
 1161
 2401162        int comparison = CompareMagnitudeEqualLength(left, right);
 2401163        return comparison == 0 ? 0 : comparison > 0 ? 1 : -1;
 1164    }
 1165
 1166    #endregion
 1167}

/home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.cs

#LineLine coverage
 1//=======================================================================
 2// WideArithmetic.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024–present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using System.Runtime.CompilerServices;
 10
 11namespace FixedMathSharp;
 12
 13/// <summary>
 14/// Owns fixed-width limb arithmetic used by exact deterministic geometry.
 15/// </summary>
 16internal static partial class WideArithmetic
 17{
 18    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 19    internal static int CompareUnsigned(
 20        ulong leftHigh,
 21        ulong leftMiddle,
 22        ulong leftLow,
 23        ulong rightHigh,
 24        ulong rightMiddle,
 25        ulong rightLow)
 26    {
 16713427        if (leftHigh != rightHigh)
 1902328            return leftHigh < rightHigh ? -1 : 1;
 14811129        if (leftMiddle != rightMiddle)
 6318630            return leftMiddle < rightMiddle ? -1 : 1;
 8492531        if (leftLow != rightLow)
 8294632            return leftLow < rightLow ? -1 : 1;
 197933        return 0;
 34    }
 35
 36    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 37    internal static int CompareUnsigned(
 38        ulong leftWord4,
 39        ulong leftWord3,
 40        ulong leftWord2,
 41        ulong leftWord1,
 42        ulong leftWord0,
 43        ulong rightWord4,
 44        ulong rightWord3,
 45        ulong rightWord2,
 46        ulong rightWord1,
 47        ulong rightWord0)
 48    {
 1995849        if (leftWord4 != rightWord4)
 104250            return leftWord4 < rightWord4 ? -1 : 1;
 1891651        if (leftWord3 != rightWord3)
 1043552            return leftWord3 < rightWord3 ? -1 : 1;
 848153        if (leftWord2 != rightWord2)
 175054            return leftWord2 < rightWord2 ? -1 : 1;
 673155        if (leftWord1 != rightWord1)
 573156            return leftWord1 < rightWord1 ? -1 : 1;
 100057        if (leftWord0 != rightWord0)
 19658            return leftWord0 < rightWord0 ? -1 : 1;
 80459        return 0;
 60    }
 61
 62    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 63    private static bool TryGetSigned95Magnitude(
 64        Signed192 value,
 65        out ulong middle,
 66        out ulong low)
 67    {
 18555768        GetMagnitude(value, out ulong high, out middle, out low);
 18555769        return high == 0UL && middle <= 0x7FFF_FFFFUL; // 2,147,483,647 (31 significant high bits).
 70    }
 71
 72    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 73    private static Signed192 MultiplySigned95(
 74        ulong leftMiddle,
 75        ulong leftLow,
 76        ulong rightMiddle,
 77        ulong rightLow,
 78        bool negative)
 79    {
 9088080        MultiplyUnsigned96(
 9088081            (uint)leftMiddle,
 9088082            leftLow,
 9088083            (uint)rightMiddle,
 9088084            rightLow,
 9088085            out _,
 9088086            out ulong word2,
 9088087            out ulong word1,
 9088088            out ulong word0);
 89
 9088090        if (negative)
 91        {
 1887692            word0 = unchecked(~word0 + 1UL);
 1887693            word1 = unchecked(~word1 + (word0 == 0UL ? 1UL : 0UL));
 1887694            word2 = unchecked(~word2 + (word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 95        }
 96
 9088097        return new Signed192(word2, word1, word0);
 98    }
 99
 100    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 101    private static void MultiplyUnsigned128(
 102        ulong leftHigh,
 103        ulong leftLow,
 104        ulong rightHigh,
 105        ulong rightLow,
 106        out ulong word3,
 107        out ulong word2,
 108        out ulong word1,
 109        out ulong word0)
 110    {
 3576591111        if ((leftHigh | rightHigh) <= uint.MaxValue)
 112        {
 2983440113            MultiplyUnsigned96(
 2983440114                (uint)leftHigh,
 2983440115                leftLow,
 2983440116                (uint)rightHigh,
 2983440117                rightLow,
 2983440118                out word3,
 2983440119                out word2,
 2983440120                out word1,
 2983440121                out word0);
 2983440122            return;
 123        }
 124
 593151125        Fixed64.Multiply64To128(leftLow, rightLow, out ulong lowHigh, out word0);
 593151126        Fixed64.Multiply64To128(leftLow, rightHigh, out ulong leftCrossHigh, out ulong leftCrossLow);
 593151127        Fixed64.Multiply64To128(leftHigh, rightLow, out ulong rightCrossHigh, out ulong rightCrossLow);
 593151128        Fixed64.Multiply64To128(leftHigh, rightHigh, out word3, out ulong highLow);
 129
 593151130        word1 = lowHigh;
 593151131        ulong carry = 0UL;
 593151132        AccumulateWord(ref word1, leftCrossLow, ref carry);
 593151133        AccumulateWord(ref word1, rightCrossLow, ref carry);
 134
 593151135        word2 = leftCrossHigh;
 593151136        ulong highCarry = 0UL;
 593151137        AccumulateWord(ref word2, rightCrossHigh, ref highCarry);
 593151138        AccumulateWord(ref word2, highLow, ref highCarry);
 593151139        AccumulateWord(ref word2, carry, ref highCarry);
 593151140        word3 = unchecked(word3 + highCarry);
 593151141    }
 142
 143    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 144    private static void MultiplyUnsigned96(
 145        uint leftHigh,
 146        ulong leftLow,
 147        uint rightHigh,
 148        ulong rightLow,
 149        out ulong word3,
 150        out ulong word2,
 151        out ulong word1,
 152        out ulong word0)
 153    {
 3074320154        Fixed64.Multiply64To128(leftLow, rightLow, out ulong lowHigh, out word0);
 3074320155        Multiply64By32(leftLow, rightHigh, out ulong leftCrossHigh, out ulong leftCrossLow);
 3074320156        Multiply64By32(rightLow, leftHigh, out ulong rightCrossHigh, out ulong rightCrossLow);
 157
 3074320158        word1 = lowHigh;
 3074320159        ulong carry = 0UL;
 3074320160        AccumulateWord(ref word1, leftCrossLow, ref carry);
 3074320161        AccumulateWord(ref word1, rightCrossLow, ref carry);
 162
 3074320163        word2 = leftCrossHigh;
 3074320164        ulong highCarry = 0UL;
 3074320165        AccumulateWord(ref word2, rightCrossHigh, ref highCarry);
 3074320166        AccumulateWord(ref word2, (ulong)leftHigh * rightHigh, ref highCarry);
 3074320167        AccumulateWord(ref word2, carry, ref highCarry);
 3074320168        word3 = highCarry;
 3074320169    }
 170
 171    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 172    private static void Multiply64By32(
 173        ulong left,
 174        uint right,
 175        out ulong high,
 176        out ulong low)
 177    {
 6148640178        ulong lowProduct = (uint)left * (ulong)right;
 6148640179        ulong highProduct = (left >> 32) * right;
 6148640180        ulong middle = (lowProduct >> 32) + (uint)highProduct;
 6148640181        low = (lowProduct & uint.MaxValue) | (middle << 32);
 6148640182        high = (highProduct >> 32) + (middle >> 32);
 6148640183    }
 184
 185    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 186    private static void AddProductAt2(
 187        ref ulong word4,
 188        ref ulong word3,
 189        ref ulong word2,
 190        ulong left,
 191        ulong right)
 192    {
 888596193        Fixed64.Multiply64To128(left, right, out ulong high, out ulong low);
 888596194        ulong previous = word2;
 888596195        word2 = unchecked(word2 + low);
 888596196        ulong carry = word2 < previous ? 1UL : 0UL;
 197
 198        // A 64-by-64 product's high word is at most UInt64.MaxValue - 1,
 199        // so adding the one-bit low-word carry cannot overflow here.
 888596200        ulong highWithCarry = high + carry;
 888596201        previous = word3;
 888596202        word3 = unchecked(word3 + highWithCarry);
 888596203        if (word3 < previous)
 404204            word4++;
 888596205    }
 206
 207    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 208    private static void AddProductAt3(
 209        ref ulong word4,
 210        ref ulong word3,
 211        ulong left,
 212        ulong right)
 213    {
 888596214        Fixed64.Multiply64To128(left, right, out ulong high, out ulong low);
 888596215        ulong previous = word3;
 888596216        word3 = unchecked(word3 + low);
 888596217        word4 = unchecked(word4 + high + (word3 < previous ? 1UL : 0UL));
 888596218    }
 219
 220    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 221    internal static void AccumulateWord(ref ulong word, ulong add, ref ulong carry)
 222    {
 18337355223        ulong previous = word;
 18337355224        word = unchecked(word + add);
 18337355225        if (word < previous)
 54117226            carry++;
 18337355227    }
 228
 229    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 230    internal static ulong SubtractWord(ulong value, ulong subtract, ref ulong borrow)
 231    {
 50239069232        ulong subtrahend = unchecked(subtract + borrow);
 50239069233        ulong overflow = subtrahend < subtract ? 1UL : 0UL;
 50239069234        ulong result = unchecked(value - subtrahend);
 50239069235        borrow = overflow | (value < subtrahend ? 1UL : 0UL);
 50239069236        return result;
 237    }
 238
 239    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 240    internal static ulong AddSignedWord(ulong left, ulong right, ref ulong carry)
 241    {
 33495973242        ulong sum = unchecked(left + right);
 33495973243        ulong result = unchecked(sum + carry);
 33495973244        carry = sum < left || result < sum ? 1UL : 0UL;
 33495973245        return result;
 246    }
 247
 248    internal static bool IsZeroMagnitude(ReadOnlySpan<ulong> value)
 249    {
 5320386250        for (int index = 0; index < value.Length; index++)
 251        {
 2642263252            if (value[index] != 0UL)
 214233253                return false;
 254        }
 255
 17930256        return true;
 257    }
 258
 259    #region Multiquadratic Comparison
 260
 261    private const int MaximumLinearRadicalCount = 6;
 262
 263    /// <summary>
 264    /// Gets the exact sign of a signed sum of nonnegative square roots.
 265    /// </summary>
 266    /// <remarks>
 267    /// Each radicand occupies <paramref name="radicandWordCount"/> words in
 268    /// little-endian order. Equal radicands are merged before the
 269    /// multiquadratic basis is built.
 270    /// </remarks>
 271    internal static int GetLinearRadicalSumSign(
 272        ReadOnlySpan<ulong> radicands,
 273        int radicandWordCount,
 274        ReadOnlySpan<int> signs)
 275    {
 5483276        int termCount = signs.Length;
 5483277        Span<ulong> uniqueRadicands = stackalloc ulong[
 5483278            MaximumLinearRadicalCount * radicandWordCount];
 5483279        Span<int> coefficients =
 5483280            stackalloc int[MaximumLinearRadicalCount];
 5483281        uniqueRadicands.Clear();
 5483282        coefficients.Clear();
 5483283        int uniqueCount = 0;
 55300284        for (int termIndex = 0; termIndex < termCount; termIndex++)
 285        {
 22167286            int sign = signs[termIndex];
 22167287            ReadOnlySpan<ulong> radicand = radicands.Slice(
 22167288                termIndex * radicandWordCount,
 22167289                radicandWordCount);
 22167290            if (sign == 0 || IsZeroMagnitude(radicand))
 291                continue;
 292
 21027293            int existingIndex = -1;
 21027294            for (int candidateIndex = 0;
 47304295                 candidateIndex < uniqueCount;
 26277296                 candidateIndex++)
 297            {
 28516298                if (CompareMagnitudeEqualLength(
 28516299                        radicand,
 28516300                        uniqueRadicands.Slice(
 28516301                            candidateIndex * radicandWordCount,
 28516302                            radicandWordCount)) == 0)
 303                {
 2239304                    existingIndex = candidateIndex;
 2239305                    break;
 306                }
 307            }
 308
 21027309            if (existingIndex >= 0)
 310            {
 2239311                coefficients[existingIndex] += sign;
 2239312                continue;
 313            }
 314
 18788315            radicand.CopyTo(uniqueRadicands.Slice(
 18788316                uniqueCount * radicandWordCount,
 18788317                radicandWordCount));
 18788318            coefficients[uniqueCount] = sign;
 18788319            uniqueCount++;
 320        }
 321
 5483322        int compactedCount = 0;
 48542323        for (int index = 0; index < uniqueCount; index++)
 324        {
 18788325            int coefficient = coefficients[index];
 18788326            if (coefficient == 0)
 327                continue;
 18495328            if (compactedCount != index)
 329            {
 119330                uniqueRadicands.Slice(
 119331                        index * radicandWordCount,
 119332                        radicandWordCount)
 119333                    .CopyTo(uniqueRadicands.Slice(
 119334                        compactedCount * radicandWordCount,
 119335                        radicandWordCount));
 336            }
 18495337            coefficients[compactedCount] = coefficient;
 18495338            compactedCount++;
 339        }
 5483340        uniqueCount = compactedCount;
 5483341        if (uniqueCount == 0)
 93342            return 0;
 343
 5390344        int basisCount = 1 << uniqueCount;
 5390345        Span<ulong> basisMagnitudes =
 5390346            stackalloc ulong[basisCount];
 5390347        Span<int> basisSigns =
 5390348            stackalloc int[basisCount];
 5390349        basisMagnitudes.Clear();
 5390350        basisSigns.Clear();
 47770351        for (int index = 0; index < uniqueCount; index++)
 352        {
 18495353            int coefficient = coefficients[index];
 18495354            int basisIndex = 1 << index;
 18495355            basisMagnitudes[basisIndex] =
 18495356                unchecked((ulong)Math.Abs(coefficient));
 18495357            basisSigns[basisIndex] = Math.Sign(coefficient);
 358        }
 359
 5390360        return GetMultiquadraticSign(
 5390361            basisMagnitudes,
 5390362            basisSigns,
 5390363            coefficientWordCount: 1,
 5390364            uniqueRadicands,
 5390365            radicandWordCount,
 5390366            uniqueCount,
 5390367            uniqueCount);
 368    }
 369
 370    private static int GetMultiquadraticSign(
 371        ReadOnlySpan<ulong> coefficientMagnitudes,
 372        ReadOnlySpan<int> coefficientSigns,
 373        int coefficientWordCount,
 374        ReadOnlySpan<ulong> radicands,
 375        int radicandWordCount,
 376        int radicalCount,
 377        int totalRadicalCount)
 378    {
 244610379        if (radicalCount == 0)
 135612380            return coefficientSigns[0];
 381
 108998382        int halfBasisCount = 1 << (radicalCount - 1);
 108998383        int halfWordCount =
 108998384            halfBasisCount * coefficientWordCount;
 108998385        int firstSign = GetMultiquadraticSign(
 108998386            coefficientMagnitudes.Slice(0, halfWordCount),
 108998387            coefficientSigns.Slice(0, halfBasisCount),
 108998388            coefficientWordCount,
 108998389            radicands,
 108998390            radicandWordCount,
 108998391            radicalCount - 1,
 108998392            totalRadicalCount);
 108998393        int secondSign = GetMultiquadraticSign(
 108998394            coefficientMagnitudes.Slice(
 108998395                halfWordCount,
 108998396                halfWordCount),
 108998397            coefficientSigns.Slice(
 108998398                halfBasisCount,
 108998399                halfBasisCount),
 108998400            coefficientWordCount,
 108998401            radicands,
 108998402            radicandWordCount,
 108998403            radicalCount - 1,
 108998404            totalRadicalCount);
 108998405        if (firstSign == 0)
 34304406            return secondSign;
 74694407        if (secondSign == 0 || firstSign == secondSign)
 53470408            return firstSign;
 409
 21224410        int eliminatedCount =
 21224411            totalRadicalCount - radicalCount + 1;
 21224412        int maximumRadicandDegree =
 21224413            1 << (eliminatedCount - 1);
 21224414        int nextCoefficientWordCount =
 21224415            maximumRadicandDegree * radicandWordCount
 21224416            + (maximumRadicandDegree << 2)
 21224417            + 1;
 21224418        Span<ulong> differenceMagnitudes = stackalloc ulong[
 21224419            halfBasisCount * nextCoefficientWordCount];
 21224420        Span<int> differenceSigns =
 21224421            stackalloc int[halfBasisCount];
 21224422        differenceMagnitudes.Clear();
 21224423        differenceSigns.Clear();
 21224424        BuildMultiquadraticSquaredDifference(
 21224425            coefficientMagnitudes.Slice(0, halfWordCount),
 21224426            coefficientSigns.Slice(0, halfBasisCount),
 21224427            coefficientMagnitudes.Slice(
 21224428                halfWordCount,
 21224429                halfWordCount),
 21224430            coefficientSigns.Slice(
 21224431                halfBasisCount,
 21224432                halfBasisCount),
 21224433            coefficientWordCount,
 21224434            radicands,
 21224435            radicandWordCount,
 21224436            radicalCount,
 21224437            differenceMagnitudes,
 21224438            differenceSigns,
 21224439            nextCoefficientWordCount);
 21224440        int squaredDifferenceSign = GetMultiquadraticSign(
 21224441            differenceMagnitudes,
 21224442            differenceSigns,
 21224443            nextCoefficientWordCount,
 21224444            radicands,
 21224445            radicandWordCount,
 21224446            radicalCount - 1,
 21224447            totalRadicalCount);
 21224448        if (squaredDifferenceSign == 0)
 288449            return 0;
 20936450        return squaredDifferenceSign > 0
 20936451            ? firstSign
 20936452            : secondSign;
 453    }
 454
 455    private static void BuildMultiquadraticSquaredDifference(
 456        ReadOnlySpan<ulong> firstMagnitudes,
 457        ReadOnlySpan<int> firstSigns,
 458        ReadOnlySpan<ulong> secondMagnitudes,
 459        ReadOnlySpan<int> secondSigns,
 460        int coefficientWordCount,
 461        ReadOnlySpan<ulong> radicands,
 462        int radicandWordCount,
 463        int radicalCount,
 464        Span<ulong> resultMagnitudes,
 465        Span<int> resultSigns,
 466        int resultWordCount)
 467    {
 21224468        AddMultiquadraticSquare(
 21224469            firstMagnitudes,
 21224470            firstSigns,
 21224471            coefficientWordCount,
 21224472            radicands,
 21224473            radicandWordCount,
 21224474            radicalCount - 1,
 21224475            extraRadicandIndex: -1,
 21224476            resultMagnitudes,
 21224477            resultSigns,
 21224478            resultWordCount,
 21224479            resultSign: 1);
 21224480        AddMultiquadraticSquare(
 21224481            secondMagnitudes,
 21224482            secondSigns,
 21224483            coefficientWordCount,
 21224484            radicands,
 21224485            radicandWordCount,
 21224486            radicalCount - 1,
 21224487            extraRadicandIndex: radicalCount - 1,
 21224488            resultMagnitudes,
 21224489            resultSigns,
 21224490            resultWordCount,
 21224491            resultSign: -1);
 21224492    }
 493
 494    private static void AddMultiquadraticSquare(
 495        ReadOnlySpan<ulong> coefficientMagnitudes,
 496        ReadOnlySpan<int> coefficientSigns,
 497        int coefficientWordCount,
 498        ReadOnlySpan<ulong> radicands,
 499        int radicandWordCount,
 500        int remainingRadicalCount,
 501        int extraRadicandIndex,
 502        Span<ulong> resultMagnitudes,
 503        Span<int> resultSigns,
 504        int resultWordCount,
 505        int resultSign)
 506    {
 42448507        int basisCount = 1 << remainingRadicalCount;
 42448508        Span<ulong> firstProduct =
 42448509            stackalloc ulong[resultWordCount];
 42448510        Span<ulong> secondProduct =
 42448511            stackalloc ulong[resultWordCount];
 42448512        for (int firstIndex = 0;
 183476513             firstIndex < basisCount;
 141028514             firstIndex++)
 515        {
 141028516            int firstCoefficientSign =
 141028517                coefficientSigns[firstIndex];
 141028518            if (firstCoefficientSign == 0)
 519                continue;
 55968520            ReadOnlySpan<ulong> firstCoefficient =
 55968521                coefficientMagnitudes.Slice(
 55968522                    firstIndex * coefficientWordCount,
 55968523                    coefficientWordCount);
 55968524            for (int secondIndex = 0;
 278100525                 secondIndex < basisCount;
 222132526                 secondIndex++)
 527            {
 222132528                int secondCoefficientSign =
 222132529                    coefficientSigns[secondIndex];
 222132530                if (secondCoefficientSign == 0)
 531                    continue;
 89546532                ReadOnlySpan<ulong> secondCoefficient =
 89546533                    coefficientMagnitudes.Slice(
 89546534                        secondIndex * coefficientWordCount,
 89546535                        coefficientWordCount);
 89546536                MultiplyMagnitudes(
 89546537                    firstCoefficient,
 89546538                    secondCoefficient,
 89546539                    firstProduct);
 89546540                Span<ulong> product = firstProduct;
 89546541                Span<ulong> scratch = secondProduct;
 89546542                int commonRadicals =
 89546543                    firstIndex & secondIndex;
 89546544                for (int radicalIndex = 0;
 274244545                     radicalIndex < remainingRadicalCount;
 184698546                     radicalIndex++)
 547                {
 184698548                    if ((commonRadicals
 184698549                            & (1 << radicalIndex)) == 0)
 550                    {
 551                        continue;
 552                    }
 37935553                    MultiplyMagnitudes(
 37935554                        product,
 37935555                        radicands.Slice(
 37935556                            radicalIndex * radicandWordCount,
 37935557                            radicandWordCount),
 37935558                        scratch);
 37935559                    Span<ulong> temporary = product;
 37935560                    product = scratch;
 37935561                    scratch = temporary;
 562                }
 89546563                if (extraRadicandIndex >= 0)
 564                {
 29017565                    MultiplyMagnitudes(
 29017566                        product,
 29017567                        radicands.Slice(
 29017568                            extraRadicandIndex
 29017569                            * radicandWordCount,
 29017570                            radicandWordCount),
 29017571                        scratch);
 29017572                    Span<ulong> temporary = product;
 29017573                    product = scratch;
 29017574                    scratch = temporary;
 575                }
 576
 89546577                int targetIndex =
 89546578                    firstIndex ^ secondIndex;
 89546579                AddSignedMagnitude(
 89546580                    product,
 89546581                    firstCoefficientSign
 89546582                    * secondCoefficientSign
 89546583                    * resultSign,
 89546584                    resultMagnitudes.Slice(
 89546585                        targetIndex * resultWordCount,
 89546586                        resultWordCount),
 89546587                    ref resultSigns[targetIndex]);
 588            }
 589        }
 42448590    }
 591
 592    #endregion
 593
 594    internal static void AddSignedMagnitude(
 595        ReadOnlySpan<ulong> addend,
 596        int addendSign,
 597        Span<ulong> result,
 598        ref int resultSign)
 599    {
 600        // Callers provide a nonzero addend with the same width as the result.
 89546601        if (resultSign == 0)
 602        {
 35098603            addend.CopyTo(result);
 35098604            resultSign = addendSign;
 35098605            return;
 606        }
 54448607        if (resultSign == addendSign)
 608        {
 28842609            AddMagnitudeInto(addend, result);
 28842610            return;
 611        }
 612
 25606613        int comparison =
 25606614            CompareMagnitudeEqualLength(result, addend);
 25606615        if (comparison == 0)
 616        {
 230617            result.Clear();
 230618            resultSign = 0;
 230619            return;
 620        }
 25376621        if (comparison > 0)
 622        {
 12491623            SubtractEqualMagnitudes(
 12491624                result,
 12491625                addend,
 12491626                result);
 12491627            return;
 628        }
 629
 12885630        Span<ulong> difference =
 12885631            stackalloc ulong[result.Length];
 12885632        SubtractEqualMagnitudes(
 12885633            addend,
 12885634            result,
 12885635            difference);
 12885636        difference.CopyTo(result);
 12885637        resultSign = addendSign;
 12885638    }
 639
 640}

/home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Magnitude.cs

#LineLine coverage
 1//=======================================================================
 2// WideArithmetic.Magnitude.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024–present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using System.Runtime.CompilerServices;
 10
 11namespace FixedMathSharp;
 12
 13/// <content>
 14/// Policy-neutral unsigned magnitude-span arithmetic.
 15/// </content>
 16internal static partial class WideArithmetic
 17{
 18    internal static int GetActiveMagnitudeLength(
 19        ReadOnlySpan<ulong> value)
 20    {
 600200121        int length = value.Length;
 11003520022        while (length > 0 && value[length - 1] == 0UL)
 10403319923            length--;
 600200124        return length;
 25    }
 26
 27    internal static int GetMagnitudeBitLength(
 28        ReadOnlySpan<ulong> value)
 29    {
 44930        int length = GetActiveMagnitudeLength(value);
 44931        return length == 0
 44932            ? 0
 44933            : ((length - 1) << 6)
 44934                + 64
 44935                - Fixed64.CountLeadingZeroes(value[length - 1]);
 36    }
 37
 38    internal static void MultiplyMagnitudes(
 39        ReadOnlySpan<ulong> left,
 40        ReadOnlySpan<ulong> right,
 41        Span<ulong> product)
 42    {
 299226543        product.Clear();
 299226544        int leftLength = GetActiveMagnitudeLength(left);
 299226545        int rightLength = GetActiveMagnitudeLength(right);
 3146712846        for (int leftIndex = 0; leftIndex < leftLength; leftIndex++)
 47        {
 1274129948            ulong leftWord = left[leftIndex];
 1274129949            if (leftWord == 0UL)
 50                continue;
 51
 8851316852            for (int rightIndex = 0; rightIndex < rightLength; rightIndex++)
 53            {
 3848785254                ulong rightWord = right[rightIndex];
 3848785255                if (rightWord == 0UL)
 56                    continue;
 57
 2821629558                Fixed64.Multiply64To128(
 2821629559                    leftWord,
 2821629560                    rightWord,
 2821629561                    out ulong high,
 2821629562                    out ulong low);
 2821629563                int productIndex = leftIndex + rightIndex;
 2821629564                AddWord(product, productIndex, low);
 2821629565                AddWord(product, productIndex + 1, high);
 66            }
 67        }
 299226568    }
 69
 70    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 71    internal static void AddWord(
 72        Span<ulong> words,
 73        int index,
 74        ulong value)
 75    {
 12541537676        while (value != 0UL && index < words.Length)
 77        {
 6898258378            ulong previous = words[index];
 6898258379            words[index] = unchecked(previous + value);
 6898258380            value = words[index] < previous ? 1UL : 0UL;
 6898258381            index++;
 82        }
 5643279383    }
 84
 85    internal static void AddEqualMagnitudes(
 86        ReadOnlySpan<ulong> left,
 87        ReadOnlySpan<ulong> right,
 88        Span<ulong> result)
 89    {
 3469090        ulong carry = 0UL;
 941155491        for (int index = 0; index < result.Length; index++)
 467108792            result[index] =
 467108793                AddSignedWord(left[index], right[index], ref carry);
 3469094    }
 95
 96    internal static void AddMagnitudeInto(
 97        ReadOnlySpan<ulong> addend,
 98        Span<ulong> result)
 99    {
 72927100        ulong carry = 0UL;
 14511232101        for (int index = 0; index < result.Length; index++)
 102        {
 7182689103            ulong value = index < addend.Length
 7182689104                ? addend[index]
 7182689105                : 0UL;
 7182689106            result[index] =
 7182689107                AddSignedWord(result[index], value, ref carry);
 108        }
 72927109    }
 110
 111    internal static void SubtractEqualMagnitudes(
 112        ReadOnlySpan<ulong> larger,
 113        ReadOnlySpan<ulong> smaller,
 114        Span<ulong> result)
 115    {
 5058190116        ulong borrow = 0UL;
 91034600117        for (int index = 0; index < result.Length; index++)
 40459110118            result[index] =
 40459110119                SubtractWord(larger[index], smaller[index], ref borrow);
 5058190120    }
 121
 122    internal static int CompareMagnitudeEqualLength(
 123        ReadOnlySpan<ulong> left,
 124        ReadOnlySpan<ulong> right)
 125    {
 171462360126        for (int index = left.Length - 1; index >= 0; index--)
 127        {
 85583469128            if (left[index] != right[index])
 16493130129                return left[index] < right[index] ? -1 : 1;
 130        }
 131
 147711132        return 0;
 133    }
 134}

/home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Ratio.cs

#LineLine coverage
 1//=======================================================================
 2// WideArithmetic.Ratio.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024-present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9
 10namespace FixedMathSharp;
 11
 12internal static partial class WideArithmetic
 13{
 14    internal static Signed320 GetSignedRatioWith64FractionBits(
 15        Signed576 numerator,
 16        Signed576 positiveDenominator)
 17    {
 718        if (numerator.Sign == 0)
 119            return default;
 20
 621        Span<ulong> numeratorMagnitude = stackalloc ulong[9];
 622        Span<ulong> denominatorMagnitude = stackalloc ulong[10];
 623        Span<ulong> remainder = stackalloc ulong[10];
 624        Span<ulong> shiftedDenominator = stackalloc ulong[10];
 625        Span<ulong> quotient = stackalloc ulong[5];
 626        GetMagnitude(numerator, numeratorMagnitude);
 627        GetMagnitude(positiveDenominator, denominatorMagnitude);
 628        remainder.Clear();
 629        quotient.Clear();
 630        numeratorMagnitude.CopyTo(remainder[1..]);
 31
 632        int quotientBit = GetMassRatioBitLength(remainder)
 633            - GetMassRatioBitLength(denominatorMagnitude);
 634        if (quotientBit >= 0)
 35        {
 236            ShiftMassRatioLeft(
 237                denominatorMagnitude,
 238                quotientBit,
 239                shiftedDenominator);
 40        }
 14841        for (int bit = quotientBit; bit >= 0; bit--)
 42        {
 6843            if (CompareMagnitudeEqualLength(
 6844                    remainder,
 6845                    shiftedDenominator) >= 0)
 46            {
 347                SubtractEqualMagnitudes(
 348                    remainder,
 349                    shiftedDenominator,
 350                    remainder);
 351                quotient[bit >> 6] |= 1UL << (bit & 63);
 52            }
 53
 6854            ShiftMassRatioRightOne(shiftedDenominator);
 55        }
 56
 657        Span<ulong> twiceRemainder = stackalloc ulong[10];
 658        remainder.CopyTo(twiceRemainder);
 659        ShiftMassRatioLeftOne(twiceRemainder);
 660        int midpointComparison = CompareMagnitudeEqualLength(
 661            twiceRemainder,
 662            denominatorMagnitude);
 663        Signed320 magnitude = new(
 664            quotient[4],
 665            quotient[3],
 666            quotient[2],
 667            quotient[1],
 668            quotient[0]);
 669        if (midpointComparison > 0
 670            || (midpointComparison == 0
 671                && (quotient[0] & 1UL) != 0UL))
 72        {
 373            magnitude = AddSigned320(
 374                magnitude,
 375                Signed320.ExtendValue(Signed192.Signed(1)));
 76        }
 77
 678        return numerator.Sign < 0
 679            ? SubtractSigned320(default, magnitude)
 680            : magnitude;
 81    }
 82
 83    private static int GetMassRatioBitLength(
 84        ReadOnlySpan<ulong> value)
 85    {
 1286        int index = value.Length - 1;
 10987        while (value[index] == 0UL)
 9788            index--;
 1289        int leadingZeroes = 0;
 1290        ulong word = value[index];
 1291        for (ulong mask = 1UL << 63;
 75592             (word & mask) == 0UL;
 74393             mask >>= 1)
 94        {
 74395            leadingZeroes++;
 96        }
 97
 1298        return (index * 64) + 64 - leadingZeroes;
 99    }
 100
 101    private static void ShiftMassRatioLeft(
 102        ReadOnlySpan<ulong> source,
 103        int bits,
 104        Span<ulong> destination)
 105    {
 2106        destination.Clear();
 2107        int wordShift = bits >> 6;
 2108        int bitShift = bits & 63;
 42109        for (int index = 0; index < source.Length; index++)
 110        {
 20111            int target = index + wordShift;
 20112            if (target >= destination.Length)
 113                break;
 114
 19115            destination[target] |= source[index] << bitShift;
 19116            if (bitShift != 0
 19117                && target + 1 < destination.Length)
 118            {
 8119                destination[target + 1] |=
 8120                    source[index] >> (64 - bitShift);
 121            }
 122        }
 2123    }
 124
 125    private static void ShiftMassRatioRightOne(
 126        Span<ulong> value)
 127    {
 68128        ulong carry = 0UL;
 1496129        for (int index = value.Length - 1; index >= 0; index--)
 130        {
 680131            ulong nextCarry = value[index] << 63;
 680132            value[index] = (value[index] >> 1) | carry;
 680133            carry = nextCarry;
 134        }
 68135    }
 136
 137    private static void ShiftMassRatioLeftOne(
 138        Span<ulong> value)
 139    {
 6140        ulong carry = 0UL;
 132141        for (int index = 0; index < value.Length; index++)
 142        {
 60143            ulong nextCarry = value[index] >> 63;
 60144            value[index] = (value[index] << 1) | carry;
 60145            carry = nextCarry;
 146        }
 6147    }
 148
 149}

/home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed192.cs

#LineLine coverage
 1//=======================================================================
 2// WideArithmetic.Signed192.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024–present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System.Runtime.CompilerServices;
 9
 10namespace FixedMathSharp;
 11
 12/// <content>
 13/// Arithmetic helpers for <see cref="Signed192"/>: magnitude/comparison,
 14/// exact add/subtract, and integer square root extraction.
 15/// </content>
 16internal static partial class WideArithmetic
 17{
 18    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 19    internal static void GetMagnitude(
 20        Signed192 value,
 21        out ulong high,
 22        out ulong middle,
 23        out ulong low)
 24    {
 1154807225        high = value.High;
 1154807226        middle = value.Middle;
 1154807227        low = value.Low;
 1154807228        if (value.Sign >= 0)
 1003730429            return;
 30
 151076831        low = unchecked(~low + 1UL);
 151076832        middle = unchecked(~middle + (low == 0UL ? 1UL : 0UL));
 151076833        high = unchecked(~high + (middle == 0UL && low == 0UL ? 1UL : 0UL));
 151076834    }
 35
 36    /// <summary>
 37    /// Compares unsigned magnitudes of signed wide values.
 38    /// </summary>
 39    internal static int CompareMagnitude(Signed192 left, Signed192 right)
 40    {
 134141        GetMagnitude(left, out ulong leftHigh, out ulong leftMiddle, out ulong leftLow);
 134142        GetMagnitude(right, out ulong rightHigh, out ulong rightMiddle, out ulong rightLow);
 134143        return CompareUnsigned(
 134144            leftHigh,
 134145            leftMiddle,
 134146            leftLow,
 134147            rightHigh,
 134148            rightMiddle,
 134149            rightLow);
 50    }
 51
 52    /// <summary>
 53    /// Returns whether a wide magnitude is at most a positive raw threshold
 54    /// shifted into the value's scale.
 55    /// </summary>
 56    internal static bool IsMagnitudeAtMost(Signed192 value, ulong rawThreshold, int leftShift)
 57    {
 6758        Signed192 threshold = new(
 6759            0UL,
 6760            rawThreshold >> (64 - leftShift),
 6761            rawThreshold << leftShift);
 6762        return CompareMagnitude(value, threshold) <= 0;
 63    }
 64
 65    /// <summary>
 66    /// Adds exact three-word values without scalar conversion.
 67    /// </summary>
 68    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 69    internal static Signed192 AddSigned192(Signed192 left, Signed192 right)
 70    {
 128384271        ulong low = unchecked(left.Low + right.Low);
 128384272        ulong carry = low < left.Low ? 1UL : 0UL;
 128384273        ulong middle = unchecked(left.Middle + right.Middle + carry);
 128384274        carry = middle < left.Middle || (carry != 0UL && middle == left.Middle) ? 1UL : 0UL;
 128384275        return new Signed192(unchecked(left.High + right.High + carry), middle, low);
 76    }
 77
 584678    internal static Signed192 Double(Signed192 value) => AddSigned192(value, value);
 79
 80    /// <summary>
 81    /// Subtracts exact three-word values without scalar conversion.
 82    /// </summary>
 83    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 84    internal static Signed192 SubtractSigned192(Signed192 left, Signed192 right)
 85    {
 83889986        ulong borrow = 0UL;
 83889987        ulong low = SubtractWord(left.Low, right.Low, ref borrow);
 83889988        ulong middle = SubtractWord(left.Middle, right.Middle, ref borrow);
 83889989        return new Signed192(unchecked(left.High - right.High - borrow), middle, low);
 90    }
 91
 92    internal static Signed192 Difference(Fixed64 left, Fixed64 right) =>
 114193        SubtractSigned192(Signed192.Signed(left.m_rawValue), Signed192.Signed(right.m_rawValue));
 94
 95    /// <summary>
 96    /// Returns the floor square root and exact remainder of a nonnegative five-word value.
 97    /// </summary>
 98    internal static Signed192 GetFloorSquareRoot(Signed320 value, out Signed192 remainder)
 99    {
 2971100        if (value.IsZero)
 101        {
 32102            remainder = default;
 32103            return default;
 104        }
 105
 2939106        if (value.Word4 == 0UL && value.Word3 == 0UL)
 1656107            return GetFloorSquareRoot192(value.Word2, value.Word1, value.Word0, out remainder);
 108
 1283109        int pairIndex = (GetBitLength(value.Word4, value.Word3, value.Word2, value.Word1, value.Word0) - 1) >> 1;
 1283110        ulong rootHigh = 0UL;
 1283111        ulong rootMiddle = 0UL;
 1283112        ulong rootLow = 0UL;
 1283113        ulong remainderHigh = 0UL;
 1283114        ulong remainderMiddle = 0UL;
 1283115        ulong remainderLow = 0UL;
 116
 257835117        for (; pairIndex >= 0; pairIndex--)
 118        {
 128276119            int pairShift = (pairIndex & 31) << 1;
 128276120            ulong pair = (pairIndex >> 5) switch
 128276121            {
 335122                4 => (value.Word4 >> pairShift) & 3UL,
 4773123                3 => (value.Word3 >> pairShift) & 3UL,
 41056124                2 => (value.Word2 >> pairShift) & 3UL,
 41056125                1 => (value.Word1 >> pairShift) & 3UL,
 41056126                _ => (value.Word0 >> pairShift) & 3UL,
 128276127            };
 128
 128276129            remainderHigh = (remainderHigh << 2) | (remainderMiddle >> 62);
 128276130            remainderMiddle = (remainderMiddle << 2) | (remainderLow >> 62);
 128276131            remainderLow = (remainderLow << 2) | pair;
 128276132            rootHigh = (rootHigh << 1) | (rootMiddle >> 63);
 128276133            rootMiddle = (rootMiddle << 1) | (rootLow >> 63);
 128276134            rootLow <<= 1;
 135
 128276136            ulong candidateHigh = (rootHigh << 1) | (rootMiddle >> 63);
 128276137            ulong candidateMiddle = (rootMiddle << 1) | (rootLow >> 63);
 128276138            ulong candidateLow = (rootLow << 1) | 1UL;
 128276139            if (CompareUnsigned(
 128276140                remainderHigh,
 128276141                remainderMiddle,
 128276142                remainderLow,
 128276143                candidateHigh,
 128276144                candidateMiddle,
 128276145                candidateLow) < 0)
 146            {
 147                continue;
 148            }
 149
 18306150            SubtractUnsigned(
 18306151                ref remainderHigh,
 18306152                ref remainderMiddle,
 18306153                ref remainderLow,
 18306154                candidateHigh,
 18306155                candidateMiddle,
 18306156                candidateLow);
 157            // The preceding shift leaves rootLow even, so this increment cannot overflow.
 18306158            rootLow++;
 159        }
 160
 1283161        remainder = new Signed192(remainderHigh, remainderMiddle, remainderLow);
 1283162        return new Signed192(rootHigh, rootMiddle, rootLow);
 163    }
 164
 165    internal static Signed192 Scale(Fixed64 value) =>
 143232166        Signed192.NarrowValue(
 143232167            MultiplySigned192(
 143232168                Signed192.Raw(value),
 143232169                Signed192.One));
 170
 155171    internal static Signed192 Negate(Signed192 value) => SubtractSigned192(default, value);
 172
 173    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 174    internal static Signed192 Absolute(Signed192 value)
 175    {
 1098176        if (value.Sign >= 0)
 984177            return value;
 114178        return SubtractSigned192(default, value);
 179    }
 180
 181    /// <summary>
 182    /// Shifts a nonnegative three-word value into a 64-bit normalized prefix.
 183    /// </summary>
 184    /// <remarks>
 185    /// Triangle normalization calls this with 0 through 67 discarded bits,
 186    /// which guarantees that the returned prefix fits in 64 bits.
 187    /// </remarks>
 188    internal static ulong ShiftRightToUInt64(Signed192 value, int bits, out bool discarded)
 189    {
 1156190        GetMagnitude(value, out ulong high, out ulong middle, out ulong low);
 1156191        if (bits == 0)
 192        {
 145193            discarded = false;
 145194            return low;
 195        }
 196
 1011197        if (bits < 64)
 198        {
 996199            discarded = (low & ((1UL << bits) - 1UL)) != 0UL;
 996200            return (middle << (64 - bits)) | (low >> bits);
 201        }
 202
 15203        int upperShift = bits - 64;
 15204        discarded = low != 0UL
 15205            || (upperShift != 0 && (middle & ((1UL << upperShift) - 1UL)) != 0UL);
 15206        return upperShift == 0
 15207            ? middle
 15208            : (high << (64 - upperShift)) | (middle >> upperShift);
 209    }
 210
 211    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 212    private static Signed192 GetFloorSquareRoot192(
 213        ulong valueHigh,
 214        ulong valueMiddle,
 215        ulong valueLow,
 216        out Signed192 remainder)
 217    {
 1656218        int pairIndex = (GetBitLength(valueHigh, valueMiddle, valueLow) - 1) >> 1;
 1656219        ulong rootHigh = 0UL;
 1656220        ulong rootLow = 0UL;
 1656221        ulong remainderHigh = 0UL;
 1656222        ulong remainderLow = 0UL;
 223
 240886224        for (; pairIndex >= 0; pairIndex--)
 225        {
 119615226            int pairShift = (pairIndex & 31) << 1;
 119615227            ulong pair = pairIndex >= 64
 119615228                ? (valueHigh >> pairShift) & 3UL
 119615229                : pairIndex >= 32
 119615230                    ? (valueMiddle >> pairShift) & 3UL
 119615231                    : (valueLow >> pairShift) & 3UL;
 232
 119615233            remainderHigh = (remainderHigh << 2) | (remainderLow >> 62);
 119615234            remainderLow = (remainderLow << 2) | pair;
 119615235            rootHigh = (rootHigh << 1) | (rootLow >> 63);
 119615236            rootLow <<= 1;
 237
 119615238            ulong candidateHigh = (rootHigh << 1) | (rootLow >> 63);
 119615239            ulong candidateLow = (rootLow << 1) | 1UL;
 119615240            if (remainderHigh < candidateHigh
 119615241                || (remainderHigh == candidateHigh && remainderLow < candidateLow))
 242            {
 243                continue;
 244            }
 245
 36247246            ulong originalRemainderLow = remainderLow;
 36247247            remainderLow -= candidateLow;
 36247248            remainderHigh -= candidateHigh + (originalRemainderLow < candidateLow ? 1UL : 0UL);
 36247249            rootLow++;
 250        }
 251
 1656252        remainder = new Signed192(0UL, remainderHigh, remainderLow);
 1656253        return new Signed192(0UL, rootHigh, rootLow);
 254    }
 255
 256    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 257    internal static void ShiftLeft(
 258        ulong high,
 259        ulong middle,
 260        ulong low,
 261        int bits,
 262        out ulong shiftedHigh,
 263        out ulong shiftedMiddle,
 264        out ulong shiftedLow)
 265    {
 623266        if (bits == 0)
 267        {
 234268            shiftedHigh = high;
 234269            shiftedMiddle = middle;
 234270            shiftedLow = low;
 234271            return;
 272        }
 273
 389274        shiftedHigh = (high << bits) | (middle >> (64 - bits));
 389275        shiftedMiddle = (middle << bits) | (low >> (64 - bits));
 389276        shiftedLow = low << bits;
 389277    }
 278
 279    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 280    internal static void ShiftLeftOne(ref ulong high, ref ulong middle, ref ulong low)
 281    {
 33429282        high = (high << 1) | (middle >> 63);
 33429283        middle = (middle << 1) | (low >> 63);
 33429284        low <<= 1;
 33429285    }
 286
 287    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 288    internal static void ShiftRightOne(ref ulong high, ref ulong middle, ref ulong low)
 289    {
 2353290        low = (low >> 1) | (middle << 63);
 2353291        middle = (middle >> 1) | (high << 63);
 2353292        high >>= 1;
 2353293    }
 294
 295    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 296    internal static int GetBitLength(ulong high, ulong middle, ulong low)
 297    {
 22597298        if (high != 0UL)
 2178299            return 192 - Fixed64.CountLeadingZeroes(high);
 20419300        if (middle != 0UL)
 1599301            return 128 - Fixed64.CountLeadingZeroes(middle);
 18820302        return 64 - Fixed64.CountLeadingZeroes(low);
 303    }
 304
 305    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 306    internal static void SubtractUnsigned(
 307        ref ulong high,
 308        ref ulong middle,
 309        ref ulong low,
 310        ulong subtractHigh,
 311        ulong subtractMiddle,
 312        ulong subtractLow)
 313    {
 30505314        ulong originalLow = low;
 30505315        low -= subtractLow;
 30505316        ulong borrow = originalLow < subtractLow ? 1UL : 0UL;
 317
 30505318        ulong middleSubtrahend = subtractMiddle + borrow;
 30505319        ulong middleOverflow = middleSubtrahend < subtractMiddle ? 1UL : 0UL;
 30505320        ulong originalMiddle = middle;
 30505321        middle -= middleSubtrahend;
 30505322        borrow = middleOverflow | (originalMiddle < middleSubtrahend ? 1UL : 0UL);
 30505323        high -= subtractHigh + borrow;
 30505324    }
 325}

/home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed320.cs

#LineLine coverage
 1//=======================================================================
 2// WideArithmetic.Signed320.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024–present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using System.Runtime.CompilerServices;
 10
 11namespace FixedMathSharp;
 12
 13/// <content>
 14/// Arithmetic helpers for <see cref="Signed320"/> values, including magnitude extraction
 15/// and combined multiply-subtract operations built from <see cref="Signed192"/> operands.
 16/// </content>
 17internal static partial class WideArithmetic
 18{
 19    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 20    internal static void GetMagnitude(
 21        Signed320 value,
 22        out ulong word4,
 23        out ulong word3,
 24        out ulong word2,
 25        out ulong word1,
 26        out ulong word0)
 27    {
 256285228        word4 = value.Word4;
 256285229        word3 = value.Word3;
 256285230        word2 = value.Word2;
 256285231        word1 = value.Word1;
 256285232        word0 = value.Word0;
 256285233        if (value.Sign >= 0)
 227887234            return;
 35
 28398036        word0 = unchecked(~word0 + 1UL);
 28398037        word1 = unchecked(~word1 + (word0 == 0UL ? 1UL : 0UL));
 28398038        word2 = unchecked(~word2 + (word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 28398039        word3 = unchecked(~word3 + (word2 == 0UL && word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 28398040        word4 = unchecked(~word4 + (word3 == 0UL && word2 == 0UL && word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 28398041    }
 42
 43    /// <summary>
 44    /// Returns the exact signed result of <c>(first * second) - (third * fourth)</c>.
 45    /// </summary>
 46    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 47    internal static Signed320 MultiplySubtract(
 48        Signed192 first,
 49        Signed192 second,
 50        Signed192 third,
 51        Signed192 fourth)
 52    {
 4907753        if (TryGetSigned95Magnitude(first, out ulong firstMiddle, out ulong firstLow)
 4907754            && TryGetSigned95Magnitude(second, out ulong secondMiddle, out ulong secondLow)
 4907755            && TryGetSigned95Magnitude(third, out ulong thirdMiddle, out ulong thirdLow)
 4907756            && TryGetSigned95Magnitude(fourth, out ulong fourthMiddle, out ulong fourthLow))
 57        {
 4544058            Signed192 narrowFirstProduct = MultiplySigned95(
 4544059                firstMiddle,
 4544060                firstLow,
 4544061                secondMiddle,
 4544062                secondLow,
 4544063                first.Sign * second.Sign < 0);
 4544064            Signed192 narrowSecondProduct = MultiplySigned95(
 4544065                thirdMiddle,
 4544066                thirdLow,
 4544067                fourthMiddle,
 4544068                fourthLow,
 4544069                third.Sign * fourth.Sign < 0);
 4544070            return Signed320.ExtendValue(SubtractSigned192(narrowFirstProduct, narrowSecondProduct));
 71        }
 72
 363773        Signed320 firstProduct = MultiplySigned192(first, second);
 363774        Signed320 secondProduct = MultiplySigned192(third, fourth);
 75
 363776        ulong word0 = unchecked(firstProduct.Word0 - secondProduct.Word0);
 363777        ulong borrow = firstProduct.Word0 < secondProduct.Word0 ? 1UL : 0UL;
 363778        ulong word1 = SubtractWord(firstProduct.Word1, secondProduct.Word1, ref borrow);
 363779        ulong word2 = SubtractWord(firstProduct.Word2, secondProduct.Word2, ref borrow);
 363780        ulong word3 = SubtractWord(firstProduct.Word3, secondProduct.Word3, ref borrow);
 363781        ulong word4 = unchecked(firstProduct.Word4 - secondProduct.Word4 - borrow);
 363782        return new Signed320(word4, word3, word2, word1, word0);
 83    }
 84
 85    /// <summary>
 86    /// Returns the signed sum of two <see cref="Signed192"/> products.
 87    /// </summary>
 88    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 89    internal static Signed320 AddProducts(
 90        Signed192 firstLeft,
 91        Signed192 firstRight,
 92        Signed192 secondLeft,
 93        Signed192 secondRight) =>
 11600994        AddSigned320(
 11600995            MultiplySigned192(firstLeft, firstRight),
 11600996            MultiplySigned192(secondLeft, secondRight));
 97
 98    /// <summary>
 99    /// Returns the signed sum of three <see cref="Signed192"/> products.
 100    /// </summary>
 101    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 102    internal static Signed320 AddProducts(
 103        Signed192 firstLeft,
 104        Signed192 firstRight,
 105        Signed192 secondLeft,
 106        Signed192 secondRight,
 107        Signed192 thirdLeft,
 108        Signed192 thirdRight) =>
 110752109        AddSigned320(
 110752110            AddProducts(
 110752111                firstLeft,
 110752112                firstRight,
 110752113                secondLeft,
 110752114                secondRight),
 110752115            MultiplySigned192(thirdLeft, thirdRight));
 116
 117    /// <summary>
 118    /// Returns the signed dot product of two three-component
 119    /// <see cref="Signed192"/> values.
 120    /// </summary>
 121    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 122    internal static Signed320 GetDotProduct3D(
 123        Signed192 leftX,
 124        Signed192 leftY,
 125        Signed192 leftZ,
 126        Signed192 rightX,
 127        Signed192 rightY,
 128        Signed192 rightZ) =>
 110541129        AddProducts(
 110541130            leftX,
 110541131            rightX,
 110541132            leftY,
 110541133            rightY,
 110541134            leftZ,
 110541135            rightZ);
 136
 137    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 138    internal static Signed320 AddSigned320(Signed320 left, Signed320 right)
 139    {
 754960140        ulong word0 = unchecked(left.Word0 + right.Word0);
 754960141        ulong carry = word0 < left.Word0 ? 1UL : 0UL;
 754960142        ulong word1 = unchecked(left.Word1 + right.Word1 + carry);
 754960143        carry = word1 < left.Word1 || (carry != 0UL && word1 == left.Word1) ? 1UL : 0UL;
 754960144        ulong word2 = unchecked(left.Word2 + right.Word2 + carry);
 754960145        carry = word2 < left.Word2 || (carry != 0UL && word2 == left.Word2) ? 1UL : 0UL;
 754960146        ulong word3 = unchecked(left.Word3 + right.Word3 + carry);
 147        // The high bit of the standard carry expression includes the incoming carry encoded in word3.
 754960148        carry = ((left.Word3 & right.Word3) | ((left.Word3 | right.Word3) & ~word3)) >> 63;
 754960149        return new Signed320(unchecked(left.Word4 + right.Word4 + carry), word3, word2, word1, word0);
 150    }
 151
 152    /// <summary>
 153    /// Subtracts exact five-word values without scalar conversion.
 154    /// </summary>
 155    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 156    internal static Signed320 SubtractSigned320(Signed320 left, Signed320 right)
 157    {
 258965158        ulong borrow = 0UL;
 258965159        ulong word0 = SubtractWord(left.Word0, right.Word0, ref borrow);
 258965160        ulong word1 = SubtractWord(left.Word1, right.Word1, ref borrow);
 258965161        ulong word2 = SubtractWord(left.Word2, right.Word2, ref borrow);
 258965162        ulong word3 = SubtractWord(left.Word3, right.Word3, ref borrow);
 258965163        return new Signed320(unchecked(left.Word4 - right.Word4 - borrow), word3, word2, word1, word0);
 164    }
 165
 166    /// <summary>
 167    /// Compares unsigned magnitudes of signed five-word values.
 168    /// </summary>
 169    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 170    internal static int CompareMagnitude(Signed320 left, Signed320 right)
 171    {
 6697172        GetMagnitude(
 6697173            left,
 6697174            out ulong leftWord4,
 6697175            out ulong leftWord3,
 6697176            out ulong leftWord2,
 6697177            out ulong leftWord1,
 6697178            out ulong leftWord0);
 6697179        GetMagnitude(
 6697180            right,
 6697181            out ulong rightWord4,
 6697182            out ulong rightWord3,
 6697183            out ulong rightWord2,
 6697184            out ulong rightWord1,
 6697185            out ulong rightWord0);
 6697186        return CompareUnsigned(
 6697187            leftWord4,
 6697188            leftWord3,
 6697189            leftWord2,
 6697190            leftWord1,
 6697191            leftWord0,
 6697192            rightWord4,
 6697193            rightWord3,
 6697194            rightWord2,
 6697195            rightWord1,
 6697196            rightWord0);
 197    }
 198
 199    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 200    internal static Signed320 MultiplySigned192(Signed192 left, Signed192 right)
 201    {
 3576591202        GetMagnitude(left, out ulong leftHigh, out ulong leftMiddle, out ulong leftLow);
 3576591203        GetMagnitude(right, out ulong rightHigh, out ulong rightMiddle, out ulong rightLow);
 204
 3576591205        MultiplyUnsigned128(
 3576591206            leftMiddle,
 3576591207            leftLow,
 3576591208            rightMiddle,
 3576591209            rightLow,
 3576591210            out ulong word3,
 3576591211            out ulong word2,
 3576591212            out ulong word1,
 3576591213            out ulong word0);
 214
 3576591215        ulong word4 = 0UL;
 3576591216        if ((leftHigh | rightHigh) != 0UL)
 217        {
 444298218            AddProductAt2(ref word4, ref word3, ref word2, leftLow, rightHigh);
 444298219            AddProductAt2(ref word4, ref word3, ref word2, leftHigh, rightLow);
 444298220            AddProductAt3(ref word4, ref word3, leftMiddle, rightHigh);
 444298221            AddProductAt3(ref word4, ref word3, leftHigh, rightMiddle);
 444298222            word4 = unchecked(word4 + (leftHigh * rightHigh));
 223        }
 224
 3576591225        if (left.Sign * right.Sign < 0)
 226        {
 501915227            word0 = unchecked(~word0 + 1UL);
 501915228            word1 = unchecked(~word1 + (word0 == 0UL ? 1UL : 0UL));
 501915229            word2 = unchecked(~word2 + (word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 501915230            word3 = unchecked(~word3 + (word2 == 0UL && word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 501915231            word4 = unchecked(~word4 + (word3 == 0UL && word2 == 0UL && word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 232        }
 233
 3576591234        return new Signed320(word4, word3, word2, word1, word0);
 235    }
 236
 237    /// <summary>
 238    /// Compares a normalized component square with the squared midpoint between
 239    /// adjacent Q32.32 raw candidates.
 240    /// </summary>
 241    internal static int CompareNormalizedComponentToMidpoint(
 242        Signed320 componentSquare,
 243        Signed320 squaredMagnitude,
 244        ulong lowerCandidateRaw)
 245    {
 580246        ulong doubledMidpoint = (lowerCandidateRaw << 1) + 1UL;
 580247        Fixed64.Multiply64To128(
 580248            doubledMidpoint,
 580249            doubledMidpoint,
 580250            out ulong multiplierHigh,
 580251            out ulong multiplierLow);
 252
 580253        if (Signed192.TryNarrowSigned(squaredMagnitude, out Signed192 narrowSquaredMagnitude))
 254        {
 568255            Signed320 rightNarrow = MultiplySigned192(
 568256                narrowSquaredMagnitude,
 568257                new Signed192(0UL, multiplierHigh, multiplierLow));
 568258            return CompareUnsigned(
 568259                (componentSquare.Word3 << 2) | (componentSquare.Word2 >> 62),
 568260                (componentSquare.Word2 << 2) | (componentSquare.Word1 >> 62),
 568261                (componentSquare.Word1 << 2) | (componentSquare.Word0 >> 62),
 568262                componentSquare.Word0 << 2,
 568263                0UL,
 568264                rightNarrow.Word4,
 568265                rightNarrow.Word3,
 568266                rightNarrow.Word2,
 568267                rightNarrow.Word1,
 568268                rightNarrow.Word0);
 269        }
 270
 12271        Span<ulong> left = stackalloc ulong[6];
 12272        left.Clear();
 12273        left[1] = componentSquare.Word0 << 2;
 12274        left[2] = (componentSquare.Word1 << 2) | (componentSquare.Word0 >> 62);
 12275        left[3] = (componentSquare.Word2 << 2) | (componentSquare.Word1 >> 62);
 12276        left[4] = (componentSquare.Word3 << 2) | (componentSquare.Word2 >> 62);
 12277        left[5] = (componentSquare.Word4 << 2) | (componentSquare.Word3 >> 62);
 12278        Span<ulong> right = stackalloc ulong[6];
 12279        right.Clear();
 12280        Span<ulong> magnitude = stackalloc ulong[5]
 12281        {
 12282            squaredMagnitude.Word0,
 12283            squaredMagnitude.Word1,
 12284            squaredMagnitude.Word2,
 12285            squaredMagnitude.Word3,
 12286            squaredMagnitude.Word4,
 12287        };
 288
 144289        for (int index = 0; index < magnitude.Length; index++)
 290        {
 60291            Fixed64.Multiply64To128(magnitude[index], multiplierLow, out ulong high, out ulong low);
 60292            AddWord(right, index, low);
 60293            AddWord(right, index + 1, high);
 60294            if (multiplierHigh == 0UL)
 295                continue;
 296
 45297            Fixed64.Multiply64To128(magnitude[index], multiplierHigh, out high, out low);
 45298            AddWord(right, index + 1, low);
 45299            if (index + 2 < right.Length)
 36300                AddWord(right, index + 2, high);
 301        }
 302
 12303        return CompareMagnitudeEqualLength(left, right);
 304    }
 305
 306    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 307    internal static void ShiftLeft(
 308        ulong word4,
 309        ulong word3,
 310        ulong word2,
 311        ulong word1,
 312        ulong word0,
 313        int bits,
 314        out ulong shiftedWord4,
 315        out ulong shiftedWord3,
 316        out ulong shiftedWord2,
 317        out ulong shiftedWord1,
 318        out ulong shiftedWord0)
 319    {
 13320        if (bits == 0)
 321        {
 2322            shiftedWord4 = word4;
 2323            shiftedWord3 = word3;
 2324            shiftedWord2 = word2;
 2325            shiftedWord1 = word1;
 2326            shiftedWord0 = word0;
 2327            return;
 328        }
 329
 11330        shiftedWord4 = (word4 << bits) | (word3 >> (64 - bits));
 11331        shiftedWord3 = (word3 << bits) | (word2 >> (64 - bits));
 11332        shiftedWord2 = (word2 << bits) | (word1 >> (64 - bits));
 11333        shiftedWord1 = (word1 << bits) | (word0 >> (64 - bits));
 11334        shiftedWord0 = word0 << bits;
 11335    }
 336
 337    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 338    internal static void ShiftLeftOne(
 339        ref ulong word4,
 340        ref ulong word3,
 341        ref ulong word2,
 342        ref ulong word1,
 343        ref ulong word0)
 344    {
 11187345        word4 = (word4 << 1) | (word3 >> 63);
 11187346        word3 = (word3 << 1) | (word2 >> 63);
 11187347        word2 = (word2 << 1) | (word1 >> 63);
 11187348        word1 = (word1 << 1) | (word0 >> 63);
 11187349        word0 <<= 1;
 11187350    }
 351
 352    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 353    internal static void ShiftRightOne(
 354        ref ulong word4,
 355        ref ulong word3,
 356        ref ulong word2,
 357        ref ulong word1,
 358        ref ulong word0)
 359    {
 99360        word0 = (word0 >> 1) | (word1 << 63);
 99361        word1 = (word1 >> 1) | (word2 << 63);
 99362        word2 = (word2 >> 1) | (word3 << 63);
 99363        word3 = (word3 >> 1) | (word4 << 63);
 99364        word4 >>= 1;
 99365    }
 366
 367    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 368    internal static int GetBitLength(
 369        ulong word4,
 370        ulong word3,
 371        ulong word2,
 372        ulong word1,
 373        ulong word0)
 374    {
 2808375        if (word4 != 0UL)
 93376            return 320 - Fixed64.CountLeadingZeroes(word4);
 2715377        if (word3 != 0UL)
 1404378            return 256 - Fixed64.CountLeadingZeroes(word3);
 1311379        if (word2 != 0UL)
 542380            return 192 - Fixed64.CountLeadingZeroes(word2);
 769381        if (word1 != 0UL)
 573382            return 128 - Fixed64.CountLeadingZeroes(word1);
 196383        return 64 - Fixed64.CountLeadingZeroes(word0);
 384    }
 385
 386    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 387    internal static void SubtractUnsigned(
 388        ref ulong word4,
 389        ref ulong word3,
 390        ref ulong word2,
 391        ref ulong word1,
 392        ref ulong word0,
 393        ulong subtractWord4,
 394        ulong subtractWord3,
 395        ulong subtractWord2,
 396        ulong subtractWord1,
 397        ulong subtractWord0)
 398    {
 5440399        ulong borrow = 0UL;
 5440400        word0 = SubtractWord(word0, subtractWord0, ref borrow);
 5440401        word1 = SubtractWord(word1, subtractWord1, ref borrow);
 5440402        word2 = SubtractWord(word2, subtractWord2, ref borrow);
 5440403        word3 = SubtractWord(word3, subtractWord3, ref borrow);
 5440404        word4 = unchecked(word4 - subtractWord4 - borrow);
 5440405    }
 406}

/home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed576.cs

#LineLine coverage
 1//=======================================================================
 2// WideArithmetic.Signed576.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024–present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using System.Runtime.CompilerServices;
 10
 11namespace FixedMathSharp;
 12
 13/// <content>
 14/// Arithmetic helpers for <see cref="Signed576"/>: magnitude extraction, comparison,
 15/// and exact addition/subtraction operating directly on the nine-word representation.
 16/// </content>
 17internal static partial class WideArithmetic
 18{
 19    internal static void GetMagnitude(Signed576 value, Span<ulong> magnitude)
 20    {
 153417721        magnitude.Clear();
 153417722        magnitude[0] = value.Word0;
 153417723        magnitude[1] = value.Word1;
 153417724        magnitude[2] = value.Word2;
 153417725        magnitude[3] = value.Word3;
 153417726        magnitude[4] = value.Word4;
 153417727        magnitude[5] = value.Word5;
 153417728        magnitude[6] = value.Word6;
 153417729        magnitude[7] = value.Word7;
 153417730        magnitude[8] = value.Word8;
 153417731        if (value.Sign >= 0)
 127865632            return;
 33
 25552134        ulong carry = 1UL;
 511042035        for (int index = 0; index < 9; index++)
 229968936            magnitude[index] = AddSignedWord(~magnitude[index], 0UL, ref carry);
 25552137    }
 38
 39    /// <summary>
 40    /// Compares two nonnegative nine-word values.
 41    /// </summary>
 42    internal static int CompareNonNegative(Signed576 left, Signed576 right)
 43    {
 3513844        if (left.Word8 != right.Word8) return left.Word8 < right.Word8 ? -1 : 1;
 3513645        if (left.Word7 != right.Word7) return left.Word7 < right.Word7 ? -1 : 1;
 3535546        if (left.Word6 != right.Word6) return left.Word6 < right.Word6 ? -1 : 1;
 3531347        if (left.Word5 != right.Word5) return left.Word5 < right.Word5 ? -1 : 1;
 3559748        if (left.Word4 != right.Word4) return left.Word4 < right.Word4 ? -1 : 1;
 5913949        if (left.Word3 != right.Word3) return left.Word3 < right.Word3 ? -1 : 1;
 963950        if (left.Word2 != right.Word2) return left.Word2 < right.Word2 ? -1 : 1;
 969151        if (left.Word1 != right.Word1) return left.Word1 < right.Word1 ? -1 : 1;
 177952        return left.Word0 == right.Word0 ? 0 : left.Word0 < right.Word0 ? -1 : 1;
 53    }
 54
 55    /// <summary>
 56    /// Adds exact nine-word values without scalar conversion.
 57    /// </summary>
 58    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 59    internal static Signed576 AddSigned576(Signed576 left, Signed576 right)
 60    {
 112940061        ulong carry = 0UL;
 112940062        ulong word0 = AddSignedWord(left.Word0, right.Word0, ref carry);
 112940063        ulong word1 = AddSignedWord(left.Word1, right.Word1, ref carry);
 112940064        ulong word2 = AddSignedWord(left.Word2, right.Word2, ref carry);
 112940065        ulong word3 = AddSignedWord(left.Word3, right.Word3, ref carry);
 112940066        ulong word4 = AddSignedWord(left.Word4, right.Word4, ref carry);
 112940067        ulong word5 = AddSignedWord(left.Word5, right.Word5, ref carry);
 112940068        ulong word6 = AddSignedWord(left.Word6, right.Word6, ref carry);
 112940069        ulong word7 = AddSignedWord(left.Word7, right.Word7, ref carry);
 112940070        ulong word8 = unchecked(left.Word8 + right.Word8 + carry);
 112940071        return new Signed576(word8, word7, word6, word5, word4, word3, word2, word1, word0);
 72    }
 73
 3274    internal static Signed576 Double(Signed576 value) => AddSigned576(value, value);
 75
 76    /// <summary>
 77    /// Subtracts exact nine-word values without scalar conversion.
 78    /// </summary>
 79    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 80    internal static Signed576 SubtractSigned576(Signed576 left, Signed576 right)
 81    {
 67796782        ulong borrow = 0UL;
 67796783        ulong word0 = SubtractWord(left.Word0, right.Word0, ref borrow);
 67796784        ulong word1 = SubtractWord(left.Word1, right.Word1, ref borrow);
 67796785        ulong word2 = SubtractWord(left.Word2, right.Word2, ref borrow);
 67796786        ulong word3 = SubtractWord(left.Word3, right.Word3, ref borrow);
 67796787        ulong word4 = SubtractWord(left.Word4, right.Word4, ref borrow);
 67796788        ulong word5 = SubtractWord(left.Word5, right.Word5, ref borrow);
 67796789        ulong word6 = SubtractWord(left.Word6, right.Word6, ref borrow);
 67796790        ulong word7 = SubtractWord(left.Word7, right.Word7, ref borrow);
 67796791        ulong word8 = unchecked(left.Word8 - right.Word8 - borrow);
 67796792        return new Signed576(word8, word7, word6, word5, word4, word3, word2, word1, word0);
 93    }
 94
 95    internal static Signed576 MultiplySigned320(Signed320 left, Signed192 right) =>
 61196        MultiplySigned576(Signed576.ExtendValue(left), right);
 97
 98    /// <summary>
 99    /// Multiplies signed five-word values in the finite-axis domain exactly.
 100    /// </summary>
 101    /// <remarks>
 102    /// Callers guarantee magnitudes below 262 bits, so the product is below
 103    /// 523 bits and cannot overflow the nine-word result.
 104    /// </remarks>
 105    internal static Signed576 MultiplySigned320(Signed320 left, Signed320 right)
 106    {
 1728337107        if (Signed192.TryNarrowSigned(left, out Signed192 narrowLeft)
 1728337108            && Signed192.TryNarrowSigned(right, out Signed192 narrowRight)
 1728337109            && GetMagnitudeBitLength(narrowLeft) + GetMagnitudeBitLength(narrowRight) <= 319)
 110        {
 1218083111            return Signed576.ExtendValue(MultiplySigned192(narrowLeft, narrowRight));
 112        }
 113
 510254114        GetMagnitude(
 510254115            left,
 510254116            out ulong leftWord4,
 510254117            out ulong leftWord3,
 510254118            out ulong leftWord2,
 510254119            out ulong leftWord1,
 510254120            out ulong leftWord0);
 510254121        GetMagnitude(
 510254122            right,
 510254123            out ulong rightWord4,
 510254124            out ulong rightWord3,
 510254125            out ulong rightWord2,
 510254126            out ulong rightWord1,
 510254127            out ulong rightWord0);
 128
 510254129        Span<ulong> leftMagnitude = stackalloc ulong[5]
 510254130        {
 510254131            leftWord0,
 510254132            leftWord1,
 510254133            leftWord2,
 510254134            leftWord3,
 510254135            leftWord4,
 510254136        };
 510254137        Span<ulong> rightMagnitude = stackalloc ulong[5]
 510254138        {
 510254139            rightWord0,
 510254140            rightWord1,
 510254141            rightWord2,
 510254142            rightWord3,
 510254143            rightWord4,
 510254144        };
 510254145        Span<ulong> product = stackalloc ulong[9];
 510254146        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 147
 510254148        if (left.Sign * right.Sign < 0)
 149        {
 51166150            ulong carry = 1UL;
 1023320151            for (int index = 0; index < product.Length; index++)
 460494152                product[index] = AddSignedWord(~product[index], 0UL, ref carry);
 153        }
 154
 510254155        return new Signed576(
 510254156            product[8],
 510254157            product[7],
 510254158            product[6],
 510254159            product[5],
 510254160            product[4],
 510254161            product[3],
 510254162            product[2],
 510254163            product[1],
 510254164            product[0]);
 165    }
 166
 167    /// <summary>
 168    /// Multiplies a signed nine-word value by a signed one-word value whose
 169    /// proven product fits in nine words.
 170    /// </summary>
 171    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 172    internal static Signed576 MultiplySigned576(Signed576 left, long right)
 173    {
 194728174        ulong factor = Fixed64.AbsToUInt64(right);
 194728175        ulong carry = 0UL;
 194728176        ulong word0 = MultiplySigned576Word(left.Word0, factor, ref carry);
 194728177        ulong word1 = MultiplySigned576Word(left.Word1, factor, ref carry);
 194728178        ulong word2 = MultiplySigned576Word(left.Word2, factor, ref carry);
 194728179        ulong word3 = MultiplySigned576Word(left.Word3, factor, ref carry);
 194728180        ulong word4 = MultiplySigned576Word(left.Word4, factor, ref carry);
 194728181        ulong word5 = MultiplySigned576Word(left.Word5, factor, ref carry);
 194728182        ulong word6 = MultiplySigned576Word(left.Word6, factor, ref carry);
 194728183        ulong word7 = MultiplySigned576Word(left.Word7, factor, ref carry);
 194728184        ulong word8 = MultiplySigned576Word(left.Word8, factor, ref carry);
 194728185        Signed576 product = new(
 194728186            word8, word7, word6, word5, word4, word3, word2, word1, word0);
 194728187        return right < 0L
 194728188            ? SubtractSigned576(default, product)
 194728189            : product;
 190    }
 191
 192    /// <summary>
 193    /// Multiplies a signed nine-word value by a signed three-word value whose
 194    /// proven product fits in nine words.
 195    /// </summary>
 196    internal static Signed576 MultiplySigned576(Signed576 left, Signed192 right)
 197    {
 994956198        if (Signed192.TryNarrowSigned(left, out Signed192 narrowLeft)
 994956199            && GetMagnitudeBitLength(narrowLeft) + GetMagnitudeBitLength(right) <= 319)
 591179200            return Signed576.ExtendValue(MultiplySigned192(narrowLeft, right));
 403777201        if (Signed320.TryNarrowSigned(left, out Signed320 mediumLeft))
 332342202            return MultiplySigned320(mediumLeft, Signed320.ExtendValue(right));
 203
 71435204        Span<ulong> leftMagnitude = stackalloc ulong[9];
 71435205        Span<ulong> rightMagnitude = stackalloc ulong[3];
 71435206        GetMagnitude(left, leftMagnitude);
 71435207        GetMagnitude(right, out rightMagnitude[2], out rightMagnitude[1], out rightMagnitude[0]);
 71435208        Span<ulong> product = stackalloc ulong[12];
 71435209        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 210
 71435211        if (left.Sign * right.Sign < 0)
 212        {
 203213            ulong carry = 1UL;
 4060214            for (int index = 0; index < 9; index++)
 1827215                product[index] = AddSignedWord(~product[index], 0UL, ref carry);
 216        }
 217
 71435218        return new Signed576(
 71435219            product[8], product[7], product[6], product[5], product[4],
 71435220            product[3], product[2], product[1], product[0]);
 221    }
 222
 223    internal static Signed576 MultiplySigned576(Signed576 value, Signed192 first, Signed192 second) =>
 258224        MultiplySigned576(
 258225            MultiplySigned576(value, first),
 258226            second);
 227
 228    internal static Signed576 MultiplySigned576(
 229        Signed576 value,
 230        Signed192 first,
 231        Signed192 second,
 232        Signed192 third) =>
 68233        MultiplySigned576(
 68234            MultiplySigned576(value, first, second),
 68235            third);
 236
 237    internal static Signed576 MultiplySigned576(
 238        Signed576 value,
 239        Signed192 first,
 240        Signed192 second,
 241        Signed192 third,
 242        Signed192 fourth) =>
 16243        MultiplySigned576(
 16244            MultiplySigned576(value, first, second, third),
 16245            fourth);
 246
 247    /// <summary>
 248    /// Returns the exact floor of the square root after applying the Q32.32
 249    /// parameter scale: <c>floor(sqrt(value * 2^64))</c>. The caller must
 250    /// prove <paramref name="value"/> is nonnegative and less than 2^523 so
 251    /// the scaled root and restoring remainder fit their five-word storage.
 252    /// </summary>
 253    internal static Signed320 GetFloorSquareRootScaledByFixed64(Signed576 value)
 254    {
 2369255        if (value.IsZero)
 4256            return default;
 257
 2365258        if ((value.Word8 | value.Word7 | value.Word6 | value.Word5 | value.Word4) == 0UL
 2365259            && (value.Word3 & (1UL << 63)) == 0UL)
 260        {
 1023261            Signed320 shifted = new(value.Word3, value.Word2, value.Word1, value.Word0, 0UL);
 1023262            Signed192 narrowRoot = GetFloorSquareRoot(shifted, out _);
 1023263            return Signed320.ExtendValue(narrowRoot);
 264        }
 265
 1342266        int bitLength = GetBitLength(value);
 1342267        int rootBitLength = ((bitLength + 1) >> 1) + FixedMath.SHIFT_AMOUNT_I;
 1342268        int activeWords = System.Math.Min(5, (rootBitLength + 64) >> 6);
 1342269        Span<ulong> rootStorage = stackalloc ulong[5];
 1342270        Span<ulong> remainderStorage = stackalloc ulong[5];
 1342271        Span<ulong> candidateStorage = stackalloc ulong[5];
 1342272        Span<ulong> root = rootStorage[..activeWords];
 1342273        Span<ulong> remainder = remainderStorage[..activeWords];
 1342274        Span<ulong> candidate = candidateStorage[..activeWords];
 1342275        rootStorage.Clear();
 1342276        remainder.Clear();
 1342277        int pairIndex = (bitLength - 1) >> 1;
 477738278        for (; pairIndex >= -FixedMath.SHIFT_AMOUNT_I; pairIndex--)
 279        {
 238198280            ShiftLeft(remainder, 2);
 238198281            if (pairIndex >= 0)
 195254282                remainder[0] |= GetBitPair(value, pairIndex);
 238198283            ShiftLeft(root, 1);
 284
 238198285            root.CopyTo(candidate);
 238198286            ShiftLeft(candidate, 1);
 238198287            candidate[0] |= 1UL;
 238198288            if (CompareMagnitudeEqualLength(remainder, candidate) < 0)
 289                continue;
 290
 35361291            SubtractEqualMagnitudes(remainder, candidate, remainder);
 35361292            root[0]++;
 293        }
 294
 1342295        return new Signed320(rootStorage[4], rootStorage[3], rootStorage[2], rootStorage[1], rootStorage[0]);
 296    }
 297
 1672298    internal static Signed320 Negate(Signed320 value) => SubtractSigned320(default, value);
 299
 300    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 301    internal static Signed576 Absolute(Signed576 value) =>
 106302        value.Sign < 0
 106303            ? SubtractSigned576(default, value)
 106304            : value;
 305
 306    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 307    internal static Signed576 ClampToNonNegative(Signed576 value)
 308    {
 309        // Two's-complement sign masking keeps this hot-path clamp branchless.
 2589310        ulong mask = ~unchecked((ulong)((long)value.Word8 >> 63));
 2589311        return new Signed576(
 2589312            value.Word8 & mask,
 2589313            value.Word7 & mask,
 2589314            value.Word6 & mask,
 2589315            value.Word5 & mask,
 2589316            value.Word4 & mask,
 2589317            value.Word3 & mask,
 2589318            value.Word2 & mask,
 2589319            value.Word1 & mask,
 2589320            value.Word0 & mask);
 321    }
 322
 323    private static int GetBitLength(Signed576 value)
 324    {
 1342325        if (value.Word8 != 0UL)
 2326            return 576 - Fixed64.CountLeadingZeroes(value.Word8);
 1340327        if (value.Word7 != 0UL)
 12328            return 512 - Fixed64.CountLeadingZeroes(value.Word7);
 1328329        if (value.Word6 != 0UL)
 191330            return 448 - Fixed64.CountLeadingZeroes(value.Word6);
 1137331        if (value.Word5 != 0UL)
 183332            return 384 - Fixed64.CountLeadingZeroes(value.Word5);
 954333        if (value.Word4 != 0UL)
 949334            return 320 - Fixed64.CountLeadingZeroes(value.Word4);
 335        // Values below 2^255 use the Signed320 restoring-square-root path.
 336        // Reaching this wide path therefore proves Word3's high bit is set.
 5337        return 256 - Fixed64.CountLeadingZeroes(value.Word3);
 338    }
 339
 340    private static int GetMagnitudeBitLength(Signed192 value)
 341    {
 3649636342        GetMagnitude(value, out ulong high, out ulong middle, out ulong low);
 3649636343        if (high != 0UL)
 406497344            return 128 + 64 - Fixed64.CountLeadingZeroes(high);
 3243139345        if (middle != 0UL)
 1097864346            return 64 + 64 - Fixed64.CountLeadingZeroes(middle);
 2145275347        return low == 0UL ? 0 : 64 - Fixed64.CountLeadingZeroes(low);
 348    }
 349
 350    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 351    private static ulong MultiplySigned576Word(
 352        ulong value,
 353        ulong factor,
 354        ref ulong carry)
 355    {
 1752552356        Fixed64.Multiply64To128(
 1752552357            value,
 1752552358            factor,
 1752552359            out ulong high,
 1752552360            out ulong low);
 1752552361        ulong product = unchecked(low + carry);
 1752552362        carry = unchecked(high + (product < low ? 1UL : 0UL));
 1752552363        return product;
 364    }
 365
 366    private static ulong GetBitPair(Signed576 value, int pairIndex)
 367    {
 195254368        int bitIndex = pairIndex << 1;
 195254369        int shift = bitIndex & 63;
 195254370        ulong word = (bitIndex >> 6) switch
 195254371        {
 42944372            0 => value.Word0,
 42944373            1 => value.Word1,
 42944374            2 => value.Word2,
 42944375            3 => value.Word3,
 13865376            4 => value.Word4,
 8132377            5 => value.Word5,
 1314378            6 => value.Word6,
 159379            7 => value.Word7,
 8380            _ => value.Word8,
 195254381        };
 195254382        return (word >> shift) & 3UL;
 383    }
 384
 385    private static void ShiftLeft(Span<ulong> value, int bits)
 386    {
 714594387        ulong carry = 0UL;
 6247752388        for (int index = 0; index < value.Length; index++)
 389        {
 2409282390            ulong nextCarry = value[index] >> (64 - bits);
 2409282391            value[index] = (value[index] << bits) | carry;
 2409282392            carry = nextCarry;
 393        }
 714594394    }
 395
 396    private static Signed576 MultiplyNonNegativeToSigned576(
 397        Signed576 left,
 398        Signed576 right)
 399    {
 287400        Span<ulong> leftWords = stackalloc ulong[9];
 287401        Span<ulong> rightWords = stackalloc ulong[9];
 287402        Span<ulong> product = stackalloc ulong[18];
 287403        GetMagnitude(left, leftWords);
 287404        GetMagnitude(right, rightWords);
 287405        MultiplyMagnitudes(leftWords, rightWords, product);
 287406        return new Signed576(
 287407            product[8],
 287408            product[7],
 287409            product[6],
 287410            product[5],
 287411            product[4],
 287412            product[3],
 287413            product[2],
 287414            product[1],
 287415            product[0]);
 416    }
 417}

/home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed704.cs

#LineLine coverage
 1//=======================================================================
 2// WideArithmetic.Signed704.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024–present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using System.Runtime.CompilerServices;
 10
 11namespace FixedMathSharp;
 12
 13/// <content>
 14/// Arithmetic helpers for <see cref="Signed704"/>, including magnitude extraction,
 15/// signed multiplication producing an eleven-word result, and square root computation.
 16/// </content>
 17internal static partial class WideArithmetic
 18{
 19    internal static void GetMagnitude(Signed704 value, Span<ulong> magnitude)
 20    {
 27368321        magnitude.Clear();
 27368322        magnitude[0] = value.Word0;
 27368323        magnitude[1] = value.Word1;
 27368324        magnitude[2] = value.Word2;
 27368325        magnitude[3] = value.Word3;
 27368326        magnitude[4] = value.Word4;
 27368327        magnitude[5] = value.Word5;
 27368328        magnitude[6] = value.Word6;
 27368329        magnitude[7] = value.Word7;
 27368330        magnitude[8] = value.Word8;
 27368331        magnitude[9] = value.Word9;
 27368332        magnitude[10] = value.Word10;
 27368333        if (value.Sign >= 0)
 22949434            return;
 35
 4418936        ulong carry = 1UL;
 106053637        for (int index = 0; index < 11; index++)
 48607938            magnitude[index] = AddSignedWord(~magnitude[index], 0UL, ref carry);
 4418939    }
 40
 41    /// <summary>
 42    /// Multiplies a signed nine-word value by a signed five-word value whose
 43    /// proven product fits in eleven words.
 44    /// </summary>
 45    internal static Signed704 MultiplySigned576ToSigned704(Signed576 left, Signed320 right)
 46    {
 72498047        Span<ulong> leftMagnitude = stackalloc ulong[9];
 72498048        Span<ulong> rightMagnitude = stackalloc ulong[5];
 72498049        GetMagnitude(left, leftMagnitude);
 72498050        CopyMagnitude(right, rightMagnitude);
 72498051        Span<ulong> product = stackalloc ulong[14];
 72498052        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 72498053        ApplySigned704Sign(product, left.Sign * right.Sign < 0);
 72498054        return CreateSigned704(product);
 55    }
 56
 57    /// <summary>
 58    /// Multiplies a nonnegative nine-word value by a nonnegative three-word
 59    /// value whose proven product fits in eleven words.
 60    /// </summary>
 61    internal static Signed704 MultiplyNonNegative(Signed576 left, Signed192 right)
 62    {
 2002963        Span<ulong> leftMagnitude = stackalloc ulong[9];
 2002964        Span<ulong> rightMagnitude = stackalloc ulong[3];
 2002965        GetMagnitude(left, leftMagnitude);
 2002966        GetMagnitude(right, out rightMagnitude[2], out rightMagnitude[1], out rightMagnitude[0]);
 2002967        Span<ulong> product = stackalloc ulong[12];
 2002968        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 2002969        return new Signed704(
 2002970            product[10], product[9], product[8], product[7], product[6], product[5],
 2002971            product[4], product[3], product[2], product[1], product[0]);
 72    }
 73
 74    /// <summary>
 75    /// Returns the exact floor square root of a nonnegative eleven-word value.
 76    /// </summary>
 77    internal static Signed576 GetFloorSquareRoot(Signed704 value)
 78    {
 7232979        if (value.IsZero)
 4480            return default;
 81
 7228582        Span<ulong> root = stackalloc ulong[6];
 7228583        Span<ulong> remainder = stackalloc ulong[6];
 7228584        Span<ulong> candidate = stackalloc ulong[6];
 7228585        root.Clear();
 7228586        remainder.Clear();
 1396969487        for (int pairIndex = (GetBitLength(value) - 1) >> 1; pairIndex >= 0; pairIndex--)
 88        {
 691256289            ShiftLeftMagnitude(remainder, 2);
 691256290            remainder[0] |= GetBitPair(value, pairIndex);
 691256291            ShiftLeftMagnitude(root, 1);
 691256292            root.CopyTo(candidate);
 691256293            ShiftLeftMagnitude(candidate, 1);
 691256294            candidate[0] |= 1UL;
 691256295            if (CompareMagnitudeEqualLength(remainder, candidate) < 0)
 96                continue;
 97
 141969998            SubtractEqualMagnitudes(remainder, candidate, remainder);
 141969999            root[0]++;
 100        }
 101
 72285102        return new Signed576(
 72285103            0UL, 0UL, 0UL,
 72285104            root[5], root[4], root[3], root[2], root[1], root[0]);
 105    }
 106
 107    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 108    internal static Signed704 AddSigned704(Signed704 left, Signed704 right)
 109    {
 631020110        ulong carry = 0UL;
 631020111        ulong word0 = AddSignedWord(left.Word0, right.Word0, ref carry);
 631020112        ulong word1 = AddSignedWord(left.Word1, right.Word1, ref carry);
 631020113        ulong word2 = AddSignedWord(left.Word2, right.Word2, ref carry);
 631020114        ulong word3 = AddSignedWord(left.Word3, right.Word3, ref carry);
 631020115        ulong word4 = AddSignedWord(left.Word4, right.Word4, ref carry);
 631020116        ulong word5 = AddSignedWord(left.Word5, right.Word5, ref carry);
 631020117        ulong word6 = AddSignedWord(left.Word6, right.Word6, ref carry);
 631020118        ulong word7 = AddSignedWord(left.Word7, right.Word7, ref carry);
 631020119        ulong word8 = AddSignedWord(left.Word8, right.Word8, ref carry);
 631020120        ulong word9 = AddSignedWord(left.Word9, right.Word9, ref carry);
 631020121        ulong word10 = unchecked(left.Word10 + right.Word10 + carry);
 631020122        return new Signed704(word10, word9, word8, word7, word6, word5, word4, word3, word2, word1, word0);
 123    }
 124
 125    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 126    internal static Signed704 SubtractSigned704(Signed704 left, Signed704 right)
 127    {
 65755128        ulong borrow = 0UL;
 65755129        ulong word0 = SubtractWord(left.Word0, right.Word0, ref borrow);
 65755130        ulong word1 = SubtractWord(left.Word1, right.Word1, ref borrow);
 65755131        ulong word2 = SubtractWord(left.Word2, right.Word2, ref borrow);
 65755132        ulong word3 = SubtractWord(left.Word3, right.Word3, ref borrow);
 65755133        ulong word4 = SubtractWord(left.Word4, right.Word4, ref borrow);
 65755134        ulong word5 = SubtractWord(left.Word5, right.Word5, ref borrow);
 65755135        ulong word6 = SubtractWord(left.Word6, right.Word6, ref borrow);
 65755136        ulong word7 = SubtractWord(left.Word7, right.Word7, ref borrow);
 65755137        ulong word8 = SubtractWord(left.Word8, right.Word8, ref borrow);
 65755138        ulong word9 = SubtractWord(left.Word9, right.Word9, ref borrow);
 65755139        ulong word10 = unchecked(left.Word10 - right.Word10 - borrow);
 65755140        return new Signed704(
 65755141            word10,
 65755142            word9,
 65755143            word8,
 65755144            word7,
 65755145            word6,
 65755146            word5,
 65755147            word4,
 65755148            word3,
 65755149            word2,
 65755150            word1,
 65755151            word0);
 152    }
 153
 154    internal static int CompareNonNegative(
 155        Signed704 left,
 156        Signed704 right)
 157    {
 8813158        if (left.Word10 != right.Word10) return left.Word10 < right.Word10 ? -1 : 1;
 8811159        if (left.Word9 != right.Word9) return left.Word9 < right.Word9 ? -1 : 1;
 8809160        if (left.Word8 != right.Word8) return left.Word8 < right.Word8 ? -1 : 1;
 8812161        if (left.Word7 != right.Word7) return left.Word7 < right.Word7 ? -1 : 1;
 8823162        if (left.Word6 != right.Word6) return left.Word6 < right.Word6 ? -1 : 1;
 8797163        if (left.Word5 != right.Word5) return left.Word5 < right.Word5 ? -1 : 1;
 17401164        if (left.Word4 != right.Word4) return left.Word4 < right.Word4 ? -1 : 1;
 107165        if (left.Word3 != right.Word3) return left.Word3 < right.Word3 ? -1 : 1;
 98166        if (left.Word2 != right.Word2) return left.Word2 < right.Word2 ? -1 : 1;
 78167        if (left.Word1 != right.Word1) return left.Word1 < right.Word1 ? -1 : 1;
 74168        return left.Word0 == right.Word0
 74169            ? 0
 74170            : left.Word0 < right.Word0 ? -1 : 1;
 171    }
 172
 173    /// <summary>
 174    /// Multiplies three five-word finite-axis factors whose proven combined
 175    /// magnitude is below 650 bits.
 176    /// </summary>
 177    internal static Signed704 MultiplySigned320(
 178        Signed320 first,
 179        Signed320 second,
 180        Signed320 third)
 181    {
 183465182        Span<ulong> firstMagnitude = stackalloc ulong[5];
 183465183        Span<ulong> secondMagnitude = stackalloc ulong[5];
 183465184        Span<ulong> thirdMagnitude = stackalloc ulong[5];
 183465185        CopyMagnitude(first, firstMagnitude);
 183465186        CopyMagnitude(second, secondMagnitude);
 183465187        CopyMagnitude(third, thirdMagnitude);
 188
 183465189        Span<ulong> firstProduct = stackalloc ulong[10];
 183465190        MultiplyMagnitudes(firstMagnitude, secondMagnitude, firstProduct);
 183465191        Span<ulong> product = stackalloc ulong[15];
 183465192        MultiplyMagnitudes(firstProduct, thirdMagnitude, product);
 193
 183465194        if (first.Sign * second.Sign * third.Sign < 0)
 195        {
 60863196            ulong carry = 1UL;
 1460712197            for (int index = 0; index < 11; index++)
 669493198                product[index] = AddSignedWord(~product[index], 0UL, ref carry);
 199        }
 200
 183465201        return new Signed704(
 183465202            product[10],
 183465203            product[9],
 183465204            product[8],
 183465205            product[7],
 183465206            product[6],
 183465207            product[5],
 183465208            product[4],
 183465209            product[3],
 183465210            product[2],
 183465211            product[1],
 183465212            product[0]);
 213    }
 214
 215    private static void CopyMagnitude(Signed320 value, Span<ulong> destination)
 216    {
 1306648217        GetMagnitude(value, out destination[4], out destination[3], out destination[2], out destination[1], out destinat
 1306648218    }
 219
 220    private static Signed704 CreateSigned704(ReadOnlySpan<ulong> words) =>
 724980221        new(
 724980222            words[10], words[9], words[8], words[7], words[6], words[5],
 724980223            words[4], words[3], words[2], words[1], words[0]);
 224
 225    private static void ApplySigned704Sign(Span<ulong> words, bool negative)
 226    {
 724980227        if (!negative)
 683029228            return;
 229
 41951230        ulong carry = 1UL;
 1006824231        for (int index = 0; index < 11; index++)
 461461232            words[index] = AddSignedWord(~words[index], 0UL, ref carry);
 41951233    }
 234
 235    private static int GetBitLength(Signed704 value)
 236    {
 72287237        if (value.Word10 != 0UL) return 704 - Fixed64.CountLeadingZeroes(value.Word10);
 72286238        if (value.Word9 != 0UL) return 640 - Fixed64.CountLeadingZeroes(value.Word9);
 72286239        if (value.Word8 != 0UL) return 576 - Fixed64.CountLeadingZeroes(value.Word8);
 72472240        if (value.Word7 != 0UL) return 512 - Fixed64.CountLeadingZeroes(value.Word7);
 88361241        if (value.Word6 != 0UL) return 448 - Fixed64.CountLeadingZeroes(value.Word6);
 58096242        if (value.Word5 != 0UL) return 384 - Fixed64.CountLeadingZeroes(value.Word5);
 54860243        if (value.Word4 != 0UL) return 320 - Fixed64.CountLeadingZeroes(value.Word4);
 76150244        if (value.Word3 != 0UL) return 256 - Fixed64.CountLeadingZeroes(value.Word3);
 35608245        if (value.Word2 != 0UL) return 192 - Fixed64.CountLeadingZeroes(value.Word2);
 21307246        if (value.Word1 != 0UL) return 128 - Fixed64.CountLeadingZeroes(value.Word1);
 19773247        return 64 - Fixed64.CountLeadingZeroes(value.Word0);
 248    }
 249
 250    private static int GetBitLength(ReadOnlySpan<ulong> value)
 251    {
 28093252        int index = value.Length - 1;
 244490253        while (value[index] == 0UL)
 216397254            index--;
 28093255        return (index * 64) + 64 - Fixed64.CountLeadingZeroes(value[index]);
 256    }
 257
 258    private static ulong GetBitPair(Signed704 value, int pairIndex)
 259    {
 6912562260        int bitIndex = pairIndex << 1;
 6912562261        int shift = bitIndex & 63;
 6912562262        ulong word = (bitIndex >> 6) switch
 6912562263        {
 1849928264            0 => value.Word0,
 1659093265            1 => value.Word1,
 1553620266            2 => value.Word2,
 670851267            3 => value.Word3,
 605267268            4 => value.Word4,
 534458269            5 => value.Word5,
 35448270            6 => value.Word6,
 3611271            7 => value.Word7,
 171272            8 => value.Word8,
 113273            9 => value.Word9,
 2274            _ => value.Word10,
 6912562275        };
 6912562276        return (word >> shift) & 3UL;
 277    }
 278
 279    private static ulong GetBitPair(ReadOnlySpan<ulong> value, int pairIndex)
 280    {
 7256540281        int bitIndex = pairIndex << 1;
 7256540282        return (value[bitIndex >> 6] >> (bitIndex & 63)) & 3UL;
 283    }
 284
 285    private static void ShiftLeftMagnitude(Span<ulong> value, int bits)
 286    {
 42527548287        ulong carry = 0UL;
 575168076288        for (int index = 0; index < value.Length; index++)
 289        {
 245056490290            ulong nextCarry = value[index] >> (64 - bits);
 245056490291            value[index] = (value[index] << bits) | carry;
 245056490292            carry = nextCarry;
 293        }
 42527548294    }
 295
 296}

/home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed832.cs

#LineLine coverage
 1//=======================================================================
 2// WideArithmetic.Signed832.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024–present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using System;
 9using System.Runtime.CompilerServices;
 10
 11namespace FixedMathSharp;
 12
 13/// <content>
 14/// Signed 832-bit arithmetic helpers: addition, magnitude extraction, and squared-ratio comparison.
 15/// </content>
 16internal static partial class WideArithmetic
 17{
 18    internal static void GetMagnitude(Signed832 value, Span<ulong> magnitude)
 19    {
 13145220        magnitude.Clear();
 13145221        magnitude[0] = value.Word0;
 13145222        magnitude[1] = value.Word1;
 13145223        magnitude[2] = value.Word2;
 13145224        magnitude[3] = value.Word3;
 13145225        magnitude[4] = value.Word4;
 13145226        magnitude[5] = value.Word5;
 13145227        magnitude[6] = value.Word6;
 13145228        magnitude[7] = value.Word7;
 13145229        magnitude[8] = value.Word8;
 13145230        magnitude[9] = value.Word9;
 13145231        magnitude[10] = value.Word10;
 13145232        magnitude[11] = value.Word11;
 13145233        magnitude[12] = value.Word12;
 13145234        if (value.Sign >= 0)
 13040735            return;
 36
 104537        ulong carry = 1UL;
 2926038        for (int index = 0; index < 13; index++)
 1358539            magnitude[index] = AddSignedWord(~magnitude[index], 0UL, ref carry);
 104540    }
 41
 42    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 43    internal static Signed832 AddSigned832(Signed832 left, Signed832 right)
 44    {
 14317545        ulong carry = 0UL;
 14317546        ulong word0 = AddSignedWord(left.Word0, right.Word0, ref carry);
 14317547        ulong word1 = AddSignedWord(left.Word1, right.Word1, ref carry);
 14317548        ulong word2 = AddSignedWord(left.Word2, right.Word2, ref carry);
 14317549        ulong word3 = AddSignedWord(left.Word3, right.Word3, ref carry);
 14317550        ulong word4 = AddSignedWord(left.Word4, right.Word4, ref carry);
 14317551        ulong word5 = AddSignedWord(left.Word5, right.Word5, ref carry);
 14317552        ulong word6 = AddSignedWord(left.Word6, right.Word6, ref carry);
 14317553        ulong word7 = AddSignedWord(left.Word7, right.Word7, ref carry);
 14317554        ulong word8 = AddSignedWord(left.Word8, right.Word8, ref carry);
 14317555        ulong word9 = AddSignedWord(left.Word9, right.Word9, ref carry);
 14317556        ulong word10 = AddSignedWord(left.Word10, right.Word10, ref carry);
 14317557        ulong word11 = AddSignedWord(left.Word11, right.Word11, ref carry);
 14317558        ulong word12 = unchecked(left.Word12 + right.Word12 + carry);
 14317559        return new Signed832(
 14317560            word12, word11, word10, word9, word8, word7, word6,
 14317561            word5, word4, word3, word2, word1, word0);
 62    }
 63
 64    internal static int CompareNonNegativeSquaredRatios(
 65        Signed832 leftNumerator,
 66        Signed576 leftDenominator,
 67        Signed832 rightNumerator,
 68        Signed576 rightDenominator)
 69    {
 21470        Span<ulong> leftNumeratorWords = stackalloc ulong[13]
 21471        {
 21472            leftNumerator.Word0, leftNumerator.Word1, leftNumerator.Word2,
 21473            leftNumerator.Word3, leftNumerator.Word4, leftNumerator.Word5,
 21474            leftNumerator.Word6, leftNumerator.Word7, leftNumerator.Word8,
 21475            leftNumerator.Word9, leftNumerator.Word10, leftNumerator.Word11,
 21476            leftNumerator.Word12,
 21477        };
 21478        Span<ulong> rightNumeratorWords = stackalloc ulong[13]
 21479        {
 21480            rightNumerator.Word0, rightNumerator.Word1, rightNumerator.Word2,
 21481            rightNumerator.Word3, rightNumerator.Word4, rightNumerator.Word5,
 21482            rightNumerator.Word6, rightNumerator.Word7, rightNumerator.Word8,
 21483            rightNumerator.Word9, rightNumerator.Word10, rightNumerator.Word11,
 21484            rightNumerator.Word12,
 21485        };
 21486        Span<ulong> leftDenominatorWords = stackalloc ulong[9];
 21487        Span<ulong> rightDenominatorWords = stackalloc ulong[9];
 21488        GetMagnitude(leftDenominator, leftDenominatorWords);
 21489        GetMagnitude(rightDenominator, rightDenominatorWords);
 90
 21491        Span<ulong> leftOnce = stackalloc ulong[22];
 21492        Span<ulong> rightOnce = stackalloc ulong[22];
 21493        Span<ulong> leftScaled = stackalloc ulong[31];
 21494        Span<ulong> rightScaled = stackalloc ulong[31];
 21495        MultiplyMagnitudes(leftNumeratorWords, rightDenominatorWords, leftOnce);
 21496        MultiplyMagnitudes(rightNumeratorWords, leftDenominatorWords, rightOnce);
 21497        MultiplyMagnitudes(leftOnce, rightDenominatorWords, leftScaled);
 21498        MultiplyMagnitudes(rightOnce, leftDenominatorWords, rightScaled);
 21499        return CompareMagnitudeEqualLength(leftScaled, rightScaled);
 100    }
 101
 102    internal static int CompareNonNegativeProducts(
 103        Signed832 firstLeft,
 104        Signed832 firstRight,
 105        Signed832 secondLeft,
 106        Signed832 secondRight)
 107    {
 2918108        Span<ulong> firstLeftWords = stackalloc ulong[13];
 2918109        Span<ulong> firstRightWords = stackalloc ulong[13];
 2918110        Span<ulong> secondLeftWords = stackalloc ulong[13];
 2918111        Span<ulong> secondRightWords = stackalloc ulong[13];
 2918112        GetMagnitude(firstLeft, firstLeftWords);
 2918113        GetMagnitude(firstRight, firstRightWords);
 2918114        GetMagnitude(secondLeft, secondLeftWords);
 2918115        GetMagnitude(secondRight, secondRightWords);
 2918116        Span<ulong> firstProduct = stackalloc ulong[26];
 2918117        Span<ulong> secondProduct = stackalloc ulong[26];
 2918118        MultiplyMagnitudes(firstLeftWords, firstRightWords, firstProduct);
 2918119        MultiplyMagnitudes(secondLeftWords, secondRightWords, secondProduct);
 2918120        return CompareMagnitudeEqualLength(firstProduct, secondProduct);
 121    }
 122
 123    /// <summary>
 124    /// Multiplies signed nine-word conic coefficients whose proven product fits
 125    /// in thirteen words.
 126    /// </summary>
 127    internal static Signed832 MultiplySigned576ToSigned832(Signed576 left, Signed576 right)
 128    {
 271136129        Span<ulong> leftMagnitude = stackalloc ulong[9];
 271136130        Span<ulong> rightMagnitude = stackalloc ulong[9];
 271136131        GetMagnitude(left, leftMagnitude);
 271136132        GetMagnitude(right, rightMagnitude);
 271136133        Span<ulong> product = stackalloc ulong[18];
 271136134        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 135
 271136136        ApplySigned832Sign(product, left.Sign * right.Sign < 0);
 137
 271136138        return CreateSigned832(product);
 139    }
 140
 141    /// <summary>
 142    /// Multiplies a signed nine-word conic coefficient by a signed five-word
 143    /// rational product whose proven result fits in thirteen words.
 144    /// </summary>
 145    internal static Signed832 MultiplySigned576ToSigned832(Signed576 left, Signed320 right)
 146    {
 31272147        Span<ulong> leftMagnitude = stackalloc ulong[9];
 31272148        Span<ulong> rightMagnitude = stackalloc ulong[5];
 31272149        GetMagnitude(left, leftMagnitude);
 31272150        CopyMagnitude(right, rightMagnitude);
 31272151        Span<ulong> product = stackalloc ulong[14];
 31272152        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 31272153        ApplySigned832Sign(product, left.Sign * right.Sign < 0);
 31272154        return CreateSigned832(product);
 155    }
 156
 157    /// <summary>
 158    /// Multiplies a signed eleven-word value by a signed three-word factor
 159    /// whose proven product fits in thirteen words.
 160    /// </summary>
 161    internal static Signed832 MultiplySigned704ToSigned832(
 162        Signed704 left,
 163        Signed192 right)
 164    {
 1165        Span<ulong> leftMagnitude = stackalloc ulong[11];
 1166        Span<ulong> rightMagnitude = stackalloc ulong[3];
 1167        GetMagnitude(left, leftMagnitude);
 1168        GetMagnitude(
 1169            right,
 1170            out rightMagnitude[2],
 1171            out rightMagnitude[1],
 1172            out rightMagnitude[0]);
 1173        Span<ulong> product = stackalloc ulong[14];
 1174        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 1175        ApplySigned832Sign(product, left.Sign * right.Sign < 0);
 1176        return CreateSigned832(product);
 177    }
 178
 179    /// <summary>
 180    /// Multiplies a signed eleven-word value by a signed five-word factor
 181    /// whose proven product fits in thirteen words.
 182    /// </summary>
 183    internal static Signed832 MultiplySigned704ToSigned832(
 184        Signed704 left,
 185        Signed320 right)
 186    {
 1187        Span<ulong> leftMagnitude = stackalloc ulong[11];
 1188        Span<ulong> rightMagnitude = stackalloc ulong[5];
 1189        GetMagnitude(left, leftMagnitude);
 1190        CopyMagnitude(right, rightMagnitude);
 1191        Span<ulong> product = stackalloc ulong[16];
 1192        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 1193        ApplySigned832Sign(product, left.Sign * right.Sign < 0);
 1194        return CreateSigned832(product);
 195    }
 196
 197    /// <summary>
 198    /// Multiplies two signed eleven-word values and a signed three-word factor
 199    /// whose proven combined product fits in thirteen words.
 200    /// </summary>
 201    internal static Signed832 MultiplySigned704ToSigned832(
 202        Signed704 first,
 203        Signed704 second,
 204        Signed192 third)
 205    {
 1206        Span<ulong> firstMagnitude = stackalloc ulong[11];
 1207        Span<ulong> secondMagnitude = stackalloc ulong[11];
 1208        Span<ulong> thirdMagnitude = stackalloc ulong[3];
 1209        GetMagnitude(first, firstMagnitude);
 1210        GetMagnitude(second, secondMagnitude);
 1211        GetMagnitude(
 1212            third,
 1213            out thirdMagnitude[2],
 1214            out thirdMagnitude[1],
 1215            out thirdMagnitude[0]);
 1216        Span<ulong> pairProduct = stackalloc ulong[22];
 1217        Span<ulong> product = stackalloc ulong[25];
 1218        MultiplyMagnitudes(
 1219            firstMagnitude,
 1220            secondMagnitude,
 1221            pairProduct);
 1222        MultiplyMagnitudes(pairProduct, thirdMagnitude, product);
 1223        ApplySigned832Sign(
 1224            product,
 1225            first.Sign * second.Sign * third.Sign < 0);
 1226        return CreateSigned832(product);
 227    }
 228
 229    /// <summary>
 230    /// Multiplies a signed thirteen-word value by a signed three-word factor
 231    /// whose proven product still fits in thirteen words.
 232    /// </summary>
 233    internal static Signed832 MultiplySigned832(
 234        Signed832 left,
 235        Signed192 right)
 236    {
 1237        Span<ulong> leftMagnitude = stackalloc ulong[13];
 1238        Span<ulong> rightMagnitude = stackalloc ulong[3];
 1239        GetMagnitude(left, leftMagnitude);
 1240        GetMagnitude(
 1241            right,
 1242            out rightMagnitude[2],
 1243            out rightMagnitude[1],
 1244            out rightMagnitude[0]);
 1245        Span<ulong> product = stackalloc ulong[16];
 1246        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 1247        ApplySigned832Sign(product, left.Sign * right.Sign < 0);
 1248        return CreateSigned832(product);
 249    }
 250
 251    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 252    internal static Signed832 SubtractSigned832(Signed832 left, Signed832 right)
 253    {
 79362254        ulong borrow = 0UL;
 79362255        ulong word0 = SubtractWord(left.Word0, right.Word0, ref borrow);
 79362256        ulong word1 = SubtractWord(left.Word1, right.Word1, ref borrow);
 79362257        ulong word2 = SubtractWord(left.Word2, right.Word2, ref borrow);
 79362258        ulong word3 = SubtractWord(left.Word3, right.Word3, ref borrow);
 79362259        ulong word4 = SubtractWord(left.Word4, right.Word4, ref borrow);
 79362260        ulong word5 = SubtractWord(left.Word5, right.Word5, ref borrow);
 79362261        ulong word6 = SubtractWord(left.Word6, right.Word6, ref borrow);
 79362262        ulong word7 = SubtractWord(left.Word7, right.Word7, ref borrow);
 79362263        ulong word8 = SubtractWord(left.Word8, right.Word8, ref borrow);
 79362264        ulong word9 = SubtractWord(left.Word9, right.Word9, ref borrow);
 79362265        ulong word10 = SubtractWord(left.Word10, right.Word10, ref borrow);
 79362266        ulong word11 = SubtractWord(left.Word11, right.Word11, ref borrow);
 79362267        ulong word12 = unchecked(left.Word12 - right.Word12 - borrow);
 79362268        return new Signed832(
 79362269            word12, word11, word10, word9, word8, word7, word6,
 79362270            word5, word4, word3, word2, word1, word0);
 271    }
 272
 273    /// <summary>
 274    /// Returns the exact floor square root of a proven-fit nonnegative conic
 275    /// discriminant product. The wider radicand remains transient stack storage.
 276    /// </summary>
 277    internal static Signed576 GetFloorSquareRootOfProduct(
 278        Signed832 value,
 279        Signed192 nonNegativeFactor)
 280    {
 32340281        if (value.IsZero || nonNegativeFactor.IsZero)
 4247282            return default;
 283
 28093284        Span<ulong> valueMagnitude = stackalloc ulong[13]
 28093285        {
 28093286            value.Word0, value.Word1, value.Word2, value.Word3, value.Word4,
 28093287            value.Word5, value.Word6, value.Word7, value.Word8, value.Word9,
 28093288            value.Word10, value.Word11, value.Word12,
 28093289        };
 28093290        Span<ulong> factorMagnitude = stackalloc ulong[3];
 28093291        GetMagnitude(
 28093292            nonNegativeFactor,
 28093293            out factorMagnitude[2],
 28093294            out factorMagnitude[1],
 28093295            out factorMagnitude[0]);
 28093296        Span<ulong> product = stackalloc ulong[16];
 28093297        MultiplyMagnitudes(valueMagnitude, factorMagnitude, product);
 298
 28093299        int productBitLength = GetBitLength(product);
 28093300        int rootBitLength = (productBitLength + 1) >> 1;
 28093301        int activeWords = System.Math.Min(9, (rootBitLength + 64) >> 6);
 28093302        Span<ulong> rootStorage = stackalloc ulong[9];
 28093303        Span<ulong> remainderStorage = stackalloc ulong[9];
 28093304        Span<ulong> candidateStorage = stackalloc ulong[9];
 28093305        Span<ulong> root = rootStorage[..activeWords];
 28093306        Span<ulong> remainder = remainderStorage[..activeWords];
 28093307        Span<ulong> candidate = candidateStorage[..activeWords];
 28093308        rootStorage.Clear();
 28093309        remainder.Clear();
 14569266310        for (int pairIndex = (productBitLength - 1) >> 1; pairIndex >= 0; pairIndex--)
 311        {
 7256540312            ShiftLeftMagnitude(remainder, 2);
 7256540313            remainder[0] |= GetBitPair(product, pairIndex);
 7256540314            ShiftLeftMagnitude(root, 1);
 7256540315            root.CopyTo(candidate);
 7256540316            ShiftLeftMagnitude(candidate, 1);
 7256540317            candidate[0] |= 1UL;
 7256540318            if (CompareMagnitudeEqualLength(remainder, candidate) < 0)
 319                continue;
 320
 2953675321            SubtractEqualMagnitudes(remainder, candidate, remainder);
 2953675322            root[0]++;
 323        }
 324
 28093325        return new Signed576(
 28093326            rootStorage[8], rootStorage[7], rootStorage[6], rootStorage[5], rootStorage[4],
 28093327            rootStorage[3], rootStorage[2], rootStorage[1], rootStorage[0]);
 328    }
 329
 330    private static Signed832 CreateSigned832(ReadOnlySpan<ulong> words) =>
 302412331        new(
 302412332            words[12], words[11], words[10], words[9], words[8], words[7],
 302412333            words[6], words[5], words[4], words[3], words[2], words[1], words[0]);
 334
 335    private static void ApplySigned832Sign(Span<ulong> words, bool negative)
 336    {
 302412337        if (!negative)
 288099338            return;
 339
 14313340        ulong carry = 1UL;
 400764341        for (int index = 0; index < 13; index++)
 186069342            words[index] = AddSignedWord(~words[index], 0UL, ref carry);
 14313343    }
 344
 345    /// <summary>
 346    /// Multiplies nonnegative thirteen-word and five-word factors whose proven
 347    /// product fits in thirteen words.
 348    /// </summary>
 349    internal static Signed832 MultiplyNonNegativeToSigned832(
 350        Signed832 left,
 351        Signed320 right)
 352    {
 55792353        Span<ulong> leftWords = stackalloc ulong[13]
 55792354        {
 55792355            left.Word0, left.Word1, left.Word2, left.Word3, left.Word4,
 55792356            left.Word5, left.Word6, left.Word7, left.Word8, left.Word9,
 55792357            left.Word10, left.Word11, left.Word12,
 55792358        };
 55792359        Span<ulong> rightWords = stackalloc ulong[5];
 55792360        GetMagnitude(
 55792361            right,
 55792362            out rightWords[4],
 55792363            out rightWords[3],
 55792364            out rightWords[2],
 55792365            out rightWords[1],
 55792366            out rightWords[0]);
 55792367        Span<ulong> product = stackalloc ulong[18];
 55792368        MultiplyMagnitudes(leftWords, rightWords, product);
 55792369        return new Signed832(
 55792370            product[12], product[11], product[10], product[9], product[8],
 55792371            product[7], product[6], product[5], product[4], product[3],
 55792372            product[2], product[1], product[0]);
 373    }
 374}
Generated by: ReportGenerator 5.5.11.0
08/04/2026 - 20:34:44
GitHub | reportgenerator.io

Methods/Properties

GetRoundedNonNegativeNormalizedDepth(FixedMathSharp.Signed576,FixedMathSharp.Signed576,FixedMathSharp.Signed320,System.Boolean&)
CompareNonNegativeNormalizedDepths(FixedMathSharp.Signed576,FixedMathSharp.Signed576,FixedMathSharp.Signed320,FixedMathSharp.Signed576,FixedMathSharp.Signed576,FixedMathSharp.Signed320)
CompareNormalizedDepthToTwiceRaw(FixedMathSharp.Signed576,FixedMathSharp.Signed576,FixedMathSharp.Signed320,FixedMathSharp.Signed192)
CompareSignedNormalizedMagnitudes(System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.ReadOnlySpan`1<System.UInt64>)
GetSignedMagnitudeAndSquareRootSign(System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.ReadOnlySpan`1<System.UInt64>)
CompareRadialProjectionDepths(FixedMathSharp.Signed576,FixedMathSharp.Signed832,FixedMathSharp.Signed576,FixedMathSharp.Signed576,FixedMathSharp.Signed576,FixedMathSharp.Signed832,FixedMathSharp.Signed576,FixedMathSharp.Signed576,FixedMathSharp.Signed192)
CompareRadialProjectionDepths(FixedMathSharp.Signed704,FixedMathSharp.Signed320,FixedMathSharp.Signed832,FixedMathSharp.Signed576,FixedMathSharp.Signed576,FixedMathSharp.Signed704,FixedMathSharp.Signed320,FixedMathSharp.Signed832,FixedMathSharp.Signed576,FixedMathSharp.Signed576)
AddSignedRadicand(System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.Span`1<System.UInt64>,System.Span`1<System.UInt64>,System.Span`1<System.UInt64>,System.Span`1<System.UInt64>,System.Int32&,System.Int32&)
BuildSquaredRadialDepthNumerator(FixedMathSharp.Signed704,FixedMathSharp.Signed320,FixedMathSharp.Signed832,FixedMathSharp.Signed576,FixedMathSharp.Signed576,FixedMathSharp.Signed576,System.Span`1<System.UInt64>)
BuildRadialDepthCrossRadicand(FixedMathSharp.Signed320,FixedMathSharp.Signed576,FixedMathSharp.Signed576,FixedMathSharp.Signed704,FixedMathSharp.Signed832,FixedMathSharp.Signed576,System.Span`1<System.UInt64>)
CompareNonNegativeRadicalPairs(System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.UInt64>)
ComparePositiveRadicalPairDifference(System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.UInt64>)
CompareNonNegativeRadicalSumToRatio(FixedMathSharp.Signed576,FixedMathSharp.Signed192,FixedMathSharp.Signed576,FixedMathSharp.Signed192,FixedMathSharp.Signed320,FixedMathSharp.Signed192)
CompareNonNegativeRadicalToRatio(FixedMathSharp.Signed576,FixedMathSharp.Signed320,FixedMathSharp.Signed320,FixedMathSharp.Signed320)
CompareSignedLinearRadicalToZero(FixedMathSharp.Signed832,FixedMathSharp.Signed704,FixedMathSharp.Signed576,FixedMathSharp.Signed320)
CompareNonNegativeRadicalToRatio(FixedMathSharp.Signed576,FixedMathSharp.Signed192,FixedMathSharp.Signed320,FixedMathSharp.Signed192)
CompareRadicalCrossTerm(FixedMathSharp.Signed576,FixedMathSharp.Signed192,FixedMathSharp.Signed576,FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed576)
CompareUnsigned(System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.UInt64)
CompareUnsigned(System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.UInt64)
TryGetSigned95Magnitude(FixedMathSharp.Signed192,System.UInt64&,System.UInt64&)
MultiplySigned95(System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.Boolean)
MultiplyUnsigned128(System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64&)
MultiplyUnsigned96(System.UInt32,System.UInt64,System.UInt32,System.UInt64,System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64&)
Multiply64By32(System.UInt64,System.UInt32,System.UInt64&,System.UInt64&)
AddProductAt2(System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64,System.UInt64)
AddProductAt3(System.UInt64&,System.UInt64&,System.UInt64,System.UInt64)
AccumulateWord(System.UInt64&,System.UInt64,System.UInt64&)
SubtractWord(System.UInt64,System.UInt64,System.UInt64&)
AddSignedWord(System.UInt64,System.UInt64,System.UInt64&)
IsZeroMagnitude(System.ReadOnlySpan`1<System.UInt64>)
GetLinearRadicalSumSign(System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.ReadOnlySpan`1<System.Int32>)
GetMultiquadraticSign(System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.Int32>,System.Int32,System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.Int32,System.Int32)
BuildMultiquadraticSquaredDifference(System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.Int32>,System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.Int32>,System.Int32,System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.Int32,System.Span`1<System.UInt64>,System.Span`1<System.Int32>,System.Int32)
AddMultiquadraticSquare(System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.Int32>,System.Int32,System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.Int32,System.Int32,System.Span`1<System.UInt64>,System.Span`1<System.Int32>,System.Int32,System.Int32)
AddSignedMagnitude(System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.Span`1<System.UInt64>,System.Int32&)
GetActiveMagnitudeLength(System.ReadOnlySpan`1<System.UInt64>)
GetMagnitudeBitLength(System.ReadOnlySpan`1<System.UInt64>)
MultiplyMagnitudes(System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.UInt64>,System.Span`1<System.UInt64>)
AddWord(System.Span`1<System.UInt64>,System.Int32,System.UInt64)
AddEqualMagnitudes(System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.UInt64>,System.Span`1<System.UInt64>)
AddMagnitudeInto(System.ReadOnlySpan`1<System.UInt64>,System.Span`1<System.UInt64>)
SubtractEqualMagnitudes(System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.UInt64>,System.Span`1<System.UInt64>)
CompareMagnitudeEqualLength(System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.UInt64>)
GetSignedRatioWith64FractionBits(FixedMathSharp.Signed576,FixedMathSharp.Signed576)
GetMassRatioBitLength(System.ReadOnlySpan`1<System.UInt64>)
ShiftMassRatioLeft(System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.Span`1<System.UInt64>)
ShiftMassRatioRightOne(System.Span`1<System.UInt64>)
ShiftMassRatioLeftOne(System.Span`1<System.UInt64>)
GetMagnitude(FixedMathSharp.Signed192,System.UInt64&,System.UInt64&,System.UInt64&)
CompareMagnitude(FixedMathSharp.Signed192,FixedMathSharp.Signed192)
IsMagnitudeAtMost(FixedMathSharp.Signed192,System.UInt64,System.Int32)
AddSigned192(FixedMathSharp.Signed192,FixedMathSharp.Signed192)
Double(FixedMathSharp.Signed192)
SubtractSigned192(FixedMathSharp.Signed192,FixedMathSharp.Signed192)
Difference(FixedMathSharp.Fixed64,FixedMathSharp.Fixed64)
GetFloorSquareRoot(FixedMathSharp.Signed320,FixedMathSharp.Signed192&)
Scale(FixedMathSharp.Fixed64)
Negate(FixedMathSharp.Signed192)
Absolute(FixedMathSharp.Signed192)
ShiftRightToUInt64(FixedMathSharp.Signed192,System.Int32,System.Boolean&)
GetFloorSquareRoot192(System.UInt64,System.UInt64,System.UInt64,FixedMathSharp.Signed192&)
ShiftLeft(System.UInt64,System.UInt64,System.UInt64,System.Int32,System.UInt64&,System.UInt64&,System.UInt64&)
ShiftLeftOne(System.UInt64&,System.UInt64&,System.UInt64&)
ShiftRightOne(System.UInt64&,System.UInt64&,System.UInt64&)
GetBitLength(System.UInt64,System.UInt64,System.UInt64)
SubtractUnsigned(System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64,System.UInt64,System.UInt64)
GetMagnitude(FixedMathSharp.Signed320,System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64&)
MultiplySubtract(FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192)
AddProducts(FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192)
AddProducts(FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192)
GetDotProduct3D(FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192)
AddSigned320(FixedMathSharp.Signed320,FixedMathSharp.Signed320)
SubtractSigned320(FixedMathSharp.Signed320,FixedMathSharp.Signed320)
CompareMagnitude(FixedMathSharp.Signed320,FixedMathSharp.Signed320)
MultiplySigned192(FixedMathSharp.Signed192,FixedMathSharp.Signed192)
CompareNormalizedComponentToMidpoint(FixedMathSharp.Signed320,FixedMathSharp.Signed320,System.UInt64)
ShiftLeft(System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.Int32,System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64&)
ShiftLeftOne(System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64&)
ShiftRightOne(System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64&)
GetBitLength(System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.UInt64)
SubtractUnsigned(System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64&,System.UInt64,System.UInt64,System.UInt64,System.UInt64,System.UInt64)
GetMagnitude(FixedMathSharp.Signed576,System.Span`1<System.UInt64>)
CompareNonNegative(FixedMathSharp.Signed576,FixedMathSharp.Signed576)
AddSigned576(FixedMathSharp.Signed576,FixedMathSharp.Signed576)
Double(FixedMathSharp.Signed576)
SubtractSigned576(FixedMathSharp.Signed576,FixedMathSharp.Signed576)
MultiplySigned320(FixedMathSharp.Signed320,FixedMathSharp.Signed192)
MultiplySigned320(FixedMathSharp.Signed320,FixedMathSharp.Signed320)
MultiplySigned576(FixedMathSharp.Signed576,System.Int64)
MultiplySigned576(FixedMathSharp.Signed576,FixedMathSharp.Signed192)
MultiplySigned576(FixedMathSharp.Signed576,FixedMathSharp.Signed192,FixedMathSharp.Signed192)
MultiplySigned576(FixedMathSharp.Signed576,FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192)
MultiplySigned576(FixedMathSharp.Signed576,FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192,FixedMathSharp.Signed192)
GetFloorSquareRootScaledByFixed64(FixedMathSharp.Signed576)
Negate(FixedMathSharp.Signed320)
Absolute(FixedMathSharp.Signed576)
ClampToNonNegative(FixedMathSharp.Signed576)
GetBitLength(FixedMathSharp.Signed576)
GetMagnitudeBitLength(FixedMathSharp.Signed192)
MultiplySigned576Word(System.UInt64,System.UInt64,System.UInt64&)
GetBitPair(FixedMathSharp.Signed576,System.Int32)
ShiftLeft(System.Span`1<System.UInt64>,System.Int32)
MultiplyNonNegativeToSigned576(FixedMathSharp.Signed576,FixedMathSharp.Signed576)
GetMagnitude(FixedMathSharp.Signed704,System.Span`1<System.UInt64>)
MultiplySigned576ToSigned704(FixedMathSharp.Signed576,FixedMathSharp.Signed320)
MultiplyNonNegative(FixedMathSharp.Signed576,FixedMathSharp.Signed192)
GetFloorSquareRoot(FixedMathSharp.Signed704)
AddSigned704(FixedMathSharp.Signed704,FixedMathSharp.Signed704)
SubtractSigned704(FixedMathSharp.Signed704,FixedMathSharp.Signed704)
CompareNonNegative(FixedMathSharp.Signed704,FixedMathSharp.Signed704)
MultiplySigned320(FixedMathSharp.Signed320,FixedMathSharp.Signed320,FixedMathSharp.Signed320)
CopyMagnitude(FixedMathSharp.Signed320,System.Span`1<System.UInt64>)
CreateSigned704(System.ReadOnlySpan`1<System.UInt64>)
ApplySigned704Sign(System.Span`1<System.UInt64>,System.Boolean)
GetBitLength(FixedMathSharp.Signed704)
GetBitLength(System.ReadOnlySpan`1<System.UInt64>)
GetBitPair(FixedMathSharp.Signed704,System.Int32)
GetBitPair(System.ReadOnlySpan`1<System.UInt64>,System.Int32)
ShiftLeftMagnitude(System.Span`1<System.UInt64>,System.Int32)
GetMagnitude(FixedMathSharp.Signed832,System.Span`1<System.UInt64>)
AddSigned832(FixedMathSharp.Signed832,FixedMathSharp.Signed832)
CompareNonNegativeSquaredRatios(FixedMathSharp.Signed832,FixedMathSharp.Signed576,FixedMathSharp.Signed832,FixedMathSharp.Signed576)
CompareNonNegativeProducts(FixedMathSharp.Signed832,FixedMathSharp.Signed832,FixedMathSharp.Signed832,FixedMathSharp.Signed832)
MultiplySigned576ToSigned832(FixedMathSharp.Signed576,FixedMathSharp.Signed576)
MultiplySigned576ToSigned832(FixedMathSharp.Signed576,FixedMathSharp.Signed320)
MultiplySigned704ToSigned832(FixedMathSharp.Signed704,FixedMathSharp.Signed192)
MultiplySigned704ToSigned832(FixedMathSharp.Signed704,FixedMathSharp.Signed320)
MultiplySigned704ToSigned832(FixedMathSharp.Signed704,FixedMathSharp.Signed704,FixedMathSharp.Signed192)
MultiplySigned832(FixedMathSharp.Signed832,FixedMathSharp.Signed192)
SubtractSigned832(FixedMathSharp.Signed832,FixedMathSharp.Signed832)
GetFloorSquareRootOfProduct(FixedMathSharp.Signed832,FixedMathSharp.Signed192)
CreateSigned832(System.ReadOnlySpan`1<System.UInt64>)
ApplySigned832Sign(System.Span`1<System.UInt64>,System.Boolean)
MultiplyNonNegativeToSigned832(FixedMathSharp.Signed832,FixedMathSharp.Signed320)