5 * Work out length of a number's string representation
7 * (c) 2002 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
30 /*----- Header files ------------------------------------------------------*/
35 /*----- Main code ---------------------------------------------------------*/
37 /* --- @mptext_len@ --- *
39 * Arguments: @mp *x@ = number to work on
40 * @int r@ = radix the number will be expressed in
42 * Returns: The number of digits needed to represent the number in the
43 * given base. This will not include space for a leading sign
44 * (use @MP_NEGP@ to check that, or just add one on for luck);
45 * neither will it add space for a terminating null. In general
46 * the answer will be an overestimate.
49 size_t mptext_len(mp
*x
, int r
)
51 unsigned long b
= mp_bits(x
);
58 * The number of digits is at most %$\lceil b \log 2/\log r \rceil$%. We
59 * produce an underestimate of %$\log_2 r = \log r/\log 2$% and divide by
60 * that. How? By linear interpolation between known points on the curve.
61 * The known points are precisely the powers of 2, so we can find a pair
62 * efficiently by doubling up. The log curve is convex, so linear
63 * interpolation between points on the curve is always an underestimate.
65 * The integer maths here is a bit weird, so here's how it works. If
66 * %$s = 2^d$% is the power of 2 below %$r$% then we want to compute
67 * %$\lceil b/(d + (r - s)/s) \rceil = \lceil (b s)/(s(d - 1) + r \rceil$%
68 * which is %$\lfloor (r + s (b + d - 1) - 1)/(r + s(d - 1)) \rfloor$%.
69 * Gluing the whole computation together like this makes the code hard to
70 * read, but means that there are fewer possibilities for rounding errors
71 * and thus we get a tighter bound.
74 /* --- Find the right pair of points --- */
87 /* --- Do the interpolation --- */
89 n
= (r
+ s
*(b
+ d
- 1) - 1)/(r
+ s
*(d
- 1));
99 /*----- That's all, folks -------------------------------------------------*/