From: Vadim Zeitlin Date: Fri, 24 Dec 1999 16:49:57 +0000 (+0000) Subject: implemented wxLongLong division - seems to work X-Git-Url: https://git.saurik.com/wxWidgets.git/commitdiff_plain/5e6a0e831533f031463477e11fd9e2c91f56bbbc implemented wxLongLong division - seems to work git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@5101 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775 --- diff --git a/include/wx/longlong.h b/include/wx/longlong.h index 562c1e1de4..c8778899ab 100644 --- a/include/wx/longlong.h +++ b/include/wx/longlong.h @@ -25,7 +25,7 @@ #include // for LONG_MAX -// #define wxUSE_LONGLONG_WX 1 -- for testing (VZ) +//#define wxUSE_LONGLONG_WX 1 // for testing (VZ) // ---------------------------------------------------------------------------- // decide upon which class we will use @@ -59,7 +59,7 @@ // have any 64 bit integer type #if !defined(__VISAGECPP__) && \ !defined(__VISUALC__) && \ - !defined(__BORLANDC__ + !defined(__BORLANDC__) #warning "Your compiler does not appear to support 64 bit integers, "\ "using emulation class instead." #endif // known compilers without long long diff --git a/samples/console/console.cpp b/samples/console/console.cpp index 771db68871..ee96ced5d4 100644 --- a/samples/console/console.cpp +++ b/samples/console/console.cpp @@ -32,11 +32,11 @@ //#define TEST_ARRAYS //#define TEST_DIR //#define TEST_LOG -#define TEST_LONGLONG +//#define TEST_LONGLONG //#define TEST_MIME //#define TEST_STRINGS //#define TEST_THREADS -//#define TEST_TIME +#define TEST_TIME // ============================================================================ // implementation @@ -224,14 +224,16 @@ static void TestSpeed() static void TestDivision() { + puts("*** Testing wxLongLong division ***\n"); + #define MAKE_LL(x1, x2, x3, x4) wxLongLong((x1 << 16) | x2, (x3 << 16) | x3) // seed pseudo random generator - //srand((unsigned)time(NULL)); + srand((unsigned)time(NULL)); wxLongLong q, r; size_t nTested = 0; - for ( size_t n = 0; n < 10000; n++ ) + for ( size_t n = 0; n < 100000; n++ ) { // get a random wxLongLong (shifting by 12 the MSB ensures that the // multiplication will not overflow) @@ -242,12 +244,19 @@ static void TestDivision() q = ll / l; r = ll % l; + // verify the result wxASSERT_MSG( ll == q*l + r, "division failure" ); + if ( !(nTested % 1000) ) + { + putchar('.'); + fflush(stdout); + } + nTested++; } - printf("\n*** Tested %u divisions/multiplications: ok\n", nTested); + puts(" done!"); #undef MAKE_LL } diff --git a/src/common/longlong.cpp b/src/common/longlong.cpp index bca0d2d1fe..d1738aff74 100644 --- a/src/common/longlong.cpp +++ b/src/common/longlong.cpp @@ -391,54 +391,128 @@ wxLongLongWx& wxLongLongWx::operator*=(const wxLongLongWx& ll) // division -void wxLongLongWx::Divide(const wxLongLongWx& divisor, +void wxLongLongWx::Divide(const wxLongLongWx& divisorIn, wxLongLongWx& quotient, wxLongLongWx& remainder) const { - if ((divisor.m_lo == 0) && (divisor.m_hi == 0)) + if ((divisorIn.m_lo == 0) && (divisorIn.m_hi == 0)) { // provoke division by zero error and silence the compilers warnings // about an expression without effect and unused variable - long dummy = divisor.m_lo/divisor.m_hi; + long dummy = divisorIn.m_lo/divisorIn.m_hi; dummy += 0; } // VZ: I'm writing this in a hurry and it's surely not the fastest way to // do this - any improvements are more than welcome + // + // code inspired by the snippet at + // http://www.bearcave.com/software/divide.htm + // + // Copyright notice: + // + // Use of this program, for any purpose, is granted the author, Ian + // Kaplan, as long as this copyright notice is included in the source + // code or any source code derived from this program. The user assumes + // all responsibility for using this code. + + // init everything + wxLongLongWx dividend = *this, + divisor = divisorIn; + + quotient = 0l; + remainder = 0l; + + // check for some particular cases + if ( divisor > dividend ) + { + remainder = dividend; + + return; + } - // the algorithm: first find N such that 2^N * divisor is less than us, - // then substract divisor from *this - 2^N * divisor as many times as - // possible + if ( divisor == dividend ) + { + quotient = 1l; + + return; + } + + // always do unsigned division and adjust the signs later: in C integer + // division, the sign of the remainder is the same as the sign of the + // dividend, while the sign of the quotient is the product of the signs of + // the dividend and divisor. Of course, we also always have + // + // dividend = quotient*divisor + remainder + // + // with 0 <= abs(remainder) < abs(divisor) + bool negRemainder = dividend.m_hi < 0; + bool negQuotient = FALSE; // assume positive + if ( dividend.m_hi < 0 ) + { + negQuotient = !negQuotient; + dividend = -dividend; + } + if ( divisor.m_hi < 0 ) + { + negQuotient = !negQuotient; + divisor = -divisor; + } - wxLongLongWx prev = divisor; - remainder = *this; + // here: dividend > divisor and both are positibe: do unsigned division + size_t nBits = 64u; + wxLongLongWx d; - quotient = 1l; + #define IS_MSB_SET(ll) ((ll.m_hi) & (1 << (8*sizeof(long) - 1))) - for ( wxLongLongWx tmp = divisor; tmp < remainder; ) + while ( remainder < divisor ) { - prev = tmp; + remainder <<= 1; + if ( IS_MSB_SET(dividend) ) + { + remainder |= 1; + } + + d = dividend; + dividend <<= 1; - tmp <<= 1; + nBits--; + } + + // undo the last loop iteration + dividend = d; + remainder >>= 1; + nBits++; - if ( tmp < 0 ) + for ( size_t i = 0; i < nBits; i++ ) + { + remainder <<= 1; + if ( IS_MSB_SET(dividend) ) { - // shifted too far - break; + remainder |= 1; } + wxLongLongWx t = remainder - divisor; + dividend <<= 1; quotient <<= 1; + if ( !IS_MSB_SET(t) ) + { + quotient |= 1; + + remainder = t; + } } - while ( remainder >= prev ) + // adjust signs + if ( negRemainder ) { - remainder -= divisor; - quotient++; + remainder = -remainder; } - // remainder should be in this range at the end - wxASSERT_MSG( (0l <= remainder) && (remainder < divisor.Abs()), - _T("logic error in wxLongLong division") ); + if ( negQuotient ) + { + quotient = -quotient; + } } wxLongLongWx wxLongLongWx::operator/(const wxLongLongWx& ll) const