数学建模社区-数学中国

标题: 谁有超长整数运算的好算法？ [打印本页]

---

作者: xuefu998    时间: 2005-2-1 16:07
标题: 谁有超长整数运算的好算法？

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

. F' J$ J! t9 Y* o" ]' ]- P7 Q

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

[em08][em08][em08]

---

作者: aftermath    时间: 2005-2-1 23:57

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

参考下面代码

#include <iostream> #include <memory> 1 i' m0 N. ]9 f9 M# include <string> using namespace std;

typedef long long hugeint;

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

struct xnum % @. V/ c9 o) T! ~0 M" I& l* Z3 \{ int Len; int Data[Capacity]; xnum() : Len(0) {} 3 W# C, b, q$ M: B# {( E6 o/ j 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[Len++] = V % Base; } % U a7 r& i4 ~1 O5 T7 ~: k xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } 3 I X. }$ T) O+ i; \ int& operator[](int Index) { return Data[Index]; } 9 A+ K. G4 B2 z; i J( f int operator[](int Index) const { return Data[Index]; } };

int compare(const xnum& A, const xnum& B) ; H) b: }2 C1 g. `+ W- [{ int I; ( p' `, _5 @( V6 E/ D+ o if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--); if (I < 0) return 0; ; v' o# P9 z: e& k/ J+ B: M return A[I] > B[I] ? 1 : -1; ' N: ^* Z% h3 x}

xnum operator+(const xnum& A, const xnum& B) { xnum R; ) |4 Y3 e* o& p7 @' S, { int I; 4 h. k* F, p- I; w1 V int Carry = 0; 1 B* e8 i( N I E7 r9 N% E" r# u% E for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) { 3 Z/ b9 \( f6 R0 k1 \ if (I < A.Len) Carry += A[I]; 2 N* _# C% f" b) I% p/ }- D if (I < B.Len) Carry += B[I]; R[I] = Carry % Base; 5 m Q/ r) \$ l. {6 c- [ Carry /= Base; } 0 b7 S! ~" ]" u# q4 I# q* V7 } R.Len = I; & s- I9 g7 l; F& j* [( x% x return R; - Y, O3 O, p7 m) G4 ]4 O& M}

xnum operator-(const xnum& A, const xnum& B) { xnum R; ) A6 x$ W# W0 q! f( I int Carry = 0; & y7 l( F* \; R R.Len = A.Len; " V- s! D* u* C+ K8 E int I; , s+ q& i- U7 Y) j for (I = 0; I < R.Len; I++) { ( b& S6 k7 b E9 N8 L* N9 H; M1 M9 p R[I] = A[I] - Carry; / w8 w# y! R- Y, k if (I < B.Len) R[I] -= B[I]; if (R[I] < 0) Carry = 1, R[I] += Base; else Carry = 0; } & L, m R# T# Y( c# ~" S while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; " Z. \1 W0 F8 U7 c+ |6 ^) L}

xnum operator*(const xnum& A, const int B) " \/ \; W3 d* J6 m: @4 E/ b{ int I; # |" Z9 B6 ?' J& f( p" L; }# c7 f0 ^) ] if (B == 0) return 0; xnum R; hugeint Carry = 0; 4 g1 F: i+ c/ U- O) X: E w7 ?, t for (I = 0; I < A.Len || Carry > 0; I++) 5 Q6 o; O3 p g" B% ^" n { if (I < A.Len) Carry += hugeint(A[I]) * B; 8 ]! e8 d/ t+ m Q0 \$ U! u! d7 H R[I] = Carry % Base; 8 ]: M g) J* e/ S Carry /= Base; 9 G; K! z/ j9 q7 b% E% R } N7 G/ ^; n* z R.Len = I; return R; }

