From 44542adf023315d60a8ffc4863f2b161b3c1eb90 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Mon, 15 Apr 2013 23:45:48 -0600 Subject: Addition, subtraction, and multiplication work now Division isn't working yet, there are too many options, I'll figure out something eventually :-P --- src/main.cpp | 117 ++++++++++++++++++++++++++++++++-- src/number.cpp | 166 ++++++++++++++++++++++++++++++++++++++++++++----- src/number.h | 11 +++- src/packedintarray.cpp | 29 ++++++++- src/packedintarray.h | 3 + 5 files changed, 304 insertions(+), 22 deletions(-) (limited to 'src') diff --git a/src/main.cpp b/src/main.cpp index be49a1d..d78bfc3 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -33,21 +33,130 @@ void numbertest1() { println("-==- Number test -==-"); - Number a("523"); - Number b("498"); + Number a("1000902491523000321"); + Number b("3004392012498000700"); println("%1 + %2 = %3"). arg( a.toString() ). arg( b.toString() ). arg( (a + b).toString() ); + + println("%1 * %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a * b).toString() ); + + a = "-872"; + b = "123"; + + println("%1 + %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a + b).toString() ); + + a = "728"; + b = "-51"; + + println("%1 + %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a + b).toString() ); + + a = "44"; + b = "-55"; + + println("%1 + %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a + b).toString() ); + + a = "44"; + b = "-66"; + + println("%1 + %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a + b).toString() ); + + a = "44"; + b = "-66"; + + println("%1 - %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a - b).toString() ); + + a = "44"; + b = "66"; + + println("%1 - %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a - b).toString() ); + + a = "7814"; + b = "24"; + + println("%1 * %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a * b).toString() ); + + a = "12345"; + b = "678"; + + println("%1 * %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a * b).toString() ); + + a = "3592846"; + b = "944634757"; + + println("%1 * %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a * b).toString() ); + + a = "3592846"; + b = ""; + + println("%1 * %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a * b).toString() ); + + a = "123"; + b = "-45"; + + println("%1 * %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a * b).toString() ); + + a = "-123"; + b = "45"; + + println("%1 * %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a * b).toString() ); + + a = "-123"; + b = "-45"; + + println("%1 * %2 = %3"). + arg( a.toString() ). + arg( b.toString() ). + arg( (a * b).toString() ); } int main( int argc, char *argv[] ) { println("CliC"); - packedtest1(); -// numbertest1(); +// packedtest1(); + numbertest1(); return 0; } diff --git a/src/number.cpp b/src/number.cpp index e64be94..ac29c61 100644 --- a/src/number.cpp +++ b/src/number.cpp @@ -6,45 +6,110 @@ Number::Number( int iOrd ) : iOrd( iOrd ), - aInt( 4 ) + aInt( 4 ), + bPositive( true ) { } Number::Number( const Bu::String &sData, int iOrd ) : iOrd( iOrd ), - aInt( 4 ) + aInt( 4 ), + bPositive( true ) { - for( int j = sData.getSize()-1; j >= 0; j-- ) - aInt.append( sData[j]-'0' ); + set( sData ); } Number::~Number() { } +Number &Number::operator=( const Bu::String &sNum ) +{ + set( sNum ); + return *this; +} + +template t tabs( t x ) { return (x<(t)0)?(-x):x; } + Number Number::operator+( const Number &rhs ) const +{ + return add( rhs, false ); +} + +Number Number::operator-( const Number &rhs ) const +{ + return add( rhs, true ); +} + +Number Number::operator*( const Number &rhs ) const { Number ret( iOrd ); - int iPlaces = Bu::buMax(rhs.aInt.getSize(), aInt.getSize() )+1; + int iPlaces = Bu::buMax(rhs.aInt.getSize(), aInt.getSize() ); + int iCnt = aInt.getSize()+rhs.aInt.getSize(); int iCarry = 0; - for( int j = 0; j < iPlaces; j++ ) + int iZeros = 0; + for( int j = 0; j < iCnt || iCarry > 0; j++ ) { - int iRes = iCarry + digit( j ) + rhs.digit( j ); - Bu::println(" Place: %1 + %2 + (%3) = %4"). - arg( digit(j) ).arg( rhs.digit( j ) ).arg( iCarry ) - .arg( iRes ); - ret.aInt.append( (iRes%iRadix) ); - if( iRes < iRadix ) - iCarry = 0; +// Bu::println("Pos %1").arg(j); + int iPos = iCarry; + iCarry = 0; + for( int k = 0; k < rhs.aInt.getSize(); k++ ) + { + if( j-k < 0 ) + break; + + int iRes = digit(j-k)*rhs.digit(k); + iPos += iRes; + +// Bu::println(" [%1] %2 * [%3] %4 = %5 -> %6"). +// arg( j-k ).arg( digit(j-k) ).arg( k ).arg( rhs.digit(k) ). +// arg( iRes ).arg( iPos ).arg( iCarry ); + } + if( (iPos%iRadix) == 0 ) + iZeros++; else - iCarry = iRes/iRadix; + { + for(; iZeros > 0; iZeros-- ) + ret.aInt.append( 0 ); + ret.aInt.append( iPos%iRadix ); + } + iCarry += iPos/iRadix; } + if( bPositive == rhs.bPositive ) + ret.bPositive = true; + else + ret.bPositive = false; + return ret; } +void Number::set( const Bu::String &sNum ) +{ + aInt.clear(); + bPositive = true; + for( int j = sNum.getSize()-1; j >= 0; j-- ) + { + if( sNum[j] == '+' ) + break; + if( sNum[j] == '-' ) + { + bPositive = false; + break; + } + aInt.append( sNum[j]-'0' ); + } +} + +Bu::String Number::toString() const +{ + if( aInt.getSize() == 0 ) + return "0"; + return (bPositive?"":"-") + aInt.toString(); +} + int Number::digit( int iOrder ) const { if( iOrder >= aInt.getSize() ) @@ -52,3 +117,76 @@ int Number::digit( int iOrder ) const return aInt[iOrder]; } +Number Number::add( const Number &rhs, bool bSub ) const +{ + Number ret( iOrd ); + + int iPlaces = Bu::buMax(rhs.aInt.getSize(), aInt.getSize() ); + + int iZeros = 0; + int iCarry = 0; + + if( bPositive == (bSub?!rhs.bPositive:rhs.bPositive)) + { + ret.bPositive = bPositive; + for( int j = 0; j < iPlaces || iCarry > 0; j++ ) + { + int iRes = iCarry + digit( j ) + rhs.digit( j ); +// Bu::println(" Place: %1 + %2 + (%3) = %4"). +// arg( digit(j) ).arg( rhs.digit( j ) ).arg( iCarry ) +// .arg( iRes ); + if( iRes == 0 ) + { + iZeros++; + continue; + } + for(; iZeros > 0; iZeros-- ) + ret.aInt.append( 0 ); + + ret.aInt.append( (iRes%iRadix) ); + if( iRes < iRadix ) + iCarry = 0; + else + iCarry = iRes/iRadix; + } + } + else + { + iCarry = 1; +// Bu::println("--method b--"); + ret.bPositive = bPositive; + int iRes; + for( int j = 0; j < iPlaces; j++ ) + { + iRes = digit( j ) + (9-rhs.digit( j )) + iCarry; +// Bu::println(" Place: %1 + %2 + (%3) = %4"). +// arg( digit(j) ).arg( 9-rhs.digit( j ) ).arg( iCarry ) +// .arg( iRes ); + if( iRes == 0 ) + { + iZeros++; + continue; + } + for(; iZeros > 0; iZeros-- ) + ret.aInt.append( 0 ); + + ret.aInt.append( (iRes%iRadix) ); + if( iRes < iRadix ) + iCarry = 0; + else + iCarry = iRes/iRadix; + } + if( iCarry == 0 ) + { + ret.bPositive = false; + ret.aInt.set( 0, 9-ret.aInt.get( 0 )+1); + for( int j = 1; j < ret.aInt.getSize(); j++ ) + { + ret.aInt.set( j, 9-ret.aInt.get( j )); + } + } + } + + return ret; +} + diff --git a/src/number.h b/src/number.h index 4ada829..1489623 100644 --- a/src/number.h +++ b/src/number.h @@ -11,19 +11,28 @@ public: Number( const Bu::String &sData, int iOrd=0 ); virtual ~Number(); + Number &operator=( const Bu::String &sNum ); Number operator+( const Number &rhs ) const; + Number operator-( const Number &rhs ) const; + Number operator*( const Number &rhs ) const; + + void set( const Bu::String &sNum ); operator Bu::String() const { return aInt.toString(); } - Bu::String toString() const { return aInt.toString(); } + Bu::String toString() const; int digit( int iOrder ) const; +private: + Number add( const Number &rhs, bool bSub ) const; + private: int iOrd; + bool bPositive; PackedIntArray aInt; }; diff --git a/src/packedintarray.cpp b/src/packedintarray.cpp index 817a7ab..7654356 100644 --- a/src/packedintarray.cpp +++ b/src/packedintarray.cpp @@ -41,11 +41,28 @@ PackedIntArray::PackedIntArray( PackedIntArray::Unit iBitWidth, int iCount ): uMask |= (1< 0 ) + iCount--; +} + PackedIntArray::Unit PackedIntArray::get( int idx ) const { int iStore = idx*iBitWidth/StoreBits; @@ -121,12 +144,12 @@ void PackedIntArray::checkCapacity() { if( iCount > iCapacity ) { - Bu::println("!!! Resizing !!!"); +// Bu::println("!!! Resizing !!!"); Store *aOldData = aData; int iNewSize = StoreCount(iCapacity*2); int iSize = StoreCount(iCapacity); - Bu::println(" %1 => %2 (%3 bit words)").arg( iSize ).arg( iNewSize ) - .arg( StoreBits ); +// Bu::println(" %1 => %2 (%3 bit words)").arg( iSize ).arg( iNewSize ) +// .arg( StoreBits ); aData = new Store[iNewSize]; memset( aData, 0, iNewSize*sizeof(Store) ); memcpy( aData, aOldData, iSize*sizeof(Store) ); diff --git a/src/packedintarray.h b/src/packedintarray.h index 953492b..8fcf794 100644 --- a/src/packedintarray.h +++ b/src/packedintarray.h @@ -9,9 +9,12 @@ public: typedef uint_fast8_t Unit; PackedIntArray( Unit iBitWidth ); PackedIntArray( Unit iBitWidth, int iCapacity ); + PackedIntArray( const PackedIntArray &rSrc ); virtual ~PackedIntArray(); + void clear(); void append( Unit i ); + void remove(); Unit operator[]( int idx ) const { return get( idx ); } Unit get( int idx ) const; Unit set( int idx, Unit i ); -- cgit v1.2.3