From 437c248d2742f772409559f86b9d7c086a0f7d42 Mon Sep 17 00:00:00 2001
From: damir <damir@gloom.mimas.ru>
Date: Wed, 24 Dec 2008 00:27:44 +0400
Subject: [PATCH] dixon

---
 dixon/Makefile |   5 +
 dixon/dixon.cc |  63 ++++++++++
 dixon/myint.cc | 374 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 dixon/myint.h  | 112 +++++++++++++++++
 4 files changed, 554 insertions(+)
 create mode 100644 dixon/Makefile
 create mode 100644 dixon/dixon.cc
 create mode 100644 dixon/myint.cc
 create mode 100644 dixon/myint.h

diff --git a/dixon/Makefile b/dixon/Makefile
new file mode 100644
index 0000000..9012f34
--- /dev/null
+++ b/dixon/Makefile
@@ -0,0 +1,5 @@
+all:
+	g++ -I. -l gmp -s -O4 myint.cc -o dixon dixon.cc -Wno-deprecated
+
+clean:
+	rm -f dixon *~
diff --git a/dixon/dixon.cc b/dixon/dixon.cc
new file mode 100644
index 0000000..07ebb41
--- /dev/null
+++ b/dixon/dixon.cc
@@ -0,0 +1,63 @@
+#include <myint.h>
+
+myInt factor(myInt n) {
+  myInt x, xx, d, root;
+
+  root = sqrt(n);
+
+  if (issquare(n))
+    return root;
+
+  x = root;
+
+  for (;; x++) {
+    d = gcd(x, n);
+
+    if (1 < d && d < n)
+      return d;
+
+    xx = (x * x) % n;
+
+    if (issquare(xx)) {
+      d = gcd((x - sqrt(xx)) % n, n);
+
+      if (1 < d && d < n)
+        return d;
+    }
+  }
+  cout << "couldn't find!" << endl;
+
+  return 0;
+};
+
+int main(int argc, char *argv[]) {
+  myInt n, f;
+
+  if (argc < 2) {
+    cerr << "usage: " << argv[0] << " number_to_factorize" << endl;
+    return 1;
+  }
+
+  n = argv[1];
+
+  if (n == 1) {
+    cout << n << ": is " << n << endl;
+    return 0;
+  }
+
+  cout << n << ": " << flush;
+
+  if (isprime(n)) {
+    cout << "is prime" << endl;
+    return 0;
+  }
+
+  while (!isprime(n)) {
+    f = factor(n);
+    cout << f << " " << flush;
+    n /= f;
+  }
+  cout << n << endl;
+
+  return 0;
+};
diff --git a/dixon/myint.cc b/dixon/myint.cc
new file mode 100644
index 0000000..f9049ce
--- /dev/null
+++ b/dixon/myint.cc
@@ -0,0 +1,374 @@
+#include <stdlib.h>
+#include "myint.h"
+
+myInt::myInt() {
+  mpz_init_set_ui(_x, 0);
+  base = 10;
+}
+
+myInt::myInt(int a) {
+  mpz_init_set_si(_x, a);
+  base = 10;
+}
+
+myInt::myInt(const myInt &a) {
+  mpz_init_set(_x, a._x);
+  base = a.base;
+}
+
+myInt::myInt(char *a) {
+  mpz_init_set_str(_x, a, 10);
+  base = 10;
+}
+
+myInt::myInt(mpz_t a) {
+  mpz_init_set(_x, a);
+  base = 10;
+}
+
+myInt::~myInt() {
+  mpz_clear(_x);
+}
+
+myInt::operator bool(void) {
+  return (bool)(mpz_cmp_ui(_x, 0));
+}
+myInt::operator int(void) {
+  return (int)mpz_get_si(_x);
+}
+
+myInt::operator float(void) {
+  return (float)mpz_get_d(_x);
+}
+myInt::operator double(void) {
+  return (double)mpz_get_d(_x);
+}
+
+void myInt::operator =(myInt a) {
+  mpz_set(_x, a._x);
+  base = a.base;
+}
+
+void myInt::operator =(int a) {
+  mpz_set_si(_x, a);
+  base = 10;
+}
+
+void myInt::operator =(char *a) {
+  mpz_set_str(_x, a, 10);
+  base = 10;
+}
+
+void myInt::operator =(const char *a) {
+  mpz_set_str(_x, a, 10);
+  base = 10;
+}
+
+void myInt::operator =(mpz_t a) {
+  mpz_set(_x, a);
+  base = 10;
+}
+
+myInt myInt::operator -(void) {
+  myInt r;
+  mpz_neg(r._x, _x);
+
+  return r;
+}
+
+bool myInt::operator !(void) {
+  return (mpz_cmp_ui(_x, 0) == 0);
+}
+
+void myInt::operator +=(myInt a) {
+  mpz_add(_x, _x, a._x);
+}
+
+void myInt::operator +=(int a) {
+  (a > 0)
+    ? mpz_add_ui(_x, _x, a)
+    : mpz_sub_ui(_x, _x, -a);
+}
+
+void myInt::operator -=(myInt a) {
+  mpz_sub(_x, _x, a._x);
+}
+
+void myInt::operator -=(int a) {
+  (a > 0)
+    ? mpz_sub_ui(_x, _x, a)
+    : mpz_add_ui(_x, _x, -a);
+}
+
+void myInt::operator *=(myInt a) {
+  mpz_mul(_x, _x, a._x);
+}
+
+void myInt::operator *=(int a) {
+  mpz_mul_ui(_x, _x, a);
+
+  if (a < 0)
+    mpz_neg(_x, _x);
+}
+
+void myInt::operator /=(myInt a) {
+  mpz_tdiv_q(_x, _x, a._x);
+}
+
+void myInt::operator /=(int a) {
+  mpz_tdiv_q_ui(_x, _x, a);
+
+  if (a < 0)
+    mpz_neg(_x, _x);
+}
+
+void myInt::operator %=(myInt a) {
+  mpz_mod(_x, _x, a._x);
+}
+
+void myInt::operator %=(int a) {
+  mpz_mod_ui(_x, _x, a);
+}
+
+myInt myInt::operator ++(void) {
+  mpz_add_ui(_x, _x, 1);
+
+  return _x;
+}
+
+myInt myInt::operator --(void) {
+  mpz_sub_ui(_x, _x, 1);
+
+  return _x;
+}
+
+myInt myInt::operator ++(int a) {
+  myInt r = _x;
+  mpz_add_ui(_x, _x, 1);
+
+  return r;
+}
+
+myInt myInt::operator --(int a) {
+  myInt r = _x;
+  mpz_sub_ui(_x, _x, 1);
+
+  return r;
+}
+
+myInt operator +(myInt a, myInt b) {
+  myInt c;
+  mpz_add(c._x, a._x, b._x);
+
+  return c;
+}
+
+myInt operator +(myInt a, int b) {
+  myInt c;
+
+  if (b > 0)
+    mpz_add_ui(c._x, a._x, b);
+  else
+    mpz_sub_ui(c._x, a._x, -b);
+
+  return c;
+}
+
+myInt operator +(int a, myInt b) {
+  return b + a;
+}
+
+myInt operator -(myInt a, myInt b) {
+  myInt c;
+  mpz_sub(c._x, a._x, b._x);
+
+  return c;
+}
+
+myInt operator -(myInt a, int b) {
+  return a + (-b);
+}
+
+myInt operator -(int a, myInt b) {
+  return -(b - a);
+}
+
+myInt
+operator *(myInt a, myInt b)
+{
+  myInt c;
+  mpz_mul(c._x, a._x, b._x);
+  return c;
+}
+
+myInt operator *(myInt a, int b) {
+  myInt c;
+  mpz_mul_ui(c._x, a._x, b);
+
+  return (b < 0
+          ? -c
+          : c);
+}
+
+myInt operator *(int a, myInt b) {
+  return b * a;
+}
+
+myInt operator /(myInt a, myInt b) {
+  myInt c;
+  mpz_tdiv_q(c._x, a._x, b._x);
+  return c;
+}
+
+myInt operator /(myInt a, int b) {
+  myInt c;
+  mpz_tdiv_q_ui(c._x, a._x, b);
+
+  return (b < 0
+          ? -c
+          : c);
+}
+
+myInt operator /(int a, myInt b) {
+  myInt c;
+  c = a;
+
+  return c / b;
+}
+
+myInt operator %(myInt a, myInt b) {
+  myInt c;
+  mpz_mod(c._x, a._x, b._x);
+
+  return c;
+}
+
+myInt operator %(myInt a, int b) {
+  myInt c;
+
+  mpz_mod_ui(c._x, a._x, b);
+  return c;
+}
+
+myInt operator %(int a, myInt b) {
+  myInt c;
+  c = a;
+
+  return c % b;
+}
+
+bool operator ==(myInt a, myInt b) {
+  return (mpz_cmp(a._x, b._x) == 0);
+}
+
+bool operator ==(myInt a, int b) {
+  return (mpz_cmp_si(a._x, b) == 0);
+}
+
+bool operator ==(int a, myInt b) {
+  return (b == a);
+}
+
+bool operator !=(myInt a, myInt b) {
+  return(mpz_cmp(a._x, b._x) != 0);
+}
+
+bool operator !=(myInt a, int b) {
+  return (mpz_cmp_si(a._x, b) != 0);
+}
+
+bool operator !=(int a, myInt b) {
+  return (b != a);
+}
+
+bool operator <(myInt a, myInt b) {
+  return (mpz_cmp(a._x, b._x) < 0);
+}
+
+bool operator <(myInt a, int b) {
+  return (mpz_cmp_si(a._x, b) < 0);
+}
+
+bool operator <(int a, myInt b) {
+  return (b > a);
+}
+
+bool operator <=(myInt a, myInt b) {
+  return (mpz_cmp(a._x, b._x) < 0);
+}
+
+bool operator <=(myInt a, int b) {
+  return (mpz_cmp_si(a._x, b) < 0);
+}
+
+bool operator <=(int a, myInt b) {
+  return(b >= a);
+}
+
+bool operator >(myInt a, myInt b) {
+  return (mpz_cmp(a._x, b._x) > 0);
+}
+
+bool operator >(myInt a, int b) {
+  return (mpz_cmp_si(a._x, b) > 0);
+}
+
+bool operator >(int a, myInt b) {
+  return (b < a);
+}
+
+bool operator >=(myInt a, myInt b) {
+  return (mpz_cmp(a._x, b._x) > 0);
+}
+
+bool operator >=(myInt a, int b) {
+  return (mpz_cmp_si(a._x, b) > 0);
+}
+
+bool operator >=(int a, myInt b) {
+  return (b <= a);
+}
+
+ostream &operator <<(ostream &s, myInt i) {
+  char *p;
+  p = (char *)new char[4 + mpz_sizeinbase(i._x, i.base) - 1];
+  mpz_get_str(p, i.base, i._x);
+  s << p;
+
+  delete p;
+
+  return s;
+}
+
+istream &operator >>(istream &s, myInt &a) {
+  char *p;
+  p = (char *)new char[8192];
+  s >> p;
+  a = (myInt)p;
+
+  delete p;
+
+  return s;
+}
+
+myInt gcd(myInt a, myInt b) {
+  myInt g;
+  mpz_gcd(g._x, a._x, b._x);
+
+  return g;
+}
+
+bool isprime(myInt a) {
+  return (bool)mpz_probab_prime_p(a._x, 25);
+}
+
+bool issquare(myInt a) {
+  return (bool)mpz_perfect_square_p(a._x);
+}
+
+myInt sqrt(myInt a) {
+  myInt r;
+  mpz_sqrt(r._x, a._x);
+
+  return r;
+}
diff --git a/dixon/myint.h b/dixon/myint.h
new file mode 100644
index 0000000..79e142c
--- /dev/null
+++ b/dixon/myint.h
@@ -0,0 +1,112 @@
+#include <stdlib.h>
+
+#ifndef __MYINT__
+#define __MYINT__
+
+#include <iostream.h>
+#include <time.h>
+#include <gmp.h>
+
+class myInt {
+ private:
+  mpz_t _x;
+  int base;
+
+ public:
+  myInt(void);
+  myInt(int);
+  myInt(const myInt &);
+  myInt(char *);
+  myInt(mpz_t);
+
+  ~myInt(void);
+
+  operator bool(void);
+  operator int(void);
+  operator float(void);
+  operator double(void);
+
+  void operator =(myInt);
+  void operator =(int);
+  void operator =(char *);
+  void operator =(const char *);
+  void operator =(mpz_t);
+
+  myInt operator -(void);
+  bool operator !(void);
+
+  void operator +=(myInt);
+  void operator +=(int);
+
+  void operator -=(myInt);
+  void operator -=(int);
+
+  void operator *=(myInt);
+  void operator *=(int);
+
+  void operator /=(myInt);
+  void operator /=(int);
+
+  void operator %=(myInt);
+  void operator %=(int);
+
+  myInt operator ++(void);
+  myInt operator --(void);
+
+  myInt operator ++(int);
+  myInt operator --(int);
+
+  friend myInt operator +(myInt, myInt);
+  friend myInt operator +(myInt, int);
+  friend myInt operator +(int, myInt);
+
+  friend myInt operator -(myInt, myInt);
+  friend myInt operator -(myInt, int);
+  friend myInt operator -(int, myInt);
+
+  friend myInt operator *(myInt, myInt);
+  friend myInt operator *(myInt, int);
+  friend myInt operator *(int, myInt);
+
+  friend myInt operator /(myInt, myInt);
+  friend myInt operator /(myInt, int);
+  friend myInt operator /(int, myInt);
+
+  friend myInt operator %(myInt, myInt);
+  friend myInt operator %(myInt, int);
+  friend myInt operator %(int, myInt);
+
+
+  friend bool operator ==(myInt, myInt);
+  friend bool operator ==(myInt, int);
+  friend bool operator ==(int, myInt);
+
+  friend bool operator !=(myInt, myInt);
+  friend bool operator !=(myInt, int);
+  friend bool operator !=(int, myInt);
+
+  friend bool operator <(myInt, myInt);
+  friend bool operator <(myInt, int);
+  friend bool operator <(int, myInt);
+
+  friend bool operator <=(myInt, myInt);
+  friend bool operator <=(myInt, int);
+  friend bool operator <=(int, myInt);
+
+  friend bool operator >(myInt, myInt);
+  friend bool operator >(myInt, int);
+  friend bool operator >(int, myInt);
+
+  friend bool operator >=(myInt, myInt);
+  friend bool operator >=(myInt, int);
+  friend bool operator >=(int, myInt);
+
+  friend ostream &operator <<(ostream &, myInt);
+  friend istream &operator >>(istream &, myInt &);
+
+  friend myInt gcd(myInt, myInt);
+  friend bool isprime(myInt);
+  friend bool issquare(myInt);
+  friend myInt sqrt(myInt);
+};
+#endif
-- 
2.11.4.GIT