longint.cc

Go to the documentation of this file.

//
//  Copyright (c) 2006 by Rafael Ostertag
//
//  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.
//
//
// $Id: longint.cc,v 1.9 2006/12/31 00:49:39 rafi Exp $
//

#include <iostream>
#include <limits>
#include <list>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

#ifdef DEBUG
#include <cassert>
#endif

#include "casobject.h"
#include "casexception.h"
#include "sum.h"
#include "product.h"
#include "fraction.h"
#include "longint.h"

// Private Methods
// ----------------------------------------------------------------------------

unsigned long
LongInt::frontpartlength() const {
    std::list<unsigned int>::const_reference i = lst.front();

    // Here we figure out how much space is needed for the last part of the
    // number.
    for ( int e = 1; e < part_len; e++ ) {
        if ( i < pow ( ( ( double ) 10 ), e ) ) {
            return e;
        }
    }

    return part_len;
}

void
LongInt::str2longint ( const char *str_num ) {

    lst.clear();

    // Points to last printable character
    // of the buffer.
    const char *str_end = str_num + ( strlen ( str_num ) - 1 );

    // This holds the part of the number, beginning from the back
    char part[part_len+1];
    // Terminate the string
    part[part_len] = '\0';

    // Initialize the rest to the character zero
    memset ( part, '0', part_len );

    SetPositive();

    bool part_need_flush = false;
    int c = part_len - 1;
    for ( ;str_num <= str_end;str_end-- ) {
        if ( ( *str_end == '-' ) || ( *str_end == '+' ) ) {
            if ( *str_end == '-' ) {
                SetNegative();
            }
        }
        else {
            part[c] = *str_end;
            part_need_flush = true;
        }
        c--;

        // The condition ``buf==buf_end is checked to make sure ``unit is
        // stored even if the length of ``buf is not a multiple
        // of ``part_len.
        if ( c < 0 || ( str_num == str_end && part_need_flush ) ) {
            unsigned int tmp = strtol ( part, NULL, 10 );
            lst.push_front ( tmp );
            part_need_flush = false;
            c = part_len - 1;
            // Reinitialize (erase) the part
            memset ( part, '0', part_len );
        }
    }

    stripzeros();
    if ( IsZero() ) {
        SetPositive();
    }
}

void
LongInt::num2longint ( const signed long num ) {
    if ( num == 0 ) {
        setzero();
    }
    else {
        // Get size of the number
        // stored in ``l
        int size = snprintf ( NULL, 0, "%ld", num ) + 1;
        char *buf = new char[size];
        snprintf ( buf, size, "%li", num );

        str2longint ( buf );

        delete[] buf;
    }
}

void
LongInt::longint2str ( char *s, unsigned long size ) const {
    if ( s == 0 ) {
        throw EInvArg();
    }

    if ( size < ( Length() + 1 ) ) {
        throw EBufTooSmall();
    }

    memset ( s, 0x0, size );

    // Make the format string
    char fmt[fmt_len];
    snprintf ( fmt, fmt_len, "%%0%du", part_len );

    char *mem_pos = s;
    if ( IsNegative() ) {
        strncpy ( s, "-", 2 );
        mem_pos++;
    }

    std::list<unsigned int>::const_iterator i = lst.begin();
    while ( i != lst.end() ) {
        // The first time, we don't want to have padding to part_len
        if ( i == lst.begin() ) {
            unsigned long frontlen = frontpartlength();
            snprintf ( mem_pos, frontlen + 1, "%u" , *i );
            // Advance pointer to next insertion point
            mem_pos += frontlen;
        }
        else {
            snprintf ( mem_pos, part_len + 1, fmt, *i );
            // Advance pointer to next insertion point
            mem_pos += part_len;
        }

        // Next item
        i++;
    }

}

void
LongInt::setzero() {
    lst.clear();
    lst.push_front ( 0 );
    SetPositive();
}

