Random failures in System.Numerics.Tests.modpowTest.ModPowAxiom test

[vargaz]

Description

When running System.Runtime.Numerics tests in a loop on wasm, like this:
while true; do ./dotnet.sh build /t:Test /p:TargetOS=Browser /p:TargetArchitecture=wasm /p:Configuration=Release /p:EnableAggressiveTrimming=true /p:RunAOTCompilation=true /p:WasmNativeStrip=false src/libraries/System.Runtime.Numerics/tests/ || break; done

Sometimes there are failures:

  fail: [FAIL] System.Numerics.Tests.modpowTest.ModPowAxiom
  info: Assert.Equal() Failure
  info:            ↓ (pos 1)
  info: Expected: 524863242896023465128953873554861870122629···
  info: Actual:   546939980250394360189857941360277104885397···
  info:            ↑ (pos 1)
  info:    at System.Numerics.Tests.modpowTest.VerifyIdentityString(String opstring1, String opstring2)
  info:    at System.Numerics.Tests.modpowTest.ModPowAxiom()

The failure is not wasm specific however, happens with a console app as well.

using System;
using System.Numerics;

public class Test
{
    public static void Main () {
        byte[] tempByteArray1;
        byte[] tempByteArray2;
        byte[] tempByteArray3;

        tempByteArray1 = new byte [] { 226, 32 };
        tempByteArray2 = new byte [] { 113 };
        tempByteArray3 = new byte [] { 15, 8, 201, 158, 96, 200, 233, 243, 184, 0, 33, 203, 210, 80, 174, 198, 244, 177, 223, 221, 168, 243, 233, 133, 103, 252, 219, 195, 187, 227, 215, 54, 66, 248, 37, 186, 232, 45, 227, 147, 100, 14, 121, 244, 56, 89, 181, 120, 205, 4, 59, 48, 65, 239, 221, 28, 30, 68, 55, 99, 237, 38, 56, 213, 40, 234, 136, 218, 42, 244, 222, 198, 205 };

        var n1 = new BigInteger (tempByteArray1);
        var n2 = new BigInteger (tempByteArray2);
        var n3 = new BigInteger (tempByteArray3);

        var res1 = BigInteger.ModPow(n1, n2, n3);
        var res2 = BigInteger.Remainder (BigInteger.Pow(n1, (int)n2), n3);
        Console.WriteLine (res1);
        Console.WriteLine (res2);
    }
}

In master/net7 preview 4, this prints:

5248632428960234651289538735548618701226298035417369475266516952575810713774356752529490610201770297680688383780908963419756694889385961142585935984058777893641945433342961982
54693998025039436018985794136027710488539704291920837071192774624968986537187541952846187915666352899137283834570037293378029168944185733267466726919021367393203218220280126

while with net6, it prints:

54693998025039436018985794136027710488539704291920837071192774624968986537187541952846187915666352899137283834570037293378029168944185733267466726919021367393203218220280126
54693998025039436018985794136027710488539704291920837071192774624968986537187541952846187915666352899137283834570037293378029168944185733267466726919021367393203218220280126

So this looks like a regression which is triggered by the specific set of inputs in the test case.

Reproduction Steps

Expected behavior

Actual behavior

Regression?

No response

Known Workarounds

No response

Configuration

No response

Other information

No response

[ghost]

Tagging subscribers to this area: @dotnet/area-system-numerics
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

When running System.Runtime.Numerics tests in a loop on wasm, like this:
while true; do ./dotnet.sh build /t:Test /p:TargetOS=Browser /p:TargetArchitecture=wasm /p:Configuration=Release /p:EnableAggressiveTrimming=true /p:RunAOTCompilation=true /p:WasmNativeStrip=false src/libraries/System.Runtime.Numerics/tests/ || break; done

Sometimes there are failures:

  fail: [FAIL] System.Numerics.Tests.modpowTest.ModPowAxiom
  info: Assert.Equal() Failure
  info:            ↓ (pos 1)
  info: Expected: 524863242896023465128953873554861870122629···
  info: Actual:   546939980250394360189857941360277104885397···
  info:            ↑ (pos 1)
  info:    at System.Numerics.Tests.modpowTest.VerifyIdentityString(String opstring1, String opstring2)
  info:    at System.Numerics.Tests.modpowTest.ModPowAxiom()

The failure is not wasm specific however, happens with a console app as well.

using System;
using System.Numerics;

