[Rate The Code] HugeInt

Gary

Hi!

Ich habe die Klasse HugeInt geschrieben, die eine Zahl ziffernweise speichert, und möchte sie nun der allgemeinen Kritik aussetzen.

Man kann mit der Klasse wie mit einer Integerzahl rechnen, nur ist der Wertebereich viel größer, man kann ihn mit der Variable HI_MAX_DIGITS festsetzen. Die Operatoren +,-,*,/,%,<,>,<=,>=,==,!=,++,-- und = sind überladen, darüber hinaus sind die Ausgabeoperatoren >> und << überladen.
Intern besteht der Datentyp aus einem Array, das die Ziffern verkehrt herum speichert. Man kann jede beliebige Ziffer mit der Methode Digits() auslesen.

Die Header-Datei:

// Module Name: 
//      hugeint.hpp 

// Abstract: 
//      Make integer calculations in any size you want. 

// Author: 
//      Gary (2002) 

#ifndef HUGEINT_HPP 
#define HUGEINT_HPP 

// You have to admit that the basic integer types have annoying limits if it comes 
// to large numbers. With HugeInt you can make integer calculations in any size you 
// want and you have got complete accuracy in your calculations. 
// And if you want to know what the 256th digit of a number is, it's no problem. 

#ifdef _MSC_VER 
// C4715: " 'operator/=' : At least one control path does not return a value" 
#pragma warning(disable:4715) // disable C4715 warning 
// #pragma warning(default:4715)      // use this to reenable, if desired 
#endif  // _MSC_VER 

#include <iostream> // ostream, istream 
using namespace std; 

// Set maximum digits. Change it if you want to have more or less digits. 
const unsigned long HI_MAX_DIGITS = 500; 

// Size = ~ HI_MAX_DIGITS * 1 byte; 
// e.g. HI_MAX_DIGITS=500 --> HugeInt = ~ 508 bytes 

// Class HugeInt 
class HugeInt 
{ 
        // Arithmetic operators 
        friend HugeInt& operator+=(HugeInt& lv,const HugeInt& rv); 
        friend HugeInt& operator*=(HugeInt& lv,const HugeInt& rv); 
        friend HugeInt& operator/=(HugeInt& lv,const HugeInt& rv); 
        friend HugeInt& operator%=(HugeInt& lv,const HugeInt& rv); 

        // Increment and decrement 
        friend HugeInt& operator++(HugeInt& h); 
        friend HugeInt& operator--(HugeInt& h); 
        friend HugeInt operator++(HugeInt& h,int); 
        friend HugeInt operator--(HugeInt& h,int); 

        private: 
        char m_digit[HI_MAX_DIGITS]; 
        unsigned long m_ndigits; 
        bool m_neg; 

        void Trim(); 
        void Shift_Left(unsigned long len); 
        void Multiply(char n); 

        public: 
        HugeInt(); // HugeInt = 0 
        HugeInt(long number); // --> no need of operators with long 
        // long range: -2.147.483.647 to 2.147.483.647 
        HugeInt(const HugeInt& h); 

        HugeInt& operator=(const HugeInt& h); 

        // the 200th digit has index 199 
        char Index(unsigned long i) const; 

        // comparison functions 
        bool IsEqual(const HugeInt& h) const; 
        bool IsLess(const HugeInt& h) const; 

        // Be careful about using these 3 methods. You might better not use them! 
        // (They are useful, if you want to code your own input method) 
        void AddChar(char ch); 
        void InvalidHugeInt(); 
        void TurnRound(); 

        unsigned long Digits() const { return m_ndigits;} 
        bool IsNegative() const { return m_neg;} 
        bool IsZero() const 
        { 
                for(unsigned long i=0;i<m_ndigits;i++) 
                { 
                        if(m_digit[i]!=0) 
                        return false; 
                } 
                return true; 
        } 
        void Negate() 
        { 
                if(m_neg) 
                m_neg=false; 
                else 
                m_neg=true; 
        } 

