Новичок
Профиль
Группа: Участник
Сообщений: 34
Регистрация: 26.11.2011
Репутация: нет
Всего: нет
|
Опишу проблему полностью. Решил скомплировать готовый исходны код, для работы с большими числами. Который использует gmp.h. Integer.cpp | Код |
/***************************** BEGIN ********************************/
#include <stdlib.h>
#include "Integer.h"
//
// Constructors
//
Integer::Integer() {mpz_init_set_ui(_x, 0); base=10;}
Integer::Integer(int a) {mpz_init_set_si(_x,a);base=10;}
Integer::Integer(unsigned int a){mpz_init_set_ui(_x, a); base=10;}
Integer::Integer(const Integer &a) {mpz_init_set(_x,a._x);base=a.base;}
Integer::Integer(char * a) {mpz_init_set_str(_x,a,10);base=10;}
Integer::Integer(mpz_t a) {mpz_init_set(_x, a);base=10;}
//
// Destructor
//
Integer::~Integer() {mpz_clear(_x); } // releases memory
//
// Simple access functions
//
int Integer::getbase(void) { return base; }
void Integer::setbase(int b) { base = b; }
//
// Casting
//
Integer::operator bool(void) { return (bool) (mpz_cmp_ui(_x,0))? 1 :0; }
Integer::operator int(void) { return (int) mpz_get_si(_x); }
Integer::operator unsigned int(void) { return (unsigned int) mpz_get_ui(_x); }
Integer::operator float(void) { return (float) mpz_get_d(_x); }
Integer::operator double(void) { return (double) mpz_get_d(_x); }
//
// Assignments
//
void Integer::operator =(Integer a) { mpz_set(_x, a._x); base=a.base;}
void Integer::operator =(int a) { mpz_set_si(_x, a); base=10;}
void Integer::operator =(unsigned int a){ mpz_set_ui(_x, a); base=10;}
void Integer::operator =(char *a) { mpz_set_str(_x, a, 10); base=10;}
void Integer::operator =(const char *a) { mpz_set_str(_x, a, 10); base=10;}
void Integer::operator =(mpz_t a) { mpz_set(_x, a); base=10; }
//
// Unary Operators -, !, etc...
//
Integer Integer::operator -(void) { Integer r; mpz_neg(r._x, _x); return r; }
bool Integer::operator !(void) { return (mpz_cmp_ui(_x, 0)==0)? 1 : 0; }
void Integer::operator +=(Integer a) { mpz_add(_x, _x, a._x); }
void Integer::operator +=(int a) { (a>0)? mpz_add_ui(_x, _x, a) : mpz_sub_ui(_x, _x, -a); }
void Integer::operator +=(unsigned int a) { mpz_add_ui(_x, _x, a); }
void Integer::operator -=(Integer a) { mpz_sub(_x, _x, a._x); }
void Integer::operator -=(int a) { (a>0)? mpz_sub_ui(_x, _x, a) : mpz_add_ui(_x, _x, -a); }
void Integer::operator -=(unsigned int a) { mpz_sub_ui(_x, _x, a); }
void Integer::operator *=(Integer a) { mpz_mul(_x, _x, a._x); }
void Integer::operator *=(int a) { mpz_mul_ui(_x, _x,(a>0)? a :-a); if (a<0) mpz_neg(_x,_x);}
void Integer::operator *=(unsigned int a) { mpz_mul_ui(_x, _x, a); }
void Integer::operator /=(Integer a) { mpz_tdiv_q(_x, _x, a._x); }
void Integer::operator /=(int a) { mpz_tdiv_q_ui(_x, _x,(a>0)? a:-a); if (a<0) mpz_neg(_x,_x);}
void Integer::operator /=(unsigned int a) { mpz_tdiv_q_ui(_x, _x, a); }
void Integer::operator %=(Integer a) { mpz_mod(_x, _x, a._x); }
void Integer::operator %=(int a) { mpz_mod_ui(_x, _x, a); }
void Integer::operator ^=(int a) { mpz_pow_ui(_x, _x, a); }
//
// Inc/Dec -- prefix: ++a
Integer Integer::operator ++(void) { mpz_add_ui(_x, _x, 1); return _x;}
Integer Integer::operator --(void) { mpz_sub_ui(_x, _x, 1); return _x;}
//
// Inc/Dec -- postfix: a++
Integer Integer::operator ++(int a) {Integer r=_x;mpz_add_ui(_x,_x,1); return r; }
Integer Integer::operator --(int a) {Integer r=_x;mpz_sub_ui(_x,_x,1); return r;}
//
// Binary (friendly) operators
//
Integer operator +(Integer a, Integer b) {Integer c;mpz_add(c._x,a._x,b._x);return c;}
Integer operator +(Integer a, int b) {Integer c; if (b>0) mpz_add_ui(c._x,a._x,b); else mpz_sub_ui(c._x, a._x, -b); return c;}
Integer operator +(int a, Integer b) { return b+a; }
Integer operator -(Integer a, Integer b) {Integer c;mpz_sub(c._x,a._x,b._x);return c;}
Integer operator -(Integer a, int b) { return a + (-b);}
Integer operator -(int a, Integer b) { return -(b-a); }
Integer operator *(Integer a, Integer b) {Integer c; mpz_mul(c._x, a._x, b._x); return c; }
Integer operator *(Integer a, int b) {Integer c; mpz_mul_ui(c._x, a._x, (b>0)? b:-b); if (b<0) return -c; else return c; }
Integer operator *(int a, Integer b) { return b*a; }
Integer operator /(Integer a, Integer b) {Integer c; mpz_tdiv_q(c._x, a._x, b._x); return c; }
Integer operator /(Integer a, int b) {Integer c; mpz_tdiv_q_ui(c._x, a._x, (b>0)? b:-b); if (b<0) return -c; else return c; }
Integer operator /(int a, Integer b) {Integer c; c = a; return c/b; }
Integer operator %(Integer a, Integer b) {Integer c; mpz_mod(c._x, a._x, b._x); return c; }
Integer operator %(Integer a, int b) {Integer c; mpz_mod_ui(c._x, a._x, b); return c; }
Integer operator %(int a, Integer b) {Integer c; c = a; return c%b; }
Integer operator ^(Integer a, int b) {Integer c; mpz_pow_ui(c._x, a._x, b); return c; }
Integer operator &(Integer a, Integer b) {Integer c; mpz_and(c._x, a._x, b._x); return c; }
Integer operator |(Integer a, Integer b) {Integer c; mpz_ior(c._x, a._x, b._x); return c; }
bool operator ==(Integer a, Integer b) {return (mpz_cmp(a._x, b._x)==0)? 1:0;}
bool operator ==(Integer a, int b) {return (mpz_cmp_si(a._x, b)==0)? 1:0;}
bool operator ==(int a, Integer b) {return (b==a); }
bool operator !=(Integer a, Integer b) {return (mpz_cmp(a._x, b._x)!=0)? 1:0;}
bool operator !=(Integer a, int b) {return (mpz_cmp_si(a._x, b)!=0)? 1:0;}
bool operator !=(int a, Integer b) {return (b!=a); }
bool operator <(Integer a, Integer b) {return (mpz_cmp(a._x, b._x)<0)? 1:0;}
bool operator <(Integer a, int b) {return (mpz_cmp_si(a._x, b)<0)? 1 : 0;}
bool operator <(int a, Integer b) {return (b>a); }
bool operator <=(Integer a,Integer b) {return (mpz_cmp(a._x, b._x)>0)? 0:1;}
bool operator <=(Integer a, int b) {return (mpz_cmp_si(a._x, b)>0)? 0 : 1;}
bool operator <=(int a, Integer b) {return (b>=a); }
bool operator >(Integer a, Integer b) {return (mpz_cmp(a._x, b._x)>0)? 1:0;}
bool operator >(Integer a, int b) {return (mpz_cmp_si(a._x, b)>0)? 1 : 0;}
bool operator >(int a, Integer b) {return (b<a); }
bool operator >=(Integer a, Integer b) {return (mpz_cmp(a._x, b._x)<0)? 0:1;}
bool operator >=(Integer a, int b) {return (mpz_cmp_si(a._x, b)<0)? 0 : 1;}
bool operator >=(int a, Integer b) {return (b<=a); }
ostream& operator <<(ostream& s, Integer i) {
char *p; p = (char *) new char[4+logn(i, i.getbase() )];
Int2a(i, p); s << p; delete p; return s; }
istream& operator >>(istream& s, Integer &a) {
char *p; p = (char *) new char[8192];
s >> p; a = (Integer) p; delete p; return s; }
Integer& operator <<(Integer a, int b) {
Integer c; c=a; mpz_mul_2exp(a._x, c._x, b); return a;
}
Integer& operator >>(Integer a, int b) {
Integer c; c=a; mpz_tdiv_q_2exp(a._x, c._x, b); return a;
}
//
// Misc Number Theory Fuctions (friendly)
//
void Int2a(Integer i, char *a) { mpz_get_str(a, i.base, i._x ); }
Integer gcd(Integer a, Integer b) {
Integer g; mpz_gcd(g._x, a._x, b._x); return g;}
Integer exgcd(Integer a, Integer b, Integer &c, Integer &d) {
Integer g; mpz_gcdext(g._x, c._x, d._x, a._x, b._x); return g; }
Integer InvModN(Integer a, Integer n) {
Integer c; mpz_invert(c._x, a._x, n._x); return c%n; }
Integer PowModN(Integer a, int b, Integer n) {
Integer c; mpz_powm_ui(c._x, a._x, b, n._x); return c%n; }
Integer PowModN(Integer a, Integer b, Integer n) {
Integer c; mpz_powm(c._x, a._x, b._x, n._x); return c%n; }
bool isprime(Integer a) { return (bool) mpz_probab_prime_p(a._x, 25); }
bool issquare(Integer a) { return (bool) mpz_perfect_square_p(a._x); }
bool testbit(Integer a, unsigned long int i) {
return (i == mpz_scan1(a._x, i))? 1 : 0; }
Integer sqrt(Integer a) { Integer r; mpz_sqrt(r._x, a._x); return r; }
int digits(Integer a, int b) { return mpz_sizeinbase(a._x, b); }
/***** I don't think these two functions are too reliable... -Paul *****/
int Jacobi(Integer a, Integer b) { return mpz_jacobi(a._x, b._x);}
int Legendre(Integer a, Integer b) { return mpz_legendre(a._x, b._x);}
/***********************************************************************/
Integer random(Integer a) {
Integer r; mp_size_t siz; long rr; time_t t;
srand48((long)time(&t)); // set seed
rr = (lrand48()&127) + 1; // get a random number
siz = (log2(a)+1)*3;
if (siz<1) siz = 1; // estimate number of limbs
while(rr--) mpz_random(r._x, siz); // get random generator goin
r %= a;
return r;
}
//
// Non friendly (miscellaneous) useful functions
//
Integer lcm(Integer a, Integer b) { return (a*b)/gcd(a,b); }
Integer LCM(Integer n) { // this is lcm[1, 2, 3, ... , n]
if (n < 3) return 2;
else return lcm(LCM(n-1), n); }
int logn(Integer a, int b) { return digits(a, b) - 1; }
int log2(Integer a) { return logn(a, 2); }
Integer fact(Integer a) {
Integer r=1, i=1; while (i++ < a) r *= i; return r;}
Integer P_n_k(Integer n, Integer k) {
Integer r=1, i=k; while (i++ < n) r *= i; return r;}
Integer C_n_k(Integer n, Integer k) {
Integer r=1, i=1; while (i++ <= k) {r *= (n-(i-2)); r /= i-1;}
return r;}
Integer nextprime(Integer a) {
if (a%2 == 0) { a++; if (isprime(a)) return a; }
do {a++; a++;} while (!isprime(a)); return a;}
Integer prevprime(Integer a) {
if (a<3) return a;
if (a%2 == 0) { a--; if (isprime(a)) return a; }
do {a--; a--;} while (!isprime(a) && a>1); return a;}
Integer euler(Integer n) { // there are better ways to do this
Integer count, i;
count = 1;
for (i=2; i<n; i++) if (gcd(i, n) == 1) count++;
return count;
}
// Quick sneaky prototype
Integer SqrtShanks(Integer x, Integer m);
Integer SqrtModN(Integer x, Integer p) {
return SqrtShanks(x, p);
}
Integer SqrtShanks(Integer x, Integer m) {
// square root mod a small prime by Shanks method
// returns 0 if root does not exist or m not prime
Integer z,y,v,w,t,q,r;
int i,e,n;
bool pp;
x %= m;
if (x==0) return 0;
if (x==1) return 1;
// if (PowModN(x,(m-1)/2,m)!=1) return 0; // Legendre symbol not 1
if (Legendre(x,m)!=1) return 0; // Legendre symbol not 1
if (m%4==3) return PowModN(x,(m+1)/4,m); // easy case for m=4.k+3
if (m%8==5) { // also relatively easy
t = PowModN(x,(m-1)/4,m);
if (t==1) return PowModN(x,(m+3)/8,m);
if (t==(m-1)) {
t = (4*x)%m; // muldiv((small)4,x,(small)0,m,&t);
t = PowModN(t,(m+3)/8,m);
t = (t*(m+1)/2)%m; // muldiv(t,(m+1)/2,(small)0,m,&t);
return t;
}
return 0;
}
q=m-1;
e=0;
while (q%2==0) {
q/=2;
e++;
}
if (e==0) return 0; // even m
for (r=2;;r++) { // find suitable z
z=PowModN(r, q, m);
if (z==1) continue;
t=z;
pp=0;
for (i=1;i<e;i++) { // check for composite m
if (t==(m-1)) pp=1;
t = (t*t)%m; // muldiv(t,t,(small)0,m,&t);
if (t==1 && !pp) return 0;
}
if (t==(m-1)) break;
if (!pp) return 0; /* m is not prime */
}
y=z;
r=e;
v=PowModN(x,(q+1)/2,m);
w=PowModN(x,q,m);
while (w!=1) {
t=w;
for (n=0;t!=1;n++) t = (t*t)%m; // muldiv(t,t,(small)0,m,&t);
if (n>=r) return 0;
y=PowModN(y, (1<<((int)r-n-1)), m);
v = (v*y)%m; // muldiv(v,y,(small)0,m,&v);
y = (y*y)%m; // muldiv(y,y,(small)0,m,&y);
w = (w*y)%m; // muldiv(w,y,(small)0,m,&w);
r=n;
}
return (Integer)v;
}
|
Integer.h | Код |
/******************************************************
* Integer.h -- C++ Integer class for the gmp integer library (from the
* GNU project.) Allows you to use the arbitrary precision integers
* from gmp as if they were plain old (int)'s or (long int)'s. Just
* include this file in your source code. Example main():
*
* #include "Integer.h"
* int main(int argc, char **argv) {
* Integer a, b, c;
*
* a = argv[1]; // automaticaly converts a string
* b = argv[2]; // into an Integer.
* c = a*b;
* cout << a << " x " << b << " = " << c << endl;
* }
*
********
* To Do:
* Rewrite all additions to check for signed (int)s (Done! with 000605)
* ChangeLog:
* 970304 - Created -- Paul Herman <[email protected]>
* 980804 - Cleaned up -- Paul Herman <[email protected]>
* 000605 - bug fixes -- Paul Herman <[email protected]>
*******************************************************/
/***************************** BEGIN ********************************/
#include <stdlib.h>
#ifndef FALSE
#define FALSE 0
#endif // FALSE
#ifndef TRUE
#define TRUE 1
#endif // TRUE
#ifndef __GMP_INTEGER_CLASS__
#define __GMP_INTEGER_CLASS__
#include <gmp.h> // provides the mpz integer routines
#include <iostream.h> // for cin & cout istreams & ostreams
#include <time.h> // use time as seed for random numbers
#ifndef ABSmodN
#define ABSmodN(x, n) (x%n) // in gmp lib, (-x)%n = (n-x)%n
#endif // ABSmodN
/**************************** INTEGER ***************************************/
class Integer {
private:
mpz_t _x;
int base;
public:
//
// Constructors
//
Integer(void);
Integer(int a);
Integer(unsigned int a);
Integer(const Integer &a);
Integer(char * a);
Integer(mpz_t a);
//
// Destructor
//
~Integer(void);
//
// Simple access functions
//
int getbase(void);
void setbase(int b);
//
// Casting (changing Integer to another type)
//
operator bool(void); // (bool) i
operator int(void); // (int) i
operator unsigned int(void);// (unsigned int) i
operator float(void); // (float) i
operator double(void); // (double)i
//
// Assignments (Setting Integer equal to something else)
//
void operator =(Integer a); // c = (Integer) a;
void operator =(int a); // c = (int) a;
void operator =(unsigned int a); // c = (unsigned int) a;
void operator =(char *a); // c = a (a string);
void operator =(const char *a); // c = "1231231";
void operator =(mpz_t a); // c = a (a mpz number);
//
// Binary (one sided) operators
//
Integer operator -(void); // c = -a;
bool operator !(void); // c = (bool) (!a)
void operator +=(Integer a); // c += a;
void operator +=(int a); // c += a;
void operator +=(unsigned int a); // c += a;
void operator -=(Integer a); // c -= a;
void operator -=(int a); // c -= a;
void operator -=(unsigned int a); // c -= a;
void operator *=(Integer a); // c *= a;
void operator *=(int a); // c *= a;
void operator *=(unsigned int a); // c *= a;
void operator /=(Integer a); // c /= a;
void operator /=(int a); // c /= a;
void operator /=(unsigned int a); // c /= a;
void operator %=(Integer a); // c %= a;
void operator %=(int a); // c %= a;
void operator ^=(int a); // c ^= a;
// WARNING: No ^ with type (Integer) as exponent
Integer operator ++(void); // c = a++;
Integer operator --(void); // c = a--;
Integer operator ++(int from); // c = ++a;
Integer operator --(int from); // c = --a;
//
// The following operators must be friendly because the are binary
//
friend Integer operator +(Integer a, Integer b); // a + b;
friend Integer operator +(Integer a, int b); // a + b;
friend Integer operator +(int a, Integer b); // a + b;
friend Integer operator -(Integer a, Integer b); // a - b;
friend Integer operator -(Integer a, int b); // a - b;
friend Integer operator -(int a, Integer b); // a - b;
friend Integer operator *(Integer a, Integer b); // a * b;
friend Integer operator *(Integer a, int b); // a * b;
friend Integer operator *(int a, Integer b); // a * b;
friend Integer operator /(Integer a, Integer b); // a / b;
friend Integer operator /(Integer a, int b); // a / b;
friend Integer operator /(int a, Integer b); // a / b;
friend Integer operator %(Integer a, Integer b); // a % b;
friend Integer operator %(Integer a, int b); // a % b;
friend Integer operator %(int a, Integer b); // a % b;
friend Integer operator ^(Integer a, int b); // a ^ b;
friend Integer operator &(Integer a, Integer b); // a & b;
friend Integer operator |(Integer a, Integer b); // a | b;
friend bool operator ==(Integer a, Integer b); // (c == a)?
friend bool operator ==(Integer a, int b); // (c == a)?
friend bool operator ==(int a, Integer b); // (c == a)?
friend bool operator !=(Integer a, Integer b); // (c != a)?
friend bool operator !=(Integer a, int b); // (c != a)?
friend bool operator !=(int a, Integer b); // (c != a)?
friend bool operator <(Integer a, Integer b); // (c < a)?
friend bool operator <(Integer a, int b); // (c < a)?
friend bool operator <(int a, Integer b); // (c < a)?
friend bool operator <=(Integer a, Integer b); // (c <= a)?
friend bool operator <=(Integer a, int b); // (c <= a)?
friend bool operator <=(int a, Integer b); // (c <= a)?
friend bool operator >(Integer a, Integer b); // (c > a)?
friend bool operator >(Integer a, int b); // (c > a)?
friend bool operator >(int a, Integer b); // (c > a)?
friend bool operator >=(Integer a, Integer b); // (c >= a)?
friend bool operator >=(Integer a, int b); // (c >= a)?
friend bool operator >=(int a, Integer b); // (c >= a)?
friend ostream& operator <<(ostream &s, Integer a); // cout << a;
friend istream& operator >>(istream &s, Integer &a); // cin >> a;
friend Integer& operator <<(Integer a, int b); // a << b;
friend Integer& operator >>(Integer a, int b); // a >> b;
//
// These functions are friendly to speed up access to the class'
// private parts.
//
friend void Int2a(Integer i, char *string);
friend Integer gcd(Integer a, Integer b);
friend Integer exgcd(Integer a, Integer b, Integer &c, Integer &d);
friend Integer InvModN(Integer a, Integer n);
friend Integer PowModN(Integer base, Integer exp, Integer n);
friend Integer PowModN(Integer base, int exp, Integer n);
friend bool isprime(Integer a);
friend bool issquare(Integer a);
friend bool testbit(Integer a, unsigned long int bit_number);
friend Integer sqrt(Integer a);
friend int digits(Integer a, int base);
friend int Jacobi(Integer m, Integer n);
friend int Legendre(Integer m, Integer n);
friend Integer random(Integer range);
}; // end 'class Integer'
//
// Misc Number theory functions (non-friendly)
//
Integer lcm(Integer a, Integer b);
Integer LCM(Integer a); // LCM(a) = lcm[1, 2, 3, ..., a]
int logn(Integer a, int base);
int log2(Integer a);
Integer fact(Integer a);
Integer P_n_k(Integer n, Integer k);
Integer C_n_k(Integer n, Integer k);
Integer nextprime(Integer a);
Integer prevprime(Integer a);
Integer SqrtModN(Integer x, Integer p);
#endif // __GMP_INTEGER_CLASS__
|
test1.cpp | Код |
/*******************************************************
* test1.cc - sample program to show how to use the
* Integer class I wrote for the gnu gmp
* library. Have fun!
*
* Compile:
* g++ -O4 -s -o test1 -I. test1.cc libgmp.a
*
* Changelog:
* 971703: Created - Paul Herman <[email protected]>
*********************************************************/
#include <Integer.h>
int main(int argc, char **argv) {
Integer a, b, c;
if (argc != 3) { // this program expects two arguments
cerr << "Usage: " << argv[0] << " num1 num2" << endl;
return -1;
}
a = argv[1]; // casting from char* to Integer is
b = argv[2]; // done automaticaly
c = a+b;
cout << a << " + " << b << " = " << c << endl;
c = a*b;
cout << a << " x " << b << " = " << c << endl;
c = a%b;
cout << a << " % " << b << " = " << c << endl;
c = gcd(a, b);
cout << "gcd(" << a << ", " << b << ") = " << c << endl;
c = lcm(a, b);
cout << "lcm(" << a << ", " << b << ") = " << c << endl;
}
|
Но он написан под линуксом, соотвественно с Visual Studio 2010 возникают проблемы из за gmp.h. Внося правки в код и подключая gmp.h программа не запускается. Если кто подскажет как запустить буду благодарен. Это сообщение отредактировал(а) CWD - 22.4.2013, 16:43 |
Ошибка gmp.h 
Загрузка ...
