谁有超长整数运算的好算法？

xuefu998 发表于 2005-2-1 16:07

谁有超长整数运算的好算法？
现在CPU还是64位的，量长整数不过int64（2^64），超过这个数的整数怎么办，如1000！等，请各位有心人指点迷津。

aftermath 发表于 2005-2-1 23:57

高精度，用一个线性表保存一个大整数，具体说，将大整数写成p进制数，线性表的每一项存p进制其中一位。参考下面代码#include <iostream>
#include <memory>
# include <string>
using namespace std;typedef long long hugeint;const int Base = 1000000000;
const int Capacity = 200;struct xnum
{
int Len;
int Data;
xnum() : Len(0) {}
xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); }
xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data = V % Base; }
xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; }
int& operator[](int Index) { return Data; }
int operator[](int Index) const { return Data; }
};
int compare(const xnum& A, const xnum& B)
{
int I;
if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1;
for (I = A.Len - 1; I >= 0 && A == B; I--);
if (I < 0) return 0;
return A > B ? 1 : -1;
}xnum operator+(const xnum& A, const xnum& B)
{
xnum R;
int I;
int Carry = 0;
for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++)
{
 if (I < A.Len) Carry += A;
 if (I < B.Len) Carry += B;
 R = Carry % Base;
 Carry /= Base;
}
R.Len = I;
return R;
}xnum operator-(const xnum& A, const xnum& B)
{
xnum R;
int Carry = 0;
R.Len = A.Len;
int I;
for (I = 0; I < R.Len; I++)
{
 R = A - Carry;
 if (I < B.Len) R -= B;
 if (R < 0) Carry = 1, R += Base;
 else Carry = 0;
}
while (R.Len > 0 && R == 0) R.Len--;
return R;
}xnum operator*(const xnum& A, const int B)
{
int I;
if (B == 0) return 0;
xnum R;
hugeint Carry = 0;
for (I = 0; I < A.Len || Carry > 0; I++)
{
 if (I < A.Len) Carry += hugeint(A) * B;
 R = Carry % Base;
 Carry /= Base;
}
R.Len = I;
return R;
}xnum operator*(const xnum& A, const xnum& B)
{
int I;
if (B.Len == 0) return 0;
xnum R;
for (I = 0; I < A.Len; I++)
{
 hugeint Carry = 0;
 for (int J = 0; J < B.Len || Carry > 0; J++)
 {
if (J < B.Len) Carry += hugeint(A) * B;
if (I + J < R.Len) Carry += R;
if (I + J >= R.Len) R = Carry % Base;
else R = Carry % Base;
Carry /= Base;
 }
}
return R;
}xnum operator/(const xnum& A, const int B)
{
xnum R;
int I;
hugeint C = 0;
for (I = A.Len - 1; I >= 0; I--)
{
 C = C * Base + A;
 R = C / B;
 C %= B;
}
R.Len = A.Len;
while (R.Len > 0 && R == 0) R.Len--;
return R;
}xnum operator/(const xnum& A, const xnum& B)
{
int I;
xnum R, Carry = 0;
int Left, Right, Mid;
for (I = A.Len - 1; I >= 0; I--)
{
 Carry = Carry * Base + A;
 Left = 0;
 Right = Base - 1;
 while (Left < Right)
 {
Mid = (Left + Right + 1) / 2;
if (compare(B * Mid, Carry) <= 0) Left = Mid;
else Right = Mid - 1;
 }
 R = Left;
 Carry = Carry - B * Left;
}
R.Len = A.Len;
while (R.Len > 0 && R == 0) R.Len--;
return R;
}
xnum operator%(const xnum& A, const xnum& B)
{
int I;
xnum R, Carry = 0;
int Left, Right, Mid;
for (I = A.Len - 1; I >= 0; I--)
{
 Carry = Carry * Base + A;
 Left = 0;
 Right = Base - 1;
 while (Left < Right)
 {
Mid = (Left + Right + 1) / 2;
if (compare(B * Mid, Carry) <= 0) Left = Mid;
else Right = Mid - 1;
 }
 R = Left;
 Carry = Carry - B * Left;
}
R.Len = A.Len;
while (R.Len > 0 && R == 0) R.Len--;
return Carry;
}istream& operator>>(istream& In, xnum& V)
{
char Ch;
for (V = 0; In >> Ch;)
{
 V = V * 10 + (Ch - '0');
 if (cin.peek() <= ' ') break;
}
return In;
}ostream& operator<<(ostream& Out, const xnum& V)
{
int I;
Out << (V.Len == 0 ? 0 : V);
for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V / J % 10;
return Out;
}

wangjiaqi49 发表于 2005-8-1 11:16

神人也，外星人！！太牛了

cshdzxjtu 发表于 2005-8-12 21:46

强！

页: [1]

数学建模社区-数学中国's Archiver

谁有超长整数运算的好算法？