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.

1 files changed, 118 insertions, 130 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;