public class Test
{
    public static void Main () {
        byte[] tempByteArray1;
        byte[] tempByteArray2;
        byte[] tempByteArray3;

        tempByteArray1 = new byte [] { 226, 32 };
        tempByteArray2 = new byte [] { 113 };
        tempByteArray3 = new byte [] { 15, 8, 201, 158, 96, 200, 233, 243, 184, 0, 33, 203, 210, 80, 174, 198, 244, 177, 223, 221, 168, 243, 233, 133, 103, 252, 219, 195, 187, 227, 215, 54, 66, 248, 37, 186, 232, 45, 227, 147, 100, 14, 121, 244, 56, 89, 181, 120, 205, 4, 59, 48, 65, 239, 221, 28, 30, 68, 55, 99, 237, 38, 56, 213, 40, 234, 136, 218, 42, 244, 222, 198, 205 };

        var n1 = new BigInteger (tempByteArray1);
        var n2 = new BigInteger (tempByteArray2);
        var n3 = new BigInteger (tempByteArray3);

        var res1 = BigInteger.ModPow(n1, n2, n3);
        var res2 = BigInteger.Remainder (BigInteger.Pow(n1, (int)n2), n3);
        Console.WriteLine (res1);
        Console.WriteLine (res2);
    }
}

In master/net7 preview 4, this prints:

5248632428960234651289538735548618701226298035417369475266516952575810713774356752529490610201770297680688383780908963419756694889385961142585935984058777893641945433342961982
54693998025039436018985794136027710488539704291920837071192774624968986537187541952846187915666352899137283834570037293378029168944185733267466726919021367393203218220280126

while with net6, it prints:

54693998025039436018985794136027710488539704291920837071192774624968986537187541952846187915666352899137283834570037293378029168944185733267466726919021367393203218220280126
54693998025039436018985794136027710488539704291920837071192774624968986537187541952846187915666352899137283834570037293378029168944185733267466726919021367393203218220280126

So this looks like a regression which is triggered by the specific set of inputs in the test case.

Reproduction Steps

Expected behavior

Actual behavior

Regression?

No response

Known Workarounds

No response

Configuration

No response

Other information

No response

Author:	vargaz
Assignees:	-
Labels:	area-System.Numerics, untriaged
Milestone:	-

[ghost]

Tagging subscribers to 'arch-wasm': @lewing
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

When running System.Runtime.Numerics tests in a loop on wasm, like this:
while true; do ./dotnet.sh build /t:Test /p:TargetOS=Browser /p:TargetArchitecture=wasm /p:Configuration=Release /p:EnableAggressiveTrimming=true /p:RunAOTCompilation=true /p:WasmNativeStrip=false src/libraries/System.Runtime.Numerics/tests/ || break; done

Sometimes there are failures:

  fail: [FAIL] System.Numerics.Tests.modpowTest.ModPowAxiom
  info: Assert.Equal() Failure
  info:            ↓ (pos 1)
  info: Expected: 524863242896023465128953873554861870122629···
  info: Actual:   546939980250394360189857941360277104885397···
  info:            ↑ (pos 1)
  info:    at System.Numerics.Tests.modpowTest.VerifyIdentityString(String opstring1, String opstring2)
  info:    at System.Numerics.Tests.modpowTest.ModPowAxiom()

The failure is not wasm specific however, happens with a console app as well.

using System;
using System.Numerics;

public class Test
{
    public static void Main () {
        byte[] tempByteArray1;
        byte[] tempByteArray2;
        byte[] tempByteArray3;

        tempByteArray1 = new byte [] { 226, 32 };
        tempByteArray2 = new byte [] { 113 };
        tempByteArray3 = new byte [] { 15, 8, 201, 158, 96, 200, 233, 243, 184, 0, 33, 203, 210, 80, 174, 198, 244, 177, 223, 221, 168, 243, 233, 133, 103, 252, 219, 195, 187, 227, 215, 54, 66, 248, 37, 186, 232, 45, 227, 147, 100, 14, 121, 244, 56, 89, 181, 120, 205, 4, 59, 48, 65, 239, 221, 28, 30, 68, 55, 99, 237, 38, 56, 213, 40, 234, 136, 218, 42, 244, 222, 198, 205 };

        var n1 = new BigInteger (tempByteArray1);
        var n2 = new BigInteger (tempByteArray2);
        var n3 = new BigInteger (tempByteArray3);

        var res1 = BigInteger.ModPow(n1, n2, n3);
        var res2 = BigInteger.Remainder (BigInteger.Pow(n1, (int)n2), n3);
        Console.WriteLine (res1);
        Console.WriteLine (res2);
    }
}

In master/net7 preview 4, this prints:

5248632428960234651289538735548618701226298035417369475266516952575810713774356752529490610201770297680688383780908963419756694889385961142585935984058777893641945433342961982
54693998025039436018985794136027710488539704291920837071192774624968986537187541952846187915666352899137283834570037293378029168944185733267466726919021367393203218220280126

while with net6, it prints:

54693998025039436018985794136027710488539704291920837071192774624968986537187541952846187915666352899137283834570037293378029168944185733267466726919021367393203218220280126
54693998025039436018985794136027710488539704291920837071192774624968986537187541952846187915666352899137283834570037293378029168944185733267466726919021367393203218220280126

So this looks like a regression which is triggered by the specific set of inputs in the test case.

Reproduction Steps

Expected behavior

Actual behavior

Regression?

No response

Known Workarounds

No response

Configuration

No response

Other information

