Initial revision

5 files changed, 885 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..ecc1607
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,21 @@
+# $Id$
+
+CC = g++
+CPPFLAGS = -Wall -Wmissing-prototypes -Wstrict-prototypes
+
+OBJECTS = main.o mtxinteger.o
+BINARY = mtx
+
+.PHONY: clean
+
+$(BINARY): $(OBJECTS)
+	$(CC) $(CPPFLAGS) -o $(BINARY) $(OBJECTS)
+
+main.o: main.cc mtxinteger.h 
+	$(CC) $(CPPFLAGS) -c -o main.o main.cc
+
+mtxinteger.o: mtxinteger.cc mtxinteger.h
+	$(CC) $(CPPFLAGS) -c -o mtxinteger.o mtxinteger.cc
+
+clean:
+	rm -f $(BINARY) *.o
diff --git a/main.cc b/main.cc
new file mode 100644
index 0000000..ed3187e
--- /dev/null
+++ b/main.cc
@@ -0,0 +1,70 @@
+/* $Id$ */
+
+/*
+ * Copyright (C) 2005-2006 Richard Braun
+ * 
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include <iostream>
+
+#include "mtxinteger.h"
+
+using namespace std;
+
+int main(int argc, char *argv[]){
+    MtxInteger a, b;
+
+    if(argc != 3){
+        fprintf(stderr, "usage: mtx <int1> <int2>\n");
+        return 1;
+    }
+
+    a = argv[1];
+    b = argv[2];
+
+    cout << "a = ";
+    a.display();
+    cout << ", b = ";
+    b.display();
+    cout << endl;
+
+    cout << "a + b = ";
+    (a + b).display();
+    cout << endl;
+
+    cout << "a - b = ";
+    (a - b).display();
+    cout << endl;
+
+    cout << "a * b = ";
+    (a * b).display();
+    cout << endl;
+
+    cout << "a / b = ";
+    (a / b).display();
+    cout << endl;
+
+    cout << "a % b = ";
+    (a % b).display();
+    cout << endl;
+
+    cout << "a > b = " << (a > b) << endl;
+    cout << "a >= b = " << (a >= b) << endl;
+    cout << "a < b = " << (a < b) << endl;
+    cout << "a <= b = " << (a <= b) << endl;
+
+    return 0;
+}
diff --git a/mtx.h b/mtx.h
new file mode 100644
index 0000000..d6026e7
--- /dev/null
+++ b/mtx.h
@@ -0,0 +1,27 @@
+/* $Id$ */
+
+/*
+ * Copyright (C) 2005-2006 Richard Braun
+ * 
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#ifndef _MTX_H
+#define _MTX_H
+
+#define MTX_POSITIVE 1
+#define MTX_NEGATIVE 2
+
+#endif /* _MTX_H */
diff --git a/mtxinteger.cc b/mtxinteger.cc
new file mode 100644
index 0000000..e283413
--- /dev/null
+++ b/mtxinteger.cc
@@ -0,0 +1,693 @@
+/* $Id$ */
+
+/*
+ * Copyright (C) 2005-2006 Richard Braun
+ * 
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+#include <iostream>
+
+#include "mtxinteger.h"
+
+using namespace std;
+
+MtxInteger::MtxInteger(){
+    digits = NULL;
+    setDigits("0");
+}
+
+MtxInteger::MtxInteger(int integer){
+    char *tmp;
+
+    digits = NULL;
+    tmp = parseInt(integer);
+    setDigits(tmp);
+    delete tmp;
+}
+
+MtxInteger::MtxInteger(const char *digits){
+    this->digits = NULL;
+    setDigits(digits);
+}
+
+MtxInteger::MtxInteger(const MtxInteger &integer){
+    digits = NULL;
+    setDigits(integer.digits);
+    sign = integer.sign;
+}
+
+MtxInteger::~MtxInteger(){
+    delete digits;
+}
+
+MtxInteger & MtxInteger::operator=(const MtxInteger &integer){
+    if(this != &integer){
+        setDigits(integer.digits);
+        sign = integer.sign;
+    }
+
+    return *this;
+}
+
+MtxInteger MtxInteger::operator+() const {
+    return *this;
+}
+
+MtxInteger MtxInteger::operator-() const {
+    MtxInteger new_integer(*this);
+
+    new_integer.sign = ((new_integer.sign == MTX_POSITIVE)
+                        && (new_integer != 0))
+                     ? MTX_NEGATIVE
+                     : MTX_POSITIVE;
+
+    return new_integer;
+}
+
+static int charToInt(char c){
+    switch(c){
+        case '0' :
+            return 0;
+            break;
+        case '1' :
+            return 1;
+            break;
+        case '2' :
+            return 2;
+            break;
+        case '3' :
+            return 3;
+            break;
+        case '4' :
+            return 4;
+            break;
+        case '5' :
+            return 5;
+            break;
+        case '6' :
+            return 6;
+            break;
+        case '7' :
+            return 7;
+            break;
+        case '8' :
+            return 8;
+            break;
+        case '9' :
+            return 9;
+            break;
+    }
+
+    return -1;
+}
+
+static char intToChar(int n){
+    switch(n){
+        case 0 :
+            return '0';
+            break;
+        case 1 :
+            return '1';
+            break;
+        case 2 :
+            return '2';
+            break;
+        case 3 :
+            return '3';
+            break;
+        case 4 :
+            return '4';
+            break;
+        case 5 :
+            return '5';
+            break;
+        case 6 :
+            return '6';
+            break;
+        case 7 :
+            return '7';
+            break;
+        case 8 :
+            return '8';
+            break;
+        case 9 :
+            return '9';
+            break;
+    }
+
+    return -1;
+}
+
+bool MtxInteger::operator==(const MtxInteger &integer) const {
+    if(sign == integer.sign && strcmp(digits, integer.digits) == 0)
+        return true;
+
+    else
+        return false;
+}
+
+bool MtxInteger::operator!=(const MtxInteger &integer) const {
+    return !(*this == integer);
+}
+
+bool MtxInteger::operator>(const MtxInteger &integer) const {
+    if(this == &integer)
+        return false;
+
+    else if(*this == integer)
+        return false;
+
+    else if(sign != integer.sign){
+        if(sign == MTX_POSITIVE)
+            return true;
+
+        else
+            return false;
+    }
+
+    else {
+        size_t i, length, length1, length2;
+        bool result;
+        int a, b;
+
+        length1 = strlen(digits);
+        length2 = strlen(integer.digits);
+        length = (length1 > length2) ? length1 : length2;
+
+        for(i = 0; i < length; i++){
+            a = ((length - length1) > i)
+                ? 0
+                : charToInt(digits[i - (length - length1)]);
+            b = ((length - length2) > i)
+                ? 0
+                : charToInt(integer.digits[i - (length - length2)]);
+
+            if(a != b){
+                if(a > b)
+                    result = true;
+
+                else
+                    result = false;
+
+                if(sign == MTX_POSITIVE)
+                    return result;
+
+                else
+                    return !result;
+            }
+        }
+
+        return false;
+    }
+}
+
+bool MtxInteger::operator>=(const MtxInteger &integer) const {
+    return (*this > integer || *this == integer);
+}
+
+bool MtxInteger::operator<(const MtxInteger &integer) const {
+    return integer > *this;
+}
+
+bool MtxInteger::operator<=(const MtxInteger &integer) const {
+    return (*this < integer || *this == integer);
+}
+
+MtxInteger MtxInteger::operator+(const MtxInteger &integer) const {
+    if(sign != integer.sign)
+        return *this - (-integer);
+
+    else {
+        size_t i, length, length1, length2;
+        MtxInteger new_integer;
+        int a, b, c, tmp_int;
+        char *tmp;
+
+        length1 = strlen(digits);
+        length2 = strlen(integer.digits);
+
+        /*
+         * Allocate enough memory for any possible decimal addition.
+         */
+        length = ((length1 > length2) ? length1 : length2) + 1;
+        tmp = new char[length + 1];
+        tmp[length] = '\0';
+
+        tmp_int = 0;
+
+        for(i = 0; i < length; i++){
+            a = (i >= length1)
+                ? 0
+                : charToInt(digits[length1 - 1 - i]);
+            b = (i >= length2)
+                ? 0
+                : charToInt(integer.digits[length2 - 1 - i]);
+            c = a + b + tmp_int;
+            tmp_int = c / 10;
+
+            if(tmp_int)
+                c -= 10;
+
+            tmp[length - 1 - i] = intToChar(c);
+        }
+
+        new_integer.setDigits(tmp);
+
+        delete tmp;
+
+        if(sign == MTX_POSITIVE)
+            return new_integer;
+
+        else
+            return -new_integer;
+    }
+}
+
+MtxInteger & MtxInteger::operator++(){
+    *this = *this + 1;
+
+    return *this;
+}
+
+MtxInteger & MtxInteger::operator++(int a){
+    *this = *this + 1;
+
+    return *this;
+}
+
+MtxInteger & MtxInteger::operator+=(const MtxInteger &integer){
+    *this = *this + integer;
+
+    return *this;
+}
+
+MtxInteger MtxInteger::operator-(const MtxInteger &integer) const {
+    if(sign != integer.sign)
+        return *this + (-integer);
+
+    else {
+        size_t i, length, length1, length2;
+        const MtxInteger *i1, *i2;
+        MtxInteger new_integer;
+        int a, b, c, tmp_int;
+        char *tmp;
+
+        if(abs() >= integer.abs()){
+            i1 = this;
+            i2 = &integer;
+        }
+
+        else {
+            i1 = &integer;
+            i2 = this;
+        }
+
+        length1 = strlen(i1->digits);
+        length2 = strlen(i2->digits);
+        length = (length1 > length2) ? length1 : length2;
+        tmp = new char[length + 1];
+        tmp[length] = '\0';
+
+        tmp_int = 0;
+
+        for(i = 0; i < length; i++){
+            a = (i >= length1)
+                ? 0
+                : charToInt(i1->digits[length1 - 1 - i]);
+            b = (i >= length2)
+                ? 0
+                : charToInt(i2->digits[length2 - 1 - i]);
+            c = a - (b + tmp_int);
+
+            if(c < 0){
+                tmp_int = 1;
+                c += 10;
+            }
+
+            else
+                tmp_int = 0;
+
+            tmp[length - 1 - i] = intToChar(c);
+        }
+
+        new_integer.setDigits(tmp);
+
+        delete tmp;
+
+        if(i1 == &integer)
+            new_integer = -new_integer;
+
+        if(sign == MTX_POSITIVE)
+            return new_integer;
+
+        else
+            return -new_integer;
+    }
+}
+
+MtxInteger & MtxInteger::operator--(){
+    *this = *this - 1;
+
+    return *this;
+}
+
+MtxInteger & MtxInteger::operator--(int a){
+    *this = *this - 1;
+
+    return *this;
+}
+
+MtxInteger & MtxInteger::operator-=(const MtxInteger &integer){
+    *this = *this - integer;
+
+    return *this;
+}
+
+MtxInteger MtxInteger::pot(int integer0, size_t power){
+    MtxInteger integer, new_integer;
+    size_t length, length1;
+    char *tmp, *ptr;
+
+    integer = integer0;
+
+    length1 = strlen(integer.digits);
+    length = length1 + power;
+    tmp = new char[length + 1];
+    tmp[length] = '\0';
+
+    ptr = tmp;
+    memcpy(ptr, integer.digits, length1);
+    ptr += length1;
+    memset(ptr, '0', power);
+
+    new_integer.setDigits(tmp);
+    new_integer.sign = integer.sign;
+
+    return new_integer;
+}
+
+MtxInteger MtxInteger::operator*(const MtxInteger &integer) const {
+    if(*this == 0 || integer == 0)
+        return 0;
+
+    else if(*this == 1)
+        return integer;
+
+    else if(integer == 1)
+        return *this;
+
+    else {
+        size_t i, j, length1, length2;
+        MtxInteger new_integer;
+
+        length1 = strlen(digits);
+        length2 = strlen(integer.digits);
+
+        for(i = 1; i <= length1; i++){
+            for(j = 1; j <= length2; j++)
+                new_integer += pot(charToInt(digits[length1 - i])
+                                   * charToInt(integer.digits[length2 - j]),
+                                   (i - 1) + (j - 1));
+        }
+
+        if(sign == integer.sign)
+            return new_integer;
+
+        else
+            return -new_integer;
+    }
+}
+
+MtxInteger & MtxInteger::operator*=(const MtxInteger &integer){
+    *this = *this * integer;
+
+    return *this;
+}
+
+MtxInteger MtxInteger::divideByTwo() const {
+    MtxInteger new_integer;
+    int a, n, tmp_int;
+    size_t i, length;
+    char *tmp;
+
+    length = strlen(digits);
+    tmp = new char[length + 1];
+    tmp[length] = '\0';
+
+    tmp_int = 0;
+
+    for(i = 0; i < length; i++){
+        n = charToInt(digits[i]);
+
+        switch(tmp_int + n){
+            case 0 : case 1 :
+                a = '0';
+                break;
+            case 2 : case 3 :
+                a = '1';
+                break;
+            case 4 : case 5 :
+                a = '2';
+                break;
+            case 6 : case 7 :
+                a = '3';
+                break;
+            case 8 : case 9 :
+                a = '4';
+                break;
+            case 10 : case 11 :
+                a = '5';
+                break;
+            case 12 : case 13 :
+                a = '6';
+                break;
+            case 14 : case 15 :
+                a = '7';
+                break;
+            case 16 : case 17 :
+                a = '8';
+                break;
+            case 18 : case 19 :
+                a = '9';
+                break;
+        }
+
+        tmp_int = n % 2;
+
+        if(tmp_int)
+            tmp_int = 10;
+
+        tmp[i] = a;
+    }
+
+    new_integer.setDigits(tmp);
+
+    delete tmp;
+
+    new_integer.sign = sign;
+
+    return new_integer;
+}
+
+MtxInteger MtxInteger::divide(const MtxInteger &integer, bool modulo0) const {
+    /*
+     * TODO: When I know how to use exceptions ... :-)
+     */
+    if(integer == 0)
+        return 0;
+
+    else if(*this == 0)
+        return 0;
+
+    else if(*this == integer){
+        if(modulo0)
+            return 0;
+
+        else
+            return 1;
+    }
+
+    else if(*this == -integer){
+        if(modulo0)
+            return 0;
+
+        else
+            return -1;
+    }
+
+    else if(integer == 1){
+        if(modulo0)
+            return 0;
+
+        else
+            return *this;
+    }
+
+    else if(integer == -1){
+        if(modulo0)
+            return 0;
+
+        else
+            return -*this;
+    }
+
+    else if(abs() < integer.abs()){
+        if(modulo0)
+            return *this;
+
+        else
+            return 0;
+    }
+
+    else {
+        MtxInteger inf, sup, tmp, result, this_abs, integer_abs, modulo;
+
+        this_abs = abs();
+        integer_abs = integer.abs();
+
+        inf = 0;
+        sup = this_abs;
+
+        do {
+            result = inf + (sup - inf).divideByTwo();
+            tmp = result * integer_abs;
+
+            if(tmp > this_abs)
+                sup = result;
+
+            else {
+                modulo = this_abs - tmp;
+
+                if(modulo < integer_abs)
+                    break;
+
+                inf = result;
+            }
+        } while(true);
+
+        if(modulo0){
+            if(sign == MTX_POSITIVE)
+                return modulo;
+
+            else
+                return -modulo;
+        }
+
+        else {
+            if(sign == integer.sign)
+                return result;
+
+            else
+                return -result;
+        }
+    }
+}
+
+MtxInteger MtxInteger::operator/(const MtxInteger &integer) const {
+    return divide(integer, false);
+}
+
+MtxInteger & MtxInteger::operator/=(const MtxInteger &integer){
+    *this = *this / integer;
+
+    return *this;
+}
+
+MtxInteger MtxInteger::operator%(const MtxInteger &integer) const {
+    return divide(integer, true);
+}
+
+MtxInteger & MtxInteger::operator%=(const MtxInteger &integer){
+    *this = *this % integer;
+
+    return *this;
+}
+
+MtxInteger MtxInteger::abs() const {
+    MtxInteger new_integer(*this);
+
+    new_integer.sign = MTX_POSITIVE;
+
+    return new_integer;
+}
+
+void MtxInteger::setDigits(const char *digits){
+    size_t size;
+
+    delete this->digits;
+
+    /*
+     * TODO: When I know how to use exceptions in C++, implement format
+     * checking here.
+     */
+
+    if(digits[0] == '-'){
+        sign = MTX_NEGATIVE;
+        digits++;
+    }
+
+    else {
+        sign = MTX_POSITIVE;
+
+        if(digits[0] == '+')
+            digits++;
+    }
+
+    while(*digits == '0')
+        digits++;
+
+    if(*digits == '\0'){
+        digits--;
+        sign = MTX_POSITIVE;
+    }
+
+    size = strlen(digits);
+    this->digits = new char[size + 1];
+    strncpy(this->digits, digits, size);
+    this->digits[size] = '\0';
+}
+
+void MtxInteger::display() const {
+    if(sign == MTX_NEGATIVE)
+        cout << '-';
+
+    cout << digits;
+}
+
+int MtxInteger::toInt() const {
+    int integer;
+
+    integer = atoi(digits);
+
+    if(sign == MTX_NEGATIVE)
+        integer = -integer;
+
+    return integer;
+}
+
+char * MtxInteger::parseInt(int integer){
+    char *tmp;
+    int size;
+
+    size = snprintf(NULL, 0, "%d", integer) + 1;
+    tmp = new char[size];
+    snprintf(tmp, size, "%d", integer);
+
+    return tmp;
+}
diff --git a/mtxinteger.h b/mtxinteger.h
new file mode 100644
index 0000000..787f26b
--- /dev/null
+++ b/mtxinteger.h
@@ -0,0 +1,74 @@
+/* $Id$ */
+
+/*
+ * Copyright (C) 2005-2006 Richard Braun
+ * 
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#ifndef _MTXINTEGER_H
+#define _MTXINTEGER_H
+
+#include "mtx.h"
+
+class MtxInteger {
+    private:
+        char *digits;
+        int sign;
+        void setDigits(const char *digits);
+        MtxInteger divideByTwo() const;
+        MtxInteger divide(const MtxInteger &integer, bool modulo0) const;
+
+        /*
+         * Return integer0 * 10^power.
+         */
+        static MtxInteger MtxInteger::pot(int integer0, size_t power);
+
+    public:
+        MtxInteger();
+        MtxInteger(int integer);
+        MtxInteger(const char *digits);
+        MtxInteger(const MtxInteger &integer);
+        ~MtxInteger();
+        MtxInteger & operator=(const MtxInteger &integer);
+        MtxInteger operator+() const;
+        MtxInteger operator-() const;
+        bool operator==(const MtxInteger &integer) const;
+        bool operator!=(const MtxInteger &integer) const;
+        bool operator>(const MtxInteger &integer) const;
+        bool operator>=(const MtxInteger &integer) const;
+        bool operator<(const MtxInteger &integer) const;
+        bool operator<=(const MtxInteger &integer) const;
+        MtxInteger operator+(const MtxInteger &integer) const;
+        MtxInteger & operator++();
+        MtxInteger & operator++(int a);
+        MtxInteger & operator+=(const MtxInteger &integer);
+        MtxInteger operator-(const MtxInteger &integer) const;
+        MtxInteger & operator--();
+        MtxInteger & operator--(int a);
+        MtxInteger & operator-=(const MtxInteger &integer);
+        MtxInteger operator*(const MtxInteger &integer) const;
+        MtxInteger & operator*=(const MtxInteger &integer);
+        MtxInteger operator/(const MtxInteger &integer) const;
+        MtxInteger & operator/=(const MtxInteger &integer);
+        MtxInteger operator%(const MtxInteger &integer) const;
+        MtxInteger & operator%=(const MtxInteger &integer);
+        MtxInteger abs() const;
+        void display() const;
+        int toInt() const;
+        static char * parseInt(int n);
+};
+
+#endif /* _MTXINTEGER_H */