codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <iostream> #include <fstream> #include <string> #include <vector> #include <algorithm> #include <functional> #include <iterator> #include <ctime> using namespace std; #define STL_WAY //#define PRINT2FILE struct BigInt { vector<int> digits; BigInt(string str="0"); BigInt operator+(const BigInt & bi) const; BigInt operator-(const BigInt & bi) const; BigInt operator*(const BigInt & bi) const; BigInt operator*(int n) const; BigInt operator<<(int n) const; }; typedef const BigInt & BICR; typedef BigInt & BIR; struct Ascii2Int { int operator()(int c) {return c-'0';} }; struct CarryPos { int & carry; CarryPos(int & c):carry(c){} int operator()(int n) { n+=carry; carry=n/10; n%=10; return n; } }; struct CarryNeg { int & carry; CarryNeg(int & c):carry(c){} int operator()(int n) { n-=carry; carry=0; while (n<0) {n+=10; carry++;} return n; } }; struct NegMinus { int operator()(int a, int b) {return b-a;} }; BigInt::BigInt(string str) { transform(str.rbegin(),str.rend(),back_inserter(digits),Ascii2Int()); } BigInt BigInt::operator+(BICR bi) const { const BigInt * max_op=this; const BigInt * min_op=&bi; if (max_op->digits.size()<min_op->digits.size()) swap(max_op,min_op); BigInt result(*max_op); #ifdef STL_WAY transform(min_op->digits.begin(),min_op->digits.end(), result.digits.begin(),result.digits.begin(),plus<int>()); int carry=0; transform(result.digits.begin(),result.digits.end(), result.digits.begin(),CarryPos(carry)); #else int carry=0; int max_size=max_op->digits.size(); int min_size=min_op->digits.size(); for (int i=0; i<min_size; i++) { result.digits[i]+=carry+min_op->digits[i]; carry=result.digits[i]/10; result.digits[i]%=10; } for (int i=min_size; i<max_size; i++) { result.digits[i]+=carry; carry=result.digits[i]/10; result.digits[i]%=10; } #endif if (carry) result.digits.push_back(carry); return result; } BigInt BigInt::operator-(BICR bi) const { BigInt result(*this); #ifdef STL_WAY transform(bi.digits.begin(),bi.digits.end(), result.digits.begin(),result.digits.begin(),NegMinus()); int carry=0; transform(result.digits.begin(),result.digits.end(), result.digits.begin(),CarryNeg(carry)); #else int carry=0; int max_size=digits.size(); int min_size=bi.digits.size(); for (int i=0; i<min_size; i++) { result.digits[i]-=carry; result.digits[i]-=bi.digits[i]; carry=0; while(result.digits[i]<0) { result.digits[i]+=10; carry++; } } int i=min_size; while (carry!=0) { result.digits[i]-=carry; carry=0; while(result.digits[i]<0) { result.digits[i]+=10; carry++; } i++; } #endif return result; } BigInt BigInt::operator*(int n) const { BigInt result(*this); #ifdef STL_WAY transform(result.digits.begin(),result.digits.end(), result.digits.begin(),bind1st(multiplies<int>(),n)); int carry=0; transform(result.digits.begin(),result.digits.end(), result.digits.begin(),CarryPos(carry)); #else int carry=0; int size=result.digits.size(); for (int i=0; i<size; i++) { result.digits[i]*=n; result.digits[i]+=carry; carry=result.digits[i]/10; result.digits[i]%=10; } #endif while (carry) { result.digits.push_back(carry%10); carry/=10; } return result; } BigInt BigInt::operator<<(int n) const { BigInt result(*this); result.digits.resize(result.digits.size()+n); copy(result.digits.rbegin()+n, result.digits.rend(),result.digits.rbegin()); fill(result.digits.begin(),result.digits.begin()+n,0); return result; } BigInt BigInt::operator*(BICR bi) const { const BigInt * max_op=this; const BigInt * min_op=&bi; int max_size=max_op->digits.size(); int min_size=min_op->digits.size(); if (max_size<min_size) { swap(max_op,min_op); swap(max_size,min_size); } BigInt * array=new BigInt[min_size]; for (int i=0; i<min_size; i++) array[i]=(*max_op)*(min_op->digits[i]); BigInt result(array[0]); for (int i=1; i<min_size; i++) result=result+(array[i]<<i); delete[] array; return result; } void split(BICR op1, BICR op2, BIR x0, BIR x1, BIR y0, BIR y1, int & m) { int size1=op1.digits.size(); int size2=op2.digits.size(); int min_size=size1; if (min_size>size2) min_size=size2; m=min_size/2; x0.digits.resize(m); x1.digits.resize(size1-m); y0.digits.resize(m); y1.digits.resize(size2-m); copy(op1.digits.begin(),op1.digits.begin()+m,x0.digits.begin()); copy(op1.digits.begin()+m,op1.digits.end(),x1.digits.begin()); copy(op2.digits.begin(),op2.digits.begin()+m,y0.digits.begin()); copy(op2.digits.begin()+m,op2.digits.end(),y1.digits.begin()); } BigInt karatsuba(BICR op1, BICR op2) { BigInt x0, x1, y0, y1; BigInt z0, z1, z2; if (op1.digits.size()<30 || op2.digits.size()<30) return op1*op2; int m; split(op1,op2,x0,x1,y0,y1,m); z0=karatsuba(x0,y0); z2=karatsuba(x1,y1); z1=(karatsuba(x0+x1,y0+y1)-z2)-z0; z1=z1<<m; z2=z2<<2*m; return z0+z1+z2; } ostream & operator<<(ostream & os, BICR bi) { copy(bi.digits.rbegin(),bi.digits.rend(),ostream_iterator<int>(os)); #ifdef PRINT2FILE #ifdef STL_WAY ofstream fout("stl.txt",ios::app); copy(bi.digits.rbegin(),bi.digits.rend(),ostream_iterator<int>(fout)); fout << endl; #else ofstream fout("loops.txt",ios::app); copy(bi.digits.rbegin(),bi.digits.rend(),ostream_iterator<int>(fout)); fout << endl; #endif #endif return os; } void test(string s1, string s2) { BigInt n1(s1); BigInt n2(s2); BigInt rs, rk; int start_s, stop_s, start_k, stop_k; start_s=clock(); rs=n1*n2; stop_s=clock(); start_k=clock(); rk=karatsuba(n1,n2); stop_k=clock(); cout << rs << endl; cout << rk << endl; cout << "standard time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl; cout << "karatsuba time: " << (stop_k-start_k)/double(CLOCKS_PER_SEC)*1000 << endl; } int main() { test( "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789", "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"); cout << "\nhit enter to continue..." << endl; cin.get(); test( "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789", "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"); cout << "\nhit enter to continue..." << endl; cin.get(); test( "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789", "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"); cout << "\nhit enter to continue..." << endl; cin.get(); test( "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789", "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"); cout << "\nhit enter to continue..." << endl; cin.get(); test( "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789" "123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789", "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321" "987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"); cout << "\nhit enter to continue..." << endl; cin.get(); return 0; }
Private
[
?
]
Run code
Submit