From e3c456752e6d98384049e88f7dc7a1d89a4da0a8 Mon Sep 17 00:00:00 2001 From: sebres Date: Fri, 25 Jan 2019 12:45:28 +0000 Subject: More simplifications in tclExecute.c (INST_EXPON), much more and well-arranged branching of wide/bignum base and exponent cases, test-cases extended to cover all this branches and edge cases. --- generic/tclExecute.c | 225 ++++++++++++++++++++++++++------------------------- tests/mathop.test | 28 ++++++- 2 files changed, 141 insertions(+), 112 deletions(-) diff --git a/generic/tclExecute.c b/generic/tclExecute.c index a433a92..06403c7 100644 --- a/generic/tclExecute.c +++ b/generic/tclExecute.c @@ -7793,6 +7793,91 @@ FinalizeOONextFilter( } /* + * WidePwrSmallExpon -- + * + * Helper to calculate small powers of integers whose result is wide. + */ +static inline Tcl_WideInt +WidePwrSmallExpon(Tcl_WideInt w1, Tcl_WideInt exponent) { + + Tcl_WideInt wResult; + + wResult = w1 * w1; /* b**2 */ + switch (exponent) { + case 2: + break; + case 3: + wResult *= w1; /* b**3 */ + break; + case 4: + wResult *= wResult; /* b**4 */ + break; + case 5: + wResult *= wResult; /* b**4 */ + wResult *= w1; /* b**5 */ + break; + case 6: + wResult *= w1; /* b**3 */ + wResult *= wResult; /* b**6 */ + break; + case 7: + wResult *= w1; /* b**3 */ + wResult *= wResult; /* b**6 */ + wResult *= w1; /* b**7 */ + break; + case 8: + wResult *= wResult; /* b**4 */ + wResult *= wResult; /* b**8 */ + break; + case 9: + wResult *= wResult; /* b**4 */ + wResult *= wResult; /* b**8 */ + wResult *= w1; /* b**9 */ + break; + case 10: + wResult *= wResult; /* b**4 */ + wResult *= w1; /* b**5 */ + wResult *= wResult; /* b**10 */ + break; + case 11: + wResult *= wResult; /* b**4 */ + wResult *= w1; /* b**5 */ + wResult *= wResult; /* b**10 */ + wResult *= w1; /* b**11 */ + break; + case 12: + wResult *= w1; /* b**3 */ + wResult *= wResult; /* b**6 */ + wResult *= wResult; /* b**12 */ + break; + case 13: + wResult *= w1; /* b**3 */ + wResult *= wResult; /* b**6 */ + wResult *= wResult; /* b**12 */ + wResult *= w1; /* b**13 */ + break; + case 14: + wResult *= w1; /* b**3 */ + wResult *= wResult; /* b**6 */ + wResult *= w1; /* b**7 */ + wResult *= wResult; /* b**14 */ + break; + case 15: + wResult *= w1; /* b**3 */ + wResult *= wResult; /* b**6 */ + wResult *= w1; /* b**7 */ + wResult *= wResult; /* b**14 */ + wResult *= w1; /* b**15 */ + break; + case 16: + wResult *= wResult; /* b**4 */ + wResult *= wResult; /* b**8 */ + wResult *= wResult; /* b**16 */ + break; + } + return wResult; +} +/* *---------------------------------------------------------------------- * * ExecuteExtendedBinaryMathOp, ExecuteExtendedUnaryMathOp -- @@ -8143,7 +8228,7 @@ ExecuteExtendedBinaryMathOp( dResult = pow(d1, d2); goto doubleResult; } - w2 = 0; + w1 = w2 = 0; /* to silence compiler warning (maybe-uninitialized) */ if (type2 == TCL_NUMBER_INT) { w2 = *((const Tcl_WideInt *) ptr2); if (w2 == 0) { @@ -8159,28 +8244,21 @@ ExecuteExtendedBinaryMathOp( return NULL; } - } - switch (type2) { - case TCL_NUMBER_INT: - w2 = *((const Tcl_WideInt *)ptr2); negativeExponent = (w2 < 0); oddExponent = (int) (w2 & (Tcl_WideInt)1); - break; - case TCL_NUMBER_BIG: + } else { Tcl_TakeBignumFromObj(NULL, value2Ptr, &big2); negativeExponent = mp_isneg(&big2); mp_mod_2d(&big2, 1, &big2); oddExponent = !mp_iszero(&big2); mp_clear(&big2); - break; } if (type1 == TCL_NUMBER_INT) { w1 = *((const Tcl_WideInt *)ptr1); - } - if (negativeExponent) { - if (type1 == TCL_NUMBER_INT) { + + if (negativeExponent) { switch (w1) { case 0: /* @@ -8201,17 +8279,21 @@ ExecuteExtendedBinaryMathOp( return constants[1]; } } + } + if (negativeExponent) { /* * Integers with magnitude greater than 1 raise to a negative * power yield the answer zero (see TIP 123). */ - return constants[0]; } - if (type1 == TCL_NUMBER_INT) { - switch (w1) { + if (type1 != TCL_NUMBER_INT) { + goto overflowExpon; + } + + switch (w1) { case 0: /* * Zero to a positive power is zero. @@ -8229,7 +8311,6 @@ ExecuteExtendedBinaryMathOp( return constants[1]; } WIDE_RESULT(-1); - } } /* @@ -8247,33 +8328,29 @@ ExecuteExtendedBinaryMathOp( return GENERAL_ARITHMETIC_ERROR; } - if (type1 == TCL_NUMBER_INT) { - if (w1 == 2) { - /* - * Reduce small powers of 2 to shifts. - */ + /* From here (up to overflowExpon) w1 and exponent w2 are wide-int's. */ + assert(type1 == TCL_NUMBER_INT && type2 == TCL_NUMBER_INT); - if ((Tcl_WideUInt) w2 < (Tcl_WideUInt) CHAR_BIT*sizeof(Tcl_WideInt) - 1) { - WIDE_RESULT(((Tcl_WideInt) 1) << (int)w2); - } - goto overflowExpon; + if (w1 == 2) { + /* + * Reduce small powers of 2 to shifts. + */ + + if ((Tcl_WideUInt) w2 < (Tcl_WideUInt) CHAR_BIT*sizeof(Tcl_WideInt) - 1) { + WIDE_RESULT(((Tcl_WideInt) 1) << (int)w2); } - if (w1 == -2) { - int signum = oddExponent ? -1 : 1; + goto overflowExpon; + } + if (w1 == -2) { + int signum = oddExponent ? -1 : 1; - /* - * Reduce small powers of 2 to shifts. - */ + /* + * Reduce small powers of 2 to shifts. + */ - if ((Tcl_WideUInt)w2 < CHAR_BIT*sizeof(Tcl_WideInt) - 1){ - WIDE_RESULT(signum * (((Tcl_WideInt) 1) << (int) w2)); - } - goto overflowExpon; + if ((Tcl_WideUInt)w2 < CHAR_BIT*sizeof(Tcl_WideInt) - 1){ + WIDE_RESULT(signum * (((Tcl_WideInt) 1) << (int) w2)); } - } - if (type1 == TCL_NUMBER_INT) { - w1 = *((const Tcl_WideInt *) ptr1); - } else { goto overflowExpon; } if (w2 - 2 < (long)MaxBase64Size @@ -8282,80 +8359,8 @@ ExecuteExtendedBinaryMathOp( /* * Small powers of integers whose result is wide. */ + wResult = WidePwrSmallExpon(w1, w2); - wResult = w1 * w1; /* b**2 */ - switch (w2) { - case 2: - break; - case 3: - wResult *= w1; /* b**3 */ - break; - case 4: - wResult *= wResult; /* b**4 */ - break; - case 5: - wResult *= wResult; /* b**4 */ - wResult *= w1; /* b**5 */ - break; - case 6: - wResult *= w1; /* b**3 */ - wResult *= wResult; /* b**6 */ - break; - case 7: - wResult *= w1; /* b**3 */ - wResult *= wResult; /* b**6 */ - wResult *= w1; /* b**7 */ - break; - case 8: - wResult *= wResult; /* b**4 */ - wResult *= wResult; /* b**8 */ - break; - case 9: - wResult *= wResult; /* b**4 */ - wResult *= wResult; /* b**8 */ - wResult *= w1; /* b**9 */ - break; - case 10: - wResult *= wResult; /* b**4 */ - wResult *= w1; /* b**5 */ - wResult *= wResult; /* b**10 */ - break; - case 11: - wResult *= wResult; /* b**4 */ - wResult *= w1; /* b**5 */ - wResult *= wResult; /* b**10 */ - wResult *= w1; /* b**11 */ - break; - case 12: - wResult *= w1; /* b**3 */ - wResult *= wResult; /* b**6 */ - wResult *= wResult; /* b**12 */ - break; - case 13: - wResult *= w1; /* b**3 */ - wResult *= wResult; /* b**6 */ - wResult *= wResult; /* b**12 */ - wResult *= w1; /* b**13 */ - break; - case 14: - wResult *= w1; /* b**3 */ - wResult *= wResult; /* b**6 */ - wResult *= w1; /* b**7 */ - wResult *= wResult; /* b**14 */ - break; - case 15: - wResult *= w1; /* b**3 */ - wResult *= wResult; /* b**6 */ - wResult *= w1; /* b**7 */ - wResult *= wResult; /* b**14 */ - wResult *= w1; /* b**15 */ - break; - case 16: - wResult *= wResult; /* b**4 */ - wResult *= wResult; /* b**8 */ - wResult *= wResult; /* b**16 */ - break; - } WIDE_RESULT(wResult); } diff --git a/tests/mathop.test b/tests/mathop.test index f122b7b..eff0852 100644 --- a/tests/mathop.test +++ b/tests/mathop.test @@ -1206,6 +1206,8 @@ test mathop-25.5 { exp operator } {TestOp ** 1 5} 1 test mathop-25.6 { exp operator } {TestOp ** 5 1} 5 test mathop-25.7 { exp operator } {TestOp ** 4 3 2 1} 262144 test mathop-25.8 { exp operator } {TestOp ** 5.5 4} 915.0625 +test mathop-25.8a { exp operator } {TestOp ** 4.0 -1} 0.25 +test mathop-25.8b { exp operator } {TestOp ** 2.0 -2} 0.25 test mathop-25.9 { exp operator } {TestOp ** 16 3.5} 16384.0 test mathop-25.10 { exp operator } {TestOp ** 3.5 0} 1.0 test mathop-25.11 { exp operator } {TestOp ** 378 0} 1 @@ -1219,8 +1221,30 @@ test mathop-25.18 { exp operator } {TestOp ** -1 -2} 1 test mathop-25.19 { exp operator } {TestOp ** -1 3} -1 test mathop-25.20 { exp operator } {TestOp ** -1 4} 1 test mathop-25.21 { exp operator } {TestOp ** 2 63} 9223372036854775808 -test mathop-25.22 { exp operator } {TestOp ** 83756485763458746358734658473567847567473 2} 7015148907444467657897585474493757781161998914521537835809623408157343003287605729 -test mathop-25.23 { exp operator errors } { +test mathop-25.22 { exp operator } {TestOp ** 2 256} 115792089237316195423570985008687907853269984665640564039457584007913129639936 +set big 83756485763458746358734658473567847567473 +test mathop-25.23 { exp operator } {TestOp ** $big 2} 7015148907444467657897585474493757781161998914521537835809623408157343003287605729 +test mathop-25.24 { exp operator } {TestOp ** $big 0} 1 +test mathop-25.25 { exp operator } {TestOp ** $big 1} $big +test mathop-25.26 { exp operator } {TestOp ** $big -1} 0 +test mathop-25.27 { exp operator } {TestOp ** $big -2} 0 +test mathop-25.28 { exp operator } {TestOp ** $big -$big} 0 +test mathop-25.29 { exp operator } {expr {[set res [TestOp ** $big -1.0]] > 0 && $res < 1.2e-41}} 1 +test mathop-25.30 { exp operator } {expr {[set res [TestOp ** $big -1e-18]] > 0 && $res < 1}} 1 +test mathop-25.31 { exp operator } {expr {[set res [TestOp ** -$big -1.0]] > -1 && $res < 0}} 1 +test mathop-25.32 { exp operator } {expr {[set res [TestOp ** -$big -2.0]] > 0 && $res < 1}} 1 +test mathop-25.33 { exp operator } {expr {[set res [TestOp ** -$big -3.0]] > -1 && $res < 0}} 1 +test mathop-25.34 { exp operator } {TestOp ** $big -1e-30} 1.0 +test mathop-25.35 { exp operator } {TestOp ** $big -1e+30} 0.0 +test mathop-25.36 { exp operator } {TestOp ** 0 $big} 0 +test mathop-25.37 { exp operator } {TestOp ** 1 $big} 1 +test mathop-25.38 { exp operator (small exponent power helper and its boundaries) } { + set pwr 0 + set res 1 + while {[incr pwr] <= 17 && [set i [TestOp ** 15 $pwr]] == [set res [expr {$res * 15}]]} {} + list [incr pwr -1] $res +} {17 98526125335693359375} +test mathop-25.37 { exp operator errors } { set res {} set exp {} -- cgit v0.12