数学建模社区-数学中国

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

---

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

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

3 d( k/ Y5 f0 P

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

[em08][em08][em08]

---

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

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

参考下面代码

#include <iostream> #include <memory> # include <string> ) b' {; I) M% \7 C! L7 A7 s4 W; Fusing namespace std;

typedef long long hugeint;

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

struct xnum 3 E( Z+ K$ G( H; `{ + ^+ ?# U5 a0 X* M0 V5 A2 G int Len; # S; i6 F$ n6 u5 a5 p: [0 M int Data[Capacity]; xnum() : Len(0) {} 0 K' ^% ^" c) l! g" k# D' x xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } ( ~4 Z" ]! Z# z xnum(int V) : Len(0) { for (; V > 0; V /= Base) Data[Len++] = V % Base; } 4 G. {( ]9 Z5 c( j, f: [ xnum& operator=(const xnum& V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof *Data); return *this; } ( q# t' Z& ^# j3 d int& operator[](int Index) { return Data[Index]; } int operator[](int Index) const { return Data[Index]; } };

int compare(const xnum& A, const xnum& B) 0 h4 O* I/ r- f$ _- {2 ~{ int I; - Q) q0 k8 c1 y1 p 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; 3 r' f) M1 b8 ]/ N( Q; S& c$ A return A[I] > B[I] ? 1 : -1; , j& \6 H+ x. Y}

xnum operator+(const xnum& A, const xnum& B) { 5 ? o6 }: i6 G# f$ ? xnum R; ! q* ^4 J$ y/ X2 g5 W" A int I; ' I4 W- B0 j5 g) @: h5 ]( H* k int Carry = 0; for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) 5 G: w4 P' S" m { 9 e% ?' V, n1 K# D) u: R if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; , s* l( c |+ @+ x! V+ \" f R[I] = Carry % Base; Carry /= Base; } 4 S/ N' c& S1 @* F R.Len = I; return R; }

xnum operator-(const xnum& A, const xnum& B) # b1 `: G- t( d8 E P& _6 I{ 3 t: u& Q. b2 j* \ xnum R; & N$ f2 w( s T* { } int Carry = 0; + D9 N8 B( Y* d4 ^& b- l) k% y R.Len = A.Len; int I; 5 A8 V+ ]/ B) U$ g$ }: t! n for (I = 0; I < R.Len; I++) { 3 K, H0 j9 n; h% A$ L O9 x4 e1 b5 B R[I] = A[I] - Carry; if (I < B.Len) R[I] -= B[I]; if (R[I] < 0) Carry = 1, R[I] += Base; 2 q0 d; L4 x" q else Carry = 0; 2 B, |, o9 ?0 K" ?( R8 { } # `- o* U0 R! T" s2 c ~: o3 t/ H while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; ^* Z8 C' ?+ u# k' H* ?1 ]7 I2 [ return R; ) \9 j5 |( }% b- q}

xnum operator*(const xnum& A, const int B) { " V2 [- f& Z0 d+ Z int I; if (B == 0) return 0; xnum R; , P/ r ]5 O6 a5 j/ d8 p hugeint Carry = 0; : Q) b; T1 z* ?% b- O for (I = 0; I < A.Len || Carry > 0; I++) * {! e) n' }5 H; ~8 B { if (I < A.Len) Carry += hugeint(A[I]) * B; R[I] = Carry % Base; Carry /= Base; } R.Len = I; 4 `. m- g2 p$ x0 w return R; 1 x8 ^* x3 r* M9 a}

xnum operator*(const xnum& A, const xnum& B) { int I; if (B.Len == 0) return 0; & D3 V+ D5 c7 D; N v8 [ xnum R; for (I = 0; I < A.Len; I++) 9 b+ f1 T' p* u. b { 4 h- `" }% L4 ^8 u( G hugeint Carry = 0; for (int J = 0; J < B.Len || Carry > 0; J++) { ! Z! \. J- y3 K$ [0 f* [ if (J < B.Len) Carry += hugeint(A[I]) * B[J]; - z. g/ n+ i0 M' t if (I + J < R.Len) Carry += R[I + J]; ! ~7 s$ h5 o r4 f3 W+ [1 p if (I + J >= R.Len) R[R.Len++] = Carry % Base; else R[I + J] = Carry % Base; 0 a' z" _4 s0 J Carry /= Base; : f! `, u" a/ p2 \ } 5 h+ n! ^: k3 |; d } return R; 1 b3 n' ?6 a2 l8 w: F}

xnum operator/(const xnum& A, const int B) 8 q1 T- }4 {6 h: K9 a{ xnum R; % O# o& `9 L8 t3 I* \8 i int I; / F- {* h7 l" M1 ~ hugeint C = 0; $ S9 n. ~; ] m9 A for (I = A.Len - 1; I >= 0; I--) 8 Y; W, ]5 j) v7 o. B& M { C = C * Base + A[I]; R[I] = C / B; 9 a' |# C( g# M- I7 j1 x C %= B; N2 H/ q# p8 R! ^, r: M } % K k7 [* K) D: `: j3 t R.Len = A.Len; : Z! ~/ v. d$ g! E2 M while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; 6 p. a5 i- K( T. N}

xnum operator/(const xnum& A, const xnum& B) & A/ q3 N% }! r3 V0 M{ int I; xnum R, Carry = 0; 5 u* D* D. ?1 L4 |( a1 r* u+ ]3 D int Left, Right, Mid; 2 E4 B8 f, H+ \6 S: F3 ]0 q; z for (I = A.Len - 1; I >= 0; I--) 8 Y" n7 X6 l1 X$ y* n$ Q" E+ l { 7 W8 J9 N* d& M5 [( U1 |( K' K Carry = Carry * Base + A[I]; " [ h3 o* U( n' w Left = 0; 3 X: G5 H+ B2 d X' V Right = Base - 1; while (Left < Right) { Mid = (Left + Right + 1) / 2; / t1 m8 d Q2 |* p- I# q! _ if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; j4 c! _& K+ `; N, {1 r" T } R[I] = Left; Carry = Carry - B * Left; 9 o0 \1 r! j; `/ U } 0 Y) Q6 W- r) m! O! j2 Z R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; % e! W, M0 I. P1 H; o return R; ) a7 C3 G1 E+ ~} 4 Z, H- _9 L, Wxnum operator%(const xnum& A, const xnum& B) { % ~3 V) k* z, n, e/ Y, B/ t int I; 5 q3 K7 c3 y- W0 ?& k R xnum R, Carry = 0; int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) { Carry = Carry * Base + A[I]; . F7 E9 h7 ]$ s/ b: ~) c8 U, k2 n Left = 0; $ X3 g: P5 ?) E0 S- K Right = Base - 1; while (Left < Right) { : j0 ]6 P+ p: r3 J Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; else Right = Mid - 1; 2 O( d4 p& L% m O% G } R[I] = Left; ) X7 G% {0 i h6 L3 ? Carry = Carry - B * Left; } 2 _5 [; L* Y1 x% q) k* _ R.Len = A.Len; while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return Carry; }

istream& operator>>(istream& In, xnum& V) 7 F7 Z+ T6 l0 A% T8 C" W{ char Ch; for (V = 0; In >> Ch;) { E( ~' \- e1 }" o V = V * 10 + (Ch - '0'); if (cin.peek() <= ' ') break; } return In; }

ostream& operator<<(ostream& Out, const xnum& V) { ! B D( \8 K+ @. j) r) } int I; c) N5 B0 a: a6 N: J* v- y 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    时间: 2005-8-1 11:16
神人也，外星人！！太牛了

---

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

---

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

Powered by Discuz! X2.5