From 0a73fc73c29a134f90a69f978ee240ef27b22650 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=A9mie=20LAVAL?= Date: Sun, 7 Dec 2008 00:10:07 +0100 Subject: [PATCH] * Karatsuba seems to work on n-sized number now. Included a Clean function to remove leading 0s. * Added GUI glade file. * Added a Makefile with some basic useful target. --- Makefile | 16 ++ biginteger.c | 50 +++++- gui.glade | 533 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 591 insertions(+), 8 deletions(-) create mode 100644 Makefile create mode 100644 gui.glade diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..cd1b737 --- /dev/null +++ b/Makefile @@ -0,0 +1,16 @@ +all: biginteger.so + +test: biginteger.so + gcc -Wall -lbiginteger -L. -o test test.c + +run: test + ./test 123456 111111 + +debug: biginteger.c biginteger.h test.c + gcc -o test -Wall -ggdb biginteger.c biginteger.h test.c + +biginteger.so: biginteger.c biginteger.h + gcc -shared -fpic -Wall -o libbiginteger.so biginteger.c biginteger.h + +clean: + rm test libbiginteger.so \ No newline at end of file diff --git a/biginteger.c b/biginteger.c index 2d41ccc..8186960 100644 --- a/biginteger.c +++ b/biginteger.c @@ -65,6 +65,23 @@ BigUnsignedInteger* CopyBigInteger(BigInteger source, BigInteger* dest, BigUnsig return node; } +void Clean(BigInteger* b) +{ + BigUnsignedInteger* node = b->AbsValEnd; + if (node->Value != 0) + return; + + while (node->Value == 0) { + BigUnsignedInteger* toFree = node; + node = node->Previous; + free(toFree); + } + + // Erase things up + b->AbsValEnd = node; + node->Next = NULL; +} + // base = part1 * 10000^N + part2 void SplitBigInteger(int N, BigInteger base, BigInteger* part1, BigInteger* part2) { @@ -314,10 +331,11 @@ BigInteger sumBigInt(BigInteger b1, BigInteger b2) cont = node2 != NULL || cont; } - if (!cont && carry > 0) - PushEndNode(&result, carry); } while(cont); + if (carry > 0) + PushEndNode(&result, carry); + return result; } @@ -416,14 +434,26 @@ BigInteger mulBigInt(BigInteger x, BigInteger y) if (x.Sign == 0 || y.Sign == 0) return CreateZeroBigInt(); - if (MAX(x.Count, y.Count) == 1) { + // If we have a biginteger with one node no point in further splitting + if (MIN(x.Count, y.Count) == 1) { BigInteger temp = CreateZeroBigInt(); temp.Sign = Positive; - unsigned int result = x.AbsValStart->Value * y.AbsValStart->Value; - if (result / BASE != 0) - PushFrontNode(&temp, result / BASE); - PushFrontNode(&temp, result % BASE); + BigUnsignedInteger* big = (x.Count == 1) ? y.AbsValStart : x.AbsValStart; + unsigned int multiplier = (x.Count == 1) ? x.AbsValStart->Value : y.AbsValStart->Value; + + unsigned int carry = 0; + + while (big != NULL) { + unsigned int r = big->Value * multiplier + carry; + carry = r / BASE; + PushEndNode(&temp, r % BASE); + + big = big->Next; + } + if (carry != 0) + PushEndNode(&temp, carry); + return temp; } @@ -451,7 +481,11 @@ BigInteger mulBigInt(BigInteger x, BigInteger y) MultiplyByBase(&a, 2*k); MultiplyByBase(&abc, k); - return sumBigInt(sumBigInt(a, abc), b); + BigInteger result = sumBigInt(sumBigInt(a, abc), b); + // Remove leading 0s if any + Clean(&result); + + return result; } // Returns b^n diff --git a/gui.glade b/gui.glade new file mode 100644 index 0000000..5daa3e2 --- /dev/null +++ b/gui.glade @@ -0,0 +1,533 @@ + + + + + + False + 200 + + + True + + + True + + + True + _Fichier + True + + + True + + + True + gtk-new + True + True + + + + + True + gtk-open + True + True + + + + + True + gtk-save + True + True + + + + + True + gtk-save-as + True + True + + + + + True + + + + + True + gtk-quit + True + True + + + + + + + + + True + É_dition + True + + + True + + + True + gtk-cut + True + True + + + + + True + gtk-copy + True + True + + + + + True + gtk-paste + True + True + + + + + True + gtk-delete + True + True + + + + + + + + + True + _Affichage + True + + + + + True + Aid_e + True + + + True + + + True + gtk-about + True + True + + + + + + + + + False + + + + + True + + + True + 7 + 20 + 5 + 5 + + + True + True + + + + + False + + + + + True + + + True + 4 + 9 + 9 + + + True + 4 + 3 + True + + + + + + True + True + True + (-) + 0 + + + 3 + 4 + + + + + True + True + True + 9 + 0 + + + + 2 + 3 + 2 + 3 + + + + + True + True + True + 8 + 0 + + + + 1 + 2 + 2 + 3 + + + + + True + True + True + 7 + 0 + + + + 2 + 3 + + + + + True + True + True + 6 + 0 + + + + 2 + 3 + 1 + 2 + + + + + True + True + True + 5 + 0 + + + + 1 + 2 + 1 + 2 + + + + + True + True + True + 4 + 0 + + + + 1 + 2 + + + + + True + True + True + 3 + 0 + + + 2 + 3 + + + + + True + True + True + 2 + 0 + + + + 1 + 2 + + + + + True + True + True + 1 + 0 + + + + + + True + True + True + 0 + 0 + + + + 2 + 3 + 3 + 4 + + + + + + + + + True + + + False + 1 + + + + + True + 4 + 9 + 9 + + + True + 5 + 2 + True + + + True + True + True + C(n,p) + 0 + + + 1 + 2 + 4 + 5 + + + + + True + True + True + ! + 0 + + + 4 + 5 + + + + + True + True + True + lcm + 0 + + + 1 + 2 + 3 + 4 + + + + + True + True + True + gcm + 0 + + + 3 + 4 + + + + + True + True + True + > < = + 0 + + + 1 + 2 + 2 + 3 + + + + + True + True + True + % + 0 + + + 2 + 3 + + + + + True + True + True + / + 0 + + + 1 + 2 + 1 + 2 + + + + + True + True + True + X + 0 + + + 1 + 2 + + + + + True + True + True + - + 0 + + + 1 + 2 + + + + + True + True + True + + + 0 + + + + + + + 2 + + + + + 1 + + + + + 1 + + + + + True + 2 + + + False + 2 + + + + + + -- 2.11.4.GIT