CODEWITHSUNDEEP
cmathmodulo
jbond
jbond

Reputation: 77

calculating with very big numbers in c

Im new to programming. I want to calculate the modulo of a number which is in range from [0,10^24]. For example: (12 * 10^22) % 89 I know that I can't do this with the usual data types like long, integer and so on. How can I do this? Is there a way to do this?

Thanks in advance

Upvotes: 1

Views: 2113

Answers (3)

Hello World
Hello World

Reputation: 305

The largest guaranteed C data type is a uint64_t (see stdint.h), which holds up to 2^64 - 1. I think it is preferable to maintain conformance to standard C when possible, so I'd suggest a way of simplifying the problem first so as to not use data types wider than that. For that, let's borrow from a modular arithmetic proof:

xy % z == ((x % z) * (y % z)) % z

From this, we can gather that, (12 * 10^22) % 89 == (12 % 89 * 10^11 % 89 * 10^11 %89) % 89 This new version certainly isn't as pretty, but it does make all the factors fit nicely into standard C data types. Simplification prior to computation such as this can be used for all the data in your range.

However, there is the problem of having storing the value you want to modulo in the first place. Clarification on what the use case is might make for a more applicable answer. For instance, is the value being stored in a string, perhaps from user input?

Alternatively, you can make use of certain libraries designed for dealing with really big numbers. I don't know which would be best for your purposes (I don't even know what OS you're on), but if you'd like to explore those options, a simple web search for "bignum", "arbitrary-precision", or "infinite-precision" libraries should give you what you want.

Upvotes: 1

vonbrand
vonbrand

Reputation: 11791

As the previous answers say, you can get by with regular integers in this case.

If you really need very large integers (like in many cryptographic applications), there are several open source libraries around. Check out the GNU MP library or Flint (Fast Library for Number Theory, take a peek at the (header only!) C++ precision package or take a peek at Wikipedia's list. Most of them are available as packages for your favorite Linux distrtibution.

Many languages handle large integers transparently, GNU's bc (at your nearest Linux box) uses them.

Upvotes: 1

Eric Postpischil
Eric Postpischil

Reputation: 222234

The expression shown can be easily calculated by reducing modulo 89 after each operation:

#include <stdio.h>


int main(void)
{
    //  Initialize a product.
    int t = 1;

    //  Calculate 10^22 (modulo 89) by multiplying by 10 (modulo 89) 22 times.
    for (int i = 0; i < 22; ++i)
        t = t * 10 % 89;

    //  Multiply by 12 (modulo 89).
    t = t * 12 % 89;

    //  Show the result.
    printf("%d\n", t);
}

Upvotes: 5

Related Questions