From 41bd4e38da467b22655ca4b81fda22bd3afd6f95 Mon Sep 17 00:00:00 2001
From: Kaz Kylheku <kaz@kylheku.com>
Date: Fri, 5 Apr 2019 20:04:40 -0700
Subject: mpi: use integer math for radix length.

* mpi/logtab.h: Regenerated.
(s_logv_2): Now table of scaled integers.
(MP_LOG_SCALE): New constant.

* mpi/make-logtab.txr (scale, type): New variables.
Generate integer table with log2 values scaled by the scale
factor, rounded up.

* mpi/config.h (MP_LOGTAB): Removed. We always use the table.

* mpi/mpi.c: Unconditionally include logtab.h.
(LOG_V_2): Macro removed.
(s_mp_outlen): Rewritten using scaled integer math.
Overflow is avoided by splitting the input into a part that is
an exact multiple of the scale factor, and a remaining
part. Only the remaining part need be multiplied by a value
from the table before dividing by the scale factor.
---
 mpi/make-logtab.txr | 27 +++++++++++++--------------
 1 file changed, 13 insertions(+), 14 deletions(-)

(limited to 'mpi/make-logtab.txr')

diff --git a/mpi/make-logtab.txr b/mpi/make-logtab.txr
index 5566dd66..90e36f38 100644
--- a/mpi/make-logtab.txr
+++ b/mpi/make-logtab.txr
@@ -1,22 +1,21 @@
-@(bind logs @(tuples 4 ^(0.0 0.0 ,*(take 63 (mapcar* [chain log2 /] (range 2))))))
-@(do (set *pprint-flo-format* "~0,9f"))
+@(bind scale 16384)
+@(bind type "unsigned int")
+@(bind logs @(tuples 4 ^(0.0 0.0
+                         ,*(take 63
+                                 (mapcar* [chain log2 / (op * scale) ceil toint]
+                                          (range 2))))))
 @(output)
 /*
- * A table of the logs of 2 for various bases (the 0 and 1 entries of
- * this table are meaningless and should not be referenced).
+ * A table of the logs of 2 for various bases scaled by a factor
+ * and converted to integer.
  *
- * This table is used to compute output lengths for the mp_toradix()
- * function.  Since a number n in radix r takes up about log_r(n)
- * digits, we estimate the output size by taking the least integer
- * greater than log_r(n), where:
- *
- * log_r(n) = log_2(n) * log_r(2)
- *
- * This table, therefore, is a table of log_r(2) for 2 <= r <= 36,
- * which are the output bases supported.
+ * This table is used to compute output lengths for the mp_toradix
+ * function.
  */
 
-const double s_logv_2[] = {
+#define MP_LOG_SCALE @scale
+
+const @type s_logv_2[] = {
 @  (repeat)
   @(rep)@logs, @(last)@logs,@(end)
 @  (last)
-- 
cgit v1.2.3