void
LongInt::stripzeros() {
    // Make sure we do not add a zero item to
    // the front, except the result is zero
    if ( lst.size() < 2 ) {
        return;
    }

    while ( ( *lst.begin() ) == 0 ) {
        lst.pop_front();
        if ( lst.size() < 2 ) {
            break;
        }
    }
}
// ----------------------------------------------------------------------------


// Constructors & Destructors
// ----------------------------------------------------------------------------

LongInt::LongInt ( signed long l ) : CASNumeric(), div_remainder ( 0 ) {
#ifdef SHOWCONSTRUCTOR
    std::cerr << "# LongInt::LongInt(signed long l)" << std::endl;
#endif
    num2longint ( l );
    SetRadix ( ( unsigned long ) pow ( ( ( double ) 10 ), part_len ) );
    meta.SetAll();
}

LongInt::LongInt ( const char *s ) : CASNumeric(), div_remainder ( 0 ) {
#ifdef SHOWCONSTRUCTOR
    std::cerr << "# LongInt::LongInt(const char *s)" << std::endl;
#endif
    str2longint ( s );
    SetRadix ( ( unsigned long ) pow ( ( ( double ) 10 ), part_len ) );
    meta.SetAll();
}

LongInt::LongInt ( const std::string &s ) : CASNumeric(), div_remainder ( 0 ) {
#ifdef SHOWCONSTRUCTOR
    std::cerr << "# LongInt::LongInt(const std::string &s)" << std::endl;
#endif
    str2longint ( s.c_str() );
    SetRadix ( ( unsigned long ) pow ( ( ( double ) 10 ), part_len ) );
    meta.SetAll();
}

LongInt::LongInt ( const LongInt &r ) {
#ifdef SHOWCONSTRUCTOR
    std::cerr << "# Copy Constructor LongInt::LongInt()" << std::endl;
#endif

    SetSign ( r.GetSign() );
    SetDivDepth ( r.GetDivDepth() );
    SetRadix ( r.GetRadix() );
    lst = r.lst;

    if ( r.div_remainder != 0 ) {
        div_remainder = new LongInt ( 0L );
        div_remainder->lst = r.div_remainder->lst;
        div_remainder->SetSign ( r.div_remainder->GetSign() );
    } else {
        div_remainder = 0;
    }
    meta = r.meta;
}

LongInt::~LongInt() {
#ifdef SHOWCONSTRUCTOR
    std::cerr << "# LongInt::~LongInt()" << std::endl;
#endif
    if ( div_remainder != 0 ) {
        delete div_remainder;
    }
}

CASObject*
LongInt::Clone() const {
    LongInt *res = new LongInt;
    *res = *this;

    return res;
}

// ----------------------------------------------------------------------------

// Public Methods
// ----------------------------------------------------------------------------
void LongInt::Get ( char **s ) const throw ( EInvArg,
        EUninitializedPtr ) { if ( s == 0 ) { throw EInvArg(); }

    if ( *s != 0 ) {
        throw EUninitializedPtr();
    }

    // Reserve memory for holding the string
    unsigned long size = Length() + 1;
    *s = new char[size];

    longint2str ( *s, size );
}

void
LongInt::Get ( char *s, unsigned long size ) const {
    longint2str ( s, size );
}

void
LongInt::Get ( std::string &s ) const {
    char *tmp = 0;

    Get ( &tmp );
    s = tmp;

    delete []tmp;
}

unsigned long
LongInt::Length() const {
    long max_strlen = lst.size() * part_len;

    // Do we have to return the length of a negative number, which implies
    // max_strlen+1 because of the space of the minus signed
    max_strlen += IsNegative() ? 1 : 0;

    // We might get a size to big if the front part has not size of part_len.
    // Therefore, we have to find out, how much is not used of the front part.
    return max_strlen - ( part_len - frontpartlength() );
}

void
LongInt::Print() const {
    char *str = 0;
    Get ( &str );

    std::cout << str;

    delete[] str;
}

CASObject*
LongInt::Invert() const {
    LongInt tmp = *this;

    tmp.InvertIP();
    return tmp.Clone();
}

