Wykonaj moduł w ogromnej liczbie?

Question

Potrzebuję wykonać operację modulus na bardzo dużych liczbach całkowitych. Największa liczba całkowita obsługiwana przez moją platformę (edycja: .NET 2.0) jest 64-bitową liczbą całkowitą, która nie jest wystarczająco duża dla liczb, z którymi pracuję.

Jak mogę wykonać moduł na naprawdę duże liczby całkowite, na przykład 12654875632126424875387321657498462167853687516876876?

Mam rozwiązanie, które traktuje liczbę jako ciąg znaków i działa w kawałkach jeden po drugim, ale chciałem wiedzieć, czy istnieje lepszy sposób.

Oto moja funkcja traktująca liczbę jako ciąg. Zasadniczo robi długi podział tak, jak robisz to ręcznie.

Public Function MyMod(ByVal numberString As String, ByVal modby As Integer) As Integer 
     Dim position As Integer = -1 
     Dim curSubtraction As Integer = 0 

     While position < numberString.Length - 1 
      position += 1 
      curSubtraction = curSubtraction * 10 + CInt(numberString.Substring(position, 1)) 

      If (curSubtraction/modby) < 1 And position = numberString.Length - 1 Then 
       Return curSubtraction 
      ElseIf (curSubtraction/modby) < 1 Then 
       Continue While 
      Else 
       curSubtraction = curSubtraction Mod modby 
      End If 
     End While 
     Return curSubtraction 
    End Function 

Czy istnieje bardziej ekologiczny i skuteczny sposób?

EDYCJA: Aby wyjaśnić, liczby całkowite pochodzą z numerów kont bankowych IBAN. Zgodnie ze specyfikacją musisz przeliczyć numer konta IBAN (zawierający litery) na jedną liczbę całkowitą. Następnie robisz moduł na liczbie całkowitej. Sądzę więc, że można powiedzieć, że prawdziwym źródłem liczby całkowitej do wykonania modułu jest ciąg cyfr.

Answer 1

Nie określono, skąd pochodzą liczby, ale można wprowadzić pewne uproszczenia. Jeśli numery są pierwotnie mniejszy, a następnie rozważyć takie rzeczy jak:

(a + b) MOD n = ((a MOD n) + (b MOD n)) MOD n 

lub

ab MOD n = (a MOD n)(b MOD n) MOD n 

Answer 2

Użyj biblioteki crypto/matematyki. Google dla bignum.

Answer 3

Trzeba arbitralnej precyzji całkowitą biblioteki matematyczne, takie jak IntX.

Answer 4

Jeśli używasz .NET 4, możesz po prostu użyć BigInteger. Ale oto jak to zrobić we wcześniejszych wersjach.

Jest matematyczna sztuczka z modów, gdzie można po prostu wziąć pierwszy x liczbę cyfr, obliczyć mod na tej wartości, a następnie poprzedzić wynik tego mod powrotem na cyfry resztki, i powtarzać proces, aż dojdziesz do końca twojego "ogromnego" numeru.

Wprowadzić metodę rekursywną! (Niestety nie robię VB)

private static int Mod(string value, int mod) { 
    if (string.IsNullOrEmpty(value)) throw new ArgumentException("Invalid value.", "value"); 
    if (mod <= 0) throw new ArgumentException("Invalid mod.", "mod"); 

    int maxLength = long.MaxValue.ToString().Length - 1; 

    return value.Length > maxLength 
     ? Mod((Convert.ToInt64(value.Substring(0, maxLength)) % mod).ToString() + value.Substring(maxLength), mod) 
     : Convert.ToInt32(Convert.ToInt64(value) % mod);}