Выполните модуль в огромном количестве?

Question

Мне нужно выполнить операцию модуля на очень больших целых числах. Самое большое целое число, поддерживаемое моей платформой (версия .NET 2.0) - это 64-битное целое число, которое недостаточно велико для чисел, с которыми я работаю.

Как я могу сделать модуль на действительно больших целых числах, например 12654875632126424875387321657498462167853687516876876?

У меня есть решение, которое обрабатывает число как строку и обрабатывает его по частям один за другим, но я хотел знать, есть ли лучший способ.

Вот моя функция обработки номера в виде строки. Это в основном делает длинное разделение так, как вы делали это вручную.

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 

Есть ли более чистый, более эффективный способ?

EDIT: Чтобы уточнить, целые числа поступают из номеров банковских счетов IBAN. Согласно спецификации, вам необходимо преобразовать номер счета IBAN (содержащий буквы) в одно целое. Затем вы выполняете модуль на целое число. Итак, я думаю, вы могли бы сказать, что реальный источник целого числа для выполнения модуля on - это строка цифр.

Answer 1

Вы не указали, с чего начинаются цифры, но вы можете сделать некоторые упрощения. Если числа первоначально меньше, а затем рассмотреть такие вещи, как:

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

или

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

Answer 2

Используйте крипто/математическую библиотеку. Google для bignum.

Answer 3

Вам нужен произвольной точности целочисленную математической библиотеки, такие как IntX.

Answer 4

Если вы используете .NET 4, вы можете просто использовать BigInteger. Но вот как это сделать с более ранними версиями.

Существует математический трюк с модами, где вы можете просто взять первое х количества цифр, вычислить моды на этом значение, то предварять результат этого мода обратно на оставшихся цифры, и повторять до тех пор, пока вы не дойдете до конца своего «огромного» номера.

Привести рекурсивный метод! (Извините, что я не делаю 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);}