From 9e204039f0b310bdb101063bbfb82b9a9fb5d5e0 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Fri, 31 Oct 2014 10:41:57 -0600 Subject: Corrected issue with particular sequences of zeros. No more known division issues. --- src/config.h | 8 ++++++++ src/number.cpp | 60 ++++++++++++++++++++++++++++++++++++++-------------------- 2 files changed, 48 insertions(+), 20 deletions(-) create mode 100644 src/config.h diff --git a/src/config.h b/src/config.h new file mode 100644 index 0000000..00fb067 --- /dev/null +++ b/src/config.h @@ -0,0 +1,8 @@ +#ifndef CONFIG_H +#define CONFIG_H + +#define DEBUG_DIVIDE false +#define DBS( s, x ) if( DEBUG_ ##s ) { x; } (void)0 + + +#endif diff --git a/src/number.cpp b/src/number.cpp index 9a7da17..328cb58 100644 --- a/src/number.cpp +++ b/src/number.cpp @@ -1,8 +1,20 @@ +#include "config.h" #include "number.h" #include #include +// Enjoy the majisty of my magic floating point literal! +// This tells us how many bits we'll need per digit to represent a particular +// radix. You can figure out how many digits any number will take up in any +// radix with the following: +// +// ceiling(ln( num ) / ln( radix )) +// +// As long as the base of the logs are the same it doesn't matter what the base +// is, it cancels out, so we don't have to be particular. But we're always +// looking for the largest number in a radix to be stored in binary, so the +// denominator is always the same, so I precomputed it. #define RadixToBits( x ) ((int)(log((x))*0xb.8aa3b295c17fp-3+1.0)) Number::Number( int iScale, int iRadix ) : @@ -392,27 +404,27 @@ void Number::set( int32_t iNum ) void Number::divide( const Number &rhs, Number &q, Number &r ) const { -// Bu::println("divide: %1 / %2").arg( *this ).arg( rhs ); + DBS( DIVIDE, Bu::println("divide: %1 / %2").arg( *this ).arg( rhs ) ); // 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 ); + DBS( DIVIDE, Bu::println("iNumShift = %1").arg( iNumShift ) ); // 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 ) ); + DBS( DIVIDE, Bu::println(" -> '%1'").arg( rhs.digit( j ) ) ); nDiv.aInt.append( rhs.digit( j ) ); } -// Bu::println("New divisor: %1").arg( nDiv ); + DBS( DIVIDE, Bu::println("New divisor: %1").arg( nDiv ) ); // 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 ); + DBS( DIVIDE, Bu::println("Anchor: %1").arg( iAnchor ) ); // Setup our output variables q.iRadix = r.iRadix = iRadix; @@ -433,22 +445,30 @@ void Number::divide( const Number &rhs, Number &q, Number &r ) const for( int j = iAnchor-iNumShift; nNum.aInt.getSize() < nDiv.aInt.getSize(); j++ ) { -// Bu::println(" ->[%1] '%2'").arg( j ).arg( digit(j) ); + DBS( DIVIDE, Bu::println(" ->[%1] '%2'").arg( j ).arg( digit(j) ) ); nNum.aInt.append( digit( j ) ); } -// Bu::println("New numerator: %1").arg( nNum ); + DBS( DIVIDE, Bu::println("New numerator: %1").arg( nNum ) ); while( iAnchor >= -iScale && (!nNum.isZero() || iAnchor > 0)) // division loop { // As long as the numerator is smaller than the divisor we keep // including new digits. - while( nNum < nDiv ) + while( nNum.aInt.getSize() < nDiv.aInt.getSize() || + nNum < nDiv ) { iAnchor--; - nNum.aInt.insert( 0, digit(iAnchor-iNumShift) ); -// Bu::println("Numerator too small, new numerator: %1").arg( nNum ); + int iDig = digit(iAnchor-iNumShift); + if( nNum.aInt.getSize() == 0 && iDig == 0 ) + { + if( iAnchor < -iScale ) + break; + continue; + } + nNum.aInt.insert( 0, iDig ); + DBS( DIVIDE, Bu::println("Numerator too small, new numerator: %1").arg( nNum ) ); } -// Bu::println(" New anchor: %1 vs iScale = %2").arg( iAnchor ).arg( iScale ); + DBS( DIVIDE, Bu::println(" New anchor: %1 vs iScale = %2").arg( iAnchor ).arg( iScale ) ); if( iAnchor < 0 && -1-iAnchor >= iScale ) break; @@ -456,11 +476,11 @@ void Number::divide( const Number &rhs, Number &q, Number &r ) const int iCount = 0; for(;nNum >= nDiv; iCount++ ) { -// Bu::print(" ==> step %3: %1 - %2 = ").arg( nNum ).arg( nDiv ).arg( iCount ); + DBS( DIVIDE, Bu::print(" ==> step %3: %1 - %2 = ").arg( nNum ).arg( nDiv ).arg( iCount ) ); nNum = nNum - nDiv; -// Bu::println("%1").arg( nNum ); + DBS( DIVIDE, Bu::println("%1").arg( nNum ) ); } -// Bu::println("Total steps: %1").arg( iCount ); + DBS( DIVIDE, Bu::println("Total steps: %1").arg( iCount ) ); if( iAnchor >= 0 ) { @@ -481,15 +501,15 @@ void Number::divide( const Number &rhs, Number &q, Number &r ) const 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 ); + DBS( DIVIDE, Bu::println("Computing remainder fraction from %1 to %2") + .arg( -iAnchor-1 ).arg( jtop ) ); r.aFrac.clear(); for( int j = -iAnchor-1, k = 0; j >= jtop && k < r.iScale; j--, k++ ) { if( j < nNum.aInt.getSize() ) { r.aFrac.set( k, nNum.aInt[j] ); -// Bu::println("setting %1 to %2").arg( k ).arg( nNum.aInt[j] ); + DBS( DIVIDE, Bu::println("setting %1 to %2").arg( k ).arg( nNum.aInt[j] ) ); } } } @@ -497,9 +517,9 @@ void Number::divide( const Number &rhs, Number &q, Number &r ) const // { // Bu::println("iAnchor: %1").arg( iAnchor ); // } -// Bu::println("Quotient: %1").arg( q ); -// Bu::println("Final numerator? %1").arg( nNum ); -// Bu::println("Remainder? %1").arg( r ); + DBS( DIVIDE, Bu::println("Quotient: %1").arg( q ) ); + DBS( DIVIDE, Bu::println("Final numerator? %1").arg( nNum ) ); + DBS( DIVIDE, Bu::println("Remainder? %1").arg( r ) ); } -- cgit v1.2.3