Rearrange the file tree.

[u/mdw/catacomb] / mptext-len.c

diff --git a/mptext-len.c b/mptext-len.c
deleted file mode 100644 (file)
index e8142fb..0000000
--- a/mptext-len.c
+++ /dev/null
@@ -1,99 +0,0 @@
-/* -*-c-*-
- *
- * $Id$
- *
- * Work out length of a number's string representation
- *
- * (c) 2002 Straylight/Edgeware
- */
-
-/*----- Licensing notice --------------------------------------------------*
- *
- * This file is part of Catacomb.
- *
- * Catacomb is free software; you can redistribute it and/or modify
- * it under the terms of the GNU Library General Public License as
- * published by the Free Software Foundation; either version 2 of the
- * License, or (at your option) any later version.
- *
- * Catacomb is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU Library General Public License for more details.
- *
- * You should have received a copy of the GNU Library General Public
- * License along with Catacomb; if not, write to the Free
- * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
- * MA 02111-1307, USA.
- */
-
-/*----- Header files ------------------------------------------------------*/
-
-#include "mp.h"
-#include "mptext.h"
-
-/*----- Main code ---------------------------------------------------------*/
-
-/* --- @mptext_len@ --- *
- *
- * Arguments:  @mp *x@ = number to work on
- *             @int r@ = radix the number will be expressed in
- *
- * Returns:    The number of digits needed to represent the number in the
- *             given base.  This will not include space for a leading sign
- *             (use @MP_NEGP@ to check that, or just add one on for luck);
- *             neither will it add space for a terminating null.  In general
- *             the answer will be an overestimate.
- */
-
-size_t mptext_len(mp *x, int r)
-{
-  unsigned long b = mp_bits(x);
-  int s, ss = 2;
-  size_t n;
-  unsigned d = 0;
-
-  /* --- Huh? --- *
-   *
-   * The number of digits is at most %$\lceil b \log 2/\log r \rceil$%.  We
-   * produce an underestimate of %$\log_2 r = \log r/\log 2$% and divide by
-   * that.  How?  By linear interpolation between known points on the curve.
-   * The known points are precisely the powers of 2, so we can find a pair
-   * efficiently by doubling up.  The log curve is convex, so linear
-   * interpolation between points on the curve is always an underestimate.
-   *
-   * The integer maths here is a bit weird, so here's how it works.  If
-   * %$s = 2^d$% is the power of 2 below %$r$% then we want to compute
-   * %$\lceil b/(d + (r - s)/s) \rceil = \lceil (b s)/(s(d - 1) + r \rceil$%
-   * which is %$\lfloor (r + s (b + d - 1) - 1)/(r + s(d - 1)) \rfloor$%.
-   * Gluing the whole computation together like this makes the code hard to
-   * read, but means that there are fewer possibilities for rounding errors
-   * and thus we get a tighter bound.
-   */
-
-  /* --- Find the right pair of points --- */
-
-  if (r < 0) r = -r;
-  do {
-    s = ss;
-    d++;
-    if (r == s) {
-      n = (b + (d - 1))/d;
-      goto done;
-    }
-    ss = s << 1;
-  } while (ss <= r);
-
-  /* --- Do the interpolation --- */
-
-  n = (r + s*(b + d - 1) - 1)/(r + s*(d - 1));
-
-  /* --- Fixups --- */
-
-done:
-  if (!n)
-    n = 1;
-  return (n);
-}
-
-/*----- That's all, folks -------------------------------------------------*/