        bool IsLong() const; // tests if HugeInt is convertable into a long - variable. 
        long ToLong() const; // only last 10 digits are transformed to long! 

        ~HugeInt() {}; 
}; 

// Other functions 
HugeInt Abs(const HugeInt& h); 

// Output / Input 
ostream& operator<<(ostream& os, HugeInt& h); 
istream& operator>>(istream& is, HugeInt& h); 

// Comparison operators 
bool operator==(const HugeInt& a, const HugeInt& b) { return a.IsEqual(b);} 
bool operator!=(const HugeInt& a, const HugeInt& b) { return !a.IsEqual(b);} 
bool operator<(const HugeInt& a, const HugeInt& b) { return a.IsLess(b);} 
bool operator<=(const HugeInt& a, const HugeInt& b) { return (a.IsLess(b)||a.IsEqual(b));} 
bool operator>(const HugeInt& a, const HugeInt& b) { return b.IsLess(a);} 
bool operator>=(const HugeInt& a, const HugeInt& b) { return (b.IsLess(a)||b.IsEqual(a));} 

// Arithmetic operators 
HugeInt& operator-=(HugeInt& lv,const HugeInt& rv); 

HugeInt operator+(const HugeInt& fo,const HugeInt& so); 
HugeInt operator-(const HugeInt& fo,const HugeInt& so); 
HugeInt operator*(const HugeInt& fo,const HugeInt& so); 
HugeInt operator/(const HugeInt& fo,const HugeInt& so); 
HugeInt operator%(const HugeInt& fo,const HugeInt& so); 

// unary operators 
inline HugeInt operator+(const HugeInt& h); 
inline HugeInt operator-(const HugeInt& h); 

////////////////////////////////////////////////////////////////////////////// 

// Constructors 
HugeInt::HugeInt() 
{ 
        for(unsigned long j=0;j<HI_MAX_DIGITS;++j) // set array zero 
        m_digit[j]=0; 
        m_ndigits=1; 
        m_neg=false; 
} 

HugeInt::HugeInt(long number) 
{ 
        unsigned long i=0; 

        for(unsigned long j=0;j<HI_MAX_DIGITS;++j) // set array zero 
        m_digit[j]=0; 
        if(number==0) 
        { 
                m_digit[0]=0; 
                m_ndigits=1; 
                m_neg=false; 
        } 
        else 
        { 
                if(number>0) 
                m_neg=false; 
                else 
                { 
                        m_neg=true; 
                        number=-number; 
                } 
                while((number/10)>=1) 
                { 
                        m_digit[i]=number%10; 
                        number/=10; 
                        ++i; 
                } 
                m_digit[i]=number; 
                m_ndigits=i+1; 
        } 
} 

HugeInt::HugeInt(const HugeInt& h) 
{ 
        m_neg=h.m_neg; 
        m_ndigits=h.m_ndigits; 
        for(unsigned long i=0;i<h.m_ndigits;++i) 
        m_digit[i]=h.m_digit[i]; 
} 

// Private functions 
void HugeInt::Trim() 
{ 
        for(unsigned long i=m_ndigits-1;i>0;--i) 
        { 
                if(m_digit[i]==0) 
                --m_ndigits; 
                else 
                break; 
        } 
        if((i==0)&&(m_digit[0]==0)) 
        { 
                m_ndigits=1; 
                m_neg=false; 
        } 
} 

void HugeInt::Shift_Left(unsigned long len) 
{ 
        if((len==0)||(len>HI_MAX_DIGITS)) 
        return; 
        unsigned long i=0; 
        m_ndigits+=len; 
        for(i=m_ndigits-1;i>=len;--i) 
        m_digit[i]=m_digit[i-len]; 
        for(i=0;i<len;++i) 
        m_digit[i]=0; 
} 

