在 C++ 中处理非常大的整数
Working with very large integers in c++
所以基本上我正在从事一个涉及一些涉及非常大的数字的代数表达式的项目。使用标准运算符(int、long int、long long 等)并不能解决问题。我目前使用的代码写成(并且是一个更大项目的一部分):
#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;
}
现在,我了解到可以使用 GMP 来处理非常大的数字。不幸的是,我对编程世界还很陌生。据我了解,GMP 依赖于 MinGW 编译器。我目前 运行宁 Visual Studio 2015。
我浏览了不同的论坛和 Google,但我无法找到任何关于如何设置 GMP (and/with MinGW) 的新指南(2014 年之后),这意味着链接已损坏,引用不存在等。我也非常害怕开始篡改 Windows/Visual Studio(尝试 "install" (?) MinGW),因为我不想失去我的当前工作 setup/compiler(标准 Visual Studio 编译器 - 不知道它叫什么)。
无论如何,如果有人能给我指明正确的方向或推荐一些文献,我将不胜感激。
作为最后的手段,我正在考虑安装 Code::Blocks(标准 MinGW?!),但我担心它会弄乱我当前的 Visual Studio 设置?另一种可能性是创建一个带有 Ubuntu 和 运行 Code::Blocks 的虚拟机。无论如何,它看起来相当广泛,我更愿意留在 Windows 与 VS - 如果可能的话。
看看Boost.Multiprecision
以下代码适用于 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;
}
并打印 44850。例如,我定义了 int4096_t 整数类型(4096 位长度),但您可以使用预定义的 boost::multiprecision::int1024_t 或其他合适的类型。
所以基本上我正在从事一个涉及一些涉及非常大的数字的代数表达式的项目。使用标准运算符(int、long int、long long 等)并不能解决问题。我目前使用的代码写成(并且是一个更大项目的一部分):
#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;
}
现在,我了解到可以使用 GMP 来处理非常大的数字。不幸的是,我对编程世界还很陌生。据我了解,GMP 依赖于 MinGW 编译器。我目前 运行宁 Visual Studio 2015。
我浏览了不同的论坛和 Google,但我无法找到任何关于如何设置 GMP (and/with MinGW) 的新指南(2014 年之后),这意味着链接已损坏,引用不存在等。我也非常害怕开始篡改 Windows/Visual Studio(尝试 "install" (?) MinGW),因为我不想失去我的当前工作 setup/compiler(标准 Visual Studio 编译器 - 不知道它叫什么)。
无论如何,如果有人能给我指明正确的方向或推荐一些文献,我将不胜感激。
作为最后的手段,我正在考虑安装 Code::Blocks(标准 MinGW?!),但我担心它会弄乱我当前的 Visual Studio 设置?另一种可能性是创建一个带有 Ubuntu 和 运行 Code::Blocks 的虚拟机。无论如何,它看起来相当广泛,我更愿意留在 Windows 与 VS - 如果可能的话。
看看Boost.Multiprecision 以下代码适用于 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;
}
并打印 44850。例如,我定义了 int4096_t 整数类型(4096 位长度),但您可以使用预定义的 boost::multiprecision::int1024_t 或其他合适的类型。