Working with very large integers in c++

Question

So basically I'm working on a project involving some algebraic expressions involving very large numbers. And using the standard operators (int, long int, long long and so on) just doesn't cut it. The code I'm currently using is written as (and is part of a larger project):

#include<iostream>
long int myPow(long int base, long int exponent, long int mod) {
    long int prod = 1;

    while (exponent > 0) {
        if (exponent & 1 == 1) {
            prod *= base;
            prod %= mod;
        }
        base *= base;
        base %= mod;
        exponent /= 2;
        }
    return prod;
}

int main () {
    long int a = myPow(2 , 1000, 100007);
    std::cout << a << std::endl;
    system("pause");
    return 0;
}

Now, I have read that it is possible to use GMP for handling very large numbers. Unfortunately, I'm rather new to the programming world. And as fare as I understand, GMP relies on the MinGW compiler. I'm currently running Visual Studio 2015.

I have browsed through different forums and Google, but I haven't been able to find any new guides (after 2014) on how to setup GMP (and/with MinGW), which means links are broken, references non-existing, etc. I'm also freakishly afraid to start tampering with Windows/Visual Studio (trying to "install" (?) MinGW), as I don't want to lose my current working setup/compiler (standard Visual Studio compiler - no clue what it's called).

Anyway, if someone could point me in the right direction or recommend some literature, it would be greatly appreciated.

As a last resort, I'm considering installing Code::Blocks (standard MinGW?!), but I'm afraid it will mess up my current setup for Visual Studio? Another possibility would be to create a Virtual Machine with Ubuntu and run Code::Blocks on it. Anyway, it seem rather extensive and I would prefer to stay in Windows with VS - if possible.

Have a look at: http://stackoverflow.com/questions/19688442/how-to-install-mpfr-and-gmp-for-c-on-visual-studio — Richard Critten, Mar 13 '17 at 22:53
@RichardCritten Hi Richard. I saw this thread already. But this solution relies on (quote): "relatively bug-free" binaries. It also only supports 32 bit systems, which seems like a waste when working with very large numbers. Anyway, I was hoping for a "better" solution, but thanks for your reply. — bgaard, Mar 13 '17 at 23:02

em2er · Accepted Answer · 2017-03-13T23:39:40.323

Have a look at Boost.Multiprecision The following code works on VS 2015:

#include "boost/multiprecision/cpp_int.hpp"
#include <iostream>

namespace mp = boost::multiprecision;

typedef mp::number<mp::cpp_int_backend<4096, 4096, mp::signed_magnitude, mp::unchecked, void> >  int4096_t;

int4096_t myPow(int4096_t base, long int exponent, long int mod) {
    int4096_t prod = 1;

    while (exponent > 0) {
        if (exponent & 1 == 1) {
            prod *= base;
            prod %= mod;
        }
        base *= base;
        base %= mod;
        exponent /= 2;
    }
    return prod;
}



int main()
{
    int4096_t a = myPow(2, 1000, 100007);
    std::cout << a << std::endl;

    int i;
    std::cin >> i;
    return 0;
}

And prints 44850. I defined int4096_t integer type (4096 bits length) for example, but you can use predefined boost::multiprecision::int1024_t or another appropriate type.

This is amazing! Thank you. If anyone else is interested, you can start here (their web-page is not too intuitive): http://www.boost.org/doc/libs/1_63_0/more/getting_started/windows.html — bgaard, Mar 14 '17 at 11:22

Working with very large integers in c++

1 Answers1