CODEWITHSUNDEEP
.netmodulo
Jim
Jim

Reputation: 11389

Perform a modulus in a huge number?

I need to do a modulus operation on very large integers. The biggest integer supported by my platform (edit: .NET 2.0) is a 64 bit integer, which aren't big enough for the numbers I'm working with.

How can I do a modulus on really big integers, like 12654875632126424875387321657498462167853687516876876?

I have a solution that treats the number as a string and works it in pieces one by one, but I wanted to know if there's a better way.

Here's my function treating the number as a string. It basically does long division the way you'd do it by hand.

    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

Is there a cleaner, more efficient way?

EDIT: To clarify, the integers are coming from IBAN bank account numbers. According to the specification, you have to convert the IBAN account number (containing letters) into one integer. Then, you do a modulus on the integer. So, I guess you could say that the real source of the integer to perform the modulus on is a string of digits.

Upvotes: 5

Views: 2356

Answers (4)

user718642
user718642

Reputation:

If you are using .NET 4, you can just use a BigInteger. But here is how to do it with earlier versions.

There is a mathematical trick with mods where you can just take the first x number of digits, calculate the mod on that value, then prepend the result of that mod back onto the leftover digits, and keep repeating the process until you reach the end of your "huge" number.

Bring on the recursive method! (Sorry I don't do 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);}

Upvotes: 0

Michael Borgwardt
Michael Borgwardt

Reputation: 346476

You need an arbitrary-precision integer math library such as IntX.

Upvotes: 0

Tony Arkles
Tony Arkles

Reputation: 1946

You haven't specified where the numbers are coming from, but you might be able to make some simplifications. If the numbers are originally smaller, then consider things like:

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

or

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

Upvotes: 6

HUAGHAGUAH
HUAGHAGUAH

Reputation: 1071

Use a crypto/math library. Google for bignum.

Upvotes: 3

Related Questions