summaryrefslogtreecommitdiff
path: root/src/number.cpp
diff options
context:
space:
mode:
authorMike Buland <mike@xagasoft.com>2014-10-31 10:41:57 -0600
committerMike Buland <mike@xagasoft.com>2014-10-31 10:41:57 -0600
commit9e204039f0b310bdb101063bbfb82b9a9fb5d5e0 (patch)
treefef00f18505f649b3dfa07a2aa3dccef92bcb651 /src/number.cpp
parent301844ef30b44966463ab22d6a518bc302330e1e (diff)
downloadclic-9e204039f0b310bdb101063bbfb82b9a9fb5d5e0.tar.gz
clic-9e204039f0b310bdb101063bbfb82b9a9fb5d5e0.tar.bz2
clic-9e204039f0b310bdb101063bbfb82b9a9fb5d5e0.tar.xz
clic-9e204039f0b310bdb101063bbfb82b9a9fb5d5e0.zip
Corrected issue with particular sequences of zeros.
No more known division issues.
Diffstat (limited to '')
-rw-r--r--src/number.cpp60
1 files changed, 40 insertions, 20 deletions
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 @@
1#include "config.h"
1#include "number.h" 2#include "number.h"
2 3
3#include <bu/sio.h> 4#include <bu/sio.h>
4#include <math.h> 5#include <math.h>
5 6
7// Enjoy the majisty of my magic floating point literal!
8// This tells us how many bits we'll need per digit to represent a particular
9// radix. You can figure out how many digits any number will take up in any
10// radix with the following:
11//
12// ceiling(ln( num ) / ln( radix ))
13//
14// As long as the base of the logs are the same it doesn't matter what the base
15// is, it cancels out, so we don't have to be particular. But we're always
16// looking for the largest number in a radix to be stored in binary, so the
17// denominator is always the same, so I precomputed it.
6#define RadixToBits( x ) ((int)(log((x))*0xb.8aa3b295c17fp-3+1.0)) 18#define RadixToBits( x ) ((int)(log((x))*0xb.8aa3b295c17fp-3+1.0))
7 19
8Number::Number( int iScale, int iRadix ) : 20Number::Number( int iScale, int iRadix ) :
@@ -392,27 +404,27 @@ void Number::set( int32_t iNum )
392 404
393void Number::divide( const Number &rhs, Number &q, Number &r ) const 405void Number::divide( const Number &rhs, Number &q, Number &r ) const
394{ 406{
395// Bu::println("divide: %1 / %2").arg( *this ).arg( rhs ); 407 DBS( DIVIDE, Bu::println("divide: %1 / %2").arg( *this ).arg( rhs ) );
396 408
397 // iNumShift is how many digits we've shifted the entire equation, 409 // iNumShift is how many digits we've shifted the entire equation,
398 // effectively multiplying the numerator and divisor by iRadix*iNumShift 410 // effectively multiplying the numerator and divisor by iRadix*iNumShift
399 int iNumShift = rhs.getEffectiveScale(); 411 int iNumShift = rhs.getEffectiveScale();
400// Bu::println("iNumShift = %1").arg( iNumShift ); 412 DBS( DIVIDE, Bu::println("iNumShift = %1").arg( iNumShift ) );
401 413
402 // Setup our divisor, this is important, it should be an integer to make 414 // Setup our divisor, this is important, it should be an integer to make
403 // things easy, and it won't change once we create it. 415 // things easy, and it won't change once we create it.
404 Number nDiv( 0, iRadix ); 416 Number nDiv( 0, iRadix );
405 for( int j = -iNumShift; j < rhs.aInt.getSize(); j++ ) 417 for( int j = -iNumShift; j < rhs.aInt.getSize(); j++ )
406 { 418 {
407// Bu::println(" -> '%1'").arg( rhs.digit( j ) ); 419 DBS( DIVIDE, Bu::println(" -> '%1'").arg( rhs.digit( j ) ) );
408 nDiv.aInt.append( rhs.digit( j ) ); 420 nDiv.aInt.append( rhs.digit( j ) );
409 } 421 }
410// Bu::println("New divisor: %1").arg( nDiv ); 422 DBS( DIVIDE, Bu::println("New divisor: %1").arg( nDiv ) );
411 423
412 // Anchor is the position in the output the new digit will appear. 424 // Anchor is the position in the output the new digit will appear.
413 // This also tells us where the ones place will be in our new numerator. 425 // This also tells us where the ones place will be in our new numerator.
414 int iAnchor = (aInt.getSize()+iNumShift)-nDiv.aInt.getSize(); 426 int iAnchor = (aInt.getSize()+iNumShift)-nDiv.aInt.getSize();
415// Bu::println("Anchor: %1").arg( iAnchor ); 427 DBS( DIVIDE, Bu::println("Anchor: %1").arg( iAnchor ) );
416 428
417 // Setup our output variables 429 // Setup our output variables
418 q.iRadix = r.iRadix = iRadix; 430 q.iRadix = r.iRadix = iRadix;
@@ -433,22 +445,30 @@ void Number::divide( const Number &rhs, Number &q, Number &r ) const
433 for( int j = iAnchor-iNumShift; 445 for( int j = iAnchor-iNumShift;
434 nNum.aInt.getSize() < nDiv.aInt.getSize(); j++ ) 446 nNum.aInt.getSize() < nDiv.aInt.getSize(); j++ )
435 { 447 {
436// Bu::println(" ->[%1] '%2'").arg( j ).arg( digit(j) ); 448 DBS( DIVIDE, Bu::println(" ->[%1] '%2'").arg( j ).arg( digit(j) ) );
437 nNum.aInt.append( digit( j ) ); 449 nNum.aInt.append( digit( j ) );
438 } 450 }
439// Bu::println("New numerator: %1").arg( nNum ); 451 DBS( DIVIDE, Bu::println("New numerator: %1").arg( nNum ) );
440 while( iAnchor >= -iScale && (!nNum.isZero() || iAnchor > 0)) // division loop 452 while( iAnchor >= -iScale && (!nNum.isZero() || iAnchor > 0)) // division loop
441 { 453 {
442 // As long as the numerator is smaller than the divisor we keep 454 // As long as the numerator is smaller than the divisor we keep
443 // including new digits. 455 // including new digits.
444 while( nNum < nDiv ) 456 while( nNum.aInt.getSize() < nDiv.aInt.getSize() ||
457 nNum < nDiv )
445 { 458 {
446 iAnchor--; 459 iAnchor--;
447 nNum.aInt.insert( 0, digit(iAnchor-iNumShift) ); 460 int iDig = digit(iAnchor-iNumShift);
448// Bu::println("Numerator too small, new numerator: %1").arg( nNum ); 461 if( nNum.aInt.getSize() == 0 && iDig == 0 )
462 {
463 if( iAnchor < -iScale )
464 break;
465 continue;
466 }
467 nNum.aInt.insert( 0, iDig );
468 DBS( DIVIDE, Bu::println("Numerator too small, new numerator: %1").arg( nNum ) );
449 } 469 }
450 470
451// Bu::println(" New anchor: %1 vs iScale = %2").arg( iAnchor ).arg( iScale ); 471 DBS( DIVIDE, Bu::println(" New anchor: %1 vs iScale = %2").arg( iAnchor ).arg( iScale ) );
452 if( iAnchor < 0 && -1-iAnchor >= iScale ) 472 if( iAnchor < 0 && -1-iAnchor >= iScale )
453 break; 473 break;
454 474
@@ -456,11 +476,11 @@ void Number::divide( const Number &rhs, Number &q, Number &r ) const
456 int iCount = 0; 476 int iCount = 0;
457 for(;nNum >= nDiv; iCount++ ) 477 for(;nNum >= nDiv; iCount++ )
458 { 478 {
459// Bu::print(" ==> step %3: %1 - %2 = ").arg( nNum ).arg( nDiv ).arg( iCount ); 479 DBS( DIVIDE, Bu::print(" ==> step %3: %1 - %2 = ").arg( nNum ).arg( nDiv ).arg( iCount ) );
460 nNum = nNum - nDiv; 480 nNum = nNum - nDiv;
461// Bu::println("%1").arg( nNum ); 481 DBS( DIVIDE, Bu::println("%1").arg( nNum ) );
462 } 482 }
463// Bu::println("Total steps: %1").arg( iCount ); 483 DBS( DIVIDE, Bu::println("Total steps: %1").arg( iCount ) );
464 484
465 if( iAnchor >= 0 ) 485 if( iAnchor >= 0 )
466 { 486 {
@@ -481,15 +501,15 @@ void Number::divide( const Number &rhs, Number &q, Number &r ) const
481 r.aInt.append( nNum.aInt[j] ); 501 r.aInt.append( nNum.aInt[j] );
482 int jtop = 0; 502 int jtop = 0;
483 for(; nNum.aInt[jtop] == 0; jtop++ ) { } 503 for(; nNum.aInt[jtop] == 0; jtop++ ) { }
484// Bu::println("Computing remainder fraction from %1 to %2") 504 DBS( DIVIDE, Bu::println("Computing remainder fraction from %1 to %2")
485// .arg( -iAnchor-1 ).arg( jtop ); 505 .arg( -iAnchor-1 ).arg( jtop ) );
486 r.aFrac.clear(); 506 r.aFrac.clear();
487 for( int j = -iAnchor-1, k = 0; j >= jtop && k < r.iScale; j--, k++ ) 507 for( int j = -iAnchor-1, k = 0; j >= jtop && k < r.iScale; j--, k++ )
488 { 508 {
489 if( j < nNum.aInt.getSize() ) 509 if( j < nNum.aInt.getSize() )
490 { 510 {
491 r.aFrac.set( k, nNum.aInt[j] ); 511 r.aFrac.set( k, nNum.aInt[j] );
492// Bu::println("setting %1 to %2").arg( k ).arg( nNum.aInt[j] ); 512 DBS( DIVIDE, Bu::println("setting %1 to %2").arg( k ).arg( nNum.aInt[j] ) );
493 } 513 }
494 } 514 }
495 } 515 }
@@ -497,9 +517,9 @@ void Number::divide( const Number &rhs, Number &q, Number &r ) const
497// { 517// {
498// Bu::println("iAnchor: %1").arg( iAnchor ); 518// Bu::println("iAnchor: %1").arg( iAnchor );
499// } 519// }
500// Bu::println("Quotient: %1").arg( q ); 520 DBS( DIVIDE, Bu::println("Quotient: %1").arg( q ) );
501// Bu::println("Final numerator? %1").arg( nNum ); 521 DBS( DIVIDE, Bu::println("Final numerator? %1").arg( nNum ) );
502// Bu::println("Remainder? %1").arg( r ); 522 DBS( DIVIDE, Bu::println("Remainder? %1").arg( r ) );
503 523
504} 524}
505 525