xnum operator*(const xnum& A, const xnum& B) { ' V4 t$ U" d0 [. ^6 Q int I; if (B.Len == 0) return 0; ( G6 C; V0 M9 x0 k; k xnum R; $ T' \( {2 O. [ for (I = 0; I < A.Len; I++) { % E8 C7 e5 i% U) f+ g hugeint Carry = 0; 2 m2 L: S/ u: _& f i6 M for (int J = 0; J < B.Len || Carry > 0; J++) 2 |: c& _) d8 t; x7 U { if (J < B.Len) Carry += hugeint(A[I]) * B[J]; + K: A) ?/ \! F4 n; A if (I + J < R.Len) Carry += R[I + J]; if (I + J >= R.Len) R[R.Len++] = Carry % Base; else R[I + J] = Carry % Base; Carry /= Base; ( l& _, W" O1 M } ( y" s0 e8 d7 ^/ b! v' z2 n } return R; }

xnum operator/(const xnum& A, const int B) : D8 Y: t$ i* \2 x3 F{ ) R' K2 s6 j7 e1 H0 Q) A; B0 S xnum R; int I; * j3 G! G6 m G, l* X! n( H hugeint C = 0; 2 q. `# n, r& c" S+ {$ b for (I = A.Len - 1; I >= 0; I--) { : O% L5 x# C0 E$ e9 i: r# L. F' p C = C * Base + A[I]; % B3 X& e# A# y; K L Y R[I] = C / B; 5 R) P6 e F, E7 L) f C %= B; } R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; ! D5 T/ ^6 l C/ I1 c: ~# G return R; " `. A; z; E0 ?' W# K}

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[I]; Left = 0; ; P" K3 g* n K: j4 G Right = Base - 1; while (Left < Right) & b& D5 o7 x$ U" B6 ^3 ~ { + Q% m" J. C' [# V7 `. t0 ] Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; ( P( T, X1 q+ j+ N9 x+ ~7 g( h else Right = Mid - 1; } 9 S6 A6 h/ D& `) W, F% K" R R[I] = Left; Carry = Carry - B * Left; } " Q2 J) x$ i- o* J8 N- G( i R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; 3 {( ?$ b3 d* V' _% E+ m return R; } + @% n# X6 j S' w+ r, z5 `2 V; Wxnum operator%(const xnum& A, const xnum& B) { , r+ K6 K$ f8 ~3 R/ p. a int I; xnum R, Carry = 0; int Left, Right, Mid; - \ D; p! l* ?- D1 ?" R$ A2 L; [ for (I = A.Len - 1; I >= 0; I--) { 0 J% Z3 t+ ?/ S Carry = Carry * Base + A[I]; : ?' u% k( D, ^# T" F, Z/ L( v9 [ Left = 0; Right = Base - 1; while (Left < Right) 6 x. v8 z, A+ D3 f { : L- p0 b% s) A" G( p Mid = (Left + Right + 1) / 2; ' J0 E8 z/ g3 z3 \% d5 D2 b if (compare(B * Mid, Carry) <= 0) Left = Mid; ) u9 [7 o) C8 [ else Right = Mid - 1; 2 B( |2 t7 f$ r" s7 K- V } R[I] = Left; Carry = Carry - B * Left; / }$ }8 W* n5 ]% m' Q } ' G& j% x$ I' w- B5 d R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return Carry; }

istream& operator>>(istream& In, xnum& V) % K# n6 X* s+ e$ f! U9 x8 G{ char Ch; for (V = 0; In >> Ch;) { V = V * 10 + (Ch - '0'); if (cin.peek() <= ' ') break; } 0 ~& F/ }6 \$ A return In; 9 Y: }' U% z" B" F( N* H7 n/ {( [}

ostream& operator<<(ostream& Out, const xnum& V) { int I; Out << (V.Len == 0 ? 0 : V[V.Len - 1]); - a0 r2 p# e1 K' W9 V for (I = V.Len - 2; I >= 0; I--) for (int J = Base / 10; J > 0; J /= 10) Out << V[I] / J % 10; 9 [% I+ ^2 H1 a( m% e2 z& y return Out; } ) Y6 h- k9 X8 Q( o6 F/ c

---

作者: wangjiaqi49    时间: 2005-8-1 11:16
神人也，外星人！！太牛了

---

作者: cshdzxjtu    时间: 2005-8-12 21:46
强！

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5