CASObject*
LongInt::Absolute() const {
    LongInt tmp = *this;

    tmp.SetPositive();
    return tmp.Clone();
}

bool
LongInt::IsZero() const{
    return ( lst.size() == 1 && lst.back() == 0 );
}

bool
LongInt::IsOne() const{
    return ( lst.size() == 1 && lst.back() == 1 );
}

CASObject*
LongInt::GCD ( const CASObject* i ) const {
    if ( GetType() != i->GetType() ) {
        LongInt tmp ( 1L );
        return tmp.Clone();
    }
    const LongInt *li = dynamic_cast<const LongInt*> ( i );
#ifdef DEBUG
    assert ( li != 0 );
#endif
    LongInt c = *this > *li ? *this : *li;
    LongInt d = *this > *li ? *li : *this;
    LongInt r;

    while ( !d.IsZero() ) {
        r = c % d;
        c = d;
        d = r;
    }

    LongInt *ret_val = new LongInt ( c );

    return ret_val;
}

LongInt
LongInt::Pow ( const LongInt &exp ) const {
    LongInt tmp ( 1L );

    for ( LongInt i ( 0L ); i < exp; i++ ) {
        tmp = tmp * ( *this );
    }

    return tmp;
}

inline LongInt
LongInt::Pow ( unsigned long exp ) const {
    LongInt tmp ( exp );
    return Pow ( tmp );
}

LongInt
LongInt::FractionalPart ( const LongInt &r ) const {
#ifdef WARNINGS
#warning "LongInt::FractionalPart(): Not fully implemented"
#endif
    // Divide the numbers
    LongInt d_res = *this / r;

    // Get the remainder
    LongInt d_remainder = * ( d_res.div_remainder );

    // Division has no fractional part
    if ( d_remainder.IsZero() ) {
        return LongInt ( 0L );
    }

    LongInt u = d_remainder;
    u.AbsoluteIP();
    LongInt v = r;
    v.AbsoluteIP();

    // This will hold the part we divide by v
    LongInt part_dividend;
    part_dividend.lst.clear();

    LongInt result;
    result.lst.clear();

    std::list<unsigned int>::const_iterator dividend = u.lst.begin();

    for ( unsigned long i = 0; i < GetDivDepth(); i++ ) {

        if ( dividend != u.lst.end() ) {
            part_dividend.lst.push_back ( *dividend );
            part_dividend.stripzeros();
            if ( i == 0 ) {
                part_dividend.lst.push_back ( 0 );
            }
        } else {
            part_dividend.lst.push_back ( 0 );
        }

        // Sum is used to hold the sum of
        // sum = sum + v, which is used
        // find v|part_dividend
        LongInt sum ( 0L );

        unsigned int t = 0;

        while ( sum < part_dividend ) {
            sum += v;
            t++;
        }

        // Check if we have counted one too much
        if ( sum > part_dividend ) {
            t--;
        }

#ifdef DEBUG
        assert ( t < ( unsigned long ) pow ( ( ( double ) 10 ), part_len ) );
#endif

        // t is now our factor appended to the
        // result
        result.lst.push_back ( t );

        part_dividend -= ( v * t );

        if ( part_dividend.IsZero() ) {
            break;
        }

        if ( dividend != u.lst.end() ) {
            dividend++;
        }
    }

    return result;

}

LongInt
LongInt::FractionalPart ( signed long r ) const {
    return FractionalPart ( LongInt ( r ) );
}

CASObject*
LongInt::Add ( const CASObject* addend ) const {
    checkptr ( addend );

    if ( GetType() == addend->GetType() ) {
        const LongInt *li_ptr = dynamic_cast<const LongInt*> ( addend );
#ifdef DEBUG
        assert ( li_ptr != 0 );
#endif
        LongInt res;

        res = ( *this ) + ( *li_ptr );
        return res.Clone();
    }

    Sum tmp;
    CASObject* result;

    tmp.Append ( this );
    result = tmp.Add ( addend );

    return result;
}

