summaryrefslogtreecommitdiff
path: root/math/bigint.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'math/bigint.cpp')
-rw-r--r--math/bigint.cpp247
1 files changed, 247 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();
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 22:59:23 +0000