void HugeInt::Multiply(char n) 
{ 
        if(n==0) 
        { 
                for(unsigned long i=0;i<m_ndigits;++i) 
                m_digit[i]=0; 
                return; 
        } 
        if(n==1) 
        return; 
        unsigned char r=0,erg=0; 
        for(unsigned long i=0;i<m_ndigits;++i) 
        { 
                erg=m_digit[i]*n+r; 
                if(erg>=10) 
                { 
                        r=erg/10; 
                        erg%=10; 
                } 
                else 
                r=0; 
                m_digit[i]=erg; 
        } 
        if(r>0) 
        { 
                m_digit[i]=r; 
                ++m_ndigits; 
        } 
} 

// Other functions 
HugeInt Abs(const HugeInt& h) 
{ 
        HugeInt tmp=h; 
        if(tmp.IsNegative()) 
        tmp.Negate(); 
        return tmp; 
} 

// unary operators 
inline HugeInt operator+(const HugeInt& h) 
{ 
        return h; 
} 

inline HugeInt operator-(const HugeInt& h) 
{ 
        HugeInt tmp=h; 
        tmp.Negate(); 
        return tmp; 
} 

// Assignment 
HugeInt& HugeInt::operator=(const HugeInt& h) 
{ 
        if(this==&h) 
        return *this; 
        m_neg=h.m_neg; 
        m_ndigits=h.m_ndigits; 
        for(unsigned long i=0;i<h.m_ndigits;++i) 
        m_digit[i]=h.m_digit[i]; 
        return *this; 
} 

// Index 
char HugeInt::Index(unsigned long i) const 
{ 
        if(i>=m_ndigits) 
        return '?'; 
        return (char)(m_digit[m_ndigits-i-1]+'0'); 
} 

// Be careful about using this method. You might better not use it! 
void HugeInt::AddChar(char ch) 
{ 
        m_digit[m_ndigits]=ch; 
        ++m_ndigits; 
} 

// Be careful about using this method. You might better not use it! 
void HugeInt::InvalidHugeInt() 
{ 
        m_ndigits=0; 
        m_neg=false; 
} 

// Be careful about using this method. You might better not use it! 
void HugeInt::TurnRound() 
{ 
        char tmp[HI_MAX_DIGITS]; 
        unsigned long i,j; 

        for(i=0,j=m_ndigits-1;i<m_ndigits;++i,--j) 
        tmp[j]=m_digit[i]; 

        for(i=0;i<m_ndigits;++i) 
        m_digit[i]=tmp[i]; 
} 

// Comparison 
bool HugeInt::IsEqual(const HugeInt& h) const 
{ 
        if((m_neg!=h.m_neg)||(m_ndigits!=h.m_ndigits)) 
        return false; 
        for(unsigned long i=0;i<m_ndigits;++i) 
        { 
                if(m_digit[i]!=h.m_digit[i]) 
                return false; 
        } 
        return true; 
} 

bool HugeInt::IsLess(const HugeInt& h) const 
{ 
        if((m_neg)&&(!h.m_neg)) 
        return true; 
        if((!m_neg)&&(h.m_neg)) 
        return false; 
        if(m_ndigits<h.m_ndigits) 
        return true; 
        if(m_ndigits>h.m_ndigits) 
        return false; 

        if(!m_neg) 
        { 
                for(unsigned long i=m_ndigits-1;;--i) 
                { 
                        if(m_digit[i]<h.m_digit[i]) 
                        return true; 
                        if(m_digit[i]>h.m_digit[i]) 
                        return false; 
                        if((i==0)&&(m_digit[i]==h.m_digit[i])) 
                        { 
                                return false; 
                        } 
                        if(i==0) 
                        return true; 
                } 
        } 
        else 
        { 
                for(unsigned long i=m_ndigits-1;;--i) 
                { 
                        if(m_digit[i]>h.m_digit[i]) 
                        return true; 
                        if(m_digit[i]<h.m_digit[i]) 
                        return false; 
                        if((i==0)&&(m_digit[i]==h.m_digit[i])) 
                        { 
                                return false; 
                        } 
                        if(i==0) 
                        return true; 
                } 
        } 
} 