CASObject*
LongInt::Subtract ( const CASObject* sub ) const {
    checkptr ( sub );

    if ( GetType() == sub->GetType() ) {
        const LongInt *li_ptr = dynamic_cast<const LongInt*> ( sub );
#ifdef DEBUG
        assert ( li_ptr != 0 );
#endif
        LongInt res;

        res = ( *this ) - ( *li_ptr );
        return res.Clone();
    }

    Sum tmp;
    CASObject *result;

    tmp.Append ( this );
    result = tmp.Subtract ( sub );


    return result;

}

CASObject*
LongInt::Multiply ( const CASObject* fact ) const {
    checkptr ( fact );

    if ( GetType() < fact->GetType() ) {
        return fact->Multiply ( this );
    }

    if ( GetType() == fact->GetType() ) {
        const LongInt *li_ptr = dynamic_cast<const LongInt*> ( fact );
#ifdef DEBUG
        assert ( li_ptr != 0 );
#endif
        LongInt res;

        res = ( *this ) * ( *li_ptr );
        return res.Clone();
    }

    Product *res = new Product;

    // "this" is a coefficient
    CASObject *tmp = this->Clone();
    tmp->meta.SetCoefficient();
    res->Append ( tmp );
    res->Append ( fact );
    CASObject::Garbage->Put ( tmp );

    return res;
}

CASObject*
LongInt::Divide ( const CASObject* divisor ) const {
    checkptr ( divisor );

    return new Fraction ( this, divisor );
}

CASObject*
LongInt::Power ( const CASObject* exp ) const {
    checkptr ( exp );

    if ( GetType() == exp->GetType() ) {
        const LongInt *num_exp = dynamic_cast<const LongInt*> ( exp );
#ifdef DEBUG
        assert ( num_exp != 0 );
#endif
        LongInt res;
        res = Pow ( *num_exp );
        return res.Clone();
    }

#ifdef WARNINGS
#warning __FILE__ " " __LINE__ "Cannot exponentiate numeric value with anything other than numeric value"
#endif
    std::cout << "Cannot exponentiate ";
    Print();
    std::cout << " by ";
    exp->Print();
    std::cout << std::endl;

    throw ENotImplemented();
}

CASObject*
LongInt::Modulo ( const CASObject* divisor ) const {
    checkptr ( divisor );

    if ( GetType() == divisor->GetType() ) {
        const LongInt *li_ptr = dynamic_cast<const LongInt*> ( divisor );
#ifdef DEBUG
        assert ( li_ptr != 0 );
#endif
        LongInt *result = new LongInt;

        *result = ( *this ) % ( *li_ptr );
        return result;
    }

    return new LongInt ( 0L );
}

bool
LongInt::IsEqual ( const CASObject* o ) const {
    checkptr ( o );

    if ( GetType() != o->GetType() ) {
        return false;
    }

    const LongInt *li_ptr = dynamic_cast<const LongInt*> ( o );
#ifdef DEBUG
    assert ( li_ptr != 0 );
#endif
    return ( *this ) == ( *li_ptr );

}

bool
LongInt::IsLT ( const CASObject* o ) const {
    checkptr ( o );

    if ( GetType() < o->GetType() ) {
        return true;
    }

    if ( GetType() > o->GetType() ) {
        return false;
    }

    const LongInt *li = dynamic_cast<const LongInt *> ( o );

#ifdef DEBUG
    assert ( li != 0 );
#endif

    return ( *this ) < ( *li );
}

bool
LongInt::IsGT ( const CASObject* o ) const {
    checkptr ( o );

    if ( IsEqual ( o ) ) {
        return false;
    }

    return !IsLT ( o );
}

bool
LongInt::IsSimilar ( const CASObject* o ) const {
    checkptr ( o );

    if ( GetType() == o->GetType() ) {
        return true;
    }

    return false;
}

CASObject*
LongInt::Evaluate() const {
    CASObject *ret_val = Clone();

    ret_val->Sort();
    ret_val->meta.SetEvaluated();

    return ret_val;
}

