N：用于 Windows 的实验性多线程大数库
4.85/5 (20投票s)
这个类允许任意大小的大数进行数学运算，只要你的可用内存能够处理它。
引言
是的，这并非最优，仅适用于 Windows，尚未完全完成。为什么还要费心呢？
不知道，只是因为你我都有兴趣了解底层的东西。继续阅读吧！
背景
数字很棒，但它们的大小只能达到 2^64 的无符号长整型。有时，你需要处理更大的数字（例如，在密码学中）。这个类允许任意大小的大数进行数学运算，只要你的可用内存能够处理它。
多核库
对于多核操作，该库使用了我自己的 tpoollib，它使用了新的 Vista+ API 来实现线程池。
N 类的内部结构
N 将其所有数字存储在向量 <D> 中（D 目前是 int 的 typedef），作为十进制数组、一个基本值（默认为 10）以了解数字是什么进制的，以及一个布尔标志来保存符号值。构造函数可以通过整数或 string 来完成
N n(5LL);
N n(-12438LL);
N n("384747274747282882818373"); // If a non digit is encountered, parsing stops
N n("-274727372737");
N n("111",2); // n = 7
N 还有一个成员函数 ParseBase
N n;
n.ParseBase("FFFF",16); // n = 65535
N 的表示和访问
在库的调试版本中，在每次更改 N 的操作之后，都会调用一个特殊函数来帮助你进行调试。
N::operator[](size_t) 给出了从右边开始的特定数字，例如如果 n = 12345，那么 n[0] 是 5。如果指定的数字超过了位数，该函数不会崩溃，而是返回 0，以便在加法或乘法中使用。
函数 s(unsigned long long base = b); 返回 N 的字符串表示形式，以指定的进制系统表示。
函数 tobase(unsigned long long nb) 返回一个新的 N，它以不同的进制系统存储相同的值。
函数 upperpart() 和 lowerpart() 返回数字的一个子部分
N a("12345");
auto a2 = a.upperpart(2); // a2 = 12
auto a3 = a.lowerpart(3); // a3 = 345
a.Set(16LL);
auto str = a.s(); // str = "16"
str = a.tobase(2).s(); // str = "10000"
str = a.tobase(16).s(); // str = "10"
str = a.tobase(10).s(); / str = "16"
单个加法
将两个相同符号的 N 相加（通过运算符或函数调用，或者减去不同符号的 N）最终会调用
static N w_add(const N& n1, const N& n2);
此函数循环遍历数字的所有数字，并将它们与进位相加
static N w_add(const N& n1, const N& n2)
{
if (n1.b != n2.b)
return w_add(n1, n2.tobase(n1.b));
if (n1.m != n2.m)
{
if (n1.m)
return w_subx(n2, n1.negative());
return w_subx(n1, n2.negative());
}
if (n1.n.empty()) return n2;
if (n2.n.empty()) return n1;
N n;
n.ChangeInternalBase(n1.b);
n.n.reserve(max(n1.NumDigits(), n2.NumDigits()));
D carry = 0;
if (n1.m && n2.m)
n.m = true;
size_t j = 0;
for (size_t i = 0; i < n1.NumDigits() || i < n2.NumDigits() ; i++)
{
j = i;
D sum = n1[i] + n2[i] + carry;
carry = 0;
if (sum >= n1.b)
{
carry = 1;
sum -= n1.b;
}
n.n.push_back(sum);
}
n.n.push_back(carry);
n.RemoveZeroes();
}
单个减法
减法最终调用函数 w_subx()
static N w_subx(const N& n1, const N& n2)
{
if (n1.m != n2.m)
return w_add(n1, n2.negative());
if (n1.absolute() < n2.absolute())
return w_subx(n2, n1).negative();
if (n2.IsZero())
return n1;
if (n1.IsZero())
return n2.negative();
N n;
n.ChangeInternalBase(n1.b);
n.m = n1.m;
int carry = 0;
for (size_t i = 0; i < n1.NumDigits() || i < n2.NumDigits(); i++)
{
signed long long sum = n1[i] - n2[i] + carry;
carry = 0;
if (sum < 0)
{
sum = n1.b + sum;
carry = -1;
}
n.n.push_back(sum);
}
n.n.push_back(carry);
n.RemoveZeroes();
return n;
}
逻辑运算
w_logical() 用于 AND、OR 和 XOR 等操作。它总是将数字转换为二进制。请注意，默认情况下，运算符 ^ 执行 w_pow()，除非两个操作数都是二进制格式。
static N w_logical(const N& n1, const N& n2,int x)
{
if (n1.b != 2)
return w_logical(n1.tobase(2),n2,x);
if (n2.b != 2)
return w_logical(n1, n2.tobase(2),x);
N n;
n.ChangeInternalBase(2);
n.n.reserve(max(n1.NumDigits(), n2.NumDigits()));
for (size_t i = 0; i < n1.NumDigits() || i < n2.NumDigits(); i++)
{
D sum = 0;
if (x == 0) sum = n1[i] & n2[i];
if (x == 1) sum = n1[i] | n2[i];
if (x == 2) sum = n1[i] ^ n2[i];
n.n.push_back(sum);
}
n.RemoveZeroes();
return n;
}
N a("10",2);
N b("11",2);
auto r = a | b; // r = 5
此外，cshl()、cshr()、shl2()、shl2()、negative() 和 absolute() 执行相关的逻辑运算。shl() 和 shr() 执行自 shl/shr，而其他函数生成一个新的 N。
乘法
乘法函数创建一个包含所有乘法的 vector<N>，然后将它们加在一起
static N w_mul(const N& n1, const N& n2)
{
if (n1.b != n2.b)
return w_mul(n1, n2.tobase(n1.b));
N n;
n.ChangeInternalBase(n1.b);
vector<N> addiz;
for (size_t i = 0; i < n1.n.size(); i++)
{
D d1 = n1.n[i];
N addi;
addi.n.reserve(i + n2.n.size());
for (size_t j = 0; j < i; j++)
addi.n.push_back(0);
D carry = 0;
for (size_t y = 0; y < n2.n.size(); y++)
{
D d2 = n2.n[y];
D dm = (d1*d2) + carry;
carry = 0;
carry = dm / n1.b;
dm %= n1.b;
addi.n.push_back(dm);
}
addi.n.push_back(carry);
addi.RemoveZeroes();
addiz.push_back(addi);
}
for (auto& a : addiz)
n += a;
if (n1.m != n2.m)
n.m = true;
return n;
}
除法
除法函数（由除法相关的东西和诸如 /,%,/=,%= 等运算符使用）返回结果和余数的元组
static tuple<N, N> w_div(const N& n1, const N& n2,bool NoChangeBase = false)
{
if (n1.b != n2.b && NoChangeBase == false)
return w_div(n1.b, n2.tobase(n1.b));
if (n2 > n1)
{
N res = n1;
return std::make_tuple<N, N>(0LL, std::forward<N>(res));
}
if (n2 == n1)
return std::make_tuple<N, N>(1LL, 0LL);
N rem = n1;
N res;
res.ChangeInternalBase(n1.b);
for (;;)
{
auto nd2 = n2.NumDigits();
auto upper = rem.upperpart(nd2);
if (upper < n2)
{
nd2++;
upper = rem.upperpart(nd2);
if (upper < n2)
{
// End...
return std::make_tuple<N, N>(forward<N>(res), forward<N>(rem));
}
}
// This needs optimization
unsigned long long js = 9;
N m1;
for (; js >= 1; js--)
{
m1 = w_mul(n2, js);
if (m1 < upper)
break;
}
res.n.insert(res.n.begin(),js);
upper -= m1;
upper.shl(rem.NumDigits() - nd2);
upper += rem.lowerpart(rem.NumDigits() - nd2);
rem = upper;
}
}
幂
没什么太复杂的。
static N w_pow(const N& n1, const N& n2)
{
N z = n1;
if (n2 == 0ll)
return 1ll;
if (n2 == 1ll)
return n1;
if (n1 == 1ll)
return 1ll;
for (N j = 1ll; j < n2; ++j)
z *= n1;
return z;
}
N a("-5");
auto a2 = N::w_pow(a, 3LL); // a2 = -125
多核操作
多核加法接受一个 N 的向量，并将它们成对相加，然后使用结果调用自身，直到只有 2 个数字需要相加
static N w_add2(vector<N>& n, tpoollib::tpool<>& pool)
{
if (n.size() == 0)
return 0LL;
if (n.size() == 1)
return n[0];
if (n.size() == 2)
{
N res = n[0];
res += n[1];
return res;
}
struct Z
{
N* n1;
N* n2;
N* res;
};
vector<Z> z(n.size());
vector<N> res(n.size() / 2);
for (size_t i = 0; i < n.size(); i += 2)
{
if (i == (n.size() - 1))
break; // odd number of additions
auto a = [](PTP_CALLBACK_INSTANCE, PVOID j, PTP_WORK)
{
Z* z = (Z*)j;
*z->res = w_add(*z->n1,*z->n2);
};
Z& zz = z[i];
zz.n1 = &n[i];
zz.n2 = &n[i + 1];
zz.res = &res[i / 2];
auto wo = pool.CreateItem<PTP_WORK, PTP_WORK_CALLBACK>(a, (PVOID)&zz);
pool.RunItem(wo);
}
pool.Join();
if (n.size() % 2)
res.push_back(n[n.size() - 1]);
return w_add2(res,pool);
}
它使用一个临时结构体 Z 将其传递给 threadpool 函数。
多核乘法创建一个乘法向量，然后使用 w_add2() 将它们相加
static N w_mul2(const N& n1, const N& n2, tpoollib::tpool<>& pool)
{
size_t muls = n1.NumDigits() * n2.NumDigits();
vector<N> a;
a.reserve(muls);
for (size_t i = 0; i < n1.NumDigits(); i++)
{
for (size_t ii = 0; ii < n2.NumDigits(); ii++)
{
N rr;
D d1 = n1[i];
D d2 = n2[ii];
unsigned long long r = d1 * d2;
rr = r;
rr.shl(ii + i);
a.push_back(rr);
}
}
return w_add2(a,pool);
}
这可以进行优化，例如在多核 for 循环本身中找到总和。
多核幂运算只使用 w_mul2()
static N w_pow2(const N& n1, const N& n2,tpoollib::tpool<>& pool)
{
N z = n1;
if (n2 == 0ll)
return 1ll;
if (n2 == 1ll)
return n1;
if (n1 == 1ll)
return 1ll;
for (N j = 1ll; j < n2; ++j)
z = w_mul2(z, n1,pool);
return z;
}
这也可以进行优化。
代码
全部包含在一个头文件中，欢迎增强！
历史
- 2016 年 8 月 11 日：首次发布