// Long - conversion 
bool HugeInt::IsLong() const 
{ 
        if(m_ndigits<10) 
        return true; 
        if(m_ndigits>10) 
        return false; 

        if(m_neg) 
        { 
                if(!(*this).IsLess(-2147483647)) 
                return true; 
        } 
        else 
        { 
                if((*this).IsLess(2147483647)||(*this).IsEqual(2147483647)) 
                return true; 
        } 
        return false; 
} 

long HugeInt::ToLong() const 
{ 
        long ret=0,ten=1; 
        short i; 

        for(i=0;i<10;++i) 
        { 
                ret+=(m_digit[i]*ten); 
                ten*=10; 
        } 
        if(m_neg) 
        ret*=(-1); 
        return ret; 
} 

// Increment and decrement 
HugeInt& operator++(HugeInt& h) 
{ 
        h+=1; 
        return h; 
} 

HugeInt& operator--(HugeInt& h) 
{ 
        h-=1; 
        return h; 
} 

HugeInt operator++(HugeInt& h,int) 
{ 
        HugeInt tmp=h; 
        h+=1; 
        return tmp; 
} 

HugeInt operator--(HugeInt& h,int) 
{ 
        HugeInt tmp=h; 
        h-=1; 
        return tmp; 
} 

// Output / Input 
ostream& operator<<(ostream& os, HugeInt& h) 
{ 
        unsigned long i; 
        if(h.IsNegative()) 
        os << '-'; 
        for(i=0;i<h.Digits();++i) 
        os << h.Index(i); 
        return os; 
} 

istream& operator>>(istream& is, HugeInt& h) 
{ 
        char input; 
        unsigned long i=0; 
        is >> input; 
        if(h.IsNegative()) 
        h.Negate(); 
        h.InvalidHugeInt(); 

        if(input=='-') 
        { 
                if(!h.IsNegative()) 
                h.Negate(); 
        } 
        else if((input>'0')&&(input<'9')) 
        { 
                h.AddChar(input-'0'); 
        } 
        else 
        return is; 

        for(;i<HI_MAX_DIGITS;++i) 
        { 
                is.get(input); 
                if((input<'0')||(input>'9')) 
                break; 
                h.AddChar(input-'0'); 
        } 
        h.TurnRound(); 
        return is; 
} 

// Arithmetic operators 
HugeInt& operator+=(HugeInt& lv,const HugeInt& rv) 
{ 
        HugeInt tmp,tmps; 
        if(lv.m_neg==rv.m_neg) 
        { 
                unsigned long i; 
                char r=0, erg=0; 

                if(lv.m_ndigits>=rv.m_ndigits) 
                { 
                        tmp=lv; 
                        tmps=rv; 
                } 
                else 
                { 
                        tmp=rv; 
                        tmps=lv; 
                } 
                for(i=0;i<tmps.m_ndigits;++i) 
                { 
                        erg=tmp.m_digit[i]+tmps.m_digit[i]+r; 
                        if(erg>=10) 
                        { 
                                erg-=10; 
                                r=1; 
                        } 
                        else 
                        r=0; 
                        tmp.m_digit[i]=erg; 
                } 
                while(r==1) 
                { 
                        erg=tmp.m_digit[i]+1; 
                        if(erg>=10) 
                        { 
                                erg-=10; 
                                r=1; 
                                tmp.m_digit[i]=erg; 
                                ++i; 
                        } 
                        else 
                        { 
                                tmp.m_digit[i]+=1; 
                                if(i>=tmp.m_ndigits) 
                                tmp.m_ndigits=i+1; 
                                break; 
                        } 
                } 
        } 
        else // different signs 
        { 
                unsigned long i; 
                char r=0, erg=0; 
                if(lv.m_ndigits==rv.m_ndigits) // m_ndigits is equal 
                { 
                        if(Abs(rv).IsLess(Abs(lv))) 
                        { 
                                tmp=lv; 
                                tmps=rv; 
                        } 
                        else 
                        { 
                                tmp=rv; 
                                tmps=lv; 
                        } 
                } 
                else // m_ndigits is not equal 
                { 
                        if(lv.m_ndigits>=rv.m_ndigits) 
                        { 
                                tmp=lv; 
                                tmps=rv; 
                        } 
                        else 
                        { 
                                tmp=rv; 
                                tmps=lv; 
                        } 
                } 
                for(i=0;i<tmp.m_ndigits;++i) 
                { 
                        erg=tmp.m_digit[i]-tmps.m_digit[i]-r; 
                        if(erg<0) 
                        { 
                                erg+=10; 
                                r=1; 
                        } 
                        else 
                        r=0; 
                        tmp.m_digit[i]=erg; 
                } 
                while(r==1) 
                { 
                        erg=tmp.m_digit[i]-1; 
                        if(erg<0) 
                        { 
                                erg+=10; 
                                r=1; 
                                tmp.m_digit[i]=erg; 
                                ++i; 
                        } 
                        else 
                        { 
                                tmp.m_digit[i]-=1; 
                                if(i>=tmp.m_ndigits) 
                                tmp.m_ndigits=i+1; 
                                break; 
                        } 
                } 
        } 
        tmp.Trim(); 
        lv=tmp; 
        return lv; 
} 