// ----------------------------------------------------------------------------

// Operators
// ----------------------------------------------------------------------------

LongInt&
LongInt::operator= ( const LongInt &r ) {
#ifdef SHOWCONSTRUCTOR
    std::cerr << "# LongInt::operator=()" << std::endl;
#endif
    if ( this == &r ) {
        return *this;
    }
    SetSign ( r.GetSign() );
    SetDivDepth ( r.GetDivDepth() );
    SetRadix ( r.GetRadix() );
    lst.clear();
    lst = r.lst;

    if ( r.div_remainder != 0 ) {
        CASObject::Garbage->Put ( div_remainder );
        div_remainder = 0;
    }

#ifdef DEBUG
    assert ( div_remainder == 0 );
#endif

    if ( r.div_remainder != 0 ) {
        div_remainder = new LongInt ( 0L );
        div_remainder->lst = r.div_remainder->lst;
        div_remainder->SetSign ( r.div_remainder->GetSign() );;
    }

    meta = r.meta;

    return *this;
}

LongInt&
LongInt::operator= ( const signed long &r ) {
    if ( r == 0 ) {
        setzero();
    }
    else {
        num2longint ( r );
    }

    SetRadix ( ( unsigned long ) pow ( ( ( double ) 10 ), part_len ) );

    if ( div_remainder != 0 ) {
        CASObject::Garbage->Put ( div_remainder );
        div_remainder = 0;
    }

    meta.SetAll();

    return *this;
}

LongInt&
LongInt::operator+= ( const LongInt &r ) {
    return ( *this = *this + r );
}

LongInt&
LongInt::operator+= ( const signed long &r ) {
    return operator+= ( LongInt ( r ) );
}

LongInt&
LongInt::operator-= ( const LongInt &r )  {
    return ( *this = *this - r );
}

LongInt&
LongInt::operator-= ( const signed long &r ) {
    return operator-= ( LongInt ( r ) );
}

LongInt&
LongInt::operator*= ( const LongInt &r ) {
    return ( *this = *this * r );
}

LongInt&
LongInt::operator*= ( const signed long &r ) {
    return operator*= ( LongInt ( r ) );
}

LongInt&
LongInt::operator/= ( const LongInt &r ) {
    return ( *this = *this / r );
}

LongInt&
LongInt::operator/= ( const signed long &r ) {
    return operator/= ( LongInt ( r ) );
}

LongInt&
LongInt::operator%= ( const LongInt &r ) {
    return ( *this = *this % r );
}

LongInt&
LongInt::operator%= ( const signed long &r ) {
    return operator%= ( LongInt ( r ) );
}

const LongInt
LongInt::operator+ ( const LongInt &r ) const {
    if ( r.IsZero() ) {
        return *this;
    }

    if ( IsNegative() && r.IsPositive() ) {
        LongInt tmp = *this;
        tmp.SetPositive();
        return r -tmp;
    }

    if ( IsPositive() && r.IsNegative() ) {
        LongInt tmp = r;
        tmp.SetPositive();
        return ( *this ) - tmp;
    }
    std::list<unsigned int> sum;

    unsigned long max_iter = r.lst.size() > lst.size() ? r.lst.size() : lst.size();
    std::list<unsigned int>::const_iterator i_addend1 = lst.end();
    i_addend1--;
    std::list<unsigned int>::const_iterator i_addend2 = r.lst.end();
    i_addend2--;

    unsigned int addend1 = *i_addend1;
    unsigned int addend2 = *i_addend2;
    unsigned int remainder = 0;

    for ( unsigned long i = 0; i < max_iter; i++ ) {

        unsigned int res = addend1 + addend2 + remainder;
        if ( res >= GetRadix() ) {
            res -= GetRadix();
            remainder = 1;
        }
        else {
            remainder = 0;
        }

        sum.push_front ( res );

        if ( i_addend1 != lst.begin() ) {
            i_addend1--;
            addend1 = *i_addend1;
        }
        else {
            addend1 = 0;
        }

        if ( i_addend2 != r.lst.begin() ) {
            i_addend2--;
            addend2 = *i_addend2;
        }
        else {
            addend2 = 0;
        }

    }

    // Flush remainder
    if ( remainder != 0 ) {
        sum.push_front ( remainder );
    }

    LongInt ret_val;
    ret_val.lst = sum;
    ret_val.SetSign ( GetSign() );

    ret_val.stripzeros();
    return ret_val;
}

