From 7026b96ec807b169f7b413056e52412ae422ea9d Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Thu, 30 Oct 2014 13:15:19 -0600 Subject: The new division works great! Other minor bug fixes including scale issues, digit() access stopped a digit before the final possible digit in the scale, >, >=, <, <= all work correctly with mixed scale numbers now, probably other fixes. --- src/number.cpp | 248 +++++++++++++++++++++++++---------------------------- src/number.h | 1 + src/options.cpp | 1 + src/parser.cpp | 4 +- src/unitnumber.cpp | 8 ++ src/unitnumber.h | 1 + src/unitparser.cpp | 4 +- 7 files changed, 134 insertions(+), 133 deletions(-) diff --git a/src/number.cpp b/src/number.cpp index 0b8e07b..c23466e 100644 --- a/src/number.cpp +++ b/src/number.cpp @@ -186,9 +186,15 @@ bool Number::operator>( const Number &rhs ) const else if( iDiff > 0 ) return bPositive; } - for( int j = 0; j < iScale; j++ ) + int iMax = iScale; + if( rhs.iScale > iMax ) + iMax = rhs.iScale; +// Bu::println("Max scale = %1").arg( iMax ); + for( int j = 0; j < iMax; j++ ) { - int iDiff = aFrac[j] - rhs.aFrac[j]; +// Bu::println(" > at %1 (%2 > %3)").arg( j ) +// .arg( digit(-1-j) ).arg( rhs.digit(-1-j) ); + int iDiff = digit(-1-j) - rhs.digit(-1-j); if( iDiff < 0 ) return !bPositive; else if( iDiff > 0 ) @@ -219,9 +225,12 @@ bool Number::operator<( const Number &rhs ) const else if( iDiff < 0 ) return bPositive; } - for( int j = 0; j < iScale; j++ ) + int iMax = iScale; + if( rhs.iScale > iMax ) + iMax = rhs.iScale; + for( int j = 0; j < iMax; j++ ) { - int iDiff = aFrac[j] - rhs.aFrac[j]; + int iDiff = digit(-1-j) - rhs.digit(-1-j); if( iDiff > 0 ) return !bPositive; else if( iDiff < 0 ) @@ -244,17 +253,18 @@ bool Number::operator>=( const Number &rhs ) const for( int j = aInt.getSize()-1; j >= 0; j-- ) { -// Bu::println(" --> %1 > %2 -> %3").arg( aInt[j] ).arg( rhs.aInt[j] ). -// arg( aInt[j] > rhs.aInt[j] ); int iDiff = aInt[j] - rhs.aInt[j]; if( iDiff < 0 ) return !bPositive; else if( iDiff > 0 ) return bPositive; } - for( int j = 0; j < iScale; j++ ) + int iMax = iScale; + if( rhs.iScale > iMax ) + iMax = rhs.iScale; + for( int j = 0; j < iMax; j++ ) { - int iDiff = aFrac[j] - rhs.aFrac[j]; + int iDiff = digit(-1-j) - rhs.digit(-1-j); if( iDiff < 0 ) return !bPositive; else if( iDiff > 0 ) @@ -285,9 +295,12 @@ bool Number::operator<=( const Number &rhs ) const else if( iDiff < 0 ) return bPositive; } - for( int j = 0; j < iScale; j++ ) + int iMax = iScale; + if( rhs.iScale > iMax ) + iMax = rhs.iScale; + for( int j = 0; j < iMax; j++ ) { - int iDiff = aFrac[j] - rhs.aFrac[j]; + int iDiff = digit(-1-j) - rhs.digit(-1-j); if( iDiff > 0 ) return !bPositive; else if( iDiff < 0 ) @@ -382,140 +395,104 @@ void Number::set( int32_t iNum ) void Number::divide( const Number &rhs, Number &q, Number &r ) const { - if( rhs.iScale > 0 ) - { - Number newrhs = Number( 0, iRadix ); - Number newbase = Number( iScale, iRadix ); - int iOff; - for( iOff = -iScale; iOff < 0 && rhs.digit( iOff ) == 0; iOff++ ) { } - if( iOff < 0 ) - { - for( int j = iOff; j < rhs.aInt.getSize(); j++ ) - { - newrhs.aInt.append( rhs.digit( j ) ); - newbase.aInt.append( digit( j ) ); - } - for( int j = rhs.aInt.getSize(); j < aInt.getSize(); j++ ) - { - newbase.aInt.append( aInt.get( j ) ); - } - for( int j = iScale+iOff; j >= -iOff; j-- ) - { - newbase.aFrac.set( j+iOff, aFrac.get( j ) ); - } +// Bu::println("divide: %1 / %2").arg( *this ).arg( rhs ); -// Bu::println("Conv %1 => %2 (iOff = %3)").arg( rhs ).arg( newrhs ).arg( iOff ); -// Bu::println("Conv %1 => %2 (iOff = %3)").arg( *this ).arg( newbase ).arg( iOff ); + // iNumShift is how many digits we've shifted the entire equation, + // effectively multiplying the numerator and divisor by iRadix*iNumShift + int iNumShift = rhs.getEffectiveScale(); +// Bu::println("iNumShift = %1").arg( iNumShift ); - newbase.divide( newrhs, q, r ); - return; - } + // Setup our divisor, this is important, it should be an integer to make + // things easy, and it won't change once we create it. + Number nDiv( 0, iRadix ); + for( int j = -iNumShift; j < rhs.aInt.getSize(); j++ ) + { +// Bu::println(" -> '%1'").arg( rhs.digit( j ) ); + nDiv.aInt.append( rhs.digit( j ) ); } - - q = Number( iScale, iRadix ); - r = *this; - - if( bPositive == rhs.bPositive ) - q.bPositive = true; - else - q.bPositive = false; - - int iMinWidth = Bu::buMax(1,rhs.aInt.getSize()); +// Bu::println("New divisor: %1").arg( nDiv ); - int iAnchor = r.aInt.getSize()-iMinWidth; - int iSample = iMinWidth; - do + // Anchor is the position in the output the new digit will appear. + // This also tells us where the ones place will be in our new numerator. + int iAnchor = (aInt.getSize()+iNumShift)-nDiv.aInt.getSize(); +// Bu::println("Anchor: %1").arg( iAnchor ); + + // Setup our output variables + q.iRadix = r.iRadix = iRadix; + q.iScale = r.iScale = iScale; + q.bPositive = !(!bPositive ^ !rhs.bPositive); + r.bPositive = true; + q.aInt.clear(); + r.aInt.clear(); + if( q.aFrac.getSize() != iScale ) + q.aFrac = PackedIntArray( aFrac.getBitWidth(), iScale ); + if( r.aFrac.getSize() != iScale ) + r.aFrac = PackedIntArray( aFrac.getBitWidth(), iScale ); + + // The numerator is re-created every step to match the divisor and + // anchor + Number nNum( iScale, iRadix ); + for( int j = iAnchor-iNumShift; + nNum.aInt.getSize() < nDiv.aInt.getSize(); j++ ) + { +// Bu::println(" ->[%1] '%2'").arg( j ).arg( digit(j) ); + nNum.aInt.append( digit( j ) ); + } +// Bu::println("New numerator: %1").arg( nNum ); + while( iAnchor > -iScale && !nNum.isZero()) // division loop { -// Bu::println("%1\n-----").arg( r.aInt.toString() ); - Number sub( 0, iRadix ); - if( iAnchor < 0 ) + // As long as the numerator is smaller than the divisor we keep + // including new digits. + while( nNum < nDiv ) { - sub = r; - sub.aInt.insert(0,0); + iAnchor--; + nNum.aInt.insert( 0, digit(iAnchor-iNumShift) ); +// Bu::println("Numerator too small, new numerator: %1").arg( nNum ); } - for(;;) + if( iAnchor < -iScale ) + break; + +// Bu::println(" New anchor: %1").arg( iAnchor ); + + // How many times does the divisor fit into the numerator + int iCount = 0; + for(;nNum >= nDiv; iCount++ ) { -// Bu::println(" -> Anchor: %1, Sample: %2").arg( iAnchor ).arg( iSample ); - if( iAnchor >= 0 ) - { - sub.aInt.set( r.aInt, iAnchor, iSample ); - } - else - { -/* sub.aInt.clear(); - for( int j = iAnchor; j < r.aInt.getSize(); j++ ) - { - sub.aInt.append( r.digit( j ) ); - } - */ - } -// Bu::println("%1\n%2\n----").arg( sub.toString() ).arg( rhs.toString() ); - if( sub < rhs ) - { - iSample++; - iAnchor--; - if( iAnchor < 0 ) - { - if( r.isZero() || iAnchor < -iScale ) - { -// Bu::println("[Inner exit] Complete: q = %1, r = %2").arg( q.toString() ).arg( r.toString() ); - return; - } - sub.aInt.insert(0, 0); - } - } - else - break; +// Bu::print(" ==> step %3: %1 - %2 = ").arg( nNum ).arg( nDiv ).arg( iCount ); + nNum = nNum - nDiv; +// Bu::println("%1").arg( nNum ); } +// Bu::println("Total steps: %1").arg( iCount ); - Number x( 0, iRadix ); - int iRes = -1; -// Bu::println("{x = %1, sub=%2, rhs=%4, iRes=%3}").arg( x ).arg(sub).arg(iRes).arg(rhs); - for( ; x <= sub; iRes++, x = x + rhs ) { -// Bu::println("{x = %1, sub=%2, rhs=%4, iRes=%3, x+rhs=%5}").arg( x ).arg(sub).arg(iRes).arg(rhs).arg(x+rhs); - } - x = sub - (x - rhs); - if( !x.bPositive ) + if( iAnchor >= 0 ) { - iSample++; - iAnchor--; -// Bu::println("What? it's negative? %1").arg( x ); - continue; + while( q.aInt.getSize() <= iAnchor ) + q.aInt.append( 0 ); + q.aInt.set( iAnchor, iCount ); } - if( iAnchor < 0 ) + else { - r = x; + while( q.aFrac.getSize() <= -1-iAnchor ) + q.aFrac.append( 0 ); + q.aFrac.set( -1-iAnchor, iCount ); } - else + } + for( int j = -iAnchor; j < nNum.aInt.getSize(); j++ ) + r.aInt.append( nNum.aInt[j] ); + int jtop = 0; + for(; nNum.aInt[jtop] == 0; jtop++ ) { } +// Bu::println("Computing remainder fraction from %1 to %2") +// .arg( -iAnchor-1 ).arg( jtop ); + for( int j = -iAnchor-1, k = 0; j >= jtop && k < r.iScale; j--, k++ ) + { + if( j <= nNum.aInt.getSize() ) { - for( int j = 0; j < x.aInt.getSize(); j++ ) - r.aInt.set( iAnchor+j, x.aInt.get( j ) ); + r.aFrac.set( k, nNum.aInt[j] ); +// Bu::println("setting %1 to %2").arg( k ).arg( nNum.aInt[j] ); } - - while( r.aInt.getSize() > Bu::buMax(0,iAnchor)+x.aInt.getSize() ) - r.aInt.remove(); -// Bu::println(" -> Post remainder patch: %1 -> %2"). -// arg( x.toString() ).arg( r.toString() ); - -// Bu::println("%1 (%2)").arg( iRes ).arg( x.toString() ); - while( q.aInt.getSize() <= iAnchor ) - q.aInt.append(0); - if( iAnchor >= 0 ) - q.aInt.set( iAnchor, iRes ); - else - q.aFrac.set( -1-iAnchor, iRes ); - - iSample = iMinWidth; - if( iAnchor > 0 ) - iAnchor -= rhs.aInt.getSize()-x.aInt.getSize(); - else - iAnchor--; -// iAnchor = r.aInt.getSize()-iMinWidth; -// Bu::println(" -> new Anchor: %1, Sample: %2").arg( iAnchor ). -// arg( iSample ); - } while( iAnchor >= -iScale ); - -// Bu::println("Complete: q = %1, r = %2").arg( q.toString() ).arg( r.toString() ); + } +// Bu::println("Final numerator? %1").arg( nNum ); +// Bu::println("Remainder? %1").arg( r ); } bool Number::isZero() const @@ -579,7 +556,7 @@ int Number::digit( int iIdx ) const { if( iIdx < 0 ) { - if( iIdx <= -iScale ) + if( iIdx < -iScale ) return 0; else return aFrac[-1-iIdx]; @@ -608,6 +585,15 @@ void Number::setScale( int iNewScale ) iScale = iNewScale; } +int Number::getEffectiveScale() const +{ + if( iScale == 0 ) + return 0; + int iSigDig = iScale-1; + for( ; iSigDig >= 0 && aFrac.get( iSigDig ) == 0; iSigDig-- ) { } + return iSigDig+1; +} + int32_t Number::toInt32() const { int32_t ret = 0; @@ -632,8 +618,10 @@ Number Number::toRadix( int iNewRadix, int iNewScale ) const n.set( iNewRadix ); while( !me.isZero() ) { - ret.aInt.append( (me%n).toInt32() ); + int dig = (me%n).toInt32(); + ret.aInt.append( dig ); me = me / n; + Bu::println("New digit: %1 (%2)").arg( dig ).arg( me ); } return ret; diff --git a/src/number.h b/src/number.h index 40dbd55..fe10788 100644 --- a/src/number.h +++ b/src/number.h @@ -47,6 +47,7 @@ public: int digit( int iIdx ) const; int getScale() const { return iScale; } + int getEffectiveScale() const; void setScale( int iNewScale ); int32_t toInt32() const; diff --git a/src/options.cpp b/src/options.cpp index 6e264f9..3581500 100644 --- a/src/options.cpp +++ b/src/options.cpp @@ -150,6 +150,7 @@ int Options::convert( Bu::StringArray aArgs ) iToRadix = strtol( lBits.last().getStr(), 0, 10 ); n = Number( *(lBits.begin()+1), 0, iFromRadix ); } + Bu::println("%1").arg( n.toString() ); Bu::println("%1").arg( n.toRadix( iToRadix ).toString() ); } diff --git a/src/parser.cpp b/src/parser.cpp index 607de8a..8675a7c 100644 --- a/src/parser.cpp +++ b/src/parser.cpp @@ -232,9 +232,11 @@ void Parser::unwind() { Token b = tsTerminal.peekPop(); Token a = tsTerminal.peekPop(); + Number *pProduct = new Number( deref(a) * deref(b) ); + pProduct->setScale( lex.getScale() ); tsTerminal.push( Token( Token::tNumber, - new Number( deref(a) * deref(b) ) + pProduct ) ); } diff --git a/src/unitnumber.cpp b/src/unitnumber.cpp index 1d63682..4846a07 100644 --- a/src/unitnumber.cpp +++ b/src/unitnumber.cpp @@ -15,6 +15,8 @@ UnitNumber::UnitNumber() "parse1", Bu::UnitSuite::expectPass ); add( static_cast(&UnitNumber::multiply1), "multiply1", Bu::UnitSuite::expectPass ); + add( static_cast(&UnitNumber::divide1), + "divide1", Bu::UnitSuite::expectPass ); add( static_cast(&UnitNumber::number1), "number1", Bu::UnitSuite::expectPass ); add( static_cast(&UnitNumber::compare1), @@ -68,6 +70,12 @@ void UnitNumber::multiply1() ); } +void UnitNumber::divide1() +{ + unitTest(Number("4") / Number("10") == "0"); + unitTest(Number("4") % Number("10") == "4"); +} + #define mathTest( anum, op, bnum, answ ) \ unitTest( (Number(anum) op Number(bnum)).toString() == answ ) diff --git a/src/unitnumber.h b/src/unitnumber.h index 83da27f..96d882e 100644 --- a/src/unitnumber.h +++ b/src/unitnumber.h @@ -12,6 +12,7 @@ public: void packed1(); void parse1(); void multiply1(); + void divide1(); void number1(); void compare1(); void radix1(); diff --git a/src/unitparser.cpp b/src/unitparser.cpp index 891f7b3..43dacfc 100644 --- a/src/unitparser.cpp +++ b/src/unitparser.cpp @@ -33,7 +33,7 @@ void UnitParser::order1() unitTest(parse("2+3*5") == "17"); unitTest(parse("2+3-5") == "0"); unitTest(parse("(2+3)*5") == "25"); - unitTest(parse("1.59*40/24*21", 5) == "55.125"); - unitTest(parse("1.59*40/(24*21)", 5) == "0.125"); // bc says it's this: "0.12619"); + unitTest(parse("1.59*40/24*21", 5) == "55.65"); + unitTest(parse("1.59*40/(24*21)", 5) == "0.12619"); // bc says it's this: "0.12619"); } -- cgit v1.2.3