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

Мне нужно выполнить операцию модуля над очень большими целыми числами. Самое большое целое число, поддерживаемое моей платформой (редактирование: .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

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

РЕДАКТИРОВАТЬ: Чтобы уточнить, целые числа поступают из номеров банковских счетов IBAN. Согласно спецификации, вы должны преобразовать номер счета IBAN (содержащий буквы) в одно целое число. Затем вы выполняете модуль над целым числом. Итак, я думаю, вы могли бы сказать, что реальным источником целого числа для выполнения модуля является строка цифр.


.net modulo
person Jim    schedule 10.11.2008    source источник
comment
Что это за язык? Возможно, вы захотите добавить тег.   -  person billjamesdev    schedule 10.11.2008
comment
Также было бы полезно включить пример. У вас есть решение огромного числа в вашем моде вопроса каким-то другим значением?   -  person Bill the Lizard    schedule 10.11.2008

Ответы (4)


arrow_upward
5
arrow_downward

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

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

or

ab MOD n = (a MOD n)(b MOD n) MOD n
person Tony Arkles    schedule 10.11.2008
comment
Да, мне нужно было уточнить вопрос получше. Ваше решение сработало бы, если бы я начал с нескольких целых чисел, но в моем случае я начинаю с одного большого целого числа. - person Jim; 10.11.2008

arrow_upward
3
arrow_downward

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

person HUAGHAGUAH    schedule 10.11.2008

arrow_upward
0
arrow_downward

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

person Michael Borgwardt    schedule 16.01.2009

arrow_upward
0
arrow_downward

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

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

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