const LongInt
LongInt::operator+ ( const long &r ) const {
    return operator+ ( LongInt ( r ) );
}

const LongInt
LongInt::operator* ( const LongInt &r ) const {

    if ( IsZero() || r.IsZero() ) {
        return LongInt ( 0L );
    }

    LongInt result ( 0L );
    LongInt tmp ( 0L );
    unsigned int prod;
    unsigned int modulo;


    std::list<unsigned int>::const_iterator fact2 = r.lst.end();
    fact2--;

    for ( unsigned long outer_l = 0; outer_l < r.lst.size(); outer_l++ ) {

        std::list<unsigned int>::const_iterator fact1 = lst.end();
        fact1--;

        unsigned int carry = 0;
        for ( unsigned long inner_l = 0; inner_l < lst.size(); inner_l++ ) {
            prod = ( ( *fact1 ) * ( *fact2 ) ) + carry;
            carry = ( unsigned int ) prod / GetRadix();
            modulo = prod % GetRadix();
            tmp = modulo;
            tmp = tmp << outer_l;
            tmp = tmp << inner_l;
            result = result + tmp;
            fact1--;
        }

        // flush carry
        if ( carry != 0 ) {
            tmp = carry;
            tmp = tmp << outer_l;
            tmp = tmp << lst.size();

            result = result + tmp;
        }
        fact2--;
    }

    // Compute sign
    result.SetSign ( ( r.IsNegative() ^ IsNegative() ? Negative : Positive ) );

    result.stripzeros();

    return result;
}

const LongInt
LongInt::operator* ( const long &r ) const {
    return operator* ( LongInt ( r ) );
}

const LongInt
LongInt::operator- ( const LongInt &r ) const {
    if ( r.IsZero() ) {
        return *this;
    }

    if ( IsNegative() && r.IsPositive() ) {
        LongInt lh = *this;
        lh.SetPositive();
        LongInt res = r + lh;
        res.SetNegative();
        return res;
    }

    if ( r.IsNegative() ) {
        LongInt tmp = r;
        tmp.SetPositive();
        return ( *this ) + tmp;
    }

    // Find out whether or not
    // the result is still positive.
    // If it will become negative, a
    // slightly other algorithm is used.
    bool stays_pos;
    if ( *this < r ) {
        stays_pos = false;
    } else {
        stays_pos = true;
    }

    std::list<unsigned int> sum;

    unsigned long max_iter = r.lst.size() > lst.size() ? r.lst.size() : lst.size();
    std::list<unsigned int>::const_iterator i_minuend =
        ( stays_pos ? lst.end() : r.lst.end() );
    i_minuend--;
    std::list<unsigned int>::const_iterator i_subtrahend =
        ( stays_pos ? r.lst.end() : lst.end() );
    i_subtrahend--;

    unsigned int minuend = *i_minuend;
    unsigned int subtrahend = *i_subtrahend;
    int remainder = 0;

    for ( unsigned long i = 0; i < max_iter; i++ ) {

        int res = minuend - ( subtrahend + remainder );
        if ( res < 0 ) {
            remainder = 1;
            res = GetRadix() + res;

        }
        else {
            remainder = 0;
        }

        sum.push_front ( ( unsigned int ) res );

        if ( i_minuend != ( stays_pos ? lst.begin() : r.lst.begin() ) ) {
            i_minuend--;
            minuend = *i_minuend;
        }
        else {
            minuend = 0;
        }

        if ( i_subtrahend != ( stays_pos ? r.lst.begin() : lst.begin() ) ) {
            i_subtrahend--;
            subtrahend = *i_subtrahend;
        }
        else {
            subtrahend = 0;
        }

    }

    LongInt ret_val;
    ret_val.lst = sum;
    ret_val.SetPositive();
    ret_val.stripzeros();
    if ( !stays_pos && !ret_val.IsZero() ) {
        ret_val.SetNegative();
    }
    return ret_val;

}

