Finite Field Addition, Subtraktion und Multiplikation

  • C#
  • .NET (FX) 4.5–4.8

Es gibt 1 Antwort in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Finite Field Addition, Subtraktion und Multiplikation

    Hey,

    Ich schreibe gerade eine Klasse für Operationen in einem finite field.
    Ich habe auch alle Operationen implementiert bekommen, allerdings nicht perfekt.
    Ich möchte das jede der Operationen:
    1. Overflowschutz hat, d.h. sollte die int.MaxValue überschritten, bzw die int.MinValue Grenze unterschritten werden.
    2. Wenn möglich die BigInteger Klasse vermeiden.
    3. Der Umgang mit negativen Werten soll funktionieren - und genau da haperts.
    Zur Kontrolle habe ich immer alle Werte mit Wolfram Alpha gechecked und dementsprechend Unit-Tests geschrieben.

    C#-Quellcode

    1. public class FiniteFieldArithmetic
    2. {
    3. /// <summary>
    4. /// The modulo or the size of the finite field
    5. /// </summary>
    6. private static int _modulo;
    7. /// <summary>
    8. /// Initializes the finite field operations for a specified modulo
    9. /// </summary>
    10. /// <param name="modulo">The modulo</param>
    11. public FiniteFieldArithmetic(int modulo)
    12. {
    13. _modulo = modulo;
    14. }
    15. /// <summary>
    16. /// Modular addition (overflow safe)
    17. /// </summary>
    18. /// <param name="a">The first number</param>
    19. /// <param name="b">The second number</param>
    20. /// <returns>The sum under the specified modulo</returns>
    21. public int Add(int a, int b)
    22. {
    23. a %= _modulo;
    24. b %= _modulo;
    25. int sum = a + b;
    26. return (sum >= _modulo || sum < a) ? sum - _modulo : sum;
    27. }
    28. /// <summary>
    29. /// Modular subtraction (overflow safe)
    30. /// </summary>
    31. /// <param name="a">The first number</param>
    32. /// <param name="b">The second number</param>
    33. /// <returns>The difference under the specified modulo</returns>
    34. public int Sub(int a, int b)
    35. {
    36. a %= _modulo;
    37. b %= _modulo;
    38. int diff = a - b;
    39. return (a < b) ? diff + _modulo : diff;
    40. }
    41. /// <summary>
    42. /// Modular multiplication
    43. /// </summary>
    44. /// <param name="a">The first number</param>
    45. /// <param name="b">The second number</param>
    46. /// <returns>The product under the specified modulo</returns>
    47. public int Mul(int a, int b)
    48. {
    49. if (a >= _modulo)
    50. a %= _modulo;
    51. if (b >= _modulo)
    52. b %= _modulo;
    53. int c = a * b / _modulo;
    54. return (a * b - c * _modulo) % _modulo;
    55. }
    56. }


    Meine Unit-Tests (Ich verwende XUnit) sehen wie folgt aus:

    C#-Quellcode

    1. public class FiniteFieldArithmeticTest
    2. {
    3. [Theory]
    4. [InlineData(2, 5, 3, 1)] // Normal Values
    5. [InlineData(-2, 5, 3, 0)] // Normal Value, a is negative
    6. [InlineData(2, -5, 3, 0)] // Normal Value, b is negative
    7. [InlineData(int.MaxValue, 1337, 420, 204)] // Upper bound overflow check with value A
    8. [InlineData(1337, int.MaxValue, 420, 204)] // Upper bound overflow check with value B
    9. [InlineData(int.MinValue, -1337, 420, 215)]// Lower bound overflow check with value A
    10. [InlineData(-1337, int.MinValue, 420, 215)] // Lower bound overflow check with value B
    11. [InlineData(1337, 420, int.MaxValue, 1757)] // Highest possible modulus
    12. [InlineData(int.MaxValue, int.MaxValue, 1337, 527)] // Upper bound Overflow check with value A and B
    13. [InlineData(int.MinValue, int.MinValue, 1337, 808)] // Upper bound Overflow check with value A and B
    14. public void FiniteFieldAddTest(int a, int b, int m, int expectedResult)
    15. {
    16. var finiteField = new FiniteFieldArithmetic(m);
    17. var result = finiteField.Add(a, b);
    18. Assert.Equal(expectedResult, result);
    19. }
    20. [Theory]
    21. [InlineData(2, 5, 3, 0)] // Normal Values
    22. [InlineData(-2, 5, 3, 2)] // Normal Value, a is negative
    23. [InlineData(2, -5, 3, 1)] // Normal Value, b is negative
    24. [InlineData(int.MaxValue, 1337, 420, 50)] // Upper bound overflow check with value A
    25. [InlineData(1337, int.MaxValue, 420, 370)] // Upper bound overflow check with value B
    26. [InlineData(int.MinValue, -1337, 420, 369)]// Lower bound overflow check with value A
    27. [InlineData(-1337, int.MinValue, 420, 51)] // Lower bound overflow check with value B
    28. [InlineData(int.MaxValue, int.MaxValue, 1337, 0)] // Upper bound Overflow check with value A and B
    29. [InlineData(int.MinValue, int.MinValue, 1337, 0)] // Upper bound Overflow check with value A and B
    30. public void FiniteFieldSubTest(int a, int b, int m, int expectedResult)
    31. {
    32. var finiteField = new FiniteFieldArithmetic(m);
    33. var result = finiteField.Sub(a, b);
    34. Assert.Equal(expectedResult, result);
    35. }
    36. [Theory]
    37. [InlineData(2, 5, 3, 1)] // Normal Values
    38. [InlineData(-2, 5, 3, 2)] // Normal Value, a is negative
    39. [InlineData(2, -5, 3, 2)] // Normal Value, b is negative
    40. [InlineData(int.MaxValue, 1337, 420, 119)] // Upper bound overflow check with value A
    41. [InlineData(1337, int.MaxValue, 420, 119)] // Upper bound overflow check with value B
    42. [InlineData(int.MinValue, -1337, 420, 196)]// Lower bound overflow check with value A
    43. [InlineData(-1337, int.MinValue, 420, 196)] // Lower bound overflow check with value B
    44. [InlineData(int.MaxValue, int.MaxValue, 1337, 911)] // Upper bound Overflow check with value A and B
    45. [InlineData(int.MinValue, int.MinValue, 1337, 102)] // Upper bound Overflow check with value A and B
    46. public void FiniteFieldMulTest(int a, int b, int m, int expectedResult)
    47. {
    48. var finiteField = new FiniteFieldArithmetic(m);
    49. var result = finiteField.Mul(a, b);
    50. Assert.Equal(expectedResult, result);
    51. }
    52. }


    Nicht alle unit tests passen. Ich habe Probleme mit negativen Werten und mit overflows.
    hat jemand eine Idee wie ich meine Methoden anpassen kann damit alle Tests passen?

    Bisher:

    C# Developer
    Learning C++

    Rikudo schrieb:

    Nicht alle unit tests passen.
    Da musst Du halt mal debuggen und feststellen, was der Algo da anders macht als er soll.
    Wir würden hier jetzt nix anderes tun.
    Vermutung:
    Wenn Du intern mit long arbeitest und die Ergebnisse hinterher begrenzt, geht vielleicht was.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!