HugeInt operator+(const HugeInt& fo,const HugeInt& so) 
{ 
        HugeInt tmp=fo; 
        tmp+=so; 
        return tmp; 
} 

HugeInt& operator-=(HugeInt& lv,const HugeInt& rv) 
{ 
        lv+=(-rv); 
        return lv; 
} 

HugeInt operator-(const HugeInt& fo,const HugeInt& so) 
{ 
        HugeInt tmp=fo; 
        tmp+=(-so); 
        return tmp; 
} 

HugeInt& operator*=(HugeInt& lv,const HugeInt& rv) 
{ 
        if((lv==0)||(rv==0)) 
        { 
                lv.m_digit[0]=0; 
                lv.m_ndigits=1; 
                lv.m_neg=false; 
                return lv; 
        } 
        if(lv.m_neg==rv.m_neg) // calculate the sign 
        lv.m_neg=false; 
        else 
        lv.m_neg=true; 

        HugeInt tmp,t; 
        unsigned long j; 

        for(j=rv.m_ndigits;j>0;j--) 
        { 
                t=lv; 
                t.Multiply(rv.m_digit[j-1]); 
                t.Shift_Left(j-1); 
                tmp+=t; 
        } 
        lv=tmp; 
        return lv; 
} 

HugeInt operator*(const HugeInt& fo,const HugeInt& so) 
{ 
        HugeInt tmp=fo; 
        tmp*=so; 
        return tmp; 
} 
// works, but very slow when it comes to large numbers are divided by small numbers 
HugeInt& operator/=(HugeInt& lv,const HugeInt& rv) 
{ 
        if(rv==0) 
        return lv; 
        if(lv==0) 
        { 
                return lv; 
        } 
        if(lv==rv) 
        { 
                lv=1; 
                return lv; 
        } 
        if(rv==1) 
        return lv; 
        if(Abs(rv)>Abs(lv)) 
        { 
                lv=0; 
                return lv; 
        } 
        if(lv.m_neg==rv.m_neg) // calculate the sign 
        lv.m_neg=false; 
        else 
        lv.m_neg=true; 

        HugeInt min(1),max(1),x(1); 

        if((lv.m_ndigits-rv.m_ndigits-1)>0) 
        min.Shift_Left(lv.m_ndigits-rv.m_ndigits-1); 
        max.Shift_Left(lv.m_ndigits-rv.m_ndigits+1); 
        x.Shift_Left(lv.m_ndigits-rv.m_ndigits); 
        if(lv.IsLess(rv*x)) 
        max=x; 
        else 
        { 
                min=x; 
                for(long i=2;i<10;++i) 
                { 
                        if((rv*x*i)<lv) 
                        min=x*i; 
                        else 
                        break; 
                } 
        } 
        HugeInt h=min; 
        for(;h<=max;++h) 
        { 
                if(lv==(rv*h)) 
                { 
                        lv=h; 
                        return lv; 
                } 
                if(lv<(rv*h)) 
                { 
                        lv=h-1; 
                        return lv; 
                } 
        } 
} 