const LongInt
LongInt::operator- ( const long &r ) const {
    return operator- ( LongInt ( r ) );
}

const LongInt
LongInt::operator/ ( const LongInt &r ) const {
    LongInt u = ( *this );
    u.AbsoluteIP();
    LongInt v = r;
    v.AbsoluteIP();

    // Result is a dummy on which we manipulate the internal
    // structures directly
    LongInt result ( 0L );

    if ( v.IsZero() ) {
        throw EDivByZero();
    }

    if ( u < v ) {
        result.div_remainder = new LongInt;
        result.div_remainder->lst = lst;
        result.div_remainder->SetSign ( GetSign() );
        return result;
    }

    if ( u == v ) {
        result = 1;
        result.div_remainder = new LongInt;
        return result;
    }

    if ( v == 1 ) {
        // Return *this, because it still has the sign properly set!
        result = *this;
        result.div_remainder = new LongInt;
        return result;
    }

    // Clear the internal list of the result
    result.lst.clear();

    // This will hold the part we divide by v
    LongInt part_dividend;
    part_dividend.lst.clear();

    std::list<unsigned int>::const_iterator dividend = u.lst.begin();

    while ( dividend != u.lst.end() ) {

        part_dividend.lst.push_back ( *dividend );
        part_dividend.stripzeros();

        // Sum is used to hold the sum of sum = sum + v, which is used
        // find v|part_dividend
        LongInt sum ( 0L );

        unsigned int t = 0;

        while ( sum < part_dividend ) {
            sum += v;
            t++;
        }

        // Check if we have counted one too much
        if ( sum > part_dividend ) {
            t--;
        }

#ifdef DEBUG
        assert ( t < ( unsigned long ) pow ( ( ( double ) 10 ), part_len ) );
#endif

        result.lst.push_back ( t );

        part_dividend -= ( v * t );
        dividend++;
    }

    // Compute Sign
    result.SetSign ( ( r.IsNegative() ^ IsNegative() ? Negative : Positive ) );
    result.stripzeros();

#ifdef DEBUG
    assert ( result.div_remainder == 0 );
#endif

    result.div_remainder = new LongInt ( 0L );
    result.div_remainder->lst = part_dividend.lst;
    result.div_remainder->SetSign ( part_dividend.GetSign() );

    return result;

}

const LongInt
LongInt::operator/ ( const long &r ) const {
    return operator/ ( LongInt ( r ) );
}

const LongInt
LongInt::operator% ( const LongInt &r ) const {
#ifdef WARNINGS
#warning "LongInt::operator%(): Not fully implemented"
#endif
    LongInt result = *this / r;
    LongInt modulo = * ( result.div_remainder );

    if ( r < 0L && *this > 0L ) {
        modulo += r;
        return modulo;
    }

    if ( r > 0L && *this < 0L ) {
        modulo -= r;
        modulo.InvertIP();
        return modulo;
    }

    if ( r < 0L && *this < 0L ) {
        modulo.InvertIP();
        return modulo;
    }

    return modulo;
}

const LongInt
LongInt::operator% ( const long &r ) const {
    return operator% ( LongInt ( r ) );
}

const bool
LongInt::operator== ( const LongInt &r ) const {
    if ( Length() != r.Length() ) {
        return false;
    }

    if ( IsNegative() != r.IsNegative() ) {
        return false;
    }

    if ( lst.size() != r.lst.size() ) {
        return false;
    }

    std::list<unsigned int>::const_iterator it1 = lst.begin();
    std::list<unsigned int>::const_iterator it2 = r.lst.begin();

    while ( it1 != lst.end() ) {
        if ( *it1 != *it2 ) {
            return false;
        }

        it1++;
        it2++;
    }

    return true;
}

