Re: [bug-grep] length of dec. representation of a number

[Paul Jarc]

Paul Eggert <address@hidden> wrote:
> /* Upper bound on the string length of an integer converted to string.
>    302 / 1000 is ceil (log10 (2.0)).  Subtract 1 for the sign bit;
>    add 1 for integer division truncation; add 1 more for a minus sign.  */
> #define INT_STRLEN_BOUND(t) ((sizeof (t) * CHAR_BIT - 1) * 302 / 1000 + 2)

Just for fun, I calculated an optimal fraction.  146/485 is the
smallest overestimate of log10(2) that can be used to calculate
(without overflowing a 16-bit signed int) the number of bytes needed
to print a 128-bit number.  Also, this handles the integer division by
(numerator+denominator-1)/denominator, so it only rounds up instead of
always adding 1.  (That's just my aesthetic preference; it won't make
a difference unless the number of bits in a type is divisible by 5 or
97.)

#define UINT_STRLEN_BOUND(t) ((sizeof (t) * CHAR_BIT * 146 + 484) / 485)
#define SINT_STRLEN_BOUND(t) (((sizeof (t) * CHAR_BIT - 1) * 146 + 484) / 485 + 
1)
Or more compact, but less comprehensible:
#define SINT_STRLEN_BOUND(t) ((sizeof (t) * CHAR_BIT * 146 + 823) / 485)

Here's the Python code I used to find the optimal fraction.  Beware,
performance is O(2**intbits), so intbits=15 is ok, but 31 takes a
while.  But since larger terms don't give monotonically better
approximations, I don't know offhand if a better algorithm is
possible.

import sys, math
maxbits=int(sys.argv[1]) # 128, to be extreme
intbits=int(sys.argv[2]) # 15, to be conservative
l=math.log10(2)
a=1
besta=1
bestb=0
while 1:
  b=int(math.floor(a/l)) # guarantees a/b >= l (that's not integer division)
  if maxbits*a+b-1 >= (1<<intbits): break # overflow
  if a*bestb < besta*b: (besta, bestb)=(a, b)
  a=a+1
print '%d/%d'%(besta, bestb)


paul