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

xuefu998

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

' P+ X4 l, _% Z# H1 A1 ]0 O

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

[em08][em08][em08]

aftermath

高精度，用一个线性表保存一个大整数，具体说，将大整数写成p进制数，线性表的每一项存p进制其中一位。

参考下面代码

#include <iostream> #include <memory> ; S. x3 W7 [4 `- _# include <string> using namespace std;

typedef long long hugeint;

const int Base = 1000000000; const int Capacity = 200;

struct xnum * E1 W. h7 f8 c3 P9 y{ z2 f, D4 ?) e3 S int Len; 0 U, [0 Q3 {# ~' K: S4 N2 c int Data[Capacity]; xnum() : Len(0) {} # X y6 Z9 i7 V1 @# c/ o xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } 5 V" E. I8 ^; q; G xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; } xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } ( l% O. J' S x8 o. B int& operator[](int Index) { return Data[Index]; } + t# C- L( I! U3 @" q int operator[](int Index) const { return Data[Index]; } 0 I9 {9 t- D- G/ b. o- x% s};

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[I] == B[I]; I--); ) }6 A" J$ Z$ r% X7 G if (I < 0) return 0; $ Q3 R- a' _' |2 w return A[I] > B[I] ? 1 : -1; }

xnum operator+(const xnum& A, const xnum& B) { xnum R; & F7 D8 h# \, y int I; int Carry = 0; " c2 w; f) j7 b+ H* k/ |) ~; L for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) " \) \$ g1 U0 Y+ ~& R0 J { . h: X7 x9 L; V4 i if (I < A.Len) Carry += A[I]; / C9 z/ T- R3 Q0 U6 ^/ ? if (I < B.Len) Carry += B[I]; 3 G V9 ~2 \( _. j; o( M% ` R[I] = Carry % Base; # I: ?- d K: y Carry /= Base; } R.Len = I; return R; $ H7 H8 K4 [$ c) O# b R}

xnum operator-(const xnum& A, const xnum& B) 7 @3 ^; g4 N4 C6 l{ 3 m# I. X# b }8 _ xnum R; int Carry = 0; R.Len = A.Len; int I; for (I = 0; I < R.Len; I++) { 4 n5 _. W3 |: h- g/ h) l R[I] = A[I] - Carry; ) Q O& O! }; Z4 Z, O8 L if (I < B.Len) R[I] -= B[I]; if (R[I] < 0) Carry = 1, R[I] += Base; else Carry = 0; } ; Y( v* ]6 f1 L while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; }

xnum operator*(const xnum& A, const int B) $ r$ C Y+ ?& F: ~1 I{ int I; ! o; y2 T; S0 C7 _, k if (B == 0) return 0; xnum R; ' `, w7 V! t0 a( H2 s" S3 [2 o hugeint Carry = 0; . W9 Y) `: E4 m( ^5 [/ L# Y for (I = 0; I < A.Len || Carry > 0; I++) { if (I < A.Len) Carry += hugeint(A[I]) * B; R[I] = Carry % Base; 8 W$ @3 f6 C1 g1 u Carry /= Base; } R.Len = I; 0 y4 o9 V. q0 ^ 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++) 7 b7 p: n- y9 ~ { ' i: J; b" S5 B, g& W9 D hugeint Carry = 0; # U1 h2 ?, q; h' b3 b for (int J = 0; J < B.Len || Carry > 0; J++) 5 B$ [- q1 C$ ~. Z; D% m7 L { 3 Y, F9 I, P1 L6 b$ O6 S% r P if (J < B.Len) Carry += hugeint(A[I]) * B[J]; 5 v$ f3 c4 e2 } B8 j& H" W if (I + J < R.Len) Carry += R[I + J]; if (I + J >= R.Len) R[R.Len++] = Carry % Base; , i, s; M8 q' d$ N6 a( ? else R[I + J] = Carry % Base; Carry /= Base; , c; @0 d0 y3 g# R2 k } 1 u; m; t5 d+ k6 D3 i; h9 A } & T6 F; N! O3 F return R; 6 w# Q+ y1 p0 m6 N# \+ H4 s}

xnum operator/(const xnum& A, const int B) ) e8 f1 P2 n7 L6 g7 T* `; B7 V{ ( J* ?7 ]+ U2 z( u5 @& o xnum R; int I; hugeint C = 0; for (I = A.Len - 1; I >= 0; I--) $ P" K8 F2 ?$ g# B8 Q { : C2 k, S. O& ?6 X C = C * Base + A[I]; R[I] = C / B; C %= B; : @6 L i4 @: u7 @ } # M' ~ u. k s, Z* v; B* u) e0 _8 {5 ^ R.Len = A.Len; 9 K% d; v/ A" r/ t while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; % E( k2 `7 b! \/ g; t/ F}

xnum operator/(const xnum& A, const xnum& B) { 0 q" M' z& y: y0 ?6 {2 ] int I; & H/ R7 a6 C E& P xnum R, Carry = 0; 7 {1 V7 }" {6 D2 O2 [( H int Left, Right, Mid; ) Y9 _* ]8 P6 E+ j$ ? for (I = A.Len - 1; I >= 0; I--) - r$ Q: H! k6 W( y4 L T { Carry = Carry * Base + A[I]; # J: I; J! J p- o0 D6 \ Left = 0; Right = Base - 1; 8 ~! X1 m! `. h4 v+ m while (Left < Right) { Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; # {$ y- G5 q9 L# Z; Y } R[I] = Left; % N, \' e; O5 [4 B$ f Carry = Carry - B * Left; } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; Y5 X% k9 O4 j; H) h: h$ i} xnum operator%(const xnum& A, const xnum& B) 1 c3 |% z* t" t. {{ $ [# g+ [* e+ u; i int I; & C f) |% f+ _2 q8 I" r xnum R, Carry = 0; ! M$ _3 y6 `( B int Left, Right, Mid; + }% Z3 A, h- @2 [3 d for (I = A.Len - 1; I >= 0; I--) { Carry = Carry * Base + A[I]; ( K5 }' b7 B2 ` Left = 0; Right = Base - 1; - ~8 p$ [5 ~0 e' D while (Left < Right) { Mid = (Left + Right + 1) / 2; C ?* z( [; x3 d3 v' { if (compare(B * Mid, Carry) <= 0) Left = Mid; : E/ x- \( X; N9 ? else Right = Mid - 1; * f/ \7 d. @, d9 ~9 T6 U# c4 B } 3 {+ X; ~# X% H* a! ~2 S) n R[I] = Left; ( q$ o; F+ f" b8 R2 c Carry = Carry - B * Left; ' Y4 q& |0 n' j' h' }- g, y/ F7 m } ) |6 g% Q3 O; S& K+ i' j+ k. }0 ^ R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; ; Z/ }$ P* X! h8 q0 N/ e* p return Carry; ! Z4 o$ T8 I" w$ J$ w1 i}

istream& operator>>(istream& In, xnum& V) 4 t3 N) m3 K8 @3 ~9 A0 I{ - \9 e. t7 w9 F) ~9 p4 A# t# ?, R& A char Ch; for (V = 0; In >> Ch;) { + @. N% q4 Z! |; ~: E& Y V = V * 10 + (Ch - '0'); & Y2 d; x; ?& ?) H! \4 { if (cin.peek() <= ' ') break; , d$ I e7 a, ? } return In; }

ostream& operator<<(ostream& Out, const xnum& V) ! A, o. H# b3 u3 k! y$ j{ * c5 m- b4 k9 Q3 n int I; 5 y: Z1 Z: b$ R0 v0 F K Out << (V.Len == 0 ? 0 : V[V.Len - 1]); for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10; return Out; }

wangjiaqi49

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

cshdzxjtu

强！