const bool
LongInt::operator== ( const long &r ) const {
    return operator== ( LongInt ( r ) );
}

const bool
LongInt::operator!= ( const LongInt &r ) const {
    return ! ( *this == r );
}

const bool
LongInt::operator!= ( const long &r ) const {
    return ! ( *this == LongInt ( r ) );
}

const bool
LongInt::operator< ( const LongInt &r ) const {
    if ( *this == r ) {
        return false;
    }

    if ( IsNegative() && r.IsPositive() ) {
        return true;
    }

    if ( IsPositive() && r.IsNegative() ) {
        return false;
    }

    if ( lst.size() < r.lst.size() ) {
        return ( IsNegative() ? false : true );
    }

    if ( lst.size() > r.lst.size() ) {
        return ( IsNegative() ? true : false );
    }

    std::list<unsigned int>::const_iterator it1 = lst.begin();
    std::list<unsigned int>::const_iterator it2 = r.lst.begin();

    while ( it1 != lst.end() ) {
        if ( *it1 != *it2 ) {
            if ( *it1 < *it2 ) {
                return ( IsNegative() ? false : true );
            }
            else {
                return ( IsNegative() ? true : false );
            }
        }

        it1++;
        it2++;
    }
    throw EInternal();
}

const bool
LongInt::operator< ( const long &r ) const {
    return operator< ( LongInt ( r ) );
}

const bool
LongInt::operator> ( const LongInt &r ) const {
    if ( *this == r ) {
        return false;
    }

    if ( IsNegative() && r.IsPositive() ) {
        return false;
    }

    if ( IsPositive() && r.IsNegative() ) {
        return true;
    }

    if ( lst.size() > r.lst.size() ) {
        return ( IsNegative() ? false : true );
    }

    if ( lst.size() < r.lst.size() ) {
        return ( IsNegative() ? true : false );
    }

    std::list<unsigned int>::const_iterator it1 = lst.begin();
    std::list<unsigned int>::const_iterator it2 = r.lst.begin();

    while ( it1 != lst.end() ) {
        if ( *it1 != *it2 ) {
            if ( *it1 > *it2 ) {
                return ( IsNegative() ? false : true );
            }
            else {
                return ( IsNegative() ? true : false );
            }
        }

        it1++;
        it2++;
    }
    throw EInternal();
}

const bool
LongInt::operator> ( const long &r ) const {
    return operator> ( LongInt ( r ) );
}

const bool
LongInt::operator>= ( const LongInt &r ) const {
    if ( *this == r ) {
        return true;
    }

    if ( *this > r ) {
        return true;
    }

    return false;
}

const bool
LongInt::operator>= ( const long &r ) const {
    return operator>= ( LongInt ( r ) );
}

const bool
LongInt::operator<= ( const LongInt &r ) const {
    if ( *this == r ) {
        return true;
    }

    if ( *this < r ) {
        return true;
    }

    return false;
}

const bool
LongInt::operator<= ( const long &r ) const {
    return operator<= ( LongInt ( r ) );
}

const LongInt
LongInt::operator<< ( const signed long &r ) const {
    if ( r < 0 ) {
        return *this;
    }

    LongInt tmp = *this;
    for ( signed long l = 0; l < r; l++ ) {
        tmp.lst.push_back ( 0 );
    }

    tmp.stripzeros();
    return tmp;
}

const LongInt
LongInt::operator++() {
    return ( *this ) = operator+ ( 1 );
}

const LongInt
LongInt::operator++ ( int ) {
    LongInt before = *this;
    ( *this ) = operator+ ( 1 );

    return before;
}

const LongInt
LongInt::operator--()  {
    return ( *this ) = operator- ( 1 );
}

const LongInt
LongInt::operator-- ( int ) {
    LongInt before = *this;
    ( *this ) = operator- ( 1 );

    return before;
}

// ----------------------------------------------------------------------------

---