Added C++ bigint implementation.

2 files changed, 250 insertions, 0 deletions

diff --git a/math/bigint.cpp b/math/bigint.cpp
new file mode 100644
index 0000000..e0424a6
--- /dev/null
+++ b/math/bigint.cpp
@@ -0,0 +1,247 @@
+// Bislang keine Division. Multiplikation nach Schulmethode.
+#define PLUS  0
+#define MINUS 1
+#define BASE  1000000000
+
+struct bigint {
+  int sign;
+  vector<ll> digits;
+
+  // Initialisiert mit 0.
+  bigint(void) {
+    sign = PLUS;
+  }
+
+  // Initialisiert mit kleinem Wert.
+  bigint(ll value) {
+    if (value == 0) sign = PLUS;
+    else {
+      sign = value >= 0 ? PLUS : MINUS;
+      value = abs(value);
+      while (value) {
+        digits.push_back(value % BASE);
+        value /= BASE;
+      }
+    } 
+  }
+
+  // Initialisiert mit C-String. Kann nicht mit Vorzeichen umgehen.
+  bigint(char *str, int length) {
+    int base = 1;
+    ll digit = 0;
+    for (int i = length - 1; i >= 0; i--) {
+      digit += base * (str[i] - '0');
+      if (base * 10 == BASE) {
+        digits.push_back(digit);
+        digit = 0;
+        base = 1;
+      } else base *= 10;
+    }
+    if (digit != 0) digits.push_back(digit);
+    sign = PLUS;
+  }
+
+  // Löscht führende Nullen und macht -0 zu 0.
+  void trim() {
+    while (digits.size() > 0 && digits[digits.size() - 1] == 0) digits.pop_back();
+    if (digits.size() == 0 && sign == MINUS) sign = PLUS;
+  }
+
+  // Gibt die Zahl aus.
+  void print() {
+    if (digits.size() == 0) {
+      printf("0");
+      return;
+    }
+    if (sign == MINUS) printf("-");
+    printf("%lld", digits[digits.size() - 1]);
+    for (int i = digits.size() - 2; i >= 0; i--) {
+      printf("%09lld", digits[i]);
+    }
+  }
+};
+
+// Kleiner-oder-gleich-Vergleich.
+bool operator<=(bigint &a, bigint &b) {
+  if (a.digits.size() == b.digits.size()) {
+    int idx = a.digits.size() - 1;
+    while (idx >= 0) {
+      if (a.digits[idx] < b.digits[idx]) return true;
+      else if (a.digits[idx] > b.digits[idx]) return false;
+      idx--;
+    }
+    return true;
+  }
+  return a.digits.size() < b.digits.size();
+}
+
+// Kleiner-Vergeleich.
+bool operator<(bigint &a, bigint &b) {
+  if (a.digits.size() == b.digits.size()) {
+    int idx = a.digits.size() - 1;
+    while (idx >= 0) {
+      if (a.digits[idx] < b.digits[idx]) return true;
+      else if (a.digits[idx] > b.digits[idx]) return false;
+      idx--;
+    }
+    return false;
+  }
+  return a.digits.size() < b.digits.size();
+}
+
+void sub(bigint *a, bigint *b, bigint *c);
+
+// a+b=c. a, b, c dürfen gleich sein.
+void add(bigint *a, bigint *b, bigint *c) {
+  if (a->sign == b->sign) c->sign = a->sign;
+  else {
+    if (a->sign == MINUS) {
+      a->sign ^= 1;
+      sub(b, a, c);
+      a->sign ^= 1;
+    } else {
+      b->sign ^= 1;
+      sub(a, b, c);
+      b->sign ^= 1;
+    }
+    return;
+  }
+
+  c->digits.resize(max(a->digits.size(), b->digits.size()));
+  ll carry = 0;
+  int i = 0;
+  for (; i < (int)min(a->digits.size(), b->digits.size()); i++) {
+    ll sum = carry + a->digits[i] + b->digits[i];
+    c->digits[i] = sum % BASE;
+    carry = sum / BASE;
+  }
+  if (i < (int)a->digits.size()) {
+    for (; i< (int)a->digits.size(); i++) {
+      ll sum = carry + a->digits[i];
+      c->digits[i] = sum % BASE;
+      carry = sum / BASE;
+    }
+  } else {
+    for (; i< (int)b->digits.size(); i++) {
+      ll sum = carry + b->digits[i];
+      c->digits[i] = sum % BASE;
+      carry = sum / BASE;
+    }
+  }
+  if (carry) {
+    c->digits.push_back(carry);
+  }
+}
+
+// a-b=c. c darf a oder b sein. a und b müssen verschieden sein.
+void sub(bigint *a, bigint *b, bigint *c) {
+  if (a->sign == MINUS || b->sign == MINUS) {
+    b->sign ^= 1;
+    add(a, b, c);
+    b->sign ^= 1;
+    return;
+  }
+
+  if (a < b) {
+    sub(b, a, c);
+    c->sign = MINUS;
+    c->trim();
+    return;
+  }
+
+  c->digits.resize(a->digits.size());
+  ll borrow = 0;
+  int i = 0;
+  for (; i < (int)b->digits.size(); i++) {
+    ll diff = a->digits[i] - borrow - b->digits[i];
+    if (a->digits[i] > 0) borrow = 0;
+    if (diff < 0) {
+      diff += BASE;
+      borrow = 1;
+    }
+    c->digits[i] = diff % BASE;
+  }
+  for (; i < (int)a->digits.size(); i++) {
+    ll diff = a->digits[i] - borrow;
+    if (a->digits[i] > 0) borrow = 0;
+    if (diff < 0) {
+      diff += BASE;
+      borrow = 1;
+    }
+    c->digits[i] = diff % BASE;
+  }
+  c->trim();
+}
+
+// Ziffernmultiplikation a*b=c. b und c dürfen gleich sein. a muss kleiner BASE sein.
+void digitMul(ll a, bigint *b, bigint *c) {
+  if (a == 0) {
+    c->digits.clear();
+    c->sign = PLUS;
+    return;
+  }
+  c->digits.resize(b->digits.size());
+  ll carry = 0;
+  for (int i = 0; i < (int)b->digits.size(); i++) {
+    ll prod = carry + b->digits[i] * a;
+    c->digits[i] = prod % BASE;
+    carry = prod / BASE;
+  }
+  if (carry) c->digits.push_back(carry);
+  c->sign = (a > 0) ? b->sign : 1 ^ b->sign;
+  c->trim();
+}
+
+// Zifferndivision b/a=c. b und c dürfen gleich sein. a muss kleiner BASE sein.
+void digitDiv(ll a, bigint *b, bigint *c) {
+  c->digits.resize(b->digits.size());
+  ll carry = 0;
+  for (int i = (int)b->digits.size() - 1; i>= 0; i--) {
+    ll quot = (carry * BASE + b->digits[i]) / a;
+    carry = carry * BASE + b->digits[i] - quot * a;
+    c->digits[i] = quot;
+  }
+  c->sign = b->sign ^ (a < 0);
+  c->trim();
+} 
+
+// a*b=c. c darf weder a noch b sein. a und b dürfen gleich sein.
+void mult(bigint *a, bigint *b, bigint *c) {
+  bigint row = *a;
+  bigint tmp;
+  c->digits.clear();
+  for (int i = 0; i < (int)b->digits.size(); i++) {
+    digitMul(b->digits[i], &row, &tmp);
+    add(&tmp, c, c);
+    row.digits.insert(row.digits.begin(), 0);
+  }
+  c->sign = a->sign != b->sign;
+  c->trim();
+}
+
+// Berechnet eine kleine Zehnerpotenz.
+inline ll pow10(int n) {
+  ll res = 1;
+  for (int i = 0; i < n; i++) res *= 10;
+  return res;
+}
+
+// Berechnet eine große Zehnerpotenz.
+void power10(ll e, bigint *out) {
+  out->digits.assign(e / 9 + 1, 0);
+  if (e % 9) out->digits[out->digits.size() - 1] = pow10(e % 9);
+  else out->digits[out->digits.size() - 1] = 1;
+}
+
+// Nimmt eine Zahl module einer Zehnerpotenz 10^e.
+void mod10(int e, bigint *a) {
+  int idx = e / 9;
+  if ((int)a->digits.size() < idx + 1) return;
+  if (e % 9) {
+    a->digits.resize(idx + 1);
+    a->digits[idx] %= pow10(e % 9);
+  } else {
+    a->digits.resize(idx);
+  }
+  a->trim();
+}
diff --git a/math/math.tex b/math/math.tex
index 90e7b3b..59219e5 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -180,3 +180,6 @@ Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximale
 
 \subsection{3D-Kugeln}
 \lstinputlisting{math/gcDist.cpp}
+
+\subsection{Big Integers}
+\lstinputlisting{math/bigint.cpp}