< 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.MagnitudeDivision.cs
File 5: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Ratio.cs
File 6: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed192.cs
File 7: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed320.cs
File 8: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed576.cs
File 9: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed704.cs
File 10: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.Signed832.cs
File 11: /home/runner/work/FixedMathSharp/FixedMathSharp/src/FixedMathSharp/Numerics/Wide/WideArithmetic.SquareRoot.cs
Line coverage
100%
Covered lines: 2765
Uncovered lines: 0
Coverable lines: 2765
Total lines: 4603
Line coverage: 100%
Branch coverage
100%
Covered branches: 865
Total branches: 865
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: CompareNonNegativeNormalizedDepths(...)100%22100%
File 1: GetRoundedNonNegativeNormalizedDepth(...)100%1818100%
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%1818100%
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 3: AddShiftedSignedMagnitude(...)100%2222100%
File 3: GetShiftedMagnitudeWord(...)100%66100%
File 4: DivideMagnitudes(...)100%3232100%
File 4: GetMagnitudeGreatestCommonDivisor(...)100%22100%
File 4: ShiftMagnitudeForDivision(...)100%66100%
File 5: GetSignedRatioWith64FractionBits(...)100%1616100%
File 5: GetMassRatioBitLength(...)100%44100%
File 5: ShiftMassRatioLeft(...)100%88100%
File 5: ShiftMassRatioRightOne(...)100%22100%
File 5: ShiftMassRatioLeftOne(...)100%22100%
File 6: ShiftLeftSigned192By32(...)100%11100%
File 6: GetMagnitude(...)100%66100%
File 6: CompareMagnitude(...)100%11100%
File 6: IsMagnitudeAtMost(...)100%11100%
File 6: AddSigned192(...)100%66100%
File 6: Double(...)100%11100%
File 6: SubtractSigned192(...)100%11100%
File 6: Difference(...)100%11100%
File 6: GetFloorSquareRoot(...)100%1515100%
File 6: Scale(...)100%11100%
File 6: Negate(...)100%11100%
File 6: Absolute(...)100%22100%
File 6: GetGreatestCommonDivisor(...)100%1818100%
File 6: CountTrailingZeroes192(...)100%44100%
File 6: ShiftRightMagnitude192(...)100%66100%
File 6: ShiftLeftMagnitude192(...)100%44100%
File 6: DivideExactSigned192(...)100%2424100%
File 6: ShiftRightToUInt64(...)100%1010100%
File 6: GetFloorSquareRoot192(...)100%1212100%
File 6: ShiftLeft(...)100%22100%
File 6: ShiftLeftOne(...)100%11100%
File 6: ShiftRightOne(...)100%11100%
File 6: GetBitLength(...)100%44100%
File 6: SubtractUnsigned(...)100%11100%
File 7: GetGreatestCommonDivisor(...)100%11100%
File 7: DivideExactSigned320(...)100%22100%
File 7: TruncateSigned320By64(...)100%22100%
File 7: ReduceCommonScale(...)100%1010100%
File 7: GetMagnitude(...)100%2020100%
File 7: MultiplySubtract(...)100%88100%
File 7: AddProducts(...)100%11100%
File 7: AddProducts(...)100%11100%
File 7: GetDotProduct3D(...)100%11100%
File 7: AddSigned320(...)100%1212100%
File 7: SubtractSigned320(...)100%11100%
File 7: CompareMagnitude(...)100%11100%
File 7: MultiplySigned192(...)100%2222100%
File 7: CompareNormalizedComponentToMidpoint(...)100%88100%
File 7: ShiftLeft(...)100%22100%
File 7: ShiftLeftOne(...)100%11100%
File 7: ShiftRightOne(...)100%11100%
File 7: GetBitLength(...)100%88100%
File 7: SubtractUnsigned(...)100%11100%
File 8: Negate(...)100%11100%
File 8: MultiplySigned576(...)100%11100%
File 8: ReduceCommonScale(...)100%1010100%
File 8: DivideSigned576ToSigned192(...)100%1616100%
File 8: GetMagnitude(...)100%44100%
File 8: CompareNonNegative(...)100%3636100%
File 8: AddSigned576(...)100%11100%
File 8: Double(...)100%11100%
File 8: SubtractSigned576(...)100%11100%
File 8: MultiplySigned320(...)100%11100%
File 8: MultiplySigned320(...)100%1010100%
File 8: MultiplySigned576(...)100%22100%
File 8: MultiplySigned576(...)100%1010100%
File 8: MultiplySigned576(...)100%11100%
File 8: MultiplySigned576(...)100%11100%
File 8: MultiplySigned576(...)100%11100%
File 8: GetFloorSquareRootScaledByFixed64(...)100%1212100%
File 8: Negate(...)100%11100%
File 8: Absolute(...)100%22100%
File 8: ClampToNonNegative(...)100%11100%
File 8: GetBitLength(...)100%1010100%
File 8: GetMagnitudeBitLength(...)100%66100%
File 8: MultiplySigned576Word(...)100%11100%
File 8: GetBitPair(...)100%99100%
File 8: ShiftLeft(...)100%22100%
File 8: MultiplyNonNegativeToSigned576(...)100%11100%
File 9: GetMagnitude(...)100%44100%
File 9: MultiplySigned576ToSigned704(...)100%11100%
File 9: MultiplyNonNegative(...)100%11100%
File 9: GetFloorSquareRoot(...)100%66100%
File 9: AddSigned704(...)100%11100%
File 9: SubtractSigned704(...)100%11100%
File 9: CompareNonNegative(...)100%4444100%
File 9: MultiplySigned320(...)100%44100%
File 9: CopyMagnitude(...)100%11100%
File 9: CreateSigned704(...)100%11100%
File 9: ApplySigned704Sign(...)100%44100%
File 9: GetBitLength(...)100%2020100%
File 9: GetBitLength(...)100%22100%
File 9: GetBitPair(...)100%1111100%
File 9: GetBitPair(...)100%11100%
File 9: ShiftLeftMagnitude(...)100%22100%
File 10: GetMagnitude(...)100%44100%
File 10: AddSigned832(...)100%11100%
File 10: CompareNonNegativeSquaredRatios(...)100%11100%
File 10: CompareNonNegativeProducts(...)100%11100%
File 10: MultiplySigned576ToSigned832(...)100%44100%
File 10: MultiplySigned576ToSigned832(...)100%44100%
File 10: MultiplySigned704ToSigned832(...)100%11100%
File 10: MultiplySigned704ToSigned832(...)100%11100%
File 10: MultiplySigned704ToSigned832(...)100%11100%
File 10: MultiplySigned832(...)100%11100%
File 10: MultiplySigned832(...)100%11100%
File 10: SubtractSigned832(...)100%11100%
File 10: GetFloorSquareRootOfProduct(...)100%1010100%
File 10: CreateSigned832(...)100%11100%
File 10: ApplySigned832Sign(...)100%44100%
File 10: MultiplyNonNegativeToSigned832(...)100%11100%
File 11: GetMagnitudeSquareRootBounds(...)100%1616100%
File 11: GetRatioFloorSquareRoot(...)100%22100%

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    {
 56338        Signed192 maximumTwiceRaw = AddSigned192(
 56339            Signed192.Signed(long.MaxValue),
 56340            Signed192.Signed(long.MaxValue));
 56341        if (CompareNormalizedDepthToTwiceRaw(
 56342                overlap,
 56343                squaredAxisLength,
 56344                commonDenominator,
 56345                maximumTwiceRaw) > 0)
 46        {
 1147            isClamped = true;
 1148            return Fixed64.MaxValue;
 49        }
 50
 55251        Signed576 approximationThreshold = Signed576.ExtendValue(
 55252            Signed320.ExtendValue(Signed192.Signed(1L << 62)));
 55253        if (CompareNonNegative(
 55254                squaredAxisLength,
 55255                approximationThreshold) < 0)
 56        {
 5057            long low = 0L;
 5058            long high = long.MaxValue;
 320059            while (low < high)
 60            {
 315061                long candidate = (long)(
 315062                    ((ulong)low + (ulong)high + 1UL) >> 1);
 315063                Signed192 candidateLowerMidpoint = SubtractSigned192(
 315064                    AddSigned192(
 315065                        Signed192.Signed(candidate),
 315066                        Signed192.Signed(candidate)),
 315067                    Signed192.Signed(1L));
 315068                int candidateComparison = CompareNormalizedDepthToTwiceRaw(
 315069                    overlap,
 315070                    squaredAxisLength,
 315071                    commonDenominator,
 315072                    candidateLowerMidpoint);
 315073                bool roundsAtLeastCandidate = candidateComparison > 0
 315074                    || (candidateComparison == 0
 315075                        && (candidate & 1L) == 0L);
 315076                if (roundsAtLeastCandidate)
 120077                    low = candidate;
 78                else
 195079                    high = candidate - 1L;
 80            }
 81
 5082            isClamped = false;
 5083            return Fixed64.FromRaw(low);
 84        }
 85
 50286        Signed320 scaledAxisLength =
 50287            GetFloorSquareRootScaledByFixed64(squaredAxisLength);
 50288        Signed576 scaledDenominator = MultiplySigned320(
 50289            scaledAxisLength,
 50290            commonDenominator);
 50291        if (!Fixed64.TryGetSignedRawRatio(
 50292                Signed832.ExtendValue(overlap),
 50293                Signed832.ExtendValue(scaledDenominator),
 50294                FixedMath.SHIFT_AMOUNT_I,
 50295                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        }
 502102        isClamped = false;
 502103        if (depth == Fixed64.Zero)
 11104            return depth;
 105
 491106        Signed192 lowerMidpoint = SubtractSigned192(
 491107            AddSigned192(
 491108                Signed192.Signed(depth.m_rawValue),
 491109                Signed192.Signed(depth.m_rawValue)),
 491110            Signed192.Signed(1L));
 491111        int comparison = CompareNormalizedDepthToTwiceRaw(
 491112            overlap,
 491113            squaredAxisLength,
 491114            commonDenominator,
 491115            lowerMidpoint);
 491116        if (comparison < (depth.m_rawValue & 1L))
 117        {
 34118            depth = Fixed64.FromRaw(depth.m_rawValue - 1L);
 119        }
 120
 491121        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    {
 13908136        Span<ulong> leftOverlapWords = stackalloc ulong[9];
 13908137        Span<ulong> rightOverlapWords = stackalloc ulong[9];
 13908138        Span<ulong> leftAxisWords = stackalloc ulong[9];
 13908139        Span<ulong> rightAxisWords = stackalloc ulong[9];
 13908140        GetMagnitude(leftOverlap, leftOverlapWords);
 13908141        GetMagnitude(rightOverlap, rightOverlapWords);
 13908142        GetMagnitude(leftSquaredAxisLength, leftAxisWords);
 13908143        GetMagnitude(rightSquaredAxisLength, rightAxisWords);
 144
 13908145        if (leftCommonDenominator.Equals(rightCommonDenominator))
 146        {
 13907147            return CompareSignedNormalizedMagnitudes(
 13907148                leftOverlapWords,
 13907149                leftOverlap.Sign,
 13907150                leftAxisWords,
 13907151                rightOverlapWords,
 13907152                rightOverlap.Sign,
 13907153                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    {
 4204223        Span<ulong> overlapWords = stackalloc ulong[9];
 4204224        Span<ulong> axisWords = stackalloc ulong[9];
 4204225        Span<ulong> commonWords = stackalloc ulong[5];
 4204226        Span<ulong> twiceRawWords = stackalloc ulong[3];
 4204227        GetMagnitude(overlap, overlapWords);
 4204228        GetMagnitude(squaredAxisLength, axisWords);
 4204229        GetMagnitude(
 4204230            commonDenominator,
 4204231            out commonWords[4],
 4204232            out commonWords[3],
 4204233            out commonWords[2],
 4204234            out commonWords[1],
 4204235            out commonWords[0]);
 4204236        GetMagnitude(
 4204237            twiceRaw,
 4204238            out twiceRawWords[2],
 4204239            out twiceRawWords[1],
 4204240            out twiceRawWords[0]);
 241
 4204242        Span<ulong> left = stackalloc ulong[25];
 4204243        MultiplyMagnitudes(overlapWords, overlapWords, left);
 4204244        ShiftLeftMagnitude(left, 2);
 245
 4204246        Span<ulong> commonSquared = stackalloc ulong[10];
 4204247        Span<ulong> twiceRawSquared = stackalloc ulong[6];
 4204248        Span<ulong> thresholdSquared = stackalloc ulong[16];
 4204249        Span<ulong> right = stackalloc ulong[25];
 4204250        MultiplyMagnitudes(commonWords, commonWords, commonSquared);
 4204251        MultiplyMagnitudes(
 4204252            twiceRawWords,
 4204253            twiceRawWords,
 4204254            twiceRawSquared);
 4204255        MultiplyMagnitudes(
 4204256            commonSquared,
 4204257            twiceRawSquared,
 4204258            thresholdSquared);
 4204259        MultiplyMagnitudes(thresholdSquared, axisWords, right);
 4204260        return CompareMagnitudeEqualLength(left, right);
 261    }
 262
 263    #endregion
 264
 265    #region Scaled-Frame Normalized Depth Comparison
 266
 267    /// <summary>Compares exact scaled-frame depths without narrowing their squared axes.</summary>
 268    internal static int CompareNonNegativeNormalizedDepths(
 269        Signed832 leftOverlap, Signed832 leftSquaredAxisLength, Signed576 leftCommonDenominator,
 270        Signed832 rightOverlap, Signed832 rightSquaredAxisLength, Signed576 rightCommonDenominator)
 271    {
 14864272        Span<ulong> leftN = stackalloc ulong[13], rightN = stackalloc ulong[13];
 14864273        Span<ulong> leftAxis = stackalloc ulong[13], rightAxis = stackalloc ulong[13];
 14864274        GetMagnitude(leftOverlap, leftN); GetMagnitude(rightOverlap, rightN);
 14864275        GetMagnitude(leftSquaredAxisLength, leftAxis); GetMagnitude(rightSquaredAxisLength, rightAxis);
 7432276        if (leftCommonDenominator.Equals(rightCommonDenominator))
 7427277            return CompareSignedNormalizedMagnitudes(leftN, leftOverlap.Sign, leftAxis,
 7427278                rightN, rightOverlap.Sign, rightAxis);
 279
 10280        Span<ulong> leftD = stackalloc ulong[9], rightD = stackalloc ulong[9];
 10281        GetMagnitude(leftCommonDenominator, leftD); GetMagnitude(rightCommonDenominator, rightD);
 10282        Span<ulong> leftSquared = stackalloc ulong[26], rightSquared = stackalloc ulong[26];
 10283        Span<ulong> leftDSquared = stackalloc ulong[18], rightDSquared = stackalloc ulong[18];
 10284        MultiplyMagnitudes(leftN, leftN, leftSquared); MultiplyMagnitudes(rightN, rightN, rightSquared);
 10285        MultiplyMagnitudes(leftD, leftD, leftDSquared); MultiplyMagnitudes(rightD, rightD, rightDSquared);
 10286        Span<ulong> leftOnce = stackalloc ulong[44], rightOnce = stackalloc ulong[44];
 10287        Span<ulong> left = stackalloc ulong[57], right = stackalloc ulong[57];
 5288        MultiplyMagnitudes(leftSquared, rightDSquared, leftOnce);
 5289        MultiplyMagnitudes(rightSquared, leftDSquared, rightOnce);
 10290        MultiplyMagnitudes(leftOnce, rightAxis, left); MultiplyMagnitudes(rightOnce, leftAxis, right);
 5291        return CompareMagnitudeEqualLength(left, right);
 292    }
 293
 294    /// <summary>Rounds a scaled-frame normalized depth once, with the same nearest-even contract as rigid SAT.</summary
 295    internal static Fixed64 GetRoundedNonNegativeNormalizedDepth(Signed832 overlap,
 296        Signed832 squaredAxisLength, Signed576 commonDenominator, out bool isClamped)
 297    {
 126298        Signed192 maximumTwice = AddSigned192(Signed192.Signed(long.MaxValue), Signed192.Signed(long.MaxValue));
 126299        if (CompareNormalizedDepthToTwiceRaw(overlap, squaredAxisLength, commonDenominator, maximumTwice) > 0)
 6300        { isClamped = true; return Fixed64.MaxValue; }
 123301        isClamped = false;
 302        // The scaled floor root has less than one raw-unit quotient error for
 303        // axes >= 2^62; exact midpoint admission corrects its final rounding.
 123304        if (SubtractSigned832(squaredAxisLength, Signed832.ExtendValue(Signed192.Signed(1L << 62))).Sign >= 0)
 305        {
 119306            Signed576 root = GetFloorSquareRootOfProduct(squaredAxisLength, new Signed192(0UL, 1UL, 0UL));
 119307            Signed832 denominator = MultiplySigned576ToSigned832(root, commonDenominator);
 119308            if (!Fixed64.TryGetSignedRawRatio(overlap, denominator, FixedMath.SHIFT_AMOUNT_I, out Fixed64 result))
 1309                result = Fixed64.MaxValue;
 128310            if (result == Fixed64.Zero) return result;
 110311            Signed192 midpoint = SubtractSigned192(AddSigned192(Signed192.Signed(result.m_rawValue),
 110312                Signed192.Signed(result.m_rawValue)), Signed192.Signed(1));
 110313            if (CompareNormalizedDepthToTwiceRaw(overlap, squaredAxisLength, commonDenominator, midpoint)
 111314                < (result.m_rawValue & 1L)) result = Fixed64.FromRaw(result.m_rawValue - 1);
 110315            return result;
 316        }
 8317        long low = 0, high = long.MaxValue;
 256318        while (low < high)
 319        {
 252320            long candidate = (long)(((ulong)low + (ulong)high + 1UL) >> 1);
 252321            Signed192 midpoint = SubtractSigned192(AddSigned192(Signed192.Signed(candidate),
 252322                Signed192.Signed(candidate)), Signed192.Signed(1));
 252323            int comparison = CompareNormalizedDepthToTwiceRaw(overlap, squaredAxisLength, commonDenominator, midpoint);
 256324            if (comparison > 0 || (comparison == 0 && (candidate & 1L) == 0)) low = candidate;
 248325            else high = candidate - 1;
 326        }
 4327        return Fixed64.FromRaw(low);
 328    }
 329
 330    private static int CompareNormalizedDepthToTwiceRaw(Signed832 overlap,
 331        Signed832 squaredAxisLength, Signed576 commonDenominator, Signed192 twiceRaw)
 332    {
 1464333        Span<ulong> n = stackalloc ulong[13], axis = stackalloc ulong[13], d = stackalloc ulong[9];
 488334        Span<ulong> raw = stackalloc ulong[3];
 1464335        GetMagnitude(overlap, n); GetMagnitude(squaredAxisLength, axis); GetMagnitude(commonDenominator, d);
 488336        GetMagnitude(twiceRaw, out raw[2], out raw[1], out raw[0]);
 976337        Span<ulong> left = stackalloc ulong[37], right = stackalloc ulong[37];
 976338        Span<ulong> dSquared = stackalloc ulong[18], rawSquared = stackalloc ulong[6];
 488339        Span<ulong> threshold = stackalloc ulong[24];
 976340        MultiplyMagnitudes(n, n, left); ShiftLeftMagnitude(left, 2);
 976341        MultiplyMagnitudes(d, d, dSquared); MultiplyMagnitudes(raw, raw, rawSquared);
 976342        MultiplyMagnitudes(dSquared, rawSquared, threshold); MultiplyMagnitudes(threshold, axis, right);
 488343        return CompareMagnitudeEqualLength(left, right);
 344    }
 345
 346    #endregion
 347
 348    #region Normalized Magnitude Comparison
 349
 350    /// <summary>
 351    /// Compares signed ratios of the form
 352    /// <c>numerator / sqrt(squaredAxisLength)</c>.
 353    /// </summary>
 354    internal static int CompareSignedNormalizedMagnitudes(
 355        ReadOnlySpan<ulong> leftNumerator,
 356        int leftSign,
 357        ReadOnlySpan<ulong> leftSquaredAxisLength,
 358        ReadOnlySpan<ulong> rightNumerator,
 359        int rightSign,
 360        ReadOnlySpan<ulong> rightSquaredAxisLength)
 361    {
 362        // Padding carries no value; size exact products from the active limbs.
 89686363        leftNumerator = leftNumerator[..GetActiveMagnitudeLength(leftNumerator)];
 89686364        rightNumerator = rightNumerator[..GetActiveMagnitudeLength(rightNumerator)];
 89686365        leftSquaredAxisLength = leftSquaredAxisLength[..GetActiveMagnitudeLength(leftSquaredAxisLength)];
 89686366        rightSquaredAxisLength = rightSquaredAxisLength[..GetActiveMagnitudeLength(rightSquaredAxisLength)];
 89686367        leftSign = leftSign == 0 || IsZeroMagnitude(leftNumerator)
 89686368            ? 0
 89686369            : leftSign;
 89686370        rightSign = rightSign == 0 || IsZeroMagnitude(rightNumerator)
 89686371            ? 0
 89686372            : rightSign;
 89686373        if (leftSign != rightSign)
 9696374            return leftSign.CompareTo(rightSign);
 79990375        if (leftSign == 0)
 192376            return 0;
 377
 79798378        int wordCount = Math.Max(
 79798379            Math.Max(leftNumerator.Length, rightNumerator.Length),
 79798380            Math.Max(
 79798381                leftSquaredAxisLength.Length,
 79798382                rightSquaredAxisLength.Length));
 79798383        int productWordCount = wordCount * 3;
 79798384        Span<ulong> products =
 79798385            stackalloc ulong[productWordCount * 2];
 79798386        Span<ulong> square = stackalloc ulong[wordCount * 2];
 79798387        Span<ulong> paddedNumerator = stackalloc ulong[wordCount];
 79798388        Span<ulong> paddedAxis = stackalloc ulong[wordCount];
 389
 79798390        paddedNumerator.Clear();
 79798391        leftNumerator.CopyTo(paddedNumerator);
 79798392        MultiplyMagnitudes(
 79798393            paddedNumerator,
 79798394            paddedNumerator,
 79798395            square);
 79798396        paddedAxis.Clear();
 79798397        rightSquaredAxisLength.CopyTo(paddedAxis);
 79798398        MultiplyMagnitudes(
 79798399            square,
 79798400            paddedAxis,
 79798401            products.Slice(0, productWordCount));
 402
 79798403        paddedNumerator.Clear();
 79798404        rightNumerator.CopyTo(paddedNumerator);
 79798405        MultiplyMagnitudes(
 79798406            paddedNumerator,
 79798407            paddedNumerator,
 79798408            square);
 79798409        paddedAxis.Clear();
 79798410        leftSquaredAxisLength.CopyTo(paddedAxis);
 79798411        MultiplyMagnitudes(
 79798412            square,
 79798413            paddedAxis,
 79798414            products.Slice(
 79798415                productWordCount,
 79798416                productWordCount));
 417
 79798418        int comparison = CompareMagnitudeEqualLength(
 79798419            products.Slice(0, productWordCount),
 79798420            products.Slice(productWordCount, productWordCount));
 79798421        return leftSign > 0 ? comparison : -comparison;
 422    }
 423
 424    /// <summary>
 425    /// Gets the exact sign of
 426    /// <c>rational + coefficient * sqrt(squaredRadicand)</c>.
 427    /// </summary>
 428    internal static int GetSignedMagnitudeAndSquareRootSign(
 429        ReadOnlySpan<ulong> rational,
 430        int rationalSign,
 431        ReadOnlySpan<ulong> coefficient,
 432        int coefficientSign,
 433        ReadOnlySpan<ulong> squaredRadicand)
 434    {
 435        // Retain every significant limb while avoiding padded-width products.
 6086436        rational = rational[..GetActiveMagnitudeLength(rational)];
 6086437        coefficient = coefficient[..GetActiveMagnitudeLength(coefficient)];
 6086438        squaredRadicand = squaredRadicand[..GetActiveMagnitudeLength(squaredRadicand)];
 6086439        rationalSign = rationalSign == 0 || IsZeroMagnitude(rational)
 6086440            ? 0
 6086441            : rationalSign;
 6086442        coefficientSign =
 6086443            coefficientSign == 0
 6086444            || IsZeroMagnitude(coefficient)
 6086445            || IsZeroMagnitude(squaredRadicand)
 6086446                ? 0
 6086447                : coefficientSign;
 6086448        if (rationalSign == 0)
 318449            return coefficientSign;
 5768450        if (coefficientSign == 0 || rationalSign == coefficientSign)
 3957451            return rationalSign;
 452
 1811453        int wordCount = Math.Max(
 1811454            Math.Max(rational.Length, coefficient.Length),
 1811455            squaredRadicand.Length);
 1811456        int productWordCount = wordCount * 3;
 1811457        Span<ulong> products =
 1811458            stackalloc ulong[productWordCount * 2];
 1811459        products.Clear();
 1811460        Span<ulong> padded = stackalloc ulong[wordCount];
 1811461        Span<ulong> square = stackalloc ulong[wordCount * 2];
 462
 1811463        padded.Clear();
 1811464        rational.CopyTo(padded);
 1811465        MultiplyMagnitudes(padded, padded, square);
 1811466        square.CopyTo(products);
 467
 1811468        padded.Clear();
 1811469        coefficient.CopyTo(padded);
 1811470        MultiplyMagnitudes(padded, padded, square);
 1811471        padded.Clear();
 1811472        squaredRadicand.CopyTo(padded);
 1811473        MultiplyMagnitudes(
 1811474            square,
 1811475            padded,
 1811476            products.Slice(
 1811477                productWordCount,
 1811478                productWordCount));
 479
 1811480        int comparison = CompareMagnitudeEqualLength(
 1811481            products.Slice(0, productWordCount),
 1811482            products.Slice(productWordCount, productWordCount));
 1811483        if (comparison == 0)
 271484            return 0;
 1540485        return comparison > 0
 1540486            ? rationalSign
 1540487            : coefficientSign;
 488    }
 489
 490    #endregion
 491
 492    #region Radial Projection Comparison
 493
 494    private const int RadialProjectionWordCount = 96;
 495
 496    /// <summary>
 497    /// Compares two nonnegative radial projection depths without materializing
 498    /// either radical.
 499    /// </summary>
 500    /// <remarks>
 501    /// Each depth has the form
 502    /// (rational + common * sqrt(radicandNumerator / radicandDenominator)) /
 503    /// (common * sqrt(axisSquared)). The comparison squares the nonnegative
 504    /// depths and reduces the result to at most two radicals on either side.
 505    /// </remarks>
 506    internal static int CompareRadialProjectionDepths(
 507        Signed576 leftRational,
 508        Signed832 leftRadicandNumerator,
 509        Signed576 leftRadicandDenominator,
 510        Signed576 leftAxisSquared,
 511        Signed576 rightRational,
 512        Signed832 rightRadicandNumerator,
 513        Signed576 rightRadicandDenominator,
 514        Signed576 rightAxisSquared,
 515        Signed192 common)
 516    {
 678517        Signed320 radialCoefficient = Signed320.ExtendValue(common);
 678518        return CompareRadialProjectionDepths(
 678519            Signed704.ExtendValue(leftRational),
 678520            radialCoefficient,
 678521            leftRadicandNumerator,
 678522            leftRadicandDenominator,
 678523            leftAxisSquared,
 678524            Signed704.ExtendValue(rightRational),
 678525            radialCoefficient,
 678526            rightRadicandNumerator,
 678527            rightRadicandDenominator,
 678528            rightAxisSquared);
 529    }
 530
 531    /// <summary>
 532    /// Compares two nonnegative radial projection depths without materializing
 533    /// either radical.
 534    /// </summary>
 535    /// <remarks>
 536    /// Each depth has the form
 537    /// (rational + radialCoefficient *
 538    /// sqrt(radicandNumerator / radicandDenominator)) /
 539    /// sqrt(axisSquared). Any shared positive denominator has already been
 540    /// omitted because it cannot change the ordering.
 541    /// </remarks>
 542    internal static int CompareRadialProjectionDepths(
 543        Signed704 leftRational,
 544        Signed320 leftRadialCoefficient,
 545        Signed832 leftRadicandNumerator,
 546        Signed576 leftRadicandDenominator,
 547        Signed576 leftAxisSquared,
 548        Signed704 rightRational,
 549        Signed320 rightRadialCoefficient,
 550        Signed832 rightRadicandNumerator,
 551        Signed576 rightRadicandDenominator,
 552        Signed576 rightAxisSquared)
 553    {
 1184554        Span<ulong> leftBase =
 1184555            stackalloc ulong[RadialProjectionWordCount];
 1184556        Span<ulong> rightBase =
 1184557            stackalloc ulong[RadialProjectionWordCount];
 1184558        BuildSquaredRadialDepthNumerator(
 1184559            leftRational,
 1184560            leftRadialCoefficient,
 1184561            leftRadicandNumerator,
 1184562            leftRadicandDenominator,
 1184563            rightAxisSquared,
 1184564            rightRadicandDenominator,
 1184565            leftBase);
 1184566        BuildSquaredRadialDepthNumerator(
 1184567            rightRational,
 1184568            rightRadialCoefficient,
 1184569            rightRadicandNumerator,
 1184570            rightRadicandDenominator,
 1184571            leftAxisSquared,
 1184572            leftRadicandDenominator,
 1184573            rightBase);
 574
 1184575        int baseComparison = CompareMagnitudeEqualLength(
 1184576            leftBase,
 1184577            rightBase);
 1184578        Span<ulong> baseMagnitude =
 1184579            stackalloc ulong[RadialProjectionWordCount];
 1184580        if (baseComparison >= 0)
 581        {
 918582            SubtractEqualMagnitudes(
 918583                leftBase,
 918584                rightBase,
 918585                baseMagnitude);
 586        }
 587        else
 588        {
 266589            SubtractEqualMagnitudes(
 266590                rightBase,
 266591                leftBase,
 266592                baseMagnitude);
 593        }
 594
 1184595        Span<ulong> baseRadicand =
 1184596            stackalloc ulong[RadialProjectionWordCount];
 1184597        MultiplyMagnitudes(
 1184598            baseMagnitude,
 1184599            baseMagnitude,
 1184600            baseRadicand);
 1184601        Span<ulong> leftRadicand =
 1184602            stackalloc ulong[RadialProjectionWordCount];
 1184603        BuildRadialDepthCrossRadicand(
 1184604            leftRadialCoefficient,
 1184605            rightAxisSquared,
 1184606            rightRadicandDenominator,
 1184607            leftRational,
 1184608            leftRadicandNumerator,
 1184609            leftRadicandDenominator,
 1184610            leftRadicand);
 1184611        Span<ulong> rightRadicand =
 1184612            stackalloc ulong[RadialProjectionWordCount];
 1184613        BuildRadialDepthCrossRadicand(
 1184614            rightRadialCoefficient,
 1184615            leftAxisSquared,
 1184616            leftRadicandDenominator,
 1184617            rightRational,
 1184618            rightRadicandNumerator,
 1184619            rightRadicandDenominator,
 1184620            rightRadicand);
 621
 1184622        int baseSign = IsZeroMagnitude(baseRadicand)
 1184623            ? 0
 1184624            : baseComparison;
 1184625        int leftSign = IsZeroMagnitude(leftRadicand)
 1184626            ? 0
 1184627            : leftRational.Sign;
 1184628        int rightSign = IsZeroMagnitude(rightRadicand)
 1184629            ? 0
 1184630            : -rightRational.Sign;
 1184631        int positiveCount =
 1184632            (baseSign > 0 ? 1 : 0)
 1184633            + (leftSign > 0 ? 1 : 0)
 1184634            + (rightSign > 0 ? 1 : 0);
 1184635        int negativeCount =
 1184636            (baseSign < 0 ? 1 : 0)
 1184637            + (leftSign < 0 ? 1 : 0)
 1184638            + (rightSign < 0 ? 1 : 0);
 1184639        if (positiveCount == 0)
 147640            return negativeCount == 0 ? 0 : -1;
 1037641        if (negativeCount == 0)
 177642            return 1;
 643
 860644        Span<ulong> positiveFirst =
 860645            stackalloc ulong[RadialProjectionWordCount];
 860646        Span<ulong> positiveSecond =
 860647            stackalloc ulong[RadialProjectionWordCount];
 860648        Span<ulong> negativeFirst =
 860649            stackalloc ulong[RadialProjectionWordCount];
 860650        Span<ulong> negativeSecond =
 860651            stackalloc ulong[RadialProjectionWordCount];
 860652        positiveFirst.Clear();
 860653        positiveSecond.Clear();
 860654        negativeFirst.Clear();
 860655        negativeSecond.Clear();
 860656        int positiveIndex = 0;
 860657        int negativeIndex = 0;
 860658        AddSignedRadicand(
 860659            baseRadicand,
 860660            baseSign,
 860661            positiveFirst,
 860662            positiveSecond,
 860663            negativeFirst,
 860664            negativeSecond,
 860665            ref positiveIndex,
 860666            ref negativeIndex);
 860667        AddSignedRadicand(
 860668            leftRadicand,
 860669            leftSign,
 860670            positiveFirst,
 860671            positiveSecond,
 860672            negativeFirst,
 860673            negativeSecond,
 860674            ref positiveIndex,
 860675            ref negativeIndex);
 860676        AddSignedRadicand(
 860677            rightRadicand,
 860678            rightSign,
 860679            positiveFirst,
 860680            positiveSecond,
 860681            negativeFirst,
 860682            negativeSecond,
 860683            ref positiveIndex,
 860684            ref negativeIndex);
 860685        return CompareNonNegativeRadicalPairs(
 860686            positiveFirst,
 860687            positiveSecond,
 860688            negativeFirst,
 860689            negativeSecond);
 690    }
 691
 692    private static void AddSignedRadicand(
 693        ReadOnlySpan<ulong> radicand,
 694        int sign,
 695        Span<ulong> positiveFirst,
 696        Span<ulong> positiveSecond,
 697        Span<ulong> negativeFirst,
 698        Span<ulong> negativeSecond,
 699        ref int positiveIndex,
 700        ref int negativeIndex)
 701    {
 2580702        if (sign == 0)
 447703            return;
 704
 2133705        if (sign > 0)
 706        {
 1024707            radicand.CopyTo(
 1024708                positiveIndex++ == 0
 1024709                    ? positiveFirst
 1024710                    : positiveSecond);
 1024711            return;
 712        }
 713
 1109714        radicand.CopyTo(
 1109715            negativeIndex++ == 0
 1109716                ? negativeFirst
 1109717                : negativeSecond);
 1109718    }
 719
 720    private static void BuildSquaredRadialDepthNumerator(
 721        Signed704 rational,
 722        Signed320 radialCoefficient,
 723        Signed832 radicandNumerator,
 724        Signed576 radicandDenominator,
 725        Signed576 otherAxisSquared,
 726        Signed576 otherRadicandDenominator,
 727        Span<ulong> result)
 728    {
 2368729        result.Clear();
 2368730        Span<ulong> rationalWords = stackalloc ulong[11];
 2368731        Span<ulong> radialCoefficientWords = stackalloc ulong[5];
 2368732        Span<ulong> numeratorWords = stackalloc ulong[13];
 2368733        Span<ulong> denominatorWords = stackalloc ulong[9];
 2368734        Span<ulong> axisWords = stackalloc ulong[9];
 2368735        Span<ulong> otherDenominatorWords = stackalloc ulong[9];
 2368736        GetMagnitude(rational, rationalWords);
 2368737        GetMagnitude(
 2368738            radialCoefficient,
 2368739            out radialCoefficientWords[4],
 2368740            out radialCoefficientWords[3],
 2368741            out radialCoefficientWords[2],
 2368742            out radialCoefficientWords[1],
 2368743            out radialCoefficientWords[0]);
 2368744        GetMagnitude(radicandNumerator, numeratorWords);
 2368745        GetMagnitude(radicandDenominator, denominatorWords);
 2368746        GetMagnitude(otherAxisSquared, axisWords);
 2368747        GetMagnitude(
 2368748            otherRadicandDenominator,
 2368749            otherDenominatorWords);
 750
 2368751        Span<ulong> rationalSquared = stackalloc ulong[22];
 2368752        Span<ulong> rationalTerm = stackalloc ulong[31];
 2368753        MultiplyMagnitudes(
 2368754            rationalWords,
 2368755            rationalWords,
 2368756            rationalSquared);
 2368757        MultiplyMagnitudes(
 2368758            rationalSquared,
 2368759            denominatorWords,
 2368760            rationalTerm);
 761
 2368762        Span<ulong> coefficientSquared = stackalloc ulong[10];
 2368763        Span<ulong> radialTerm = stackalloc ulong[23];
 2368764        MultiplyMagnitudes(
 2368765            radialCoefficientWords,
 2368766            radialCoefficientWords,
 2368767            coefficientSquared);
 2368768        MultiplyMagnitudes(
 2368769            coefficientSquared,
 2368770            numeratorWords,
 2368771            radialTerm);
 772
 2368773        Span<ulong> numerator = stackalloc ulong[32];
 2368774        numerator.Clear();
 2368775        AddMagnitudeInto(rationalTerm, numerator);
 2368776        AddMagnitudeInto(radialTerm, numerator);
 2368777        Span<ulong> axisScaled = stackalloc ulong[41];
 2368778        Span<ulong> fullyScaled = stackalloc ulong[50];
 2368779        MultiplyMagnitudes(
 2368780            numerator,
 2368781            axisWords,
 2368782            axisScaled);
 2368783        MultiplyMagnitudes(
 2368784            axisScaled,
 2368785            otherDenominatorWords,
 2368786            fullyScaled);
 2368787        fullyScaled.CopyTo(result);
 2368788    }
 789
 790    private static void BuildRadialDepthCrossRadicand(
 791        Signed320 radialCoefficient,
 792        Signed576 otherAxisSquared,
 793        Signed576 otherRadicandDenominator,
 794        Signed704 rational,
 795        Signed832 radicandNumerator,
 796        Signed576 radicandDenominator,
 797        Span<ulong> result)
 798    {
 2368799        if (radialCoefficient.IsZero
 2368800            || rational.IsZero
 2368801            || radicandNumerator.IsZero)
 802        {
 470803            result.Clear();
 470804            return;
 805        }
 806
 1898807        Span<ulong> radialCoefficientWords = stackalloc ulong[5];
 1898808        Span<ulong> axisWords = stackalloc ulong[9];
 1898809        Span<ulong> otherDenominatorWords = stackalloc ulong[9];
 1898810        Span<ulong> rationalWords = stackalloc ulong[11];
 1898811        Span<ulong> numeratorWords = stackalloc ulong[13];
 1898812        Span<ulong> denominatorWords = stackalloc ulong[9];
 1898813        GetMagnitude(
 1898814            radialCoefficient,
 1898815            out radialCoefficientWords[4],
 1898816            out radialCoefficientWords[3],
 1898817            out radialCoefficientWords[2],
 1898818            out radialCoefficientWords[1],
 1898819            out radialCoefficientWords[0]);
 1898820        GetMagnitude(otherAxisSquared, axisWords);
 1898821        GetMagnitude(
 1898822            otherRadicandDenominator,
 1898823            otherDenominatorWords);
 1898824        GetMagnitude(rational, rationalWords);
 1898825        GetMagnitude(radicandNumerator, numeratorWords);
 1898826        GetMagnitude(radicandDenominator, denominatorWords);
 827
 1898828        Span<ulong> coefficientAndAxis = stackalloc ulong[14];
 1898829        Span<ulong> withRational = stackalloc ulong[25];
 1898830        Span<ulong> completeCoefficient = stackalloc ulong[34];
 1898831        Span<ulong> coefficientSquared = stackalloc ulong[68];
 1898832        Span<ulong> withNumerator = stackalloc ulong[81];
 1898833        MultiplyMagnitudes(
 1898834            radialCoefficientWords,
 1898835            axisWords,
 1898836            coefficientAndAxis);
 1898837        MultiplyMagnitudes(
 1898838            coefficientAndAxis,
 1898839            rationalWords,
 1898840            withRational);
 1898841        MultiplyMagnitudes(
 1898842            withRational,
 1898843            otherDenominatorWords,
 1898844            completeCoefficient);
 1898845        MultiplyMagnitudes(
 1898846            completeCoefficient,
 1898847            completeCoefficient,
 1898848            coefficientSquared);
 1898849        MultiplyMagnitudes(
 1898850            coefficientSquared,
 1898851            numeratorWords,
 1898852            withNumerator);
 1898853        MultiplyMagnitudes(
 1898854            withNumerator,
 1898855            denominatorWords,
 1898856            result);
 1898857        ShiftLeftMagnitude(result, 2);
 1898858    }
 859
 860    private static int CompareNonNegativeRadicalPairs(
 861        ReadOnlySpan<ulong> leftFirst,
 862        ReadOnlySpan<ulong> leftSecond,
 863        ReadOnlySpan<ulong> rightFirst,
 864        ReadOnlySpan<ulong> rightSecond)
 865    {
 860866        Span<ulong> leftBase =
 860867            stackalloc ulong[RadialProjectionWordCount];
 860868        Span<ulong> rightBase =
 860869            stackalloc ulong[RadialProjectionWordCount];
 860870        AddEqualMagnitudes(leftFirst, leftSecond, leftBase);
 860871        AddEqualMagnitudes(rightFirst, rightSecond, rightBase);
 860872        int baseComparison = CompareMagnitudeEqualLength(
 860873            leftBase,
 860874            rightBase);
 860875        Span<ulong> baseMagnitude =
 860876            stackalloc ulong[RadialProjectionWordCount];
 860877        if (baseComparison >= 0)
 878        {
 607879            SubtractEqualMagnitudes(
 607880                leftBase,
 607881                rightBase,
 607882                baseMagnitude);
 883        }
 884        else
 885        {
 253886            SubtractEqualMagnitudes(
 253887                rightBase,
 253888                leftBase,
 253889                baseMagnitude);
 890        }
 891
 860892        Span<ulong> leftProduct =
 860893            stackalloc ulong[RadialProjectionWordCount * 2];
 860894        Span<ulong> rightProduct =
 860895            stackalloc ulong[RadialProjectionWordCount * 2];
 860896        MultiplyMagnitudes(leftFirst, leftSecond, leftProduct);
 860897        MultiplyMagnitudes(rightFirst, rightSecond, rightProduct);
 860898        if (baseComparison >= 0)
 899        {
 607900            return ComparePositiveRadicalPairDifference(
 607901                baseMagnitude,
 607902                leftProduct,
 607903                rightProduct);
 904        }
 905
 253906        return -ComparePositiveRadicalPairDifference(
 253907            baseMagnitude,
 253908            rightProduct,
 253909            leftProduct);
 910    }
 911
 912    private static int ComparePositiveRadicalPairDifference(
 913        ReadOnlySpan<ulong> positiveBase,
 914        ReadOnlySpan<ulong> sameSideProduct,
 915        ReadOnlySpan<ulong> oppositeSideProduct)
 916    {
 860917        Span<ulong> baseSquared =
 860918            stackalloc ulong[RadialProjectionWordCount * 2];
 860919        Span<ulong> fourSame =
 860920            stackalloc ulong[RadialProjectionWordCount * 2];
 860921        Span<ulong> fourOpposite =
 860922            stackalloc ulong[RadialProjectionWordCount * 2];
 860923        MultiplyMagnitudes(
 860924            positiveBase,
 860925            positiveBase,
 860926            baseSquared);
 860927        sameSideProduct.CopyTo(fourSame);
 860928        oppositeSideProduct.CopyTo(fourOpposite);
 860929        ShiftLeftMagnitude(fourSame, 2);
 860930        ShiftLeftMagnitude(fourOpposite, 2);
 931
 860932        Span<ulong> knownLeft =
 860933            stackalloc ulong[RadialProjectionWordCount * 2];
 860934        AddEqualMagnitudes(baseSquared, fourSame, knownLeft);
 860935        int knownComparison = CompareMagnitudeEqualLength(
 860936            knownLeft,
 860937            fourOpposite);
 860938        if (knownComparison > 0)
 574939            return 1;
 286940        if (knownComparison == 0)
 941        {
 942            // This reducer partitions three signed radical terms. Therefore
 943            // at least one side has a zero product; equality of the known
 944            // squared terms can only occur when the remaining cross term is
 945            // also zero.
 278946            return 0;
 947        }
 948
 8949        Span<ulong> remainder =
 8950            stackalloc ulong[RadialProjectionWordCount * 2];
 8951        SubtractEqualMagnitudes(
 8952            fourOpposite,
 8953            knownLeft,
 8954            remainder);
 8955        Span<ulong> crossSquared =
 8956            stackalloc ulong[RadialProjectionWordCount * 4];
 8957        Span<ulong> remainderSquared =
 8958            stackalloc ulong[RadialProjectionWordCount * 4];
 8959        MultiplyMagnitudes(
 8960            baseSquared,
 8961            sameSideProduct,
 8962            crossSquared);
 8963        ShiftLeftMagnitude(crossSquared, 4);
 8964        MultiplyMagnitudes(
 8965            remainder,
 8966            remainder,
 8967            remainderSquared);
 8968        return CompareMagnitudeEqualLength(
 8969            crossSquared,
 8970            remainderSquared);
 971    }
 972
 973    #endregion
 974
 975    #region Radical Comparison
 976
 977
 978    /// <summary>
 979    /// Compares <c>sqrt(firstNumerator / firstDenominator) +
 980    /// sqrt(secondNumerator / secondDenominator)</c> with a nonnegative ratio.
 981    /// </summary>
 982    internal static int CompareNonNegativeRadicalSumToRatio(
 983        Signed576 firstNumerator,
 984        Signed192 firstDenominator,
 985        Signed576 secondNumerator,
 986        Signed192 secondDenominator,
 987        Signed320 ratioNumerator,
 988        Signed192 ratioDenominator)
 989    {
 729990        bool firstZero = firstNumerator.IsZero;
 729991        bool secondZero = secondNumerator.IsZero;
 729992        if (firstZero && secondZero)
 39993            return ratioNumerator.IsZero ? 0 : -1;
 690994        if (firstZero)
 995        {
 238996            return CompareNonNegativeRadicalToRatio(
 238997                secondNumerator,
 238998                secondDenominator,
 238999                ratioNumerator,
 2381000                ratioDenominator);
 1001        }
 4521002        if (secondZero)
 1003        {
 1651004            return CompareNonNegativeRadicalToRatio(
 1651005                firstNumerator,
 1651006                firstDenominator,
 1651007                ratioNumerator,
 1651008                ratioDenominator);
 1009        }
 1010
 2871011        Signed576 ratioSquared = MultiplySigned320(ratioNumerator, ratioNumerator);
 2871012        Signed576 denominatorProduct = MultiplySigned320(
 2871013            Signed320.ExtendValue(firstDenominator),
 2871014            Signed320.ExtendValue(secondDenominator));
 2871015        Signed576 squaredRatioTerm = MultiplyNonNegativeToSigned576(
 2871016            ratioSquared,
 2871017            denominatorProduct);
 2871018        Signed576 radicalSquares = AddSigned576(
 2871019            MultiplySigned576(firstNumerator, secondDenominator),
 2871020            MultiplySigned576(secondNumerator, firstDenominator));
 2871021        Signed320 ratioDenominatorSquared = MultiplySigned192(
 2871022            ratioDenominator,
 2871023            ratioDenominator);
 2871024        _ = Signed192.TryNarrowSigned(
 2871025            Signed576.ExtendValue(ratioDenominatorSquared),
 2871026            out Signed192 narrowRatioDenominatorSquared);
 2871027        Signed576 radicalSquareTerm = MultiplySigned576(
 2871028            radicalSquares,
 2871029            narrowRatioDenominatorSquared);
 2871030        Signed576 remainder = SubtractSigned576(
 2871031            squaredRatioTerm,
 2871032            radicalSquareTerm);
 2871033        if (remainder.Sign <= 0)
 471034            return 1;
 1035
 2401036        return CompareRadicalCrossTerm(
 2401037            firstNumerator,
 2401038            firstDenominator,
 2401039            secondNumerator,
 2401040            secondDenominator,
 2401041            ratioDenominator,
 2401042            remainder);
 1043    }
 1044
 1045    /// <summary>
 1046    /// Compares a nonnegative radical with a nonnegative ratio whose
 1047    /// denominators require the full five-word geometry range.
 1048    /// </summary>
 1049    internal static int CompareNonNegativeRadicalToRatio(
 1050        Signed576 numerator,
 1051        Signed320 denominator,
 1052        Signed320 ratioNumerator,
 1053        Signed320 ratioDenominator)
 1054    {
 1471055        Span<ulong> numeratorWords = stackalloc ulong[9];
 1471056        Span<ulong> denominatorWords = stackalloc ulong[5];
 1471057        Span<ulong> ratioNumeratorWords = stackalloc ulong[5];
 1471058        Span<ulong> ratioDenominatorWords = stackalloc ulong[5];
 1471059        GetMagnitude(numerator, numeratorWords);
 1471060        GetMagnitude(
 1471061            denominator,
 1471062            out denominatorWords[4],
 1471063            out denominatorWords[3],
 1471064            out denominatorWords[2],
 1471065            out denominatorWords[1],
 1471066            out denominatorWords[0]);
 1471067        GetMagnitude(
 1471068            ratioNumerator,
 1471069            out ratioNumeratorWords[4],
 1471070            out ratioNumeratorWords[3],
 1471071            out ratioNumeratorWords[2],
 1471072            out ratioNumeratorWords[1],
 1471073            out ratioNumeratorWords[0]);
 1471074        GetMagnitude(
 1471075            ratioDenominator,
 1471076            out ratioDenominatorWords[4],
 1471077            out ratioDenominatorWords[3],
 1471078            out ratioDenominatorWords[2],
 1471079            out ratioDenominatorWords[1],
 1471080            out ratioDenominatorWords[0]);
 1081
 1471082        Span<ulong> ratioNumeratorSquared = stackalloc ulong[10];
 1471083        Span<ulong> ratioDenominatorSquared = stackalloc ulong[10];
 1471084        Span<ulong> left = stackalloc ulong[19];
 1471085        Span<ulong> right = stackalloc ulong[19];
 1471086        MultiplyMagnitudes(
 1471087            ratioNumeratorWords,
 1471088            ratioNumeratorWords,
 1471089            ratioNumeratorSquared);
 1471090        MultiplyMagnitudes(
 1471091            ratioDenominatorWords,
 1471092            ratioDenominatorWords,
 1471093            ratioDenominatorSquared);
 1471094        MultiplyMagnitudes(
 1471095            numeratorWords,
 1471096            ratioDenominatorSquared,
 1471097            left);
 1471098        MultiplyMagnitudes(
 1471099            ratioNumeratorSquared,
 1471100            denominatorWords,
 1471101            right);
 1471102        return CompareMagnitudeEqualLength(left, right);
 1103    }
 1104
 1105    /// <summary>
 1106    /// Returns the sign of a signed rational term plus a signed coefficient
 1107    /// multiplied by one nonnegative radical.
 1108    /// </summary>
 1109    internal static int CompareSignedLinearRadicalToZero(
 1110        Signed832 rational,
 1111        Signed704 radicalCoefficient,
 1112        Signed576 radicandNumerator,
 1113        Signed320 radicandDenominator)
 1114    {
 100211115        int rationalSign = rational.Sign;
 100211116        int coefficientSign = radicandNumerator.IsZero
 100211117            ? 0
 100211118            : radicalCoefficient.Sign;
 100211119        if (rationalSign == 0)
 14361120            return coefficientSign;
 85851121        if (coefficientSign == 0 || rationalSign == coefficientSign)
 52921122            return rationalSign;
 1123
 32931124        Span<ulong> rationalWords = stackalloc ulong[13];
 32931125        Span<ulong> coefficientWords = stackalloc ulong[11];
 32931126        Span<ulong> numeratorWords = stackalloc ulong[9];
 32931127        Span<ulong> denominatorWords = stackalloc ulong[5];
 32931128        GetMagnitude(rational, rationalWords);
 32931129        GetMagnitude(radicalCoefficient, coefficientWords);
 32931130        GetMagnitude(radicandNumerator, numeratorWords);
 32931131        GetMagnitude(
 32931132            radicandDenominator,
 32931133            out denominatorWords[4],
 32931134            out denominatorWords[3],
 32931135            out denominatorWords[2],
 32931136            out denominatorWords[1],
 32931137            out denominatorWords[0]);
 1138
 32931139        Span<ulong> rationalSquared = stackalloc ulong[26];
 32931140        Span<ulong> coefficientSquared = stackalloc ulong[22];
 32931141        Span<ulong> rationalScaled = stackalloc ulong[31];
 32931142        Span<ulong> coefficientScaled = stackalloc ulong[31];
 32931143        MultiplyMagnitudes(
 32931144            rationalWords,
 32931145            rationalWords,
 32931146            rationalSquared);
 32931147        MultiplyMagnitudes(
 32931148            coefficientWords,
 32931149            coefficientWords,
 32931150            coefficientSquared);
 32931151        MultiplyMagnitudes(
 32931152            rationalSquared,
 32931153            denominatorWords,
 32931154            rationalScaled);
 32931155        MultiplyMagnitudes(
 32931156            coefficientSquared,
 32931157            numeratorWords,
 32931158            coefficientScaled);
 32931159        int comparison = CompareMagnitudeEqualLength(
 32931160            rationalScaled,
 32931161            coefficientScaled);
 32931162        return comparison == 0
 32931163            ? 0
 32931164            : comparison > 0
 32931165                ? rationalSign
 32931166                : coefficientSign;
 1167    }
 1168
 1169    private static int CompareNonNegativeRadicalToRatio(
 1170        Signed576 numerator,
 1171        Signed192 denominator,
 1172        Signed320 ratioNumerator,
 1173        Signed192 ratioDenominator)
 1174    {
 4031175        Signed320 ratioDenominatorSquared = MultiplySigned192(
 4031176            ratioDenominator,
 4031177            ratioDenominator);
 4031178        _ = Signed192.TryNarrowSigned(
 4031179            Signed576.ExtendValue(ratioDenominatorSquared),
 4031180            out Signed192 narrowRatioDenominatorSquared);
 4031181        Signed576 left = MultiplySigned576(
 4031182            numerator,
 4031183            narrowRatioDenominatorSquared);
 4031184        Signed576 right = MultiplySigned576(
 4031185            MultiplySigned320(ratioNumerator, ratioNumerator),
 4031186            denominator);
 4031187        return CompareNonNegative(left, right);
 1188    }
 1189
 1190    private static int CompareRadicalCrossTerm(
 1191        Signed576 firstNumerator,
 1192        Signed192 firstDenominator,
 1193        Signed576 secondNumerator,
 1194        Signed192 secondDenominator,
 1195        Signed192 ratioDenominator,
 1196        Signed576 remainder)
 1197    {
 2401198        Span<ulong> firstNumeratorWords = stackalloc ulong[9];
 2401199        Span<ulong> secondNumeratorWords = stackalloc ulong[9];
 2401200        Span<ulong> firstDenominatorWords = stackalloc ulong[3];
 2401201        Span<ulong> secondDenominatorWords = stackalloc ulong[3];
 2401202        Span<ulong> ratioDenominatorWords = stackalloc ulong[3];
 2401203        Span<ulong> remainderWords = stackalloc ulong[9];
 2401204        GetMagnitude(firstNumerator, firstNumeratorWords);
 2401205        GetMagnitude(secondNumerator, secondNumeratorWords);
 2401206        GetMagnitude(
 2401207            firstDenominator,
 2401208            out firstDenominatorWords[2],
 2401209            out firstDenominatorWords[1],
 2401210            out firstDenominatorWords[0]);
 2401211        GetMagnitude(
 2401212            secondDenominator,
 2401213            out secondDenominatorWords[2],
 2401214            out secondDenominatorWords[1],
 2401215            out secondDenominatorWords[0]);
 2401216        GetMagnitude(
 2401217            ratioDenominator,
 2401218            out ratioDenominatorWords[2],
 2401219            out ratioDenominatorWords[1],
 2401220            out ratioDenominatorWords[0]);
 2401221        GetMagnitude(remainder, remainderWords);
 1222
 2401223        Span<ulong> numeratorProduct = stackalloc ulong[18];
 2401224        Span<ulong> ratioSquared = stackalloc ulong[6];
 2401225        Span<ulong> ratioFourth = stackalloc ulong[12];
 2401226        Span<ulong> denominatorProduct = stackalloc ulong[6];
 2401227        Span<ulong> numeratorAndRatio = stackalloc ulong[30];
 2401228        Span<ulong> left = stackalloc ulong[36];
 2401229        Span<ulong> right = stackalloc ulong[36];
 2401230        MultiplyMagnitudes(
 2401231            firstNumeratorWords,
 2401232            secondNumeratorWords,
 2401233            numeratorProduct);
 2401234        MultiplyMagnitudes(
 2401235            ratioDenominatorWords,
 2401236            ratioDenominatorWords,
 2401237            ratioSquared);
 2401238        MultiplyMagnitudes(ratioSquared, ratioSquared, ratioFourth);
 2401239        MultiplyMagnitudes(
 2401240            firstDenominatorWords,
 2401241            secondDenominatorWords,
 2401242            denominatorProduct);
 2401243        MultiplyMagnitudes(
 2401244            numeratorProduct,
 2401245            ratioFourth,
 2401246            numeratorAndRatio);
 2401247        MultiplyMagnitudes(
 2401248            numeratorAndRatio,
 2401249            denominatorProduct,
 2401250            left);
 2401251        ShiftLeftMagnitude(left, 2);
 2401252        MultiplyMagnitudes(remainderWords, remainderWords, right);
 1253
 2401254        int comparison = CompareMagnitudeEqualLength(left, right);
 2401255        return comparison == 0 ? 0 : comparison > 0 ? 1 : -1;
 1256    }
 1257
 1258    #endregion
 1259}

/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    {
 129509727        if (leftHigh != rightHigh)
 6532528            return leftHigh < rightHigh ? -1 : 1;
 122977229        if (leftMiddle != rightMiddle)
 85896330            return leftMiddle < rightMiddle ? -1 : 1;
 37080931        if (leftLow != rightLow)
 34529032            return leftLow < rightLow ? -1 : 1;
 2551933        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    {
 4357749        if (leftWord4 != rightWord4)
 1040950            return leftWord4 < rightWord4 ? -1 : 1;
 3316851        if (leftWord3 != rightWord3)
 1233852            return leftWord3 < rightWord3 ? -1 : 1;
 2083053        if (leftWord2 != rightWord2)
 920154            return leftWord2 < rightWord2 ? -1 : 1;
 1162955        if (leftWord1 != rightWord1)
 799556            return leftWord1 < rightWord1 ? -1 : 1;
 363457        if (leftWord0 != rightWord0)
 162158            return leftWord0 < rightWord0 ? -1 : 1;
 201359        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    {
 55824768        GetMagnitude(value, out ulong high, out middle, out low);
 55824769        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    {
 27712680        MultiplyUnsigned96(
 27712681            (uint)leftMiddle,
 27712682            leftLow,
 27712683            (uint)rightMiddle,
 27712684            rightLow,
 27712685            out _,
 27712686            out ulong word2,
 27712687            out ulong word1,
 27712688            out ulong word0);
 89
 27712690        if (negative)
 91        {
 4949592            word0 = unchecked(~word0 + 1UL);
 4949593            word1 = unchecked(~word1 + (word0 == 0UL ? 1UL : 0UL));
 4949594            word2 = unchecked(~word2 + (word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 95        }
 96
 27712697        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    {
 22064576111        if ((leftHigh | rightHigh) <= uint.MaxValue)
 112        {
 17166464113            MultiplyUnsigned96(
 17166464114                (uint)leftHigh,
 17166464115                leftLow,
 17166464116                (uint)rightHigh,
 17166464117                rightLow,
 17166464118                out word3,
 17166464119                out word2,
 17166464120                out word1,
 17166464121                out word0);
 17166464122            return;
 123        }
 124
 4898112125        Fixed64.Multiply64To128(leftLow, rightLow, out ulong lowHigh, out word0);
 4898112126        Fixed64.Multiply64To128(leftLow, rightHigh, out ulong leftCrossHigh, out ulong leftCrossLow);
 4898112127        Fixed64.Multiply64To128(leftHigh, rightLow, out ulong rightCrossHigh, out ulong rightCrossLow);
 4898112128        Fixed64.Multiply64To128(leftHigh, rightHigh, out word3, out ulong highLow);
 129
 4898112130        word1 = lowHigh;
 4898112131        ulong carry = 0UL;
 4898112132        AccumulateWord(ref word1, leftCrossLow, ref carry);
 4898112133        AccumulateWord(ref word1, rightCrossLow, ref carry);
 134
 4898112135        word2 = leftCrossHigh;
 4898112136        ulong highCarry = 0UL;
 4898112137        AccumulateWord(ref word2, rightCrossHigh, ref highCarry);
 4898112138        AccumulateWord(ref word2, highLow, ref highCarry);
 4898112139        AccumulateWord(ref word2, carry, ref highCarry);
 4898112140        word3 = unchecked(word3 + highCarry);
 4898112141    }
 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    {
 17443590154        Fixed64.Multiply64To128(leftLow, rightLow, out ulong lowHigh, out word0);
 17443590155        Multiply64By32(leftLow, rightHigh, out ulong leftCrossHigh, out ulong leftCrossLow);
 17443590156        Multiply64By32(rightLow, leftHigh, out ulong rightCrossHigh, out ulong rightCrossLow);
 157
 17443590158        word1 = lowHigh;
 17443590159        ulong carry = 0UL;
 17443590160        AccumulateWord(ref word1, leftCrossLow, ref carry);
 17443590161        AccumulateWord(ref word1, rightCrossLow, ref carry);
 162
 17443590163        word2 = leftCrossHigh;
 17443590164        ulong highCarry = 0UL;
 17443590165        AccumulateWord(ref word2, rightCrossHigh, ref highCarry);
 17443590166        AccumulateWord(ref word2, (ulong)leftHigh * rightHigh, ref highCarry);
 17443590167        AccumulateWord(ref word2, carry, ref highCarry);
 17443590168        word3 = highCarry;
 17443590169    }
 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    {
 34887180178        ulong lowProduct = (uint)left * (ulong)right;
 34887180179        ulong highProduct = (left >> 32) * right;
 34887180180        ulong middle = (lowProduct >> 32) + (uint)highProduct;
 34887180181        low = (lowProduct & uint.MaxValue) | (middle << 32);
 34887180182        high = (highProduct >> 32) + (middle >> 32);
 34887180183    }
 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    {
 3379042193        Fixed64.Multiply64To128(left, right, out ulong high, out ulong low);
 3379042194        ulong previous = word2;
 3379042195        word2 = unchecked(word2 + low);
 3379042196        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.
 3379042200        ulong highWithCarry = high + carry;
 3379042201        previous = word3;
 3379042202        word3 = unchecked(word3 + highWithCarry);
 3379042203        if (word3 < previous)
 408204            word4++;
 3379042205    }
 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    {
 3379042214        Fixed64.Multiply64To128(left, right, out ulong high, out ulong low);
 3379042215        ulong previous = word3;
 3379042216        word3 = unchecked(word3 + low);
 3379042217        word4 = unchecked(word4 + high + (word3 < previous ? 1UL : 0UL));
 3379042218    }
 219
 220    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 221    internal static void AccumulateWord(ref ulong word, ulong add, ref ulong carry)
 222    {
 111708510223        ulong previous = word;
 111708510224        word = unchecked(word + add);
 111708510225        if (word < previous)
 327605226            carry++;
 111708510227    }
 228
 229    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 230    internal static ulong SubtractWord(ulong value, ulong subtract, ref ulong borrow)
 231    {
 415954348232        ulong subtrahend = unchecked(subtract + borrow);
 415954348233        ulong overflow = subtrahend < subtract ? 1UL : 0UL;
 415954348234        ulong result = unchecked(value - subtrahend);
 415954348235        borrow = overflow | (value < subtrahend ? 1UL : 0UL);
 415954348236        return result;
 237    }
 238
 239    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 240    internal static ulong AddSignedWord(ulong left, ulong right, ref ulong carry)
 241    {
 187616392242        ulong sum = unchecked(left + right);
 187616392243        ulong result = unchecked(sum + carry);
 187616392244        carry = sum < left || result < sum ? 1UL : 0UL;
 187616392245        return result;
 246    }
 247
 248    internal static bool IsZeroMagnitude(ReadOnlySpan<ulong> value)
 249    {
 1995234250        for (int index = 0; index < value.Length; index++)
 251        {
 990867252            if (value[index] != 0UL)
 234122253                return false;
 254        }
 255
 6750256        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    {
 3383276        int termCount = signs.Length;
 3383277        Span<ulong> uniqueRadicands = stackalloc ulong[
 3383278            MaximumLinearRadicalCount * radicandWordCount];
 3383279        Span<int> coefficients =
 3383280            stackalloc int[MaximumLinearRadicalCount];
 3383281        uniqueRadicands.Clear();
 3383282        coefficients.Clear();
 3383283        int uniqueCount = 0;
 27458284        for (int termIndex = 0; termIndex < termCount; termIndex++)
 285        {
 10346286            int sign = signs[termIndex];
 10346287            ReadOnlySpan<ulong> radicand = radicands.Slice(
 10346288                termIndex * radicandWordCount,
 10346289                radicandWordCount);
 10346290            if (sign == 0 || IsZeroMagnitude(radicand))
 291                continue;
 292
 7487293            int existingIndex = -1;
 7487294            for (int candidateIndex = 0;
 10379295                 candidateIndex < uniqueCount;
 2892296                 candidateIndex++)
 297            {
 5098298                if (CompareMagnitudeEqualLength(
 5098299                        radicand,
 5098300                        uniqueRadicands.Slice(
 5098301                            candidateIndex * radicandWordCount,
 5098302                            radicandWordCount)) == 0)
 303                {
 2206304                    existingIndex = candidateIndex;
 2206305                    break;
 306                }
 307            }
 308
 7487309            if (existingIndex >= 0)
 310            {
 2206311                coefficients[existingIndex] += sign;
 2206312                continue;
 313            }
 314
 5281315            radicand.CopyTo(uniqueRadicands.Slice(
 5281316                uniqueCount * radicandWordCount,
 5281317                radicandWordCount));
 5281318            coefficients[uniqueCount] = sign;
 5281319            uniqueCount++;
 320        }
 321
 3383322        int compactedCount = 0;
 17328323        for (int index = 0; index < uniqueCount; index++)
 324        {
 5281325            int coefficient = coefficients[index];
 5281326            if (coefficient == 0)
 327                continue;
 5069328            if (compactedCount != index)
 329            {
 85330                uniqueRadicands.Slice(
 85331                        index * radicandWordCount,
 85332                        radicandWordCount)
 85333                    .CopyTo(uniqueRadicands.Slice(
 85334                        compactedCount * radicandWordCount,
 85335                        radicandWordCount));
 336            }
 5069337            coefficients[compactedCount] = coefficient;
 5069338            compactedCount++;
 339        }
 3383340        uniqueCount = compactedCount;
 3383341        if (uniqueCount == 0)
 129342            return 0;
 343
 3254344        int basisCount = 1 << uniqueCount;
 3254345        Span<ulong> basisMagnitudes =
 3254346            stackalloc ulong[basisCount];
 3254347        Span<int> basisSigns =
 3254348            stackalloc int[basisCount];
 3254349        basisMagnitudes.Clear();
 3254350        basisSigns.Clear();
 16646351        for (int index = 0; index < uniqueCount; index++)
 352        {
 5069353            int coefficient = coefficients[index];
 5069354            int basisIndex = 1 << index;
 5069355            basisMagnitudes[basisIndex] =
 5069356                unchecked((ulong)Math.Abs(coefficient));
 5069357            basisSigns[basisIndex] = Math.Sign(coefficient);
 358        }
 359
 3254360        return GetMultiquadraticSign(
 3254361            basisMagnitudes,
 3254362            basisSigns,
 3254363            coefficientWordCount: 1,
 3254364            uniqueRadicands,
 3254365            radicandWordCount,
 3254366            uniqueCount,
 3254367            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    {
 35947379        if (radicalCount == 0)
 20668380            return coefficientSigns[0];
 381
 15279382        int halfBasisCount = 1 << (radicalCount - 1);
 15279383        int halfWordCount =
 15279384            halfBasisCount * coefficientWordCount;
 15279385        int firstSign = GetMultiquadraticSign(
 15279386            coefficientMagnitudes.Slice(0, halfWordCount),
 15279387            coefficientSigns.Slice(0, halfBasisCount),
 15279388            coefficientWordCount,
 15279389            radicands,
 15279390            radicandWordCount,
 15279391            radicalCount - 1,
 15279392            totalRadicalCount);
 15279393        int secondSign = GetMultiquadraticSign(
 15279394            coefficientMagnitudes.Slice(
 15279395                halfWordCount,
 15279396                halfWordCount),
 15279397            coefficientSigns.Slice(
 15279398                halfBasisCount,
 15279399                halfBasisCount),
 15279400            coefficientWordCount,
 15279401            radicands,
 15279402            radicandWordCount,
 15279403            radicalCount - 1,
 15279404            totalRadicalCount);
 15279405        if (firstSign == 0)
 6857406            return secondSign;
 8422407        if (secondSign == 0 || firstSign == secondSign)
 6287408            return firstSign;
 409
 2135410        int eliminatedCount =
 2135411            totalRadicalCount - radicalCount + 1;
 2135412        int maximumRadicandDegree =
 2135413            1 << (eliminatedCount - 1);
 2135414        int nextCoefficientWordCount =
 2135415            maximumRadicandDegree * radicandWordCount
 2135416            + (maximumRadicandDegree << 2)
 2135417            + 1;
 2135418        Span<ulong> differenceMagnitudes = stackalloc ulong[
 2135419            halfBasisCount * nextCoefficientWordCount];
 2135420        Span<int> differenceSigns =
 2135421            stackalloc int[halfBasisCount];
 2135422        differenceMagnitudes.Clear();
 2135423        differenceSigns.Clear();
 2135424        BuildMultiquadraticSquaredDifference(
 2135425            coefficientMagnitudes.Slice(0, halfWordCount),
 2135426            coefficientSigns.Slice(0, halfBasisCount),
 2135427            coefficientMagnitudes.Slice(
 2135428                halfWordCount,
 2135429                halfWordCount),
 2135430            coefficientSigns.Slice(
 2135431                halfBasisCount,
 2135432                halfBasisCount),
 2135433            coefficientWordCount,
 2135434            radicands,
 2135435            radicandWordCount,
 2135436            radicalCount,
 2135437            differenceMagnitudes,
 2135438            differenceSigns,
 2135439            nextCoefficientWordCount);
 2135440        int squaredDifferenceSign = GetMultiquadraticSign(
 2135441            differenceMagnitudes,
 2135442            differenceSigns,
 2135443            nextCoefficientWordCount,
 2135444            radicands,
 2135445            radicandWordCount,
 2135446            radicalCount - 1,
 2135447            totalRadicalCount);
 2135448        if (squaredDifferenceSign == 0)
 174449            return 0;
 1961450        return squaredDifferenceSign > 0
 1961451            ? firstSign
 1961452            : 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    {
 2135468        AddMultiquadraticSquare(
 2135469            firstMagnitudes,
 2135470            firstSigns,
 2135471            coefficientWordCount,
 2135472            radicands,
 2135473            radicandWordCount,
 2135474            radicalCount - 1,
 2135475            extraRadicandIndex: -1,
 2135476            resultMagnitudes,
 2135477            resultSigns,
 2135478            resultWordCount,
 2135479            resultSign: 1);
 2135480        AddMultiquadraticSquare(
 2135481            secondMagnitudes,
 2135482            secondSigns,
 2135483            coefficientWordCount,
 2135484            radicands,
 2135485            radicandWordCount,
 2135486            radicalCount - 1,
 2135487            extraRadicandIndex: radicalCount - 1,
 2135488            resultMagnitudes,
 2135489            resultSigns,
 2135490            resultWordCount,
 2135491            resultSign: -1);
 2135492    }
 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    {
 4270507        int basisCount = 1 << remainingRadicalCount;
 4270508        Span<ulong> firstProduct =
 4270509            stackalloc ulong[resultWordCount];
 4270510        Span<ulong> secondProduct =
 4270511            stackalloc ulong[resultWordCount];
 4270512        for (int firstIndex = 0;
 18406513             firstIndex < basisCount;
 14136514             firstIndex++)
 515        {
 14136516            int firstCoefficientSign =
 14136517                coefficientSigns[firstIndex];
 14136518            if (firstCoefficientSign == 0)
 519                continue;
 5469520            ReadOnlySpan<ulong> firstCoefficient =
 5469521                coefficientMagnitudes.Slice(
 5469522                    firstIndex * coefficientWordCount,
 5469523                    coefficientWordCount);
 5469524            for (int secondIndex = 0;
 29657525                 secondIndex < basisCount;
 24188526                 secondIndex++)
 527            {
 24188528                int secondCoefficientSign =
 24188529                    coefficientSigns[secondIndex];
 24188530                if (secondCoefficientSign == 0)
 531                    continue;
 9017532                ReadOnlySpan<ulong> secondCoefficient =
 9017533                    coefficientMagnitudes.Slice(
 9017534                        secondIndex * coefficientWordCount,
 9017535                        coefficientWordCount);
 9017536                MultiplyMagnitudes(
 9017537                    firstCoefficient,
 9017538                    secondCoefficient,
 9017539                    firstProduct);
 9017540                Span<ulong> product = firstProduct;
 9017541                Span<ulong> scratch = secondProduct;
 9017542                int commonRadicals =
 9017543                    firstIndex & secondIndex;
 9017544                for (int radicalIndex = 0;
 29301545                     radicalIndex < remainingRadicalCount;
 20284546                     radicalIndex++)
 547                {
 20284548                    if ((commonRadicals
 20284549                            & (1 << radicalIndex)) == 0)
 550                    {
 551                        continue;
 552                    }
 4006553                    MultiplyMagnitudes(
 4006554                        product,
 4006555                        radicands.Slice(
 4006556                            radicalIndex * radicandWordCount,
 4006557                            radicandWordCount),
 4006558                        scratch);
 4006559                    Span<ulong> temporary = product;
 4006560                    product = scratch;
 4006561                    scratch = temporary;
 562                }
 9017563                if (extraRadicandIndex >= 0)
 564                {
 2941565                    MultiplyMagnitudes(
 2941566                        product,
 2941567                        radicands.Slice(
 2941568                            extraRadicandIndex
 2941569                            * radicandWordCount,
 2941570                            radicandWordCount),
 2941571                        scratch);
 2941572                    Span<ulong> temporary = product;
 2941573                    product = scratch;
 2941574                    scratch = temporary;
 575                }
 576
 9017577                int targetIndex =
 9017578                    firstIndex ^ secondIndex;
 9017579                AddSignedMagnitude(
 9017580                    product,
 9017581                    firstCoefficientSign
 9017582                    * secondCoefficientSign
 9017583                    * resultSign,
 9017584                    resultMagnitudes.Slice(
 9017585                        targetIndex * resultWordCount,
 9017586                        resultWordCount),
 9017587                    ref resultSigns[targetIndex]);
 588            }
 589        }
 4270590    }
 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.
 9017601        if (resultSign == 0)
 602        {
 3423603            addend.CopyTo(result);
 3423604            resultSign = addendSign;
 3423605            return;
 606        }
 5594607        if (resultSign == addendSign)
 608        {
 2702609            AddMagnitudeInto(addend, result);
 2702610            return;
 611        }
 612
 2892613        int comparison =
 2892614            CompareMagnitudeEqualLength(result, addend);
 2892615        if (comparison == 0)
 616        {
 94617            result.Clear();
 94618            resultSign = 0;
 94619            return;
 620        }
 2798621        if (comparison > 0)
 622        {
 1647623            SubtractEqualMagnitudes(
 1647624                result,
 1647625                addend,
 1647626                result);
 1647627            return;
 628        }
 629
 1151630        Span<ulong> difference =
 1151631            stackalloc ulong[result.Length];
 1151632        SubtractEqualMagnitudes(
 1151633            addend,
 1151634            result,
 1151635            difference);
 1151636        difference.CopyTo(result);
 1151637        resultSign = addendSign;
 1151638    }
 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    {
 7563675821        int length = value.Length;
 150472758122        while (length > 0 && value[length - 1] == 0UL)
 142909082323            length--;
 7563675824        return length;
 25    }
 26
 27    internal static int GetMagnitudeBitLength(
 28        ReadOnlySpan<ulong> value)
 29    {
 72040230        int length = GetActiveMagnitudeLength(value);
 72040231        return length == 0
 72040232            ? 0
 72040233            : ((length - 1) << 6)
 72040234                + 64
 72040235                - 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    {
 3041668943        product.Clear();
 44        // High input limbs cannot contribute to retained low product limbs.
 45        // Factor out whole powers of 2^64 before convolution; the cleared
 46        // output prefix stays zero and both scans are bounded by output width.
 3041668947        left = left[..Math.Min(left.Length, product.Length)];
 3041668948        right = right[..Math.Min(right.Length, product.Length)];
 3041668949        int leftSkip = 0;
 39468177750        while (leftSkip < left.Length && left[leftSkip] == 0)
 36426508851            leftSkip++;
 3041668952        int rightSkip = 0;
 18997615553        while (rightSkip < right.Length && right[rightSkip] == 0)
 15955946654            rightSkip++;
 3041668955        if (leftSkip >= product.Length - rightSkip)
 335805456            return;
 2705863557        left = left[leftSkip..];
 2705863558        right = right[rightSkip..];
 2705863559        product = product[(leftSkip + rightSkip)..];
 2705863560        int leftLength = GetActiveMagnitudeLength(left);
 2705863561        int rightLength = GetActiveMagnitudeLength(right);
 2705863562        int retainedLeft = Math.Min(leftLength, product.Length);
 32695566463        for (int leftIndex = 0; leftIndex < retainedLeft; leftIndex++)
 64        {
 13641919765            ulong leftWord = left[leftIndex];
 13641919766            if (leftWord == 0UL)
 67                continue;
 68
 13442730369            ulong carry = 0;
 13442730370            int retainedRight = Math.Min(rightLength, product.Length - leftIndex);
 214748364771            for (int rightIndex = 0; rightIndex < retainedRight; rightIndex++)
 72            {
 214748364773                int productIndex = leftIndex + rightIndex;
 214748364774                ulong rightWord = right[rightIndex];
 214748364775                if (rightWord == 0)
 76                {
 77                    // A sparse zero limb still owns the preceding carry.
 78                    // Flush it once before skipping this multiplication.
 17661279                    AddWord(product, productIndex, carry);
 17661280                    carry = 0;
 17661281                    continue;
 82                }
 214748364783                Fixed64.Multiply64To128(
 214748364784                    leftWord,
 214748364785                    rightWord,
 214748364786                    out ulong high,
 214748364787                    out ulong low);
 214748364788                ulong sum = unchecked(low + product[productIndex]);
 214748364789                high += sum < low ? 1UL : 0UL;
 214748364790                ulong value = unchecked(sum + carry);
 214748364791                carry = high + (value < sum ? 1UL : 0UL);
 214748364792                product[productIndex] = value;
 93            }
 94            // One carry per row replaces two ripple additions per limb.
 95            // A limb product plus the old word and carry is at most 2^128-1,
 96            // so the next carry always fits. Preserve low-word truncation.
 13442730397            AddWord(product, leftIndex + retainedRight, carry);
 98        }
 2705863599    }
 100
 101    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 102    internal static void AddWord(
 103        Span<ulong> words,
 104        int index,
 105        ulong value)
 106    {
 248662379107        while (value != 0UL && index < words.Length)
 108        {
 110646327109            ulong previous = words[index];
 110646327110            words[index] = unchecked(previous + value);
 110646327111            value = words[index] < previous ? 1UL : 0UL;
 110646327112            index++;
 113        }
 138016052114    }
 115
 116    internal static void AddEqualMagnitudes(
 117        ReadOnlySpan<ulong> left,
 118        ReadOnlySpan<ulong> right,
 119        Span<ulong> result)
 120    {
 335833121        ulong carry = 0UL;
 30937418122        for (int index = 0; index < result.Length; index++)
 15132876123            result[index] =
 15132876124                AddSignedWord(left[index], right[index], ref carry);
 335833125    }
 126
 127    internal static void AddMagnitudeInto(
 128        ReadOnlySpan<ulong> addend,
 129        Span<ulong> result)
 130    {
 426700131        ulong carry = 0UL;
 33740022132        for (int index = 0; index < result.Length; index++)
 133        {
 16443311134            ulong value = index < addend.Length
 16443311135                ? addend[index]
 16443311136                : 0UL;
 16443311137            result[index] =
 16443311138                AddSignedWord(result[index], value, ref carry);
 139        }
 426700140    }
 141
 142    internal static void SubtractEqualMagnitudes(
 143        ReadOnlySpan<ulong> larger,
 144        ReadOnlySpan<ulong> smaller,
 145        Span<ulong> result)
 146    {
 1260623147        ulong borrow = 0UL;
 36556080148        for (int index = 0; index < result.Length; index++)
 17017417149            result[index] =
 17017417150                SubtractWord(larger[index], smaller[index], ref borrow);
 1260623151    }
 152
 153    internal static int CompareMagnitudeEqualLength(
 154        ReadOnlySpan<ulong> left,
 155        ReadOnlySpan<ulong> right)
 156    {
 46816570157        for (int index = left.Length - 1; index >= 0; index--)
 158        {
 23262991159            if (left[index] != right[index])
 4009393160                return left[index] < right[index] ? -1 : 1;
 161        }
 162
 145294163        return 0;
 164    }
 165
 166    /// <summary>
 167    /// Accumulates a signed magnitude shifted left by a nonnegative bit count.
 168    /// Source and destination are disjoint; the destination has proven room
 169    /// for the complete result. No shifted copy or subtraction buffer is made.
 170    /// </summary>
 171    internal static void AddShiftedSignedMagnitude(ReadOnlySpan<ulong> addend,
 172        int addendSign, int shift, Span<ulong> result, ref int resultSign)
 173    {
 26527473174        if (addendSign == 0)
 4058915175            return;
 22468558176        int wordShift = shift >> 6;
 22468558177        int bitShift = shift & 63;
 22468558178        if (resultSign == 0)
 179        {
 563900522180            for (int index = 0; index < result.Length; index++)
 274978551181                result[index] = GetShiftedMagnitudeWord(addend, index, wordShift, bitShift);
 6971710182            resultSign = addendSign;
 6971710183            return;
 184        }
 15496848185        if (resultSign == addendSign)
 186        {
 187            // Below the shift and beyond the active source, only a carry can
 188            // change the destination. Reuse the bounded carry owner rather
 189            // than scanning padded words; retain truncation at its edge.
 3357329190            int end = (int)Math.Min(result.Length,
 3357329191                (long)wordShift + GetActiveMagnitudeLength(addend) + (bitShift == 0 ? 0 : 1));
 3357329192            ulong carry = 0;
 70072780193            for (int index = wordShift; index < end; index++)
 31679061194                result[index] = AddSignedWord(result[index],
 31679061195                    GetShiftedMagnitudeWord(addend, index, wordShift, bitShift), ref carry);
 3357329196            AddWord(result, end, carry);
 3357329197            return;
 198        }
 199
 12139519200        int comparison = 0;
 330752036201        for (int index = result.Length - 1; index >= 0 && comparison == 0; index--)
 153236499202            comparison = result[index].CompareTo(GetShiftedMagnitudeWord(addend, index, wordShift, bitShift));
 12139519203        if (comparison == 0)
 204        {
 475316205            result.Clear();
 475316206            resultSign = 0;
 475316207            return;
 208        }
 11664203209        ulong borrow = 0;
 680592440210        for (int index = 0; index < result.Length; index++)
 211        {
 328632017212            ulong shifted = GetShiftedMagnitudeWord(addend, index, wordShift, bitShift);
 328632017213            result[index] = comparison > 0
 328632017214                ? SubtractWord(result[index], shifted, ref borrow)
 328632017215                : SubtractWord(shifted, result[index], ref borrow);
 216        }
 11664203217        if (comparison < 0)
 8418981218            resultSign = addendSign;
 11664203219    }
 220
 221    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 222    private static ulong GetShiftedMagnitudeWord(ReadOnlySpan<ulong> source,
 223        int index, int wordShift, int bitShift)
 224    {
 788526128225        int lowIndex = index - wordShift;
 788526128226        ulong low = (uint)lowIndex < (uint)source.Length ? source[lowIndex] : 0UL;
 788526128227        ulong high = bitShift != 0 && (uint)(lowIndex - 1) < (uint)source.Length
 788526128228            ? source[lowIndex - 1] >> (64 - bitShift) : 0UL;
 788526128229        return (low << bitShift) | high;
 230    }
 231}

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

#LineLine coverage
 1//=======================================================================
 2// WideArithmetic.MagnitudeDivision.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/// Unsigned Euclidean division and integer-content reduction using supplied
 14/// scratch. Inputs are little-endian magnitudes, without hidden allocation.
 15/// </content>
 16internal static partial class WideArithmetic
 17{
 18    /// <summary>
 19    /// Divides by a nonzero magnitude. The quotient may be omitted. Scratch
 20    /// requires numerator.Length + divisor.Length + 1 words and must be
 21    /// disjoint from all inputs/outputs. A supplied quotient needs at least
 22    /// numerator.Length words; remainder needs at least divisor.Length words.
 23    /// Outputs must not overlap each other or divisor, but either may replace
 24    /// numerator. Unused output words are cleared.
 25    /// </summary>
 26    internal static void DivideMagnitudes(ReadOnlySpan<ulong> numerator,
 27        ReadOnlySpan<ulong> divisor, Span<ulong> quotient, Span<ulong> remainder,
 28        Span<ulong> scratch)
 29    {
 324140830        int numeratorLength = GetActiveMagnitudeLength(numerator);
 324140831        int divisorLength = GetActiveMagnitudeLength(divisor);
 32        System.Diagnostics.Debug.Assert(divisorLength > 0);
 324140833        if (numeratorLength < divisorLength)
 34        {
 9274935            numerator[..numeratorLength].CopyTo(remainder);
 9274936            remainder[numeratorLength..].Clear();
 9274937            quotient.Clear();
 9274938            return;
 39        }
 40
 41        // Normalizing the high divisor bit bounds each trial quotient's
 42        // overestimate by two. One extra numerator word retains its carry.
 314865943        int shift = Fixed64.CountLeadingZeroes(divisor[divisorLength - 1]);
 314865944        Span<ulong> dividend = scratch[..(numeratorLength + 1)];
 314865945        Span<ulong> normalizedDivisor = scratch.Slice(numeratorLength + 1, divisorLength);
 314865946        ShiftMagnitudeForDivision(numerator[..numeratorLength], dividend, shift);
 314865947        ShiftMagnitudeForDivision(divisor[..divisorLength], normalizedDivisor, shift);
 314865948        quotient.Clear();
 314865949        ulong top = normalizedDivisor[divisorLength - 1];
 1736499250        for (int offset = numeratorLength - divisorLength; offset >= 0; offset--)
 51        {
 553383752            ulong high = dividend[offset + divisorLength];
 553383753            ulong low = dividend[offset + divisorLength - 1];
 54            ulong trial;
 55            ulong trialRemainder;
 56            bool remainderOverflow;
 553383757            if (high == top)
 58            {
 7359                trial = ulong.MaxValue;
 7360                trialRemainder = unchecked(low + top);
 7361                remainderOverflow = trialRemainder < low;
 62            }
 63            else
 64            {
 553376465                trial = Fixed64.Divide128By64(high, low, top, out trialRemainder);
 553376466                remainderOverflow = false;
 67            }
 68
 553383769            if (divisorLength > 1)
 70            {
 740891271                for (int correction = 0; correction < 2 && !remainderOverflow; correction++)
 72                {
 361570473                    Fixed64.Multiply64To128(trial, normalizedDivisor[divisorLength - 2],
 361570474                        out ulong productHigh, out ulong productLow);
 361570475                    if (productHigh < trialRemainder
 361570476                        || (productHigh == trialRemainder
 361570477                            && productLow <= dividend[offset + divisorLength - 2]))
 78                        break;
 26000479                    trial--;
 26000480                    ulong previous = trialRemainder;
 26000481                    trialRemainder = unchecked(trialRemainder + top);
 26000482                    remainderOverflow = trialRemainder < previous;
 83                }
 84            }
 85
 553383786            ulong carry = 0;
 18893422087            for (int index = 0; index < divisorLength; index++)
 88            {
 8893327389                Fixed64.Multiply64To128(trial, normalizedDivisor[index],
 8893327390                    out ulong productHigh, out ulong productLow);
 8893327391                ulong previous = productLow;
 8893327392                productLow = unchecked(productLow + carry);
 8893327393                carry = unchecked(productHigh + (productLow < previous ? 1UL : 0UL));
 8893327394                ulong value = dividend[offset + index];
 8893327395                dividend[offset + index] = unchecked(value - productLow);
 8893327396                if (value < productLow)
 3676664097                    carry++;
 98            }
 553383799            bool borrowed = dividend[offset + divisorLength] < carry;
 5533837100            dividend[offset + divisorLength] = unchecked(dividend[offset + divisorLength] - carry);
 5533837101            if (borrowed)
 102            {
 103                // The top-two-word test can leave one excess trial unit.
 104                // Add the divisor back; the quotient is now exact.
 52105                trial--;
 52106                carry = 0;
 2336107                for (int index = 0; index < divisorLength; index++)
 1116108                    dividend[offset + index] = AddSignedWord(dividend[offset + index],
 1116109                        normalizedDivisor[index], ref carry);
 52110                dividend[offset + divisorLength] = unchecked(dividend[offset + divisorLength] + carry);
 111            }
 5533837112            if (!quotient.IsEmpty)
 3509457113                quotient[offset] = trial;
 114        }
 115
 51209704116        for (int index = 0; index < divisorLength; index++)
 117        {
 22456193118            ulong upper = shift == 0 ? 0UL : dividend[index + 1] << (64 - shift);
 22456193119            remainder[index] = (dividend[index] >> shift) | upper;
 120        }
 3148659121        remainder[divisorLength..].Clear();
 3148659122    }
 123
 124    /// <summary>
 125    /// Replaces first with gcd(first, second), including gcd(0,0)=0.
 126    /// Both equal-width operands are scratch; they must not overlap.
 127    /// The supplied scratch requires twice that width plus one word.
 128    /// </summary>
 129    internal static void GetMagnitudeGreatestCommonDivisor(Span<ulong> first,
 130        Span<ulong> second, Span<ulong> scratch)
 131    {
 128837132        Span<ulong> left = first;
 128837133        Span<ulong> right = second;
 2017408134        while (GetActiveMagnitudeLength(right) != 0)
 135        {
 1888571136            DivideMagnitudes(left, right, Span<ulong>.Empty, left, scratch);
 1888571137            Span<ulong> swap = left;
 1888571138            left = right;
 1888571139            right = swap;
 140        }
 128837141        left.CopyTo(first);
 128837142    }
 143
 144    private static void ShiftMagnitudeForDivision(ReadOnlySpan<ulong> source,
 145        Span<ulong> destination, int shift)
 146    {
 6297318147        ulong carry = 0;
 107189764148        for (int index = 0; index < source.Length; index++)
 149        {
 47297564150            ulong value = source[index];
 47297564151            destination[index] = (value << shift) | carry;
 47297564152            carry = shift == 0 ? 0UL : value >> (64 - shift);
 153        }
 6297318154        if (destination.Length > source.Length)
 3148659155            destination[source.Length] = carry;
 6297318156    }
 157}

/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, integer content reduction, and square root extraction.
 15/// </content>
 16internal static partial class WideArithmetic
 17{
 18    /// <summary>Returns the low 192 bits of the signed integer multiplied by 2^32.</summary>
 19    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 20    internal static Signed192 ShiftLeftSigned192By32(Signed192 value) =>
 41097221        new((value.High << 32) | (value.Middle >> 32),
 41097222            (value.Middle << 32) | (value.Low >> 32), value.Low << 32);
 23
 24    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 25    internal static void GetMagnitude(
 26        Signed192 value,
 27        out ulong high,
 28        out ulong middle,
 29        out ulong low)
 30    {
 6284621831        high = value.High;
 6284621832        middle = value.Middle;
 6284621833        low = value.Low;
 6284621834        if (value.Sign >= 0)
 4973098535            return;
 36
 1311523337        low = unchecked(~low + 1UL);
 1311523338        middle = unchecked(~middle + (low == 0UL ? 1UL : 0UL));
 1311523339        high = unchecked(~high + (middle == 0UL && low == 0UL ? 1UL : 0UL));
 1311523340    }
 41
 42    /// <summary>
 43    /// Compares unsigned magnitudes of signed wide values.
 44    /// </summary>
 45    internal static int CompareMagnitude(Signed192 left, Signed192 right)
 46    {
 82554847        GetMagnitude(left, out ulong leftHigh, out ulong leftMiddle, out ulong leftLow);
 82554848        GetMagnitude(right, out ulong rightHigh, out ulong rightMiddle, out ulong rightLow);
 82554849        return CompareUnsigned(
 82554850            leftHigh,
 82554851            leftMiddle,
 82554852            leftLow,
 82554853            rightHigh,
 82554854            rightMiddle,
 82554855            rightLow);
 56    }
 57
 58    /// <summary>
 59    /// Returns whether a wide magnitude is at most a positive raw threshold
 60    /// shifted into the value's scale.
 61    /// </summary>
 62    internal static bool IsMagnitudeAtMost(Signed192 value, ulong rawThreshold, int leftShift)
 63    {
 6764        Signed192 threshold = new(
 6765            0UL,
 6766            rawThreshold >> (64 - leftShift),
 6767            rawThreshold << leftShift);
 6768        return CompareMagnitude(value, threshold) <= 0;
 69    }
 70
 71    /// <summary>
 72    /// Adds exact three-word values without scalar conversion.
 73    /// </summary>
 74    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 75    internal static Signed192 AddSigned192(Signed192 left, Signed192 right)
 76    {
 735505677        ulong low = unchecked(left.Low + right.Low);
 735505678        ulong carry = low < left.Low ? 1UL : 0UL;
 735505679        ulong middle = unchecked(left.Middle + right.Middle + carry);
 735505680        carry = middle < left.Middle || (carry != 0UL && middle == left.Middle) ? 1UL : 0UL;
 735505681        return new Signed192(unchecked(left.High + right.High + carry), middle, low);
 82    }
 83
 152407284    internal static Signed192 Double(Signed192 value) => AddSigned192(value, value);
 85
 86    /// <summary>
 87    /// Subtracts exact three-word values without scalar conversion.
 88    /// </summary>
 89    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 90    internal static Signed192 SubtractSigned192(Signed192 left, Signed192 right)
 91    {
 489502692        ulong borrow = 0UL;
 489502693        ulong low = SubtractWord(left.Low, right.Low, ref borrow);
 489502694        ulong middle = SubtractWord(left.Middle, right.Middle, ref borrow);
 489502695        return new Signed192(unchecked(left.High - right.High - borrow), middle, low);
 96    }
 97
 98    internal static Signed192 Difference(Fixed64 left, Fixed64 right) =>
 117645699        SubtractSigned192(Signed192.Signed(left.m_rawValue), Signed192.Signed(right.m_rawValue));
 100
 101    /// <summary>
 102    /// Returns the floor square root and exact remainder of a nonnegative five-word value.
 103    /// </summary>
 104    internal static Signed192 GetFloorSquareRoot(Signed320 value, out Signed192 remainder)
 105    {
 119946106        if (value.IsZero)
 107        {
 5359108            remainder = default;
 5359109            return default;
 110        }
 111
 114587112        if (value.Word4 == 0UL && value.Word3 == 0UL)
 111231113            return GetFloorSquareRoot192(value.Word2, value.Word1, value.Word0, out remainder);
 114
 3356115        int pairIndex = (GetBitLength(value.Word4, value.Word3, value.Word2, value.Word1, value.Word0) - 1) >> 1;
 3356116        ulong rootHigh = 0UL;
 3356117        ulong rootMiddle = 0UL;
 3356118        ulong rootLow = 0UL;
 3356119        ulong remainderHigh = 0UL;
 3356120        ulong remainderMiddle = 0UL;
 3356121        ulong remainderLow = 0UL;
 122
 765898123        for (; pairIndex >= 0; pairIndex--)
 124        {
 381271125            int pairShift = (pairIndex & 31) << 1;
 381271126            ulong pair = (pairIndex >> 5) switch
 381271127            {
 8934128                4 => (value.Word4 >> pairShift) & 3UL,
 50161129                3 => (value.Word3 >> pairShift) & 3UL,
 107392130                2 => (value.Word2 >> pairShift) & 3UL,
 107392131                1 => (value.Word1 >> pairShift) & 3UL,
 107392132                _ => (value.Word0 >> pairShift) & 3UL,
 381271133            };
 134
 381271135            remainderHigh = (remainderHigh << 2) | (remainderMiddle >> 62);
 381271136            remainderMiddle = (remainderMiddle << 2) | (remainderLow >> 62);
 381271137            remainderLow = (remainderLow << 2) | pair;
 381271138            rootHigh = (rootHigh << 1) | (rootMiddle >> 63);
 381271139            rootMiddle = (rootMiddle << 1) | (rootLow >> 63);
 381271140            rootLow <<= 1;
 141
 381271142            ulong candidateHigh = (rootHigh << 1) | (rootMiddle >> 63);
 381271143            ulong candidateMiddle = (rootMiddle << 1) | (rootLow >> 63);
 381271144            ulong candidateLow = (rootLow << 1) | 1UL;
 381271145            if (CompareUnsigned(
 381271146                remainderHigh,
 381271147                remainderMiddle,
 381271148                remainderLow,
 381271149                candidateHigh,
 381271150                candidateMiddle,
 381271151                candidateLow) < 0)
 152            {
 153                continue;
 154            }
 155
 81896156            SubtractUnsigned(
 81896157                ref remainderHigh,
 81896158                ref remainderMiddle,
 81896159                ref remainderLow,
 81896160                candidateHigh,
 81896161                candidateMiddle,
 81896162                candidateLow);
 163            // The preceding shift leaves rootLow even, so this increment cannot overflow.
 81896164            rootLow++;
 165        }
 166
 3356167        remainder = new Signed192(remainderHigh, remainderMiddle, remainderLow);
 3356168        return new Signed192(rootHigh, rootMiddle, rootLow);
 169    }
 170
 171    internal static Signed192 Scale(Fixed64 value) =>
 1418257172        Signed192.NarrowValue(
 1418257173            MultiplySigned192(
 1418257174                Signed192.Raw(value),
 1418257175                Signed192.One));
 176
 107241177    internal static Signed192 Negate(Signed192 value) => SubtractSigned192(default, value);
 178
 179    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 180    internal static Signed192 Absolute(Signed192 value)
 181    {
 1124182        if (value.Sign >= 0)
 1003183            return value;
 121184        return SubtractSigned192(default, value);
 185    }
 186
 187    /// <summary>
 188    /// Returns the nonnegative greatest common divisor, including gcd(0,0)=0.
 189    /// Both operand magnitudes must be less than 2^191.
 190    /// </summary>
 191    internal static Signed192 GetGreatestCommonDivisor(Signed192 first, Signed192 second)
 192    {
 45336193        if (first.Sign < 0) first = Negate(first);
 55577194        if (second.Sign < 0) second = Negate(second);
 50491195        if (first.IsZero) return second;
 44929196        if (second.IsZero) return first;
 197
 30293198        int firstShift = CountTrailingZeroes192(first);
 30293199        int secondShift = CountTrailingZeroes192(second);
 30293200        int commonShift = firstShift < secondShift ? firstShift : secondShift;
 30293201        first = ShiftRightMagnitude192(first, firstShift);
 30293202        second = ShiftRightMagnitude192(second, secondShift);
 114822203        while (true)
 204        {
 145115205            if (CompareMagnitude(first, second) > 0)
 42398206                (first, second) = (second, first);
 207            // Integer one is not Signed192.One, which is the Q32.32 unit.
 145115208            if ((first.High | first.Middle) == 0UL && first.Low == 1UL)
 24622209                return ShiftLeftMagnitude192(first, commonShift);
 120493210            second = SubtractSigned192(second, first);
 120493211            if (second.IsZero)
 5671212                return ShiftLeftMagnitude192(first, commonShift);
 114822213            second = ShiftRightMagnitude192(second, CountTrailingZeroes192(second));
 214        }
 215    }
 216
 217    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 218    private static int CountTrailingZeroes192(Signed192 value)
 219    {
 220        System.Diagnostics.Debug.Assert(!value.IsZero);
 242720221        ulong word = value.Low;
 242720222        int offset = 0;
 242720223        if (word == 0UL)
 224        {
 9169225            word = value.Middle;
 9169226            offset = 64;
 9541227            if (word == 0UL) { word = value.High; offset = 128; }
 228        }
 242720229        return offset + 63 - Fixed64.CountLeadingZeroes(word & unchecked(0UL - word));
 230    }
 231
 232    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 233    private static Signed192 ShiftRightMagnitude192(Signed192 value, int bits)
 234    {
 235        System.Diagnostics.Debug.Assert(bits >= 0 && bits < 192);
 236684236        if (bits >= 128) return new Signed192(0UL, 0UL, value.High >> (bits - 128));
 254274237        if (bits >= 64) { value = new Signed192(0UL, value.High, value.Middle); bits -= 64; }
 237965238        if (bits == 0) return value;
 234659239        return new Signed192(value.High >> bits,
 234659240            (value.Middle >> bits) | (value.High << (64 - bits)),
 234659241            (value.Low >> bits) | (value.Middle << (64 - bits)));
 242    }
 243
 244    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 245    private static Signed192 ShiftLeftMagnitude192(Signed192 value, int bits)
 246    {
 247        System.Diagnostics.Debug.Assert(bits >= 0 && bits < 192);
 30373248        if (bits >= 128) return new Signed192(value.Low << (bits - 128), 0UL, 0UL);
 30433249        if (bits >= 64) { value = new Signed192(value.Middle, value.Low, 0UL); bits -= 64; }
 30213250        ShiftLeft(value.High, value.Middle, value.Low, bits,
 30213251            out ulong high, out ulong middle, out ulong low);
 30213252        return new Signed192(high, middle, low);
 253    }
 254
 255    /// <summary>
 256    /// Divides a signed value exactly by a positive nonzero divisor.
 257    /// The value's magnitude must be less than 2^191 and divisibility is required.
 258    /// </summary>
 259    internal static Signed192 DivideExactSigned192(Signed192 value, Signed192 divisor)
 260    {
 261        System.Diagnostics.Debug.Assert(divisor.Sign > 0);
 88694262        if (value.IsZero || (divisor.High == 0UL && divisor.Middle == 0UL && divisor.Low == 1UL))
 21382263            return value;
 67312264        int sign = value.Sign;
 67312265        if (sign < 0)
 22651266            value = Negate(value);
 67312267        int divisorShift = CountTrailingZeroes192(divisor);
 67312268        if (GetBitLength(divisor.High, divisor.Middle, divisor.Low) == divisorShift + 1)
 269        {
 270            System.Diagnostics.Debug.Assert(CountTrailingZeroes192(value) >= divisorShift);
 61090271            Signed192 shifted = ShiftRightMagnitude192(value, divisorShift);
 61090272            return sign < 0 ? Negate(shifted) : shifted;
 273        }
 6222274        Signed192 quotient = default;
 6222275        Signed192 remainder = default;
 6222276        int bit = GetBitLength(value.High, value.Middle, value.Low);
 685238277        while (bit-- > 0)
 278        {
 679016279            ulong word = bit < 64 ? value.Low : bit < 128 ? value.Middle : value.High;
 280            // The next remainder is at most the consumed numerator prefix,
 281            // itself below 2^191. The shift therefore stays nonnegative even
 282            // for a divisor near the top of the admitted signed domain.
 679016283            remainder = Double(remainder);
 679016284            remainder = new Signed192(remainder.High, remainder.Middle,
 679016285                remainder.Low | ((word >> (bit & 63)) & 1UL));
 679016286            quotient = Double(quotient);
 679016287            if (CompareMagnitude(remainder, divisor) >= 0)
 288            {
 47039289                remainder = SubtractSigned192(remainder, divisor);
 47039290                quotient = new Signed192(quotient.High, quotient.Middle, quotient.Low | 1UL);
 291            }
 292        }
 293        System.Diagnostics.Debug.Assert(remainder.IsZero);
 6222294        return sign < 0 ? Negate(quotient) : quotient;
 295    }
 296
 297    /// <summary>
 298    /// Shifts a nonnegative three-word value into a 64-bit normalized prefix.
 299    /// </summary>
 300    /// <remarks>
 301    /// Triangle normalization calls this with 0 through 67 discarded bits,
 302    /// which guarantees that the returned prefix fits in 64 bits.
 303    /// </remarks>
 304    internal static ulong ShiftRightToUInt64(Signed192 value, int bits, out bool discarded)
 305    {
 11092306        GetMagnitude(value, out ulong high, out ulong middle, out ulong low);
 11092307        if (bits == 0)
 308        {
 151309            discarded = false;
 151310            return low;
 311        }
 312
 10941313        if (bits < 64)
 314        {
 10926315            discarded = (low & ((1UL << bits) - 1UL)) != 0UL;
 10926316            return (middle << (64 - bits)) | (low >> bits);
 317        }
 318
 15319        int upperShift = bits - 64;
 15320        discarded = low != 0UL
 15321            || (upperShift != 0 && (middle & ((1UL << upperShift) - 1UL)) != 0UL);
 15322        return upperShift == 0
 15323            ? middle
 15324            : (high << (64 - upperShift)) | (middle >> upperShift);
 325    }
 326
 327    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 328    private static Signed192 GetFloorSquareRoot192(
 329        ulong valueHigh,
 330        ulong valueMiddle,
 331        ulong valueLow,
 332        out Signed192 remainder)
 333    {
 111231334        int pairIndex = (GetBitLength(valueHigh, valueMiddle, valueLow) - 1) >> 1;
 111231335        ulong rootHigh = 0UL;
 111231336        ulong rootLow = 0UL;
 111231337        ulong remainderHigh = 0UL;
 111231338        ulong remainderLow = 0UL;
 339
 8186235340        for (; pairIndex >= 0; pairIndex--)
 341        {
 4037502342            int pairShift = (pairIndex & 31) << 1;
 4037502343            ulong pair = pairIndex >= 64
 4037502344                ? (valueHigh >> pairShift) & 3UL
 4037502345                : pairIndex >= 32
 4037502346                    ? (valueMiddle >> pairShift) & 3UL
 4037502347                    : (valueLow >> pairShift) & 3UL;
 348
 4037502349            remainderHigh = (remainderHigh << 2) | (remainderLow >> 62);
 4037502350            remainderLow = (remainderLow << 2) | pair;
 4037502351            rootHigh = (rootHigh << 1) | (rootLow >> 63);
 4037502352            rootLow <<= 1;
 353
 4037502354            ulong candidateHigh = (rootHigh << 1) | (rootLow >> 63);
 4037502355            ulong candidateLow = (rootLow << 1) | 1UL;
 4037502356            if (remainderHigh < candidateHigh
 4037502357                || (remainderHigh == candidateHigh && remainderLow < candidateLow))
 358            {
 359                continue;
 360            }
 361
 1670522362            ulong originalRemainderLow = remainderLow;
 1670522363            remainderLow -= candidateLow;
 1670522364            remainderHigh -= candidateHigh + (originalRemainderLow < candidateLow ? 1UL : 0UL);
 1670522365            rootLow++;
 366        }
 367
 111231368        remainder = new Signed192(0UL, remainderHigh, remainderLow);
 111231369        return new Signed192(0UL, rootHigh, rootLow);
 370    }
 371
 372    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 373    internal static void ShiftLeft(
 374        ulong high,
 375        ulong middle,
 376        ulong low,
 377        int bits,
 378        out ulong shiftedHigh,
 379        out ulong shiftedMiddle,
 380        out ulong shiftedLow)
 381    {
 31560382        if (bits == 0)
 383        {
 1169384            shiftedHigh = high;
 1169385            shiftedMiddle = middle;
 1169386            shiftedLow = low;
 1169387            return;
 388        }
 389
 30391390        shiftedHigh = (high << bits) | (middle >> (64 - bits));
 30391391        shiftedMiddle = (middle << bits) | (low >> (64 - bits));
 30391392        shiftedLow = low << bits;
 30391393    }
 394
 395    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 396    internal static void ShiftLeftOne(ref ulong high, ref ulong middle, ref ulong low)
 397    {
 78243398        high = (high << 1) | (middle >> 63);
 78243399        middle = (middle << 1) | (low >> 63);
 78243400        low <<= 1;
 78243401    }
 402
 403    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 404    internal static void ShiftRightOne(ref ulong high, ref ulong middle, ref ulong low)
 405    {
 3580406        low = (low >> 1) | (middle << 63);
 3580407        middle = (middle >> 1) | (high << 63);
 3580408        high >>= 1;
 3580409    }
 410
 411    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 412    internal static int GetBitLength(ulong high, ulong middle, ulong low)
 413    {
 212523414        if (high != 0UL)
 17899415            return 192 - Fixed64.CountLeadingZeroes(high);
 194624416        if (middle != 0UL)
 33431417            return 128 - Fixed64.CountLeadingZeroes(middle);
 161193418        return 64 - Fixed64.CountLeadingZeroes(low);
 419    }
 420
 421    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 422    internal static void SubtractUnsigned(
 423        ref ulong high,
 424        ref ulong middle,
 425        ref ulong low,
 426        ulong subtractHigh,
 427        ulong subtractMiddle,
 428        ulong subtractLow)
 429    {
 104866430        ulong originalLow = low;
 104866431        low -= subtractLow;
 104866432        ulong borrow = originalLow < subtractLow ? 1UL : 0UL;
 433
 104866434        ulong middleSubtrahend = subtractMiddle + borrow;
 104866435        ulong middleOverflow = middleSubtrahend < subtractMiddle ? 1UL : 0UL;
 104866436        ulong originalMiddle = middle;
 104866437        middle -= middleSubtrahend;
 104866438        borrow = middleOverflow | (originalMiddle < middleSubtrahend ? 1UL : 0UL);
 104866439        high -= subtractHigh + borrow;
 104866440    }
 441}

/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    /// <summary>Returns the nonnegative gcd of operands whose magnitudes are below 2^319.</summary>
 20    internal static Signed320 GetGreatestCommonDivisor(Signed320 first, Signed320 second)
 21    {
 1905022        Span<ulong> a = stackalloc ulong[5], b = stackalloc ulong[5], scratch = stackalloc ulong[11];
 635023        GetMagnitude(first, out a[4], out a[3], out a[2], out a[1], out a[0]);
 635024        GetMagnitude(second, out b[4], out b[3], out b[2], out b[1], out b[0]);
 635025        GetMagnitudeGreatestCommonDivisor(a, b, scratch);
 635026        return new Signed320(a[4], a[3], a[2], a[1], a[0]);
 27    }
 28
 29    /// <summary>Divides a signed value exactly by a positive divisor; both magnitudes are below 2^319.</summary>
 30    internal static Signed320 DivideExactSigned320(Signed320 value, Signed320 divisor)
 31    {
 479659232        Span<ulong> n = stackalloc ulong[5], d = stackalloc ulong[5], remainder = stackalloc ulong[5], scratch = stackal
 119914833        GetMagnitude(value, out n[4], out n[3], out n[2], out n[1], out n[0]);
 119914834        GetMagnitude(divisor, out d[4], out d[3], out d[2], out d[1], out d[0]);
 119914835        DivideMagnitudes(n, d, n, remainder, scratch);
 36        System.Diagnostics.Debug.Assert(GetActiveMagnitudeLength(remainder) == 0);
 119914837        var result = new Signed320(n[4], n[3], n[2], n[1], n[0]);
 119914838        return value.Sign < 0 ? Negate(result) : result;
 39    }
 40
 41    /// <summary>
 42    /// Divides by 2^64 toward zero. The caller proves that the input magnitude
 43    /// is below 2^255, so the quotient fits the signed 192-bit domain.
 44    /// </summary>
 45    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 46    internal static Signed192 TruncateSigned320By64(Signed320 value)
 47    {
 1850248        GetMagnitude(value, out ulong word4, out ulong word3, out ulong word2, out ulong word1, out _);
 49#if DEBUG
 50        System.Diagnostics.Debug.Assert(word4 == 0 && (word3 & (1UL << 63)) == 0);
 51#endif
 1850252        Signed192 result = new(word3, word2, word1);
 1850253        return value.Sign < 0 ? Negate(result) : result;
 54    }
 55
 56    /// <summary>
 57    /// Divides a nonempty collection containing at least one nonzero value by
 58    /// its common positive magnitude gcd, preserving every sign and ratio.
 59    /// </summary>
 60    internal static void ReduceCommonScale(Span<Signed320> values)
 61    {
 1085762        Span<ulong> content = stackalloc ulong[5];
 1085763        Span<ulong> other = stackalloc ulong[5];
 1085764        Span<ulong> division = stackalloc ulong[11];
 1085765        GetMagnitude(values[0], out content[4], out content[3], out content[2],
 1085766            out content[1], out content[0]);
 10948067        for (int index = 1; index < values.Length; index++)
 68        {
 4501269            GetMagnitude(values[index], out other[4], out other[3], out other[2],
 4501270                out other[1], out other[0]);
 4501271            GetMagnitudeGreatestCommonDivisor(content, other, division);
 4501272            if (content[0] == 1 && GetActiveMagnitudeLength(content) == 1)
 112973                return;
 74        }
 972875        Span<ulong> remainder = stackalloc ulong[5];
 12632676        for (int index = 0; index < values.Length; index++)
 77        {
 5343578            int sign = values[index].Sign;
 5343579            GetMagnitude(values[index], out other[4], out other[3], out other[2],
 5343580                out other[1], out other[0]);
 5343581            DivideMagnitudes(other, content, other, remainder, division);
 5343582            var value = new Signed320(other[4], other[3], other[2], other[1], other[0]);
 5343583            values[index] = sign < 0 ? Negate(value) : value;
 84        }
 972885    }
 86
 87    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 88    internal static void GetMagnitude(
 89        Signed320 value,
 90        out ulong word4,
 91        out ulong word3,
 92        out ulong word2,
 93        out ulong word1,
 94        out ulong word0)
 95    {
 538169896        word4 = value.Word4;
 538169897        word3 = value.Word3;
 538169898        word2 = value.Word2;
 538169899        word1 = value.Word1;
 5381698100        word0 = value.Word0;
 5381698101        if (value.Sign >= 0)
 4213841102            return;
 103
 1167857104        word0 = unchecked(~word0 + 1UL);
 1167857105        word1 = unchecked(~word1 + (word0 == 0UL ? 1UL : 0UL));
 1167857106        word2 = unchecked(~word2 + (word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 1167857107        word3 = unchecked(~word3 + (word2 == 0UL && word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 1167857108        word4 = unchecked(~word4 + (word3 == 0UL && word2 == 0UL && word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 1167857109    }
 110
 111    /// <summary>
 112    /// Returns the exact signed result of <c>(first * second) - (third * fourth)</c>.
 113    /// </summary>
 114    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 115    internal static Signed320 MultiplySubtract(
 116        Signed192 first,
 117        Signed192 second,
 118        Signed192 third,
 119        Signed192 fourth)
 120    {
 142378121        if (TryGetSigned95Magnitude(first, out ulong firstMiddle, out ulong firstLow)
 142378122            && TryGetSigned95Magnitude(second, out ulong secondMiddle, out ulong secondLow)
 142378123            && TryGetSigned95Magnitude(third, out ulong thirdMiddle, out ulong thirdLow)
 142378124            && TryGetSigned95Magnitude(fourth, out ulong fourthMiddle, out ulong fourthLow))
 125        {
 138563126            Signed192 narrowFirstProduct = MultiplySigned95(
 138563127                firstMiddle,
 138563128                firstLow,
 138563129                secondMiddle,
 138563130                secondLow,
 138563131                first.Sign * second.Sign < 0);
 138563132            Signed192 narrowSecondProduct = MultiplySigned95(
 138563133                thirdMiddle,
 138563134                thirdLow,
 138563135                fourthMiddle,
 138563136                fourthLow,
 138563137                third.Sign * fourth.Sign < 0);
 138563138            return Signed320.ExtendValue(SubtractSigned192(narrowFirstProduct, narrowSecondProduct));
 139        }
 140
 3815141        Signed320 firstProduct = MultiplySigned192(first, second);
 3815142        Signed320 secondProduct = MultiplySigned192(third, fourth);
 143
 3815144        ulong word0 = unchecked(firstProduct.Word0 - secondProduct.Word0);
 3815145        ulong borrow = firstProduct.Word0 < secondProduct.Word0 ? 1UL : 0UL;
 3815146        ulong word1 = SubtractWord(firstProduct.Word1, secondProduct.Word1, ref borrow);
 3815147        ulong word2 = SubtractWord(firstProduct.Word2, secondProduct.Word2, ref borrow);
 3815148        ulong word3 = SubtractWord(firstProduct.Word3, secondProduct.Word3, ref borrow);
 3815149        ulong word4 = unchecked(firstProduct.Word4 - secondProduct.Word4 - borrow);
 3815150        return new Signed320(word4, word3, word2, word1, word0);
 151    }
 152
 153    /// <summary>
 154    /// Returns the signed sum of two <see cref="Signed192"/> products.
 155    /// </summary>
 156    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 157    internal static Signed320 AddProducts(
 158        Signed192 firstLeft,
 159        Signed192 firstRight,
 160        Signed192 secondLeft,
 161        Signed192 secondRight) =>
 459878162        AddSigned320(
 459878163            MultiplySigned192(firstLeft, firstRight),
 459878164            MultiplySigned192(secondLeft, secondRight));
 165
 166    /// <summary>
 167    /// Returns the signed sum of three <see cref="Signed192"/> products.
 168    /// </summary>
 169    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 170    internal static Signed320 AddProducts(
 171        Signed192 firstLeft,
 172        Signed192 firstRight,
 173        Signed192 secondLeft,
 174        Signed192 secondRight,
 175        Signed192 thirdLeft,
 176        Signed192 thirdRight) =>
 280069177        AddSigned320(
 280069178            AddProducts(
 280069179                firstLeft,
 280069180                firstRight,
 280069181                secondLeft,
 280069182                secondRight),
 280069183            MultiplySigned192(thirdLeft, thirdRight));
 184
 185    /// <summary>
 186    /// Returns the signed dot product of two three-component
 187    /// <see cref="Signed192"/> values.
 188    /// </summary>
 189    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 190    internal static Signed320 GetDotProduct3D(
 191        Signed192 leftX,
 192        Signed192 leftY,
 193        Signed192 leftZ,
 194        Signed192 rightX,
 195        Signed192 rightY,
 196        Signed192 rightZ) =>
 279858197        AddProducts(
 279858198            leftX,
 279858199            rightX,
 279858200            leftY,
 279858201            rightY,
 279858202            leftZ,
 279858203            rightZ);
 204
 205    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 206    internal static Signed320 AddSigned320(Signed320 left, Signed320 right)
 207    {
 8601820208        ulong word0 = unchecked(left.Word0 + right.Word0);
 8601820209        ulong carry = word0 < left.Word0 ? 1UL : 0UL;
 8601820210        ulong word1 = unchecked(left.Word1 + right.Word1 + carry);
 8601820211        carry = word1 < left.Word1 || (carry != 0UL && word1 == left.Word1) ? 1UL : 0UL;
 8601820212        ulong word2 = unchecked(left.Word2 + right.Word2 + carry);
 8601820213        carry = word2 < left.Word2 || (carry != 0UL && word2 == left.Word2) ? 1UL : 0UL;
 8601820214        ulong word3 = unchecked(left.Word3 + right.Word3 + carry);
 215        // The high bit of the standard carry expression includes the incoming carry encoded in word3.
 8601820216        carry = ((left.Word3 & right.Word3) | ((left.Word3 | right.Word3) & ~word3)) >> 63;
 8601820217        return new Signed320(unchecked(left.Word4 + right.Word4 + carry), word3, word2, word1, word0);
 218    }
 219
 220    /// <summary>
 221    /// Subtracts exact five-word values without scalar conversion.
 222    /// </summary>
 223    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 224    internal static Signed320 SubtractSigned320(Signed320 left, Signed320 right)
 225    {
 2960108226        ulong borrow = 0UL;
 2960108227        ulong word0 = SubtractWord(left.Word0, right.Word0, ref borrow);
 2960108228        ulong word1 = SubtractWord(left.Word1, right.Word1, ref borrow);
 2960108229        ulong word2 = SubtractWord(left.Word2, right.Word2, ref borrow);
 2960108230        ulong word3 = SubtractWord(left.Word3, right.Word3, ref borrow);
 2960108231        return new Signed320(unchecked(left.Word4 - right.Word4 - borrow), word3, word2, word1, word0);
 232    }
 233
 234    /// <summary>
 235    /// Compares unsigned magnitudes of signed five-word values.
 236    /// </summary>
 237    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 238    internal static int CompareMagnitude(Signed320 left, Signed320 right)
 239    {
 11905240        GetMagnitude(
 11905241            left,
 11905242            out ulong leftWord4,
 11905243            out ulong leftWord3,
 11905244            out ulong leftWord2,
 11905245            out ulong leftWord1,
 11905246            out ulong leftWord0);
 11905247        GetMagnitude(
 11905248            right,
 11905249            out ulong rightWord4,
 11905250            out ulong rightWord3,
 11905251            out ulong rightWord2,
 11905252            out ulong rightWord1,
 11905253            out ulong rightWord0);
 11905254        return CompareUnsigned(
 11905255            leftWord4,
 11905256            leftWord3,
 11905257            leftWord2,
 11905258            leftWord1,
 11905259            leftWord0,
 11905260            rightWord4,
 11905261            rightWord3,
 11905262            rightWord2,
 11905263            rightWord1,
 11905264            rightWord0);
 265    }
 266
 267    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 268    internal static Signed320 MultiplySigned192(Signed192 left, Signed192 right)
 269    {
 22064576270        GetMagnitude(left, out ulong leftHigh, out ulong leftMiddle, out ulong leftLow);
 22064576271        GetMagnitude(right, out ulong rightHigh, out ulong rightMiddle, out ulong rightLow);
 272
 22064576273        MultiplyUnsigned128(
 22064576274            leftMiddle,
 22064576275            leftLow,
 22064576276            rightMiddle,
 22064576277            rightLow,
 22064576278            out ulong word3,
 22064576279            out ulong word2,
 22064576280            out ulong word1,
 22064576281            out ulong word0);
 282
 22064576283        ulong word4 = 0UL;
 22064576284        if ((leftHigh | rightHigh) != 0UL)
 285        {
 1689521286            AddProductAt2(ref word4, ref word3, ref word2, leftLow, rightHigh);
 1689521287            AddProductAt2(ref word4, ref word3, ref word2, leftHigh, rightLow);
 1689521288            AddProductAt3(ref word4, ref word3, leftMiddle, rightHigh);
 1689521289            AddProductAt3(ref word4, ref word3, leftHigh, rightMiddle);
 1689521290            word4 = unchecked(word4 + (leftHigh * rightHigh));
 291        }
 292
 22064576293        if (left.Sign * right.Sign < 0)
 294        {
 4996116295            word0 = unchecked(~word0 + 1UL);
 4996116296            word1 = unchecked(~word1 + (word0 == 0UL ? 1UL : 0UL));
 4996116297            word2 = unchecked(~word2 + (word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 4996116298            word3 = unchecked(~word3 + (word2 == 0UL && word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 4996116299            word4 = unchecked(~word4 + (word3 == 0UL && word2 == 0UL && word1 == 0UL && word0 == 0UL ? 1UL : 0UL));
 300        }
 301
 22064576302        return new Signed320(word4, word3, word2, word1, word0);
 303    }
 304
 305    /// <summary>
 306    /// Compares a normalized component square with the squared midpoint between
 307    /// adjacent Q32.32 raw candidates.
 308    /// </summary>
 309    internal static int CompareNormalizedComponentToMidpoint(
 310        Signed320 componentSquare,
 311        Signed320 squaredMagnitude,
 312        ulong lowerCandidateRaw)
 313    {
 5548314        ulong doubledMidpoint = (lowerCandidateRaw << 1) + 1UL;
 5548315        Fixed64.Multiply64To128(
 5548316            doubledMidpoint,
 5548317            doubledMidpoint,
 5548318            out ulong multiplierHigh,
 5548319            out ulong multiplierLow);
 320
 5548321        if (Signed192.TryNarrowSigned(squaredMagnitude, out Signed192 narrowSquaredMagnitude))
 322        {
 5454323            Signed320 rightNarrow = MultiplySigned192(
 5454324                narrowSquaredMagnitude,
 5454325                new Signed192(0UL, multiplierHigh, multiplierLow));
 5454326            return CompareUnsigned(
 5454327                (componentSquare.Word3 << 2) | (componentSquare.Word2 >> 62),
 5454328                (componentSquare.Word2 << 2) | (componentSquare.Word1 >> 62),
 5454329                (componentSquare.Word1 << 2) | (componentSquare.Word0 >> 62),
 5454330                componentSquare.Word0 << 2,
 5454331                0UL,
 5454332                rightNarrow.Word4,
 5454333                rightNarrow.Word3,
 5454334                rightNarrow.Word2,
 5454335                rightNarrow.Word1,
 5454336                rightNarrow.Word0);
 337        }
 338
 94339        Span<ulong> left = stackalloc ulong[6];
 94340        left.Clear();
 94341        left[1] = componentSquare.Word0 << 2;
 94342        left[2] = (componentSquare.Word1 << 2) | (componentSquare.Word0 >> 62);
 94343        left[3] = (componentSquare.Word2 << 2) | (componentSquare.Word1 >> 62);
 94344        left[4] = (componentSquare.Word3 << 2) | (componentSquare.Word2 >> 62);
 94345        left[5] = (componentSquare.Word4 << 2) | (componentSquare.Word3 >> 62);
 94346        Span<ulong> right = stackalloc ulong[6];
 94347        right.Clear();
 94348        Span<ulong> magnitude = stackalloc ulong[5]
 94349        {
 94350            squaredMagnitude.Word0,
 94351            squaredMagnitude.Word1,
 94352            squaredMagnitude.Word2,
 94353            squaredMagnitude.Word3,
 94354            squaredMagnitude.Word4,
 94355        };
 356
 1128357        for (int index = 0; index < magnitude.Length; index++)
 358        {
 470359            Fixed64.Multiply64To128(magnitude[index], multiplierLow, out ulong high, out ulong low);
 470360            AddWord(right, index, low);
 470361            AddWord(right, index + 1, high);
 470362            if (multiplierHigh == 0UL)
 363                continue;
 364
 355365            Fixed64.Multiply64To128(magnitude[index], multiplierHigh, out high, out low);
 355366            AddWord(right, index + 1, low);
 355367            if (index + 2 < right.Length)
 284368                AddWord(right, index + 2, high);
 369        }
 370
 94371        return CompareMagnitudeEqualLength(left, right);
 372    }
 373
 374    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 375    internal static void ShiftLeft(
 376        ulong word4,
 377        ulong word3,
 378        ulong word2,
 379        ulong word1,
 380        ulong word0,
 381        int bits,
 382        out ulong shiftedWord4,
 383        out ulong shiftedWord3,
 384        out ulong shiftedWord2,
 385        out ulong shiftedWord1,
 386        out ulong shiftedWord0)
 387    {
 976388        if (bits == 0)
 389        {
 2390            shiftedWord4 = word4;
 2391            shiftedWord3 = word3;
 2392            shiftedWord2 = word2;
 2393            shiftedWord1 = word1;
 2394            shiftedWord0 = word0;
 2395            return;
 396        }
 397
 974398        shiftedWord4 = (word4 << bits) | (word3 >> (64 - bits));
 974399        shiftedWord3 = (word3 << bits) | (word2 >> (64 - bits));
 974400        shiftedWord2 = (word2 << bits) | (word1 >> (64 - bits));
 974401        shiftedWord1 = (word1 << bits) | (word0 >> (64 - bits));
 974402        shiftedWord0 = word0 << bits;
 974403    }
 404
 405    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 406    internal static void ShiftLeftOne(
 407        ref ulong word4,
 408        ref ulong word3,
 409        ref ulong word2,
 410        ref ulong word1,
 411        ref ulong word0)
 412    {
 22671413        word4 = (word4 << 1) | (word3 >> 63);
 22671414        word3 = (word3 << 1) | (word2 >> 63);
 22671415        word2 = (word2 << 1) | (word1 >> 63);
 22671416        word1 = (word1 << 1) | (word0 >> 63);
 22671417        word0 <<= 1;
 22671418    }
 419
 420    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 421    internal static void ShiftRightOne(
 422        ref ulong word4,
 423        ref ulong word3,
 424        ref ulong word2,
 425        ref ulong word1,
 426        ref ulong word0)
 427    {
 99428        word0 = (word0 >> 1) | (word1 << 63);
 99429        word1 = (word1 >> 1) | (word2 << 63);
 99430        word2 = (word2 >> 1) | (word3 << 63);
 99431        word3 = (word3 >> 1) | (word4 << 63);
 99432        word4 >>= 1;
 99433    }
 434
 435    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 436    internal static int GetBitLength(
 437        ulong word4,
 438        ulong word3,
 439        ulong word2,
 440        ulong word1,
 441        ulong word0)
 442    {
 4886443        if (word4 != 0UL)
 1301444            return 320 - Fixed64.CountLeadingZeroes(word4);
 3585445        if (word3 != 0UL)
 2269446            return 256 - Fixed64.CountLeadingZeroes(word3);
 1316447        if (word2 != 0UL)
 542448            return 192 - Fixed64.CountLeadingZeroes(word2);
 774449        if (word1 != 0UL)
 573450            return 128 - Fixed64.CountLeadingZeroes(word1);
 201451        return 64 - Fixed64.CountLeadingZeroes(word0);
 452    }
 453
 454    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 455    internal static void SubtractUnsigned(
 456        ref ulong word4,
 457        ref ulong word3,
 458        ref ulong word2,
 459        ref ulong word1,
 460        ref ulong word0,
 461        ulong subtractWord4,
 462        ulong subtractWord3,
 463        ulong subtractWord2,
 464        ulong subtractWord1,
 465        ulong subtractWord0)
 466    {
 10389467        ulong borrow = 0UL;
 10389468        word0 = SubtractWord(word0, subtractWord0, ref borrow);
 10389469        word1 = SubtractWord(word1, subtractWord1, ref borrow);
 10389470        word2 = SubtractWord(word2, subtractWord2, ref borrow);
 10389471        word3 = SubtractWord(word3, subtractWord3, ref borrow);
 10389472        word4 = unchecked(word4 - subtractWord4 - borrow);
 10389473    }
 474}

/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{
 8241219    internal static Signed576 Negate(Signed576 value) => SubtractSigned576(default, value);
 20    internal static Signed832 MultiplySigned576(Signed576 first, Signed576 second) =>
 3625021        MultiplySigned576ToSigned832(first, second);
 22    /// <summary>Removes common positive content without changing signs or exact ratios.</summary>
 23    internal static void ReduceCommonScale(Span<Signed576> values)
 24    {
 741425        Span<ulong> content = stackalloc ulong[9], other = stackalloc ulong[9],
 741426            division = stackalloc ulong[19], remainder = stackalloc ulong[9];
 370727        GetMagnitude(values[0], content);
 2105428        for (int index = 1; index < values.Length; index++)
 29        {
 755030            GetMagnitude(values[index], other);
 755031            GetMagnitudeGreatestCommonDivisor(content, other, division);
 828032            if (content[0] == 1 && GetActiveMagnitudeLength(content) == 1) return;
 33        }
 2472434        for (int index = 0; index < values.Length; index++)
 35        {
 938536            int sign = values[index].Sign;
 938537            GetMagnitude(values[index], other);
 938538            DivideMagnitudes(other, content, other, remainder, division);
 938539            Signed576 value = new(other[8], other[7], other[6], other[5], other[4],
 938540                other[3], other[2], other[1], other[0]);
 938541            values[index] = sign < 0 ? SubtractSigned576(default, value) : value;
 42        }
 297743    }
 44
 45    /// <summary>
 46    /// Divides signed integers, truncating toward zero. Throws for a zero
 47    /// denominator or a quotient outside the signed 192-bit domain.
 48    /// </summary>
 49    internal static Signed192 DivideSigned576ToSigned192(Signed576 numerator, Signed320 denominator)
 50    {
 16851        if (denominator.IsZero)
 1552            throw new DivideByZeroException();
 15353        if (numerator.IsZero)
 954            return default;
 55
 14456        Span<ulong> dividend = stackalloc ulong[9];
 14457        Span<ulong> divisor = stackalloc ulong[5];
 14458        Span<ulong> quotient = stackalloc ulong[9];
 14459        Span<ulong> remainder = stackalloc ulong[5];
 14460        Span<ulong> scratch = stackalloc ulong[15];
 14461        GetMagnitude(numerator, dividend);
 14462        GetMagnitude(denominator, out divisor[4], out divisor[3], out divisor[2], out divisor[1], out divisor[0]);
 14463        DivideMagnitudes(dividend, divisor, quotient, remainder, scratch);
 14464        bool negative = numerator.Sign != denominator.Sign;
 65        const ulong signBit = 1UL << 63;
 14466        if ((quotient[8] | quotient[7] | quotient[6] | quotient[5] | quotient[4] | quotient[3]) != 0
 14467            || quotient[2] > signBit
 14468            || (quotient[2] == signBit && (!negative || (quotient[1] | quotient[0]) != 0)))
 3469            throw new OverflowException("The quotient is outside the signed 192-bit domain.");
 70
 11071        Signed192 result = new(quotient[2], quotient[1], quotient[0]);
 11072        return negative ? Negate(result) : result;
 73    }
 74
 75    internal static void GetMagnitude(Signed576 value, Span<ulong> magnitude)
 76    {
 1048386477        magnitude[0] = value.Word0;
 1048386478        magnitude[1] = value.Word1;
 1048386479        magnitude[2] = value.Word2;
 1048386480        magnitude[3] = value.Word3;
 1048386481        magnitude[4] = value.Word4;
 1048386482        magnitude[5] = value.Word5;
 1048386483        magnitude[6] = value.Word6;
 1048386484        magnitude[7] = value.Word7;
 1048386485        magnitude[8] = value.Word8;
 1048386486        magnitude[9..].Clear();
 1048386487        if (value.Sign >= 0)
 738406588            return;
 89
 309979990        ulong carry = 1UL;
 6199598091        for (int index = 0; index < 9; index++)
 2789819192            magnitude[index] = AddSignedWord(~magnitude[index], 0UL, ref carry);
 309979993    }
 94
 95    /// <summary>
 96    /// Compares two nonnegative nine-word values.
 97    /// </summary>
 98    internal static int CompareNonNegative(Signed576 left, Signed576 right)
 99    {
 45701100        if (left.Word8 != right.Word8) return left.Word8 < right.Word8 ? -1 : 1;
 45699101        if (left.Word7 != right.Word7) return left.Word7 < right.Word7 ? -1 : 1;
 45941102        if (left.Word6 != right.Word6) return left.Word6 < right.Word6 ? -1 : 1;
 45586103        if (left.Word5 != right.Word5) return left.Word5 < right.Word5 ? -1 : 1;
 46213104        if (left.Word4 != right.Word4) return left.Word4 < right.Word4 ? -1 : 1;
 48409105        if (left.Word3 != right.Word3) return left.Word3 < right.Word3 ? -1 : 1;
 47074106        if (left.Word2 != right.Word2) return left.Word2 < right.Word2 ? -1 : 1;
 63159107        if (left.Word1 != right.Word1) return left.Word1 < right.Word1 ? -1 : 1;
 4345108        return left.Word0 == right.Word0 ? 0 : left.Word0 < right.Word0 ? -1 : 1;
 109    }
 110
 111    /// <summary>
 112    /// Adds exact nine-word values without scalar conversion.
 113    /// </summary>
 114    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 115    internal static Signed576 AddSigned576(Signed576 left, Signed576 right)
 116    {
 4668120117        ulong carry = 0UL;
 4668120118        ulong word0 = AddSignedWord(left.Word0, right.Word0, ref carry);
 4668120119        ulong word1 = AddSignedWord(left.Word1, right.Word1, ref carry);
 4668120120        ulong word2 = AddSignedWord(left.Word2, right.Word2, ref carry);
 4668120121        ulong word3 = AddSignedWord(left.Word3, right.Word3, ref carry);
 4668120122        ulong word4 = AddSignedWord(left.Word4, right.Word4, ref carry);
 4668120123        ulong word5 = AddSignedWord(left.Word5, right.Word5, ref carry);
 4668120124        ulong word6 = AddSignedWord(left.Word6, right.Word6, ref carry);
 4668120125        ulong word7 = AddSignedWord(left.Word7, right.Word7, ref carry);
 4668120126        ulong word8 = unchecked(left.Word8 + right.Word8 + carry);
 4668120127        return new Signed576(word8, word7, word6, word5, word4, word3, word2, word1, word0);
 128    }
 129
 32130    internal static Signed576 Double(Signed576 value) => AddSigned576(value, value);
 131
 132    /// <summary>
 133    /// Subtracts exact nine-word values without scalar conversion.
 134    /// </summary>
 135    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 136    internal static Signed576 SubtractSigned576(Signed576 left, Signed576 right)
 137    {
 4143237138        ulong borrow = 0UL;
 4143237139        ulong word0 = SubtractWord(left.Word0, right.Word0, ref borrow);
 4143237140        ulong word1 = SubtractWord(left.Word1, right.Word1, ref borrow);
 4143237141        ulong word2 = SubtractWord(left.Word2, right.Word2, ref borrow);
 4143237142        ulong word3 = SubtractWord(left.Word3, right.Word3, ref borrow);
 4143237143        ulong word4 = SubtractWord(left.Word4, right.Word4, ref borrow);
 4143237144        ulong word5 = SubtractWord(left.Word5, right.Word5, ref borrow);
 4143237145        ulong word6 = SubtractWord(left.Word6, right.Word6, ref borrow);
 4143237146        ulong word7 = SubtractWord(left.Word7, right.Word7, ref borrow);
 4143237147        ulong word8 = unchecked(left.Word8 - right.Word8 - borrow);
 4143237148        return new Signed576(word8, word7, word6, word5, word4, word3, word2, word1, word0);
 149    }
 150
 151    internal static Signed576 MultiplySigned320(Signed320 left, Signed192 right) =>
 1943989152        MultiplySigned576(Signed576.ExtendValue(left), right);
 153
 154    /// <summary>
 155    /// Multiplies signed five-word values in the finite-axis domain exactly.
 156    /// </summary>
 157    /// <remarks>
 158    /// Callers prove that the sum of the operand magnitude bit lengths is at
 159    /// most 575, so the complete signed product fits the nine-word result.
 160    /// </remarks>
 161    internal static Signed576 MultiplySigned320(Signed320 left, Signed320 right)
 162    {
 3544250163        if (Signed192.TryNarrowSigned(left, out Signed192 narrowLeft)
 3544250164            && Signed192.TryNarrowSigned(right, out Signed192 narrowRight)
 3544250165            && GetMagnitudeBitLength(narrowLeft) + GetMagnitudeBitLength(narrowRight) <= 319)
 166        {
 3135750167            return Signed576.ExtendValue(MultiplySigned192(narrowLeft, narrowRight));
 168        }
 169
 408500170        GetMagnitude(
 408500171            left,
 408500172            out ulong leftWord4,
 408500173            out ulong leftWord3,
 408500174            out ulong leftWord2,
 408500175            out ulong leftWord1,
 408500176            out ulong leftWord0);
 408500177        GetMagnitude(
 408500178            right,
 408500179            out ulong rightWord4,
 408500180            out ulong rightWord3,
 408500181            out ulong rightWord2,
 408500182            out ulong rightWord1,
 408500183            out ulong rightWord0);
 184
 408500185        Span<ulong> leftMagnitude = stackalloc ulong[5]
 408500186        {
 408500187            leftWord0,
 408500188            leftWord1,
 408500189            leftWord2,
 408500190            leftWord3,
 408500191            leftWord4,
 408500192        };
 408500193        Span<ulong> rightMagnitude = stackalloc ulong[5]
 408500194        {
 408500195            rightWord0,
 408500196            rightWord1,
 408500197            rightWord2,
 408500198            rightWord3,
 408500199            rightWord4,
 408500200        };
 408500201        Span<ulong> product = stackalloc ulong[9];
 408500202        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 203
 408500204        if (left.Sign * right.Sign < 0)
 205        {
 130399206            ulong carry = 1UL;
 2607980207            for (int index = 0; index < product.Length; index++)
 1173591208                product[index] = AddSignedWord(~product[index], 0UL, ref carry);
 209        }
 210
 408500211        return new Signed576(
 408500212            product[8],
 408500213            product[7],
 408500214            product[6],
 408500215            product[5],
 408500216            product[4],
 408500217            product[3],
 408500218            product[2],
 408500219            product[1],
 408500220            product[0]);
 221    }
 222
 223    /// <summary>
 224    /// Multiplies a signed nine-word value by a signed one-word value whose
 225    /// proven product fits in nine words.
 226    /// </summary>
 227    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 228    internal static Signed576 MultiplySigned576(Signed576 left, long right)
 229    {
 441918230        ulong factor = Fixed64.AbsToUInt64(right);
 441918231        ulong carry = 0UL;
 441918232        ulong word0 = MultiplySigned576Word(left.Word0, factor, ref carry);
 441918233        ulong word1 = MultiplySigned576Word(left.Word1, factor, ref carry);
 441918234        ulong word2 = MultiplySigned576Word(left.Word2, factor, ref carry);
 441918235        ulong word3 = MultiplySigned576Word(left.Word3, factor, ref carry);
 441918236        ulong word4 = MultiplySigned576Word(left.Word4, factor, ref carry);
 441918237        ulong word5 = MultiplySigned576Word(left.Word5, factor, ref carry);
 441918238        ulong word6 = MultiplySigned576Word(left.Word6, factor, ref carry);
 441918239        ulong word7 = MultiplySigned576Word(left.Word7, factor, ref carry);
 441918240        ulong word8 = MultiplySigned576Word(left.Word8, factor, ref carry);
 441918241        Signed576 product = new(
 441918242            word8, word7, word6, word5, word4, word3, word2, word1, word0);
 441918243        return right < 0L
 441918244            ? SubtractSigned576(default, product)
 441918245            : product;
 246    }
 247
 248    /// <summary>
 249    /// Multiplies a signed nine-word value by a signed three-word value whose
 250    /// proven product fits in nine words.
 251    /// </summary>
 252    internal static Signed576 MultiplySigned576(Signed576 left, Signed192 right)
 253    {
 4779806254        if (Signed192.TryNarrowSigned(left, out Signed192 narrowLeft)
 4779806255            && GetMagnitudeBitLength(narrowLeft) + GetMagnitudeBitLength(right) <= 319)
 4479055256            return Signed576.ExtendValue(MultiplySigned192(narrowLeft, right));
 300751257        if (Signed320.TryNarrowSigned(left, out Signed320 mediumLeft))
 287733258            return MultiplySigned320(mediumLeft, Signed320.ExtendValue(right));
 259
 13018260        Span<ulong> leftMagnitude = stackalloc ulong[9];
 13018261        Span<ulong> rightMagnitude = stackalloc ulong[3];
 13018262        GetMagnitude(left, leftMagnitude);
 13018263        GetMagnitude(right, out rightMagnitude[2], out rightMagnitude[1], out rightMagnitude[0]);
 13018264        Span<ulong> product = stackalloc ulong[12];
 13018265        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 266
 13018267        if (left.Sign * right.Sign < 0)
 268        {
 2810269            ulong carry = 1UL;
 56200270            for (int index = 0; index < 9; index++)
 25290271                product[index] = AddSignedWord(~product[index], 0UL, ref carry);
 272        }
 273
 13018274        return new Signed576(
 13018275            product[8], product[7], product[6], product[5], product[4],
 13018276            product[3], product[2], product[1], product[0]);
 277    }
 278
 279    internal static Signed576 MultiplySigned576(Signed576 value, Signed192 first, Signed192 second) =>
 53848280        MultiplySigned576(
 53848281            MultiplySigned576(value, first),
 53848282            second);
 283
 284    internal static Signed576 MultiplySigned576(
 285        Signed576 value,
 286        Signed192 first,
 287        Signed192 second,
 288        Signed192 third) =>
 287289        MultiplySigned576(
 287290            MultiplySigned576(value, first, second),
 287291            third);
 292
 293    internal static Signed576 MultiplySigned576(
 294        Signed576 value,
 295        Signed192 first,
 296        Signed192 second,
 297        Signed192 third,
 298        Signed192 fourth) =>
 135299        MultiplySigned576(
 135300            MultiplySigned576(value, first, second, third),
 135301            fourth);
 302
 303    /// <summary>
 304    /// Returns the exact floor of the square root after applying the Q32.32
 305    /// parameter scale: <c>floor(sqrt(value * 2^64))</c>. The caller must
 306    /// prove <paramref name="value"/> is nonnegative and less than 2^523 so
 307    /// the scaled root and restoring remainder fit their five-word storage.
 308    /// </summary>
 309    internal static Signed320 GetFloorSquareRootScaledByFixed64(Signed576 value)
 310    {
 4219311        if (value.IsZero)
 4312            return default;
 313
 4215314        if ((value.Word8 | value.Word7 | value.Word6 | value.Word5 | value.Word4) == 0UL
 4215315            && (value.Word3 & (1UL << 63)) == 0UL)
 316        {
 2248317            Signed320 shifted = new(value.Word3, value.Word2, value.Word1, value.Word0, 0UL);
 2248318            Signed192 narrowRoot = GetFloorSquareRoot(shifted, out _);
 2248319            return Signed320.ExtendValue(narrowRoot);
 320        }
 321
 1967322        int bitLength = GetBitLength(value);
 1967323        int rootBitLength = ((bitLength + 1) >> 1) + FixedMath.SHIFT_AMOUNT_I;
 1967324        int activeWords = System.Math.Min(5, (rootBitLength + 64) >> 6);
 1967325        Span<ulong> rootStorage = stackalloc ulong[5];
 1967326        Span<ulong> remainderStorage = stackalloc ulong[5];
 1967327        Span<ulong> candidateStorage = stackalloc ulong[5];
 1967328        Span<ulong> root = rootStorage[..activeWords];
 1967329        Span<ulong> remainder = remainderStorage[..activeWords];
 1967330        Span<ulong> candidate = candidateStorage[..activeWords];
 1967331        rootStorage.Clear();
 1967332        remainder.Clear();
 1967333        int pairIndex = (bitLength - 1) >> 1;
 678759334        for (; pairIndex >= -FixedMath.SHIFT_AMOUNT_I; pairIndex--)
 335        {
 338396336            ShiftLeft(remainder, 2);
 338396337            if (pairIndex >= 0)
 275452338                remainder[0] |= GetBitPair(value, pairIndex);
 338396339            ShiftLeft(root, 1);
 340
 338396341            root.CopyTo(candidate);
 338396342            ShiftLeft(candidate, 1);
 338396343            candidate[0] |= 1UL;
 338396344            if (CompareMagnitudeEqualLength(remainder, candidate) < 0)
 345                continue;
 346
 36373347            SubtractEqualMagnitudes(remainder, candidate, remainder);
 36373348            root[0]++;
 349        }
 350
 1967351        return new Signed320(rootStorage[4], rootStorage[3], rootStorage[2], rootStorage[1], rootStorage[0]);
 352    }
 353
 1027308354    internal static Signed320 Negate(Signed320 value) => SubtractSigned320(default, value);
 355
 356    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 357    internal static Signed576 Absolute(Signed576 value) =>
 106358        value.Sign < 0
 106359            ? SubtractSigned576(default, value)
 106360            : value;
 361
 362    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 363    internal static Signed576 ClampToNonNegative(Signed576 value)
 364    {
 365        // Two's-complement sign masking keeps this hot-path clamp branchless.
 709366        ulong mask = ~unchecked((ulong)((long)value.Word8 >> 63));
 709367        return new Signed576(
 709368            value.Word8 & mask,
 709369            value.Word7 & mask,
 709370            value.Word6 & mask,
 709371            value.Word5 & mask,
 709372            value.Word4 & mask,
 709373            value.Word3 & mask,
 709374            value.Word2 & mask,
 709375            value.Word1 & mask,
 709376            value.Word0 & mask);
 377    }
 378
 379    private static int GetBitLength(Signed576 value)
 380    {
 1967381        if (value.Word8 != 0UL)
 2382            return 576 - Fixed64.CountLeadingZeroes(value.Word8);
 1965383        if (value.Word7 != 0UL)
 12384            return 512 - Fixed64.CountLeadingZeroes(value.Word7);
 1953385        if (value.Word6 != 0UL)
 191386            return 448 - Fixed64.CountLeadingZeroes(value.Word6);
 1762387        if (value.Word5 != 0UL)
 183388            return 384 - Fixed64.CountLeadingZeroes(value.Word5);
 1579389        if (value.Word4 != 0UL)
 1574390            return 320 - Fixed64.CountLeadingZeroes(value.Word4);
 391        // Values below 2^255 use the Signed320 restoring-square-root path.
 392        // Reaching this wide path therefore proves Word3's high bit is set.
 5393        return 256 - Fixed64.CountLeadingZeroes(value.Word3);
 394    }
 395
 396    private static int GetMagnitudeBitLength(Signed192 value)
 397    {
 15338570398        GetMagnitude(value, out ulong high, out ulong middle, out ulong low);
 15338570399        if (high != 0UL)
 1859646400            return 128 + 64 - Fixed64.CountLeadingZeroes(high);
 13478924401        if (middle != 0UL)
 3468507402            return 64 + 64 - Fixed64.CountLeadingZeroes(middle);
 10010417403        return low == 0UL ? 0 : 64 - Fixed64.CountLeadingZeroes(low);
 404    }
 405
 406    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 407    private static ulong MultiplySigned576Word(
 408        ulong value,
 409        ulong factor,
 410        ref ulong carry)
 411    {
 3977262412        Fixed64.Multiply64To128(
 3977262413            value,
 3977262414            factor,
 3977262415            out ulong high,
 3977262416            out ulong low);
 3977262417        ulong product = unchecked(low + carry);
 3977262418        carry = unchecked(high + (product < low ? 1UL : 0UL));
 3977262419        return product;
 420    }
 421
 422    private static ulong GetBitPair(Signed576 value, int pairIndex)
 423    {
 275452424        int bitIndex = pairIndex << 1;
 275452425        int shift = bitIndex & 63;
 275452426        ulong word = (bitIndex >> 6) switch
 275452427        {
 62944428            0 => value.Word0,
 62944429            1 => value.Word1,
 62944430            2 => value.Word2,
 62944431            3 => value.Word3,
 14069432            4 => value.Word4,
 8132433            5 => value.Word5,
 1308434            6 => value.Word6,
 159435            7 => value.Word7,
 8436            _ => value.Word8,
 275452437        };
 275452438        return (word >> shift) & 3UL;
 439    }
 440
 441    private static void ShiftLeft(Span<ulong> value, int bits)
 442    {
 1015188443        ulong carry = 0UL;
 8652468444        for (int index = 0; index < value.Length; index++)
 445        {
 3311046446            ulong nextCarry = value[index] >> (64 - bits);
 3311046447            value[index] = (value[index] << bits) | carry;
 3311046448            carry = nextCarry;
 449        }
 1015188450    }
 451
 452    private static Signed576 MultiplyNonNegativeToSigned576(
 453        Signed576 left,
 454        Signed576 right)
 455    {
 287456        Span<ulong> leftWords = stackalloc ulong[9];
 287457        Span<ulong> rightWords = stackalloc ulong[9];
 287458        Span<ulong> product = stackalloc ulong[18];
 287459        GetMagnitude(left, leftWords);
 287460        GetMagnitude(right, rightWords);
 287461        MultiplyMagnitudes(leftWords, rightWords, product);
 287462        return new Signed576(
 287463            product[8],
 287464            product[7],
 287465            product[6],
 287466            product[5],
 287467            product[4],
 287468            product[3],
 287469            product[2],
 287470            product[1],
 287471            product[0]);
 472    }
 473}

/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    {
 30443721        magnitude.Clear();
 30443722        magnitude[0] = value.Word0;
 30443723        magnitude[1] = value.Word1;
 30443724        magnitude[2] = value.Word2;
 30443725        magnitude[3] = value.Word3;
 30443726        magnitude[4] = value.Word4;
 30443727        magnitude[5] = value.Word5;
 30443728        magnitude[6] = value.Word6;
 30443729        magnitude[7] = value.Word7;
 30443730        magnitude[8] = value.Word8;
 30443731        magnitude[9] = value.Word9;
 30443732        magnitude[10] = value.Word10;
 30443733        if (value.Sign >= 0)
 21950134            return;
 35
 8493636        ulong carry = 1UL;
 203846437        for (int index = 0; index < 11; index++)
 93429638            magnitude[index] = AddSignedWord(~magnitude[index], 0UL, ref carry);
 8493639    }
 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    {
 74426847        Span<ulong> leftMagnitude = stackalloc ulong[9];
 74426848        Span<ulong> rightMagnitude = stackalloc ulong[5];
 74426849        GetMagnitude(left, leftMagnitude);
 74426850        CopyMagnitude(right, rightMagnitude);
 74426851        Span<ulong> product = stackalloc ulong[14];
 74426852        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 74426853        ApplySigned704Sign(product, left.Sign * right.Sign < 0);
 74426854        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    {
 2004363        Span<ulong> leftMagnitude = stackalloc ulong[9];
 2004364        Span<ulong> rightMagnitude = stackalloc ulong[3];
 2004365        GetMagnitude(left, leftMagnitude);
 2004366        GetMagnitude(right, out rightMagnitude[2], out rightMagnitude[1], out rightMagnitude[0]);
 2004367        Span<ulong> product = stackalloc ulong[12];
 2004368        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 2004369        return new Signed704(
 2004370            product[10], product[9], product[8], product[7], product[6], product[5],
 2004371            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    {
 2545879        if (value.IsZero)
 6480            return default;
 81
 2539482        Span<ulong> root = stackalloc ulong[6];
 2539483        Span<ulong> remainder = stackalloc ulong[6];
 2539484        Span<ulong> candidate = stackalloc ulong[6];
 2539485        root.Clear();
 2539486        remainder.Clear();
 89552687        for (int pairIndex = (GetBitLength(value) - 1) >> 1; pairIndex >= 0; pairIndex--)
 88        {
 42236989            ShiftLeftMagnitude(remainder, 2);
 42236990            remainder[0] |= GetBitPair(value, pairIndex);
 42236991            ShiftLeftMagnitude(root, 1);
 42236992            root.CopyTo(candidate);
 42236993            ShiftLeftMagnitude(candidate, 1);
 42236994            candidate[0] |= 1UL;
 42236995            if (CompareMagnitudeEqualLength(remainder, candidate) < 0)
 96                continue;
 97
 12575298            SubtractEqualMagnitudes(remainder, candidate, remainder);
 12575299            root[0]++;
 100        }
 101
 25394102        return new Signed576(
 25394103            0UL, 0UL, 0UL,
 25394104            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    {
 505239110        ulong carry = 0UL;
 505239111        ulong word0 = AddSignedWord(left.Word0, right.Word0, ref carry);
 505239112        ulong word1 = AddSignedWord(left.Word1, right.Word1, ref carry);
 505239113        ulong word2 = AddSignedWord(left.Word2, right.Word2, ref carry);
 505239114        ulong word3 = AddSignedWord(left.Word3, right.Word3, ref carry);
 505239115        ulong word4 = AddSignedWord(left.Word4, right.Word4, ref carry);
 505239116        ulong word5 = AddSignedWord(left.Word5, right.Word5, ref carry);
 505239117        ulong word6 = AddSignedWord(left.Word6, right.Word6, ref carry);
 505239118        ulong word7 = AddSignedWord(left.Word7, right.Word7, ref carry);
 505239119        ulong word8 = AddSignedWord(left.Word8, right.Word8, ref carry);
 505239120        ulong word9 = AddSignedWord(left.Word9, right.Word9, ref carry);
 505239121        ulong word10 = unchecked(left.Word10 + right.Word10 + carry);
 505239122        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    {
 114575128        ulong borrow = 0UL;
 114575129        ulong word0 = SubtractWord(left.Word0, right.Word0, ref borrow);
 114575130        ulong word1 = SubtractWord(left.Word1, right.Word1, ref borrow);
 114575131        ulong word2 = SubtractWord(left.Word2, right.Word2, ref borrow);
 114575132        ulong word3 = SubtractWord(left.Word3, right.Word3, ref borrow);
 114575133        ulong word4 = SubtractWord(left.Word4, right.Word4, ref borrow);
 114575134        ulong word5 = SubtractWord(left.Word5, right.Word5, ref borrow);
 114575135        ulong word6 = SubtractWord(left.Word6, right.Word6, ref borrow);
 114575136        ulong word7 = SubtractWord(left.Word7, right.Word7, ref borrow);
 114575137        ulong word8 = SubtractWord(left.Word8, right.Word8, ref borrow);
 114575138        ulong word9 = SubtractWord(left.Word9, right.Word9, ref borrow);
 114575139        ulong word10 = unchecked(left.Word10 - right.Word10 - borrow);
 114575140        return new Signed704(
 114575141            word10,
 114575142            word9,
 114575143            word8,
 114575144            word7,
 114575145            word6,
 114575146            word5,
 114575147            word4,
 114575148            word3,
 114575149            word2,
 114575150            word1,
 114575151            word0);
 152    }
 153
 154    internal static int CompareNonNegative(
 155        Signed704 left,
 156        Signed704 right)
 157    {
 11277158        if (left.Word10 != right.Word10) return left.Word10 < right.Word10 ? -1 : 1;
 11275159        if (left.Word9 != right.Word9) return left.Word9 < right.Word9 ? -1 : 1;
 11273160        if (left.Word8 != right.Word8) return left.Word8 < right.Word8 ? -1 : 1;
 11272161        if (left.Word7 != right.Word7) return left.Word7 < right.Word7 ? -1 : 1;
 11285162        if (left.Word6 != right.Word6) return left.Word6 < right.Word6 ? -1 : 1;
 11258163        if (left.Word5 != right.Word5) return left.Word5 < right.Word5 ? -1 : 1;
 11943164        if (left.Word4 != right.Word4) return left.Word4 < right.Word4 ? -1 : 1;
 12226165        if (left.Word3 != right.Word3) return left.Word3 < right.Word3 ? -1 : 1;
 9004166        if (left.Word2 != right.Word2) return left.Word2 < right.Word2 ? -1 : 1;
 17069167        if (left.Word1 != right.Word1) return left.Word1 < right.Word1 ? -1 : 1;
 251168        return left.Word0 == right.Word0
 251169            ? 0
 251170            : 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    {
 63513182        Span<ulong> firstMagnitude = stackalloc ulong[5];
 63513183        Span<ulong> secondMagnitude = stackalloc ulong[5];
 63513184        Span<ulong> thirdMagnitude = stackalloc ulong[5];
 63513185        CopyMagnitude(first, firstMagnitude);
 63513186        CopyMagnitude(second, secondMagnitude);
 63513187        CopyMagnitude(third, thirdMagnitude);
 188
 63513189        Span<ulong> firstProduct = stackalloc ulong[10];
 63513190        MultiplyMagnitudes(firstMagnitude, secondMagnitude, firstProduct);
 63513191        Span<ulong> product = stackalloc ulong[15];
 63513192        MultiplyMagnitudes(firstProduct, thirdMagnitude, product);
 193
 63513194        if (first.Sign * second.Sign * third.Sign < 0)
 195        {
 25751196            ulong carry = 1UL;
 618024197            for (int index = 0; index < 11; index++)
 283261198                product[index] = AddSignedWord(~product[index], 0UL, ref carry);
 199        }
 200
 63513201        return new Signed704(
 63513202            product[10],
 63513203            product[9],
 63513204            product[8],
 63513205            product[7],
 63513206            product[6],
 63513207            product[5],
 63513208            product[4],
 63513209            product[3],
 63513210            product[2],
 63513211            product[1],
 63513212            product[0]);
 213    }
 214
 215    private static void CopyMagnitude(Signed320 value, Span<ulong> destination)
 216    {
 1605789217        GetMagnitude(value, out destination[4], out destination[3], out destination[2], out destination[1], out destinat
 1605789218    }
 219
 220    private static Signed704 CreateSigned704(ReadOnlySpan<ulong> words) =>
 744268221        new(
 744268222            words[10], words[9], words[8], words[7], words[6], words[5],
 744268223            words[4], words[3], words[2], words[1], words[0]);
 224
 225    private static void ApplySigned704Sign(Span<ulong> words, bool negative)
 226    {
 744268227        if (!negative)
 672339228            return;
 229
 71929230        ulong carry = 1UL;
 1726296231        for (int index = 0; index < 11; index++)
 791219232            words[index] = AddSignedWord(~words[index], 0UL, ref carry);
 71929233    }
 234
 235    private static int GetBitLength(Signed704 value)
 236    {
 25396237        if (value.Word10 != 0UL) return 704 - Fixed64.CountLeadingZeroes(value.Word10);
 25395238        if (value.Word9 != 0UL) return 640 - Fixed64.CountLeadingZeroes(value.Word9);
 25390239        if (value.Word8 != 0UL) return 576 - Fixed64.CountLeadingZeroes(value.Word8);
 25471240        if (value.Word7 != 0UL) return 512 - Fixed64.CountLeadingZeroes(value.Word7);
 25316241        if (value.Word6 != 0UL) return 448 - Fixed64.CountLeadingZeroes(value.Word6);
 25459242        if (value.Word5 != 0UL) return 384 - Fixed64.CountLeadingZeroes(value.Word5);
 25240243        if (value.Word4 != 0UL) return 320 - Fixed64.CountLeadingZeroes(value.Word4);
 25140244        if (value.Word3 != 0UL) return 256 - Fixed64.CountLeadingZeroes(value.Word3);
 25210245        if (value.Word2 != 0UL) return 192 - Fixed64.CountLeadingZeroes(value.Word2);
 25245246        if (value.Word1 != 0UL) return 128 - Fixed64.CountLeadingZeroes(value.Word1);
 23919247        return 64 - Fixed64.CountLeadingZeroes(value.Word0);
 248    }
 249
 250    private static int GetBitLength(ReadOnlySpan<ulong> value)
 251    {
 6907252        int index = value.Length - 1;
 81504253        while (value[index] == 0UL)
 74597254            index--;
 6907255        return (index * 64) + 64 - Fixed64.CountLeadingZeroes(value[index]);
 256    }
 257
 258    private static ulong GetBitPair(Signed704 value, int pairIndex)
 259    {
 422369260        int bitIndex = pairIndex << 1;
 422369261        int shift = bitIndex & 63;
 422369262        ulong word = (bitIndex >> 6) switch
 422369263        {
 346033264            0 => value.Word0,
 28093265            1 => value.Word1,
 17781266            2 => value.Word2,
 13623267            3 => value.Word3,
 8798268            4 => value.Word4,
 4063269            5 => value.Word5,
 3090270            6 => value.Word6,
 612271            7 => value.Word7,
 161272            8 => value.Word8,
 113273            9 => value.Word9,
 2274            _ => value.Word10,
 422369275        };
 422369276        return (word >> shift) & 3UL;
 277    }
 278
 279    private static ulong GetBitPair(ReadOnlySpan<ulong> value, int pairIndex)
 280    {
 613175281        int bitIndex = pairIndex << 1;
 613175282        return (value[bitIndex >> 6] >> (bitIndex & 63)) & 3UL;
 283    }
 284
 285    private static void ShiftLeftMagnitude(Span<ulong> value, int bits)
 286    {
 3115190287        ulong carry = 0UL;
 38875288288        for (int index = 0; index < value.Length; index++)
 289        {
 16322454290            ulong nextCarry = value[index] >> (64 - bits);
 16322454291            value[index] = (value[index] << bits) | carry;
 16322454292            carry = nextCarry;
 293        }
 3115190294    }
 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    {
 235363620        magnitude[0] = value.Word0;
 235363621        magnitude[1] = value.Word1;
 235363622        magnitude[2] = value.Word2;
 235363623        magnitude[3] = value.Word3;
 235363624        magnitude[4] = value.Word4;
 235363625        magnitude[5] = value.Word5;
 235363626        magnitude[6] = value.Word6;
 235363627        magnitude[7] = value.Word7;
 235363628        magnitude[8] = value.Word8;
 235363629        magnitude[9] = value.Word9;
 235363630        magnitude[10] = value.Word10;
 235363631        magnitude[11] = value.Word11;
 235363632        magnitude[12] = value.Word12;
 235363633        magnitude[13..].Clear();
 235363634        if (value.Sign >= 0)
 181971835            return;
 36
 53391837        ulong carry = 1UL;
 1494970438        for (int index = 0; index < 13; index++)
 694093439            magnitude[index] = AddSignedWord(~magnitude[index], 0UL, ref carry);
 53391840    }
 41
 42    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 43    internal static Signed832 AddSigned832(Signed832 left, Signed832 right)
 44    {
 249929145        ulong carry = 0UL;
 249929146        ulong word0 = AddSignedWord(left.Word0, right.Word0, ref carry);
 249929147        ulong word1 = AddSignedWord(left.Word1, right.Word1, ref carry);
 249929148        ulong word2 = AddSignedWord(left.Word2, right.Word2, ref carry);
 249929149        ulong word3 = AddSignedWord(left.Word3, right.Word3, ref carry);
 249929150        ulong word4 = AddSignedWord(left.Word4, right.Word4, ref carry);
 249929151        ulong word5 = AddSignedWord(left.Word5, right.Word5, ref carry);
 249929152        ulong word6 = AddSignedWord(left.Word6, right.Word6, ref carry);
 249929153        ulong word7 = AddSignedWord(left.Word7, right.Word7, ref carry);
 249929154        ulong word8 = AddSignedWord(left.Word8, right.Word8, ref carry);
 249929155        ulong word9 = AddSignedWord(left.Word9, right.Word9, ref carry);
 249929156        ulong word10 = AddSignedWord(left.Word10, right.Word10, ref carry);
 249929157        ulong word11 = AddSignedWord(left.Word11, right.Word11, ref carry);
 249929158        ulong word12 = unchecked(left.Word12 + right.Word12 + carry);
 249929159        return new Signed832(
 249929160            word12, word11, word10, word9, word8, word7, word6,
 249929161            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    {
 11470        Span<ulong> leftNumeratorWords = stackalloc ulong[13]
 11471        {
 11472            leftNumerator.Word0, leftNumerator.Word1, leftNumerator.Word2,
 11473            leftNumerator.Word3, leftNumerator.Word4, leftNumerator.Word5,
 11474            leftNumerator.Word6, leftNumerator.Word7, leftNumerator.Word8,
 11475            leftNumerator.Word9, leftNumerator.Word10, leftNumerator.Word11,
 11476            leftNumerator.Word12,
 11477        };
 11478        Span<ulong> rightNumeratorWords = stackalloc ulong[13]
 11479        {
 11480            rightNumerator.Word0, rightNumerator.Word1, rightNumerator.Word2,
 11481            rightNumerator.Word3, rightNumerator.Word4, rightNumerator.Word5,
 11482            rightNumerator.Word6, rightNumerator.Word7, rightNumerator.Word8,
 11483            rightNumerator.Word9, rightNumerator.Word10, rightNumerator.Word11,
 11484            rightNumerator.Word12,
 11485        };
 11486        Span<ulong> leftDenominatorWords = stackalloc ulong[9];
 11487        Span<ulong> rightDenominatorWords = stackalloc ulong[9];
 11488        GetMagnitude(leftDenominator, leftDenominatorWords);
 11489        GetMagnitude(rightDenominator, rightDenominatorWords);
 90
 11491        Span<ulong> leftOnce = stackalloc ulong[22];
 11492        Span<ulong> rightOnce = stackalloc ulong[22];
 11493        Span<ulong> leftScaled = stackalloc ulong[31];
 11494        Span<ulong> rightScaled = stackalloc ulong[31];
 11495        MultiplyMagnitudes(leftNumeratorWords, rightDenominatorWords, leftOnce);
 11496        MultiplyMagnitudes(rightNumeratorWords, leftDenominatorWords, rightOnce);
 11497        MultiplyMagnitudes(leftOnce, rightDenominatorWords, leftScaled);
 11498        MultiplyMagnitudes(rightOnce, leftDenominatorWords, rightScaled);
 11499        return CompareMagnitudeEqualLength(leftScaled, rightScaled);
 100    }
 101
 102    internal static int CompareNonNegativeProducts(
 103        Signed832 firstLeft,
 104        Signed832 firstRight,
 105        Signed832 secondLeft,
 106        Signed832 secondRight)
 107    {
 22432108        Span<ulong> firstLeftWords = stackalloc ulong[13];
 22432109        Span<ulong> firstRightWords = stackalloc ulong[13];
 22432110        Span<ulong> secondLeftWords = stackalloc ulong[13];
 22432111        Span<ulong> secondRightWords = stackalloc ulong[13];
 22432112        GetMagnitude(firstLeft, firstLeftWords);
 22432113        GetMagnitude(firstRight, firstRightWords);
 22432114        GetMagnitude(secondLeft, secondLeftWords);
 22432115        GetMagnitude(secondRight, secondRightWords);
 22432116        Span<ulong> firstProduct = stackalloc ulong[26];
 22432117        Span<ulong> secondProduct = stackalloc ulong[26];
 22432118        MultiplyMagnitudes(firstLeftWords, firstRightWords, firstProduct);
 22432119        MultiplyMagnitudes(secondLeftWords, secondRightWords, secondProduct);
 22432120        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    {
 4671884129        if (left.IsZero || right.IsZero) return default;
 1641840130        Span<ulong> leftMagnitude = stackalloc ulong[9];
 1641840131        Span<ulong> rightMagnitude = stackalloc ulong[9];
 1641840132        GetMagnitude(left, leftMagnitude);
 1641840133        GetMagnitude(right, rightMagnitude);
 1641840134        Span<ulong> product = stackalloc ulong[18];
 1641840135        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 136
 1641840137        ApplySigned832Sign(product, left.Sign * right.Sign < 0);
 138
 1641840139        return CreateSigned832(product);
 140    }
 141
 142    /// <summary>
 143    /// Multiplies a signed nine-word conic coefficient by a signed five-word
 144    /// rational product whose proven result fits in thirteen words.
 145    /// </summary>
 146    internal static Signed832 MultiplySigned576ToSigned832(Signed576 left, Signed320 right)
 147    {
 1309093148        if (left.IsZero || right.IsZero) return default;
 670981149        Span<ulong> leftMagnitude = stackalloc ulong[9];
 670981150        Span<ulong> rightMagnitude = stackalloc ulong[5];
 670981151        GetMagnitude(left, leftMagnitude);
 670981152        CopyMagnitude(right, rightMagnitude);
 670981153        Span<ulong> product = stackalloc ulong[14];
 670981154        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 670981155        ApplySigned832Sign(product, left.Sign * right.Sign < 0);
 670981156        return CreateSigned832(product);
 157    }
 158
 159    /// <summary>
 160    /// Multiplies a signed eleven-word value by a signed three-word factor
 161    /// whose proven product fits in thirteen words.
 162    /// </summary>
 163    internal static Signed832 MultiplySigned704ToSigned832(
 164        Signed704 left,
 165        Signed192 right)
 166    {
 116345167        Span<ulong> leftMagnitude = stackalloc ulong[11];
 116345168        Span<ulong> rightMagnitude = stackalloc ulong[3];
 116345169        GetMagnitude(left, leftMagnitude);
 116345170        GetMagnitude(
 116345171            right,
 116345172            out rightMagnitude[2],
 116345173            out rightMagnitude[1],
 116345174            out rightMagnitude[0]);
 116345175        Span<ulong> product = stackalloc ulong[14];
 116345176        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 116345177        ApplySigned832Sign(product, left.Sign * right.Sign < 0);
 116345178        return CreateSigned832(product);
 179    }
 180
 181    /// <summary>
 182    /// Multiplies a signed eleven-word value by a signed five-word factor
 183    /// whose proven product fits in thirteen words.
 184    /// </summary>
 185    internal static Signed832 MultiplySigned704ToSigned832(
 186        Signed704 left,
 187        Signed320 right)
 188    {
 1189        Span<ulong> leftMagnitude = stackalloc ulong[11];
 1190        Span<ulong> rightMagnitude = stackalloc ulong[5];
 1191        GetMagnitude(left, leftMagnitude);
 1192        CopyMagnitude(right, rightMagnitude);
 1193        Span<ulong> product = stackalloc ulong[16];
 1194        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 1195        ApplySigned832Sign(product, left.Sign * right.Sign < 0);
 1196        return CreateSigned832(product);
 197    }
 198
 199    /// <summary>
 200    /// Multiplies two signed eleven-word values and a signed three-word factor
 201    /// whose proven combined product fits in thirteen words.
 202    /// </summary>
 203    internal static Signed832 MultiplySigned704ToSigned832(
 204        Signed704 first,
 205        Signed704 second,
 206        Signed192 third)
 207    {
 1208        Span<ulong> firstMagnitude = stackalloc ulong[11];
 1209        Span<ulong> secondMagnitude = stackalloc ulong[11];
 1210        Span<ulong> thirdMagnitude = stackalloc ulong[3];
 1211        GetMagnitude(first, firstMagnitude);
 1212        GetMagnitude(second, secondMagnitude);
 1213        GetMagnitude(
 1214            third,
 1215            out thirdMagnitude[2],
 1216            out thirdMagnitude[1],
 1217            out thirdMagnitude[0]);
 1218        Span<ulong> pairProduct = stackalloc ulong[22];
 1219        Span<ulong> product = stackalloc ulong[25];
 1220        MultiplyMagnitudes(
 1221            firstMagnitude,
 1222            secondMagnitude,
 1223            pairProduct);
 1224        MultiplyMagnitudes(pairProduct, thirdMagnitude, product);
 1225        ApplySigned832Sign(
 1226            product,
 1227            first.Sign * second.Sign * third.Sign < 0);
 1228        return CreateSigned832(product);
 229    }
 230
 231    /// <summary>
 232    /// Multiplies a signed thirteen-word value by a signed three-word factor
 233    /// whose proven product still fits in thirteen words.
 234    /// </summary>
 235    internal static Signed832 MultiplySigned832(
 236        Signed832 left,
 237        Signed192 right)
 238    {
 500989239        Span<ulong> leftMagnitude = stackalloc ulong[13];
 500989240        Span<ulong> rightMagnitude = stackalloc ulong[3];
 500989241        GetMagnitude(left, leftMagnitude);
 500989242        GetMagnitude(
 500989243            right,
 500989244            out rightMagnitude[2],
 500989245            out rightMagnitude[1],
 500989246            out rightMagnitude[0]);
 500989247        Span<ulong> product = stackalloc ulong[16];
 500989248        MultiplyMagnitudes(leftMagnitude, rightMagnitude, product);
 500989249        ApplySigned832Sign(product, left.Sign * right.Sign < 0);
 500989250        return CreateSigned832(product);
 251    }
 252
 253    /// <summary>Multiplies values whose caller has proved the result fits thirteen words.</summary>
 254    internal static Signed832 MultiplySigned832(Signed832 left, Signed320 right)
 255    {
 20340256        Span<ulong> a = stackalloc ulong[13], b = stackalloc ulong[5], product = stackalloc ulong[18];
 6780257        GetMagnitude(left, a);
 6780258        GetMagnitude(right, out b[4], out b[3], out b[2], out b[1], out b[0]);
 6780259        MultiplyMagnitudes(a, b, product);
 6780260        ApplySigned832Sign(product, left.Sign * right.Sign < 0);
 6780261        return CreateSigned832(product);
 262    }
 263
 264    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 265    internal static Signed832 SubtractSigned832(Signed832 left, Signed832 right)
 266    {
 1130934267        ulong borrow = 0UL;
 1130934268        ulong word0 = SubtractWord(left.Word0, right.Word0, ref borrow);
 1130934269        ulong word1 = SubtractWord(left.Word1, right.Word1, ref borrow);
 1130934270        ulong word2 = SubtractWord(left.Word2, right.Word2, ref borrow);
 1130934271        ulong word3 = SubtractWord(left.Word3, right.Word3, ref borrow);
 1130934272        ulong word4 = SubtractWord(left.Word4, right.Word4, ref borrow);
 1130934273        ulong word5 = SubtractWord(left.Word5, right.Word5, ref borrow);
 1130934274        ulong word6 = SubtractWord(left.Word6, right.Word6, ref borrow);
 1130934275        ulong word7 = SubtractWord(left.Word7, right.Word7, ref borrow);
 1130934276        ulong word8 = SubtractWord(left.Word8, right.Word8, ref borrow);
 1130934277        ulong word9 = SubtractWord(left.Word9, right.Word9, ref borrow);
 1130934278        ulong word10 = SubtractWord(left.Word10, right.Word10, ref borrow);
 1130934279        ulong word11 = SubtractWord(left.Word11, right.Word11, ref borrow);
 1130934280        ulong word12 = unchecked(left.Word12 - right.Word12 - borrow);
 1130934281        return new Signed832(
 1130934282            word12, word11, word10, word9, word8, word7, word6,
 1130934283            word5, word4, word3, word2, word1, word0);
 284    }
 285
 286    /// <summary>
 287    /// Returns the exact floor square root of a proven-fit nonnegative conic
 288    /// discriminant product. The wider radicand remains transient stack storage.
 289    /// </summary>
 290    internal static Signed576 GetFloorSquareRootOfProduct(
 291        Signed832 value,
 292        Signed192 nonNegativeFactor)
 293    {
 17393294        if (value.IsZero || nonNegativeFactor.IsZero)
 10486295            return default;
 296
 6907297        Span<ulong> valueMagnitude = stackalloc ulong[13]
 6907298        {
 6907299            value.Word0, value.Word1, value.Word2, value.Word3, value.Word4,
 6907300            value.Word5, value.Word6, value.Word7, value.Word8, value.Word9,
 6907301            value.Word10, value.Word11, value.Word12,
 6907302        };
 6907303        Span<ulong> factorMagnitude = stackalloc ulong[3];
 6907304        GetMagnitude(
 6907305            nonNegativeFactor,
 6907306            out factorMagnitude[2],
 6907307            out factorMagnitude[1],
 6907308            out factorMagnitude[0]);
 6907309        Span<ulong> product = stackalloc ulong[16];
 6907310        MultiplyMagnitudes(valueMagnitude, factorMagnitude, product);
 311
 6907312        int productBitLength = GetBitLength(product);
 313        // Reuse the scalar-limb root when the exact product fits its positive
 314        // five-word domain. Point-core distances need at most 130 bits.
 6907315        if (productBitLength <= 319)
 316        {
 4309317            Signed192 narrowRoot = GetFloorSquareRoot(
 4309318                new Signed320(product[4], product[3], product[2], product[1], product[0]),
 4309319                out _);
 4309320            return Signed576.ExtendValue(Signed320.ExtendValue(narrowRoot));
 321        }
 322
 2598323        int rootBitLength = (productBitLength + 1) >> 1;
 2598324        int activeWords = System.Math.Min(9, (rootBitLength + 64) >> 6);
 2598325        Span<ulong> rootStorage = stackalloc ulong[9];
 2598326        Span<ulong> remainderStorage = stackalloc ulong[9];
 2598327        Span<ulong> candidateStorage = stackalloc ulong[9];
 2598328        Span<ulong> root = rootStorage[..activeWords];
 2598329        Span<ulong> remainder = remainderStorage[..activeWords];
 2598330        Span<ulong> candidate = candidateStorage[..activeWords];
 2598331        rootStorage.Clear();
 2598332        remainder.Clear();
 1231546333        for (int pairIndex = (productBitLength - 1) >> 1; pairIndex >= 0; pairIndex--)
 334        {
 613175335            ShiftLeftMagnitude(remainder, 2);
 613175336            remainder[0] |= GetBitPair(product, pairIndex);
 613175337            ShiftLeftMagnitude(root, 1);
 613175338            root.CopyTo(candidate);
 613175339            ShiftLeftMagnitude(candidate, 1);
 613175340            candidate[0] |= 1UL;
 613175341            if (CompareMagnitudeEqualLength(remainder, candidate) < 0)
 342                continue;
 343
 125837344            SubtractEqualMagnitudes(remainder, candidate, remainder);
 125837345            root[0]++;
 346        }
 347
 2598348        return new Signed576(
 2598349            rootStorage[8], rootStorage[7], rootStorage[6], rootStorage[5], rootStorage[4],
 2598350            rootStorage[3], rootStorage[2], rootStorage[1], rootStorage[0]);
 351    }
 352
 353    private static Signed832 CreateSigned832(ReadOnlySpan<ulong> words) =>
 2936937354        new(
 2936937355            words[12], words[11], words[10], words[9], words[8], words[7],
 2936937356            words[6], words[5], words[4], words[3], words[2], words[1], words[0]);
 357
 358    private static void ApplySigned832Sign(Span<ulong> words, bool negative)
 359    {
 2936937360        if (!negative)
 1865829361            return;
 362
 1071108363        ulong carry = 1UL;
 29991024364        for (int index = 0; index < 13; index++)
 13924404365            words[index] = AddSignedWord(~words[index], 0UL, ref carry);
 1071108366    }
 367
 368    /// <summary>
 369    /// Multiplies nonnegative thirteen-word and five-word factors whose proven
 370    /// product fits in thirteen words.
 371    /// </summary>
 372    internal static Signed832 MultiplyNonNegativeToSigned832(
 373        Signed832 left,
 374        Signed320 right)
 375    {
 47711376        Span<ulong> leftWords = stackalloc ulong[13]
 47711377        {
 47711378            left.Word0, left.Word1, left.Word2, left.Word3, left.Word4,
 47711379            left.Word5, left.Word6, left.Word7, left.Word8, left.Word9,
 47711380            left.Word10, left.Word11, left.Word12,
 47711381        };
 47711382        Span<ulong> rightWords = stackalloc ulong[5];
 47711383        GetMagnitude(
 47711384            right,
 47711385            out rightWords[4],
 47711386            out rightWords[3],
 47711387            out rightWords[2],
 47711388            out rightWords[1],
 47711389            out rightWords[0]);
 47711390        Span<ulong> product = stackalloc ulong[18];
 47711391        MultiplyMagnitudes(leftWords, rightWords, product);
 47711392        return new Signed832(
 47711393            product[12], product[11], product[10], product[9], product[8],
 47711394            product[7], product[6], product[5], product[4], product[3],
 47711395            product[2], product[1], product[0]);
 396    }
 397}

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

#LineLine coverage
 1//=======================================================================
 2// WideArithmetic.SquareRoot.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/// Policy-neutral magnitude square-root enclosures and clipped ratio floors.
 14/// </content>
 15internal static partial class WideArithmetic
 16{
 17    /// <summary>
 18    /// Encloses sqrt(value) between lower*2^shift and upper*2^shift without
 19    /// mutating the little-endian magnitude. Empty and zero inputs give zero.
 20    /// Endpoints are nonnegative and at most 97 bits; they differ by zero or one.
 21    /// </summary>
 22    internal static void GetMagnitudeSquareRootBounds(ReadOnlySpan<ulong> value,
 23        out Signed192 lower, out Signed192 upper, out int shift)
 24    {
 8060325        int bits = GetMagnitudeBitLength(value);
 8060326        shift = bits <= 192 ? 0 : (bits - 191) / 2;
 27        // Removing an even number of bits keeps sqrt scaling exact. The
 28        // retained prefix has at most 192 bits, so the existing narrow root
 29        // owner suffices even for much wider input magnitudes.
 8060330        int discardedBits = 2 * shift;
 8060331        int wordShift = discardedBits >> 6;
 8060332        int bitShift = discardedBits & 63;
 8060333        Span<ulong> prefix = stackalloc ulong[3];
 64482434        for (int index = 0; index < prefix.Length; index++)
 35        {
 24180936            int sourceIndex = wordShift + index;
 24180937            ulong low = sourceIndex < value.Length ? value[sourceIndex] : 0;
 38            // A nonzero bitShift implies a 191/192-bit retained prefix.
 39            // The active input therefore has at least wordShift+4 words:
 40            // sourceIndex+1 exists even for the last prefix word.
 24180941            ulong high = bitShift != 0
 24180942                ? value[sourceIndex + 1] << (64 - bitShift) : 0;
 24180943            prefix[index] = (low >> bitShift) | high;
 44        }
 8060345        lower = GetFloorSquareRoot(new Signed320(0, 0, prefix[2], prefix[1], prefix[0]),
 8060346            out Signed192 remainder);
 8060347        bool discarded = false;
 21434648        for (int index = 0; index < wordShift; index++)
 2657049            discarded |= value[index] != 0;
 8060350        if (bitShift != 0)
 398251            discarded |= (value[wordShift] & ((1UL << bitShift) - 1)) != 0;
 52        // A perfect prefix alone does not prove a perfect full input. Otherwise
 53        // value < (q+1)^2*2^(2*shift), including a carry from q's 96th bit.
 8060354        upper = remainder.IsZero && !discarded ? lower
 8060355            : AddSigned192(lower, new Signed192(0, 0, 1));
 8060356    }
 57
 58    /// <summary>
 59    /// Returns min(cap, floor(sqrt(numerator/denominator))) without mutating
 60    /// inputs. Both little-endian magnitudes have equal padded widths of at
 61    /// least two words; denominator is positive. No quotient bits are truncated.
 62    /// </summary>
 63    internal static ulong GetRatioFloorSquareRoot(ReadOnlySpan<ulong> numerator,
 64        ReadOnlySpan<ulong> denominator, ulong cap)
 65    {
 2750966        int words = numerator.Length;
 67        // cap^2*D needs two extra words even though both input bounds fit W.
 68        // Division still needs a full-width quotient, not merely its low128 bits.
 2750969        Span<ulong> storage = stackalloc ulong[5 * words + 5];
 2750970        Span<ulong> product = storage[..(words + 2)];
 2750971        Span<ulong> quotient = storage.Slice(words + 2, words + 2);
 2750972        Span<ulong> remainder = storage.Slice(2 * words + 4, words);
 2750973        Span<ulong> division = storage[(3 * words + 4)..];
 2750974        Span<ulong> squareCap = stackalloc ulong[2];
 2750975        Fixed64.Multiply64To128(cap, cap, out squareCap[1], out squareCap[0]);
 2750976        MultiplyMagnitudes(denominator, squareCap, product);
 2750977        quotient.Clear();
 2750978        numerator.CopyTo(quotient);
 2750979        if (CompareMagnitudeEqualLength(quotient, product) >= 0)
 16680            return cap;
 2734381        DivideMagnitudes(numerator, denominator, quotient[..words], remainder, division);
 82        // The unclipped quotient is <cap^2<2^128, so packing its two low words
 83        // loses no bits. floor(sqrt(floor(N/D))) equals floor(sqrt(N/D)).
 2734384        return GetFloorSquareRoot(new Signed320(0, 0, 0, quotient[1], quotient[0]), out _).Low;
 85    }
 86}
Generated by: ReportGenerator 5.5.12.0
11/04/2026 - 16:26:30
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)
CompareNonNegativeNormalizedDepths(FixedMathSharp.Signed832,FixedMathSharp.Signed832,FixedMathSharp.Signed576,FixedMathSharp.Signed832,FixedMathSharp.Signed832,FixedMathSharp.Signed576)
GetRoundedNonNegativeNormalizedDepth(FixedMathSharp.Signed832,FixedMathSharp.Signed832,FixedMathSharp.Signed576,System.Boolean&)
CompareNormalizedDepthToTwiceRaw(FixedMathSharp.Signed832,FixedMathSharp.Signed832,FixedMathSharp.Signed576,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>)
AddShiftedSignedMagnitude(System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.Int32,System.Span`1<System.UInt64>,System.Int32&)
GetShiftedMagnitudeWord(System.ReadOnlySpan`1<System.UInt64>,System.Int32,System.Int32,System.Int32)
DivideMagnitudes(System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.UInt64>,System.Span`1<System.UInt64>,System.Span`1<System.UInt64>,System.Span`1<System.UInt64>)
GetMagnitudeGreatestCommonDivisor(System.Span`1<System.UInt64>,System.Span`1<System.UInt64>,System.Span`1<System.UInt64>)
ShiftMagnitudeForDivision(System.ReadOnlySpan`1<System.UInt64>,System.Span`1<System.UInt64>,System.Int32)
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>)
ShiftLeftSigned192By32(FixedMathSharp.Signed192)
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)
GetGreatestCommonDivisor(FixedMathSharp.Signed192,FixedMathSharp.Signed192)
CountTrailingZeroes192(FixedMathSharp.Signed192)
ShiftRightMagnitude192(FixedMathSharp.Signed192,System.Int32)
ShiftLeftMagnitude192(FixedMathSharp.Signed192,System.Int32)
DivideExactSigned192(FixedMathSharp.Signed192,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)
GetGreatestCommonDivisor(FixedMathSharp.Signed320,FixedMathSharp.Signed320)
DivideExactSigned320(FixedMathSharp.Signed320,FixedMathSharp.Signed320)
TruncateSigned320By64(FixedMathSharp.Signed320)
ReduceCommonScale(System.Span`1<FixedMathSharp.Signed320>)
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)
Negate(FixedMathSharp.Signed576)
MultiplySigned576(FixedMathSharp.Signed576,FixedMathSharp.Signed576)
ReduceCommonScale(System.Span`1<FixedMathSharp.Signed576>)
DivideSigned576ToSigned192(FixedMathSharp.Signed576,FixedMathSharp.Signed320)
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)
MultiplySigned832(FixedMathSharp.Signed832,FixedMathSharp.Signed320)
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)
GetMagnitudeSquareRootBounds(System.ReadOnlySpan`1<System.UInt64>,FixedMathSharp.Signed192&,FixedMathSharp.Signed192&,System.Int32&)
GetRatioFloorSquareRoot(System.ReadOnlySpan`1<System.UInt64>,System.ReadOnlySpan`1<System.UInt64>,System.UInt64)