No response

Author:	vargaz
Assignees:	-
Labels:	arch-wasm, area-System.Numerics, untriaged
Milestone:	-

[jeffhandley]

Here's our plan on this issue:

1. We are still working to get a fix in place before the RC1 snap
2. If the fix misses the snap but lands soon thereafter, we will consider going through Tactics Ask Mode to port the fix into RC1
3. If the fix misses Ask Mode or is not justified for it, but it's proven to be a regression from .NET 6, we will fix it in RC2
4. If the issue proves not to be a regression, we will fix it in .NET 8

[dakersnar]

I've been looking into this, here's an update. The short of it is a fix will not be ready for the RC1 snap.

The long story is I'm trying to break down the algorithms to figure out what is causing the difference. I'm also trying to verify which output is correct, the original behavior or the new behavior.

The n3 BigInteger that gets used in the example above is a negative number, yet the result of this ModPow is a positive number. This contradicts the output of tools like WolframAlpha . I can also reproduce this behavior with smaller inputs. It seems to me that WolframAlpha is using a different definition of modulo compared to .NET. This site expands on what I think is the difference: https://www.omnicalculator.com/math/modulo-of-negative-numbers#how-does-modulo-work-with-negative-numbers.

Given this discrepancy, it's hard for me to tell which output is actually correct. Regardless, either way I think the behavior change is probably due to this PR #35565. I'm going to spend some time tomorrow diving into that.

[sakno]

@dakersnar , I'll take a look.

[sakno]

@dakersnar , you can assign it to me. Will try to fix this quick, just returned from vacation with absolutely clean brain 😄

[dakersnar]

Can do, let me know if you need any help with that.

[dakersnar]

@sakno Also, I have a more reproducible failing unit test set up here if you would like to cherry pick this commit https://github.com/dakersnar/runtime/tree/fix-70330

[sakno]

This is a correct output

54693998025039436018985794136027710488539704291920837071192774624968986537187541952846187915666352899137283834570037293378029168944185733267466726919021367393203218220280126

Checked in java (it doesn't accept negative modulos, yay)

import java.math.*;

class HelloWorld {
    public static void main(String[] args) {
        
        var n1 = new BigInteger ("8418");
        var n2 = new BigInteger ("113");
        var n3 = new BigInteger ("12421714448554955886377993147779372741715160061029778448376437168219030709121226880650783927927868674313412837516053211174986358043602622119800674680911960141623475683349428209");
        
        System.out.println(n1.modPow(n2, n3));
    }
}

So .NET 6 behavior is correct. Something wrong with ModPow operation itself, because combination of public Remainder and Pow are working as expected.

[dakersnar]

The ModPow algorithm is very interesting. I don't exactly know how it works and where it came from. But here is the key difference between ModPow and Pow + Remainder.

Pow + Remainder does each half to completion sequentially. The Pow algorithm is here, it's pretty simple: https://source.dot.net/#System.Runtime.Numerics/System/Numerics/BigIntegerCalculator.PowMod.cs,46

ModPow basically does the Mod during the Pow algorithm. You can see it calling Reduce after each step, which is basically a Mod operation. I can't tell if it's correct or not: https://source.dot.net/#System.Runtime.Numerics/System/Numerics/BigIntegerCalculator.PowMod.cs,441

[dakersnar]

I think there is something very peculiar about this specific input that is making this test fail. Stepping through the very last call to Divide, here is the state of left at this line, just before it zeros out element 19. https://source.dot.net/#System.Runtime.Numerics/System/Numerics/BigIntegerCalculator.DivRem.cs,192. That 0 in the 18 spot is coincidental and might be an edge case this Divide algorithm (or a user of it) isn't accounting for.

[sakno]

@dakersnar , yes, I found the same. The problem when the result is copying from the temp buffer back to the final buffer which contains the garbage at the highest elements. I found already the source of this garbage. Slice was too optimistic from my side. I'm working on the fix.

[sakno]

@dakersnar , @jeffhandley , PR is ready for review.

[tannergooding]

Noting that ModPow and Pow + Remainder are two different operations AFAIR.

I believe ModPow is doing a proper modulus and therefore -21 mod 4 == 3. This is different from the % operator which computes a remainder and therefore -21 % 4 == -1.

[dakersnar]

As far as I can tell ModPow is computing a remainder and behaving the same as Pow + Remainder for all cases. https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEUCuA7AHwAEAmABgFgAoUgRmqLIAIjaA6AORwFsYoBLMAGcA3NWoA3AIZQmeWkwC8TAEL8A5gEk8GGOr5sACjKEwAFACI4JWhYCUYqtNl4SS1Ru279UIyfMWtg6SMnIAzO5qWjp6BsZQppYo9o4hsrBCCspRXrG+ALIQACaGEADuZvJociTVeGHBTqEZbtmeMT5sAEow3FL8eEV8TGY5HXHllbTVZgMYdq52dQ2OrACcIxm0jeubMEIkDkA=