HugeInt operator/(const HugeInt& fo,const HugeInt& so) 
{ 
        HugeInt tmp=fo; 
        tmp/=so; 
        return tmp; 
} 

HugeInt& operator%=(HugeInt& lv,const HugeInt& rv) 
{ 
        if(rv==0) 
        return lv; 
        if(lv==0) 
        { 
                lv=rv; 
                return lv; 
        } 
        if(rv==1) 
        { 
                lv=0; 
                return lv; 
        } 
        if(lv==rv) 
        { 
                lv=0; 
                return lv; 
        } 
        if(lv<rv) 
        { 
                return lv; 
        } 

        HugeInt tmp=lv; 
        tmp/=rv; 
        lv-=(tmp*rv); 
        return lv; 
} 

HugeInt operator%(const HugeInt& fo,const HugeInt& so) 
{ 
        HugeInt tmp=fo; 
        tmp%=so; 
        return tmp; 
} 

#endif // HUGEINT_HPP

Ich weiß, dass ich äußerst spärlich kommentiere. Falls Fragen auftauchen, dann sagts mir einfach.
mfg Gary

phlox81

Glaubst du das sich jemand die mühe macht deinen Wirren Unkommentiereten
Code durchzulesen ??

Devil

volkard

#pragma warning(disable:4715) // disable C4715 warning
besser #pragma warning(push) und pop drum, ist einfach besser wartbar. und warnings so lokal wie müglich deaktivieren!

const unsigned long HI_MAX_DIGITS = 500; 
const size_t

char m_digit[HI_MAX_DIGITS]; 
unsigned long m_ndigits; 
bool m_neg;

ndigits? halte UN für veraltet.
neg? nicht gut, zu viele fallunterscheidungen! lieber HugeNatural bauen ohne neg und dann daraus HugeInt mit ner HugeNatural als Attribut!

bool IsZero() const 
        { 
                for(unsigned long i=0;i<m_ndigits;i++) 
                { 
                        if(m_digit[i]!=0) 
                        return false; 
                } 
                return true; 
        } 
bis auf das size_t hastes schon drauf.

        void Negate() 
        { 
                if(m_neg) 
                m_neg=false; 
                else 
                m_neg=true; 
        } 
nicht neg=!neg?

HugeInt::HugeInt() 
{ 
        for(unsigned long j=0;j<HI_MAX_DIGITS;++j) // set array zero 
        m_digit[j]=0; 
        m_ndigits=1; 
        m_neg=false; 
} 
verwendest i und j willkürlich?

HugeInt::HugeInt(long number) 
{ 
        unsigned long i=0; 

        for(unsigned long j=0;j<HI_MAX_DIGITS;++j) // set array zero 
        m_digit[j]=0; 
        if(number==0) 
        { 
                m_digit[0]=0; 
                m_ndigits=1; 
                m_neg=false; 
        } 
        else 
        { 
                if(number>0) 
                m_neg=false; 
                else 
                { 
                        m_neg=true; 
                        number=-number; 
                } 
                while((number/10)>=1) 
                { 
                        m_digit[i]=number%10; 
                        number/=10; 
                        ++i; 
                } 
                m_digit[i]=number; 
                m_ndigits=i+1; 
        } 
} 
uff. viel zu groß!

char HugeInt::Index(unsigned long i) const 
{ 
        if(i>=m_ndigits) 
        return '?'; 
        return (char)(m_digit[m_ndigits-i-1]+'0'); 
} 
das ist aber heikel. mach doch lieber assert oder throw.

