Instead of O(n) in the value of the exponent, we can compute exponents
in O(log n), with exponentiation by squaring. With this patch, "time
echo 'eval(3**2000000000)' | m4" drops from 2 seconds to under 10
milliseconds.
* src/eval.c (parse_expr): Use exponentiation by squaring.
* doc/m4.texi (Eval): Test it.
---
doc/m4.texi | 16 ++++++++++++++++
src/eval.c | 17 +++++++++++++----
2 files changed, 29 insertions(+), 4 deletions(-)
diff --git a/doc/m4.texi b/doc/m4.texi
index 81476bc8..612ed945 100644
--- a/doc/m4.texi
+++ b/doc/m4.texi
@@ -7235,6 +7235,22 @@ Eval
@result{}
@end example
+@ignore
+@comment This test makes sure the algorithm is fast, but does not
+@comment need to be displayed as-is in the manual.
+
+@example
+eval(`3**2000000000')
+@result{}632360961
+define(`loop', `ifelse(`$1', `1000', `pass',
+`loop(eval($1+!!(3**2000000000)))')')loop(0)
+@result{}pass
+define(`check', `ifelse(`$1', `100', `pass', `$2', eval(-3**$1),
+`check(incr($1), eval(-3*$2))', `oops')')check(0, 1)
+@result{}pass
+@end example
+@end ignore
+
Within @var{expression}, (but not @var{radix} or @var{width}), numbers
without a special prefix are decimal. A simple @samp{0} prefix
introduces an octal number. @samp{0x} introduces a hexadecimal number.
diff --git a/src/eval.c b/src/eval.c
index 163e2634..69cd5e41 100644
--- a/src/eval.c
+++ b/src/eval.c
@@ -389,6 +389,8 @@ parse_expr (int32_t *v1, eval_error er, unsigned min_prec)
int32_t v2;
int32_t v3;
uint32_t u1;
+ uint32_t u2;
+ uint32_t u3;
if (er >= SYNTAX_ERROR)
return er;
@@ -429,17 +431,24 @@ parse_expr (int32_t *v1, eval_error er, unsigned min_prec)
that the implementation-defined overflow when casting
unsigned to signed is a silent twos-complement
wrap-around. */
- u1 = 1;
if (v2 < 0)
er = NEGATIVE_EXPONENT;
else if (*v1 == 0 && v2 == 0)
er = DIVIDE_ZERO;
else
{
- while (v2-- > 0)
- u1 *= (uint32_t) *v1;
+ u1 = *v1;
+ u2 = v2;
+ u3 = 1;
+ while (u2)
+ {
+ if (u2 & 1)
+ u3 *= u1;
+ u1 *= u1;
+ u2 >>= 1;
+ }
}
- *v1 = u1;
+ *v1 = u3;
break;
case TIMES:
--
2.49.0
_______________________________________________
M4-patches mailing list
M4-patches@gnu.org
https://lists.gnu.org/mailman/listinfo/m4-patches
