[我正在编写一个生成大整数的程序，将它们保存在数组中，并执行一些基本操作，例如乘法或加法。
我真的很担心实际代码的性能，希望获得一些技巧或改进以使其更快。任何建议都是值得欢迎的，即使它改变了我的整个程序或数据类型。
我将在下面的代码中添加一些代码，以便您可以看到我正在使用的结构以及我如何尝试处理此B.I.N。：
unsigned int seed;
void LongNumInit( char *L, unsigned N )
{
for ( int i=0; i< N; i++ )
{
L[i] = myRandom() % 10; // 0 to 9 value
}
}
char LongNumAddition( char *Vin1, char *Vin2, char *Vout, unsigned N )
{
char CARRY = 0;
for ( int i=0; i< N; i++ )
{
char R = Vin1[i] + Vin2[i] + CARRY;
if ( R <= 9 )
{
Vout[i] = R; CARRY = 0;
}
else
{
Vout[i] = R-10; CARRY = 1;
}
}
return CARRY;
}
int main(int argc, char **argv)
{
int N=10000;
unsigned char *V1= (unsigned char*) malloc( N*sizeof(unsigned char) );
unsigned char *V2= (unsigned char*) malloc( N*sizeof(unsigned char) );
unsigned char *V3= (unsigned char*) malloc( N*sizeof(unsigned char) );
LongNumInit ( V1, N ); LongNumInit ( V2, N );
LongNumAddition ( V1, V2, V3, N );
}
PS：不能使用外部库，并且此工作要求以10为底。
由于现代拥有者在处理固定的位长数字时效率很高，所以为什么没有数组呢？
假设您使用unsigned long long。它们应为64位宽度，因此最大可能的unsigned long long应为2^64 - 1。让我们将任何数字表示为数字的集合，如下所示：
-big_num = ( n_s, n_0, n_1, ...)
-n_s仅需使用0和1来表示+和-号
-n_0表示0到10 ^ a -1之间的数字（指数a有待确定）
-n_1将代表10 ^ a和10 ^（a + 1）-1之间的数字等等，等等...
确定a：
所有n_必须以10^a-1为界。因此，当添加两个big_num时，这意味着我们需要如下添加n_：
// A + B = ( (to be determent later),
// bound(n_A_1 + n_B_1) and carry to next,
// bound(n_A_2 + n_B_2 + carry) and carry to next,
// ...)
边界可以通过以下方式完成：
bound(n_A_i + n_B_i + carry) = (n_A_i + n_B_i + carry)%(10^a)
因此，将i+1的进位确定为：
// carry (to be used in i+1) = (n_A_i + n_B_i + carry)/(10^a)
// (division of unsigned in c++ will floor the result by construction)
这告诉我们最坏的情况是carry = 10^a -1，因此最差的加法(n_A_i + n_B_i + carry)是：(worst case) (10^a-1) + (10^a-1) + (10^a-1) = 3*(10^a-1)因为类型是无符号的，所以如果我们不想在此加法上发生溢出，我们必须将指数绑定为：
// 3*(10^a-1) <= 2^64 - 1, and a an positive integer
// => a <= floor( Log10((2^64 - 1)/3 + 1) )
// => a <= 18
因此，现在已将最大可能的a固定为18，因此用n_表示的最大可能的unsigned long long为10^18 -1 = 999,999,999,999,999,999。通过此基本设置，现在让我们看一些实际的代码。现在，我将使用std::vector来保存我们讨论过的big_num，但这可以更改：
// Example code with unsigned long long
#include <cstdlib>
#include <vector>
//
// FOR NOW BigNum WILL BE REPRESENTED
// BY std::vector. YOU CAN CHANGE THIS LATTER
// DEPENDING ON WHAT OPTIMIZATIONS YOU WHANT
//
using BigNum = std::vector<unsigned long long>;
// suffix ULL garanties number be interpeted as unsigned long long
#define MAX_BASE_10 999999999999999999ULL
// random generate big number
void randomize_BigNum(BigNum &a){
// assuming MyRandom() returns a random number
// of type unsigned long long
for(size_t i=1; i<a.size(); i++)
a[i] = MyRandom()%(MAX_NUM_BASE_10+1); // cap the numbers
}
// wrapper functions
void add(const BigNum &a, const BigNum &b, BigNum &c); // c = a + b
void add(const BigNum &a, BigNum &b); // b = a + b
// actual work done here
void add_equal_size(const BigNum &a, const BigNum &b, BigNum &c, size_t &N);
void add_equal_size(const BigNum &a, const BigNum &b, size_t &N);
void blindly_add_one(BigNum &c);
// Missing cases
// void add_equal_size(BigNum &a, BigNum &b, BigNum &c, size_t &Na, size_t &Nb);
// void add_equal_size(BigNum &a, BigNum &b, size_t &Na, size_t &Nb);
int main(){
size_t n=10;
BigNum a(n), b(n), c(n);
randomize_BigNum(a);
randomize_BigNum(b);
add(a,b,c);
return;
}
包装函数应如下所示。他们将防止出现错误的数组调用大小：
// To do: add support for when size of a,b,c not equal
// c = a + b
void add(const BigNum &a, const BigNum &b, BigNum &c){
c.resize(std::max(a.size(),b.size()));
if(a.size()==b.size())
add_equal_size(a,b,c,a.size());
else
// To do: add_unequal_size(a,b,c,a.size(),b.size());
return;
};
// b = a + b
void add(const BigNum &a, const BigNum &b){
if(a.size()==b.size())
add_equal_size(a,b,a.size());
else{
b.resize(a.size());
// To do: add_unequal_size(a,b,a.size());
}
return;
};
这里的主要工作将在这里完成（如果您知道自己在做什么，则可以直接调用而跳过函数调用）：
// If a,b,c same size array
// c = a + b
void add_equal_size(const BigNum &a, const BigNum &b, BigNum &c, const size_t &N){
// start with sign of c is sign of a
// Specific details follow on whether I need to flip the
// sign or not
c[0] = a[0];
unsigned long long carry=0;
// DISTINGUISH TWO GRAND CASES:
//
// a and b have the same sign
// a and b have oposite sign
// no need to check which has which sign (details follow)
//
if(a[0]==b[0]){// if a and b have the same sign
//
// This means that either +a+b or -a-b=-(a+b)
// In both cases I just need to add two numbers a and b
// and I already got the sign of the result c correct form the
// start
//
for(size_t i=1; i<N;i++){
c[i] = (a[i] + b[i] + carry)%(MAX_BASE_10+1);
carry = c[i]/(MAX_BASE_10+1);
}
if(carry){// if carry>0 then I need to extend my array to fit the final carry
c.resize(N+1);
c[N]=carry;
}
}
else{// if a and b have opposite sign
//
// If I have opposite sign then I am subtracting the
// numbers. The following is inspired by how
// you can subtract two numbers with bitwise operations.
for(size_t i=1; i<N;i++){
c[i] = (a[i] + (MAX_BASE_10 - b[i]) + carry)%(MAX_BASE_10+1);
carry = c[i]/(MAX_BASE_10+1);
}
if(carry){ // I carried? then I got the sign right from the start
// just add 1 and I am done
blindly_add_one(c);
}
else{ // I didn't carry? then I got the sign wrong from the start
// flip the sign
c[0] ^= 1ULL;
// and take the compliment
for(size_t i=1; i;<N;i++)
c[i] = MAX_BASE_10 - c[i];
}
}
return;
};
关于// if a and b have opposite sign案例的一些细节如下：让我们以10为底进行工作。假设我们要减去a - b，然后将其转换为加法。定义以下操作：
让数字di的基数以10为基数。那么任何数字都是n = d1 + 10*d2 + 10*10*d3...现在将一个数字的补码定义为：
`compliment(d1) = 9-d1`
然后对数字n的补充是：
compliment(n) = compliment(d1)
+ 10*compliment(d2)
+ 10*10*compliment(d3)
...
考虑两种情况，a>b和a<b：
a>b的例子：至少说a=830和b=126。进行以下830 - 126 -> 830 + compliment(126) = 830 + 873 = 1703确定，因此，如果a>b我丢掉1，然后加1，结果是704！
a<b的例子：至少说a=126和b=830。是否执行以下126 - 830 -> 126 + compliment(830) = 126 + 169 = 295 ...？好吧，如果我称赞它呢？compliment(295) = 704!!!因此，如果a<b我已经有了相反符号的结果。
就我们而言，由于数组中的每个数字都以MAX_BASE_10为界，所以我们对数字的称赞是
compliment(n) = MAX_BASE_10 - n
因此使用此恭维将减法转换为加法我只需要注意如果我在加法的结尾（a>b情况）。现在的算法是
找到进位->（na_i +称赞（nb_i）+进位（i-1））/ MAX_BASE_10
继续添加数组编号...
如果要携带，在数组末尾，请忘记携带并加1。否则取结果的称赞
此“加一”由另一个功能完成：
// Just add 1, no matter the sign of c
void blindly_add_one(BigNum &c){
unsigned long long carry=1;
for(size_t i=1; i<N;i++){
c[i] = carry%(MAX_BASE_10+1);
carry = c[i]/(MAX_BASE_10+1);
}
if(carry){ // if carry>0 then I need to extend my basis to fit the number
c.resize(N+1);
c[N]=carry;
}
};
到这里为止。特别是在此代码中，请不要忘记在函数开始时将c的符号设置为a的符号。因此，如果我随身携带，则意味着我有|a|>|b|，而我做了+a-b>0或-a+b=-(a-b)<0。无论哪种情况，将结果c符号设置为a符号都是正确的。如果我不随身携带|a|<|b|和+a-b<0或-a+b=-(a-b)>0。无论哪种情况，将结果c符号设置为a符号都是错误的，因此如果我不携带，则需要翻转符号。
以下功能的操作方式与上述功能相同，只是c = a + b的剂量不等于b = a + b
// same logic as above, only b = a + b
void add_equal_size(BigNum &a, BigNum &b, size_t &N){
unsigned long long carry=0;
if(a[0]==b[0]){// if a and b have the same sign
for(size_t i=1; i<N;i++){
b[i] = (a[i] + b[i] + carry)%(MAX_BASE_10+1);
carry = b[i]/(MAX_BASE_10+1);
}
if(carry){// if carry>0 then I need to extend my basis to fit the number
b.resize(N+1);
b[N]=carry;
}
}
else{ // if a and b have oposite sign
b[0] = a[0];
for(size_t i=1; i<N;i++){
b[i] = (a[i] + (MAX_BASE_10 - b[i]) + carry)%(MAX_BASE_10+1);
carry = b[i]/(MAX_BASE_10+1);
}
if(carry){
add_one(b);
}
else{
b[0] ^= 1ULL;
for(size_t i=1; i;<N;i++)
b[i] = MAX_BASE_10 - b[i];
}
}
return;
};
这是关于如何使用数组中的无符号数字表示非常大的整数的基本设置。
从这里去哪里
他们从现在开始要做很多事情来优化代码，我会提到一些我能想到的：
--尝试用可能的BLAS调用替换附加数组
-请确保您正在使用矢量化。根据编写循环的方式，您可能会或可能不会生成矢量化代码。如果阵列变大，您可能会从中受益。
-本着上述精神，请确保您在内存中已正确对齐数组以实际利用矢量化。根据我的理解std::vector不能保证对齐。两者均不致盲malloc。我认为boost库具有向量版本，在这里您可以声明固定对齐方式，在这种情况下，您可以为unsigned long long数组请求64位对齐数组。另一个选择是拥有自己的类，该类使用自定义定位器来管理原始指针和剂量对齐的分配。从aligned_malloc借用aligned_free和https://embeddedartistry.com/blog/2017/02/22/generating-aligned-memory/，您可以拥有一个类似的类来替换std :: vector：
// aligned_malloc and aligned_free from:
// https://embeddedartistry.com/blog/2017/02/22/generating-aligned-memory/
// wrapping in absolutly minimal class to handle
// memory allocation and freeing
class BigNum{
private:
unsigned long long *ptr;
size_t size;
public:
BigNum() : ptr(nullptr)
, size(0)
{};
BigNum(const size_t &N) : ptr(nullptr)
, size(N)
{
resize(N);
}
// Defining destructor this will now delete copy and move constructor and assignment. Make your own if you need them
~BigNum(){
aligned_free(ptr);
}
// Access an object in aligned storage
const unsigned long long& operator[](std::size_t pos) const{
return *reinterpret_cast<const unsigned long long*>(&ptr[pos]);
}
// return my size
void size(){
return size;
}
// resize memory allocation
void resize(const size_t &N){
size = N;
if(N){
void* temp = aligned_malloc(ptr,N+1); // N+1, always keep first entry for the sign of BigNum
if(temp!=nullptr)
ptr = static_cast<unsigned long long>(temp);
else
throw std::bad_alloc();
}
else{
aligned_free(ptr);
}
}
};
您可以使用Fast Fourier Transform在O（n log n）中执行大整数乘法。