HugeInt& operator+=(HugeInt& lv,const HugeInt& rv) 
{ 
        HugeInt tmp,tmps; 
        if(lv.m_neg==rv.m_neg) 
        { 
                unsigned long i; 
                char r=0, erg=0; 

                if(lv.m_ndigits>=rv.m_ndigits) 
                { 
                        tmp=lv; 
                        tmps=rv; 
                } 
                else 
                { 
                        tmp=rv; 
                        tmps=lv; 
                } 
                for(i=0;i<tmps.m_ndigits;++i) 
                { 
                        erg=tmp.m_digit[i]+tmps.m_digit[i]+r; 
                        if(erg>=10) 
                        { 
                                erg-=10; 
                                r=1; 
                        } 
                        else 
                        r=0; 
                        tmp.m_digit[i]=erg; 
                } 
                while(r==1) 
                { 
                        erg=tmp.m_digit[i]+1; 
                        if(erg>=10) 
                        { 
                                erg-=10; 
                                r=1; 
                                tmp.m_digit[i]=erg; 
                                ++i; 
                        } 
                        else 
                        { 
                                tmp.m_digit[i]+=1; 
                                if(i>=tmp.m_ndigits) 
                                tmp.m_ndigits=i+1; 
                                break; 
                        } 
                } 
        } 
        else // different signs 
        { 
                unsigned long i; 
                char r=0, erg=0; 
                if(lv.m_ndigits==rv.m_ndigits) // m_ndigits is equal 
                { 
                        if(Abs(rv).IsLess(Abs(lv))) 
                        { 
                                tmp=lv; 
                                tmps=rv; 
                        } 
                        else 
                        { 
                                tmp=rv; 
                                tmps=lv; 
                        } 
                } 
                else // m_ndigits is not equal 
                { 
                        if(lv.m_ndigits>=rv.m_ndigits) 
                        { 
                                tmp=lv; 
                                tmps=rv; 
                        } 
                        else 
                        { 
                                tmp=rv; 
                                tmps=lv; 
                        } 
                } 
                for(i=0;i<tmp.m_ndigits;++i) 
                { 
                        erg=tmp.m_digit[i]-tmps.m_digit[i]-r; 
                        if(erg<0) 
                        { 
                                erg+=10; 
                                r=1; 
                        } 
                        else 
                        r=0; 
                        tmp.m_digit[i]=erg; 
                } 
                while(r==1) 
                { 
                        erg=tmp.m_digit[i]-1; 
                        if(erg<0) 
                        { 
                                erg+=10; 
                                r=1; 
                                tmp.m_digit[i]=erg; 
                                ++i; 
                        } 
                        else 
                        { 
                                tmp.m_digit[i]-=1; 
                                if(i>=tmp.m_ndigits) 
                                tmp.m_ndigits=i+1; 
                                break; 
                        } 
                } 
        } 
        tmp.Trim(); 
        lv=tmp; 
        return lv; 
}

lol! ich lieg hilflos auf dem rücken vor lachen und strample mit allen vieren!

du hast so geil angefangen! hat mir echt gefallen. wollts grad hinschreiben. also elegante schleifen und wenige fallunterscheidungen. generell wenig doppelter code. und no so ein schocker.

ich würd sagen, mach mal allen doppelten code weg. und alles, was umständlich wirkt. ich hack mal ungestestet den Konstruktor rein.

HugeInt::HugeInt(long number) 
{ 
   set_zero();//ist private-funktion und wird ja auch von anderen dauernd aufgerufen
   if(number<0)
   {
      m_neg=true;
      number=-number;
   }
   size_t i=0;
   do
      m_digit[i]=number%10;
   while(number/=10)
}

Ist natürlich viel zu große. Besser, man trennt das Vorzeichen echt ab und baut erstmal nur natürliche Zahlen.

