数学建模社区-数学中国

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

---

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

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

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

[em08][em08][em08]

---

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

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

参考下面代码

#include <iostream> 0 @) a0 c- ^ O#include <memory> # include <string> using namespace std;

typedef long long hugeint;

const int Base = 1000000000; [7 B* x$ @+ t. o) ]3 N( Z: p- nconst int Capacity = 200;

struct xnum { int Len; ( \: ]* f- j: v5 }$ a int Data[Capacity]; 5 _. ~/ X5 d. W5 e g! {) z( p" B xnum() : Len(0) {} xnum(const xnum& V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof *Data); } ; [ m9 c5 b W; c& F 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; } " q3 g. Z, g2 s5 d: z: s' x int& operator[](int Index) { return Data[Index]; } int operator[](int Index) const { return Data[Index]; } # C; s9 _% ^! T4 V( H2 k( \& l) N. M! F};

int compare(const xnum& A, const xnum& B) . q- y M# V- g{ int I; 9 f3 w3 g9 H: ~! R( p7 B if (A.Len != B.Len) return A.Len > B.Len ? 1 : -1; for (I = A.Len - 1; I >= 0 && A[I] == B[I]; I--); . i) O- w1 x4 P$ C& m if (I < 0) return 0; ' d- S& B% U& e6 m6 N, o return A[I] > B[I] ? 1 : -1; }

xnum operator+(const xnum& A, const xnum& B) 7 S& W' P8 i2 M& C{ xnum R; , V8 s5 z9 Z: |* q L! r% S int I; . n% W0 P' R# v/ d& K# R& c9 |) u int Carry = 0; ! P4 u/ h3 H9 U4 k( c for (I = 0; I < A.Len || I < B.Len || Carry > 0; I++) / e. V; S9 g+ V, ^0 | { ; o0 f9 h9 s# N9 v5 C if (I < A.Len) Carry += A[I]; if (I < B.Len) Carry += B[I]; 6 O' Z, N. d6 |& d4 ~7 f R[I] = Carry % Base; - |* b+ ~. H2 d9 k5 U, k Carry /= Base; } : q6 \, F: O( Z; p$ z) g R.Len = I; return R; ' u) O& t5 r( C+ k( F8 L}

xnum operator-(const xnum& A, const xnum& B) { xnum R; % z" B5 \0 q. h: z int Carry = 0; . m) M" U4 I$ {3 E5 } R.Len = A.Len; / k1 T/ c, e) v, B1 A0 {8 d' \' o int I; for (I = 0; I < R.Len; I++) { R[I] = A[I] - Carry; : O8 H! e3 b) y$ G+ M if (I < B.Len) R[I] -= B[I]; if (R[I] < 0) Carry = 1, R[I] += Base; " w9 b; |$ V% H3 [$ ~0 |5 | else Carry = 0; ; |! b i1 |: E! M+ K! \6 V3 p9 J } while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return R; }

xnum operator*(const xnum& A, const int B) { O2 J1 Z5 y! y7 u/ N' t int I; , A- g# _* }1 |8 I j if (B == 0) return 0; 5 g' S6 v# G& i0 s xnum R; hugeint Carry = 0; ' I" J8 W/ G- v2 {2 K/ \ for (I = 0; I < A.Len || Carry > 0; I++) 3 ]4 O6 R+ X, I' A) z- S: i' | { if (I < A.Len) Carry += hugeint(A[I]) * B; 6 d( u! `- L D! V: ^! h' K) ]4 ~ R[I] = Carry % Base; Carry /= Base; # M4 m. K' o! T4 [ } 1 o) q1 D7 ~ d5 r R.Len = I; return R; }

xnum operator*(const xnum& A, const xnum& B) { 9 c5 c7 W$ S/ W' m: B5 \9 V int I; if (B.Len == 0) return 0; xnum R; for (I = 0; I < A.Len; I++) { & F" \1 C" U& u1 Z$ ]& h hugeint Carry = 0; for (int J = 0; J < B.Len || Carry > 0; J++) 9 e6 l' x0 q' l# [9 v) a { if (J < B.Len) Carry += hugeint(A[I]) * B[J]; 3 i( X9 {) l$ Z( {' b 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; ' d+ A* i$ m' ?: X* k R Carry /= Base; # u6 {6 K3 Z4 |8 _( d } * Q4 J# S' w6 i: B* H# o } return R; + S6 N& |7 @: O/ s2 s3 x}

xnum operator/(const xnum& A, const int B) # ?6 }& o: i }{ 0 W8 w$ E D6 l% l3 q xnum R; ' {- z" G4 Z; e/ U E; Z+ f" K int I; " j |! z' Z6 {) F4 z+ S2 W% c hugeint C = 0; for (I = A.Len - 1; I >= 0; I--) { * Y2 W8 Q% X$ W3 y1 D7 g C = C * Base + A[I]; 3 T: H3 }6 O& j$ m2 c8 w9 T4 i R[I] = C / B; C %= B; / z' u! I( |# B( w } : O( H# U2 [: x4 ?/ Q( A R.Len = A.Len; ( W' V/ d1 Z( J4 b- e( r* q6 y while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; 6 E. K$ n# O, O6 u; ~8 {. n return R; + E k9 h3 P k( A* O2 O% [# ^4 f}

xnum operator/(const xnum& A, const xnum& B) { int I; 4 }" Q1 O. O6 b0 ~3 F: ~% q+ g xnum R, Carry = 0; int Left, Right, Mid; : r* U9 [8 l& c$ _ for (I = A.Len - 1; I >= 0; I--) { 7 B& |) t5 w6 O! ]. l" A/ Z Carry = Carry * Base + A[I]; - \" W6 u- @& |6 s Left = 0; ! X4 @/ m9 t/ b" b' Q" X1 w" v Right = Base - 1; while (Left < Right) { * s- T- ]( |, {$ r! O$ z4 w Mid = (Left + Right + 1) / 2; if (compare(B * Mid, Carry) <= 0) Left = Mid; 9 m! I5 M) v) o% F' l" e1 } else Right = Mid - 1; } R[I] = Left; Carry = Carry - B * Left; % a- z% j+ I: S* u/ n! T } 4 \% z) o$ c8 ^0 m8 _3 i R.Len = A.Len; + N& w% Z# ~1 `; Z& A. W while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; # j1 W5 a4 @& Z0 U return R; } / S& D: ?# O( W) A8 v" Gxnum operator%(const xnum& A, const xnum& B) ! `, k$ w" x3 P$ S4 w3 G# D{ int I; 1 T/ J1 J3 `$ Q0 t! k, n; v xnum R, Carry = 0; int Left, Right, Mid; for (I = A.Len - 1; I >= 0; I--) $ s( k8 R3 R0 E" M- T( y) Z3 @% e7 | { ! q4 _1 m, g8 o/ h Carry = Carry * Base + A[I]; Left = 0; ' j& A4 P. f# M% H4 Q6 F Right = Base - 1; $ f. L( Q7 d% \* }8 N while (Left < Right) { Mid = (Left + Right + 1) / 2; ( w7 I0 p$ |& g4 }( i- R if (compare(B * Mid, Carry) <= 0) Left = Mid; % H- G& s" W# _; Y* j6 L else Right = Mid - 1; } R[I] = Left; 5 c' T, k3 C) I3 t$ \8 \$ F* {9 F Carry = Carry - B * Left; 0 o u4 i4 ?+ ^$ c6 Y, |7 [+ \8 q } , B G7 v- ^6 E F X' q R.Len = A.Len; $ g g1 c9 L9 h* c' |1 x# B while (R.Len > 0 && R[R.Len - 1] == 0) R.Len--; return Carry; }

istream& operator>>(istream& In, xnum& V) { 5 C. b! U* C6 x6 Z char Ch; & s% M( S- V+ w/ L" \2 N, y for (V = 0; In >> Ch;) { : ] Q M# c! ?7 r V = V * 10 + (Ch - '0'); if (cin.peek() <= ' ') break; } return In; }

ostream& operator<<(ostream& Out, const xnum& V) ! B% E: |# \ d{ * o$ Y# ?- b; ~ int I; 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; } ' T& B8 n0 S1 H& a

---

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

---

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

---

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

Powered by Discuz! X2.5