also um faktor 2 schaffste es noch, deinen code zu straffen. wenn das geschafft ist, dann geht der dicke spaß los! dann probier mal, nen schnellen algorithmus zum multiplizieren, karatsuba. oder beliebig lange zahlen. oder (ganz krass, aber ganz schnell) nimm als basis nicht 10 sondern 2^32!

<edit> hab mal Code-Tags reingebaut</edit>

[ Dieser Beitrag wurde am 14.11.2002 um 17:25 Uhr von kingruedi editiert. ]

SG1

Original erstellt von volkard:
nimm als basis nicht 10 sondern 2^32!

Ich würd als Basis nur 2^16 nehmen, sonst gibts Probleme mit den Zwischenergebnissen, besonders bei der Multiplikation (es sei denn, man schreibt für 'nen 64bit-Prozessor...)

volkard

Original erstellt von SG1:
Ich würd als Basis nur 2^16 nehmen, sonst gibts Probleme mit den Zwischenergebnissen, besonders bei der Multiplikation (es sei denn, man schreibt für 'nen 64bit-Prozessor...)

jo, ist net einfach. ich denke dran, mindestens ne mini-assembler-funktion zu machen, die 2 int32 multipliziert und das ergebnis in zwei int32 steckt.

Gary

Danke fürs Feedback!
Ich bin schon dabei, den Code umzuschreiben.

Wegen Karatsuba-Algo:
Gibts da irgendwo eine deutsche Erklärung dazu?
Ich hab mir schon mehrere englische Texte dazu durchgelesen, blick aber nicht ganz durch.
Karatsuba gibts auch fürs Dividieren, oder?

volkard

Original erstellt von Gary:
**Danke fürs Feedback!
Ich bin schon dabei, den Code umzuschreiben.

Wegen Karatsuba-Algo:
Gibts da irgendwo eine deutsche Erklärung dazu?
Ich hab mir schon mehrere englische Texte dazu durchgelesen, blick aber nicht ganz durch.
Karatsuba gibts auch fürs Dividieren, oder?**

kenne karatsuba nur für multiplikationen.
deutsch? ka.
schätze, "teile und herrsche karatsuba" ist bestes google-suchwort.

Gary

Hi!
Ich hab nochmal ein paar Fragen:

Was für Vorteile hat size_t?
Die Geschichte mit HugeNatural und HugeInt. Was ist besser?

HugeInt : public HugeNatural

plus Membervariable neg.

oder

HugeInt
{
private:
HugeNatural hn;
bool neg;

Basis 2^32
Soll das heißen ein Array von 4-Byte Variablen?

mfg Gary

volkard

Original erstellt von Gary:

Was für Vorteile hat size_t?

brauchst nicht aufpassen, was beim nächsten compiler sein wird. size_t ist der gute typ für größen von c++-objekten.

Die Geschichte mit HugeNatural und HugeInt. Was ist besser?
HugeInt : public HugeNatural
plus Membervariable neg.
oder
HugeInt
{
private:
HugeNatural hn;
bool neg;

Siehe "Effektiv C++ Programmieren".
Vererbung hieße: Eine HugeInt IST eine HugeNatural, und das wäre inhaltlich falsch.

Basis 2^32
Soll das heißen ein Array von 4-Byte Variablen?

Ganz genau das. Aber mach erstmal nur 2-Byte-Variablen, wie SG1 sagt. Auf 4 Bytes rüsten kannste später immer noch. Bringt eh kaum noch Zusatz-Speed.
Was aber richtig Speed bringt, ist daß Du Deine Basis auf ne Zweierpotenz umstellst.

Gary

Danke erstmal
ist size_t unsigned und wieviel Bytes belegt die Variable?

[ Dieser Beitrag wurde am 23.11.2002 um 13:19 Uhr von Gary editiert. ]

Shade Of Mine

Original erstellt von Gary:
**Danke erstmal
ist size_t unsigned und wieviel Bytes belegt die Variable?
**

jep, ist unsigned und belegt exakt soviele bytes wie du brauchst um alle groessenagaben darstellen zu koennen