[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [bug-grep] length of dec. representation of a number
From: |
Paul Jarc |
Subject: |
Re: [bug-grep] length of dec. representation of a number |
Date: |
Fri, 04 Mar 2005 18:13:34 -0500 |
User-agent: |
Gnus/5.110003 (No Gnus v0.3) Emacs/21.4 (gnu/linux) |
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
- Re: [bug-grep] length of dec. representation of a number,
Paul Jarc <=
- Re: [bug-grep] length of dec. representation of a number, Paul Eggert, 2005/03/05
- [bug-grep] Re: length of dec. representation of a number, Stepan Kasal, 2005/03/07
- Re: [bug-grep] length of dec. representation of a number, Jim Meyering, 2005/03/08
- Re: [bug-grep] length of dec. representation of a number, Paul Jarc, 2005/03/08
- Re: [bug-grep] length of dec. representation of a number, Jim Meyering, 2005/03/08
- Re: [bug-gnulib] Re: [bug-grep] length of dec. representation of a number, Stepan Kasal, 2005/03/09
- Re: [bug-gnulib] Re: [bug-grep] length of dec. representation of a number, Paul Jarc, 2005/03/09
- [bug-grep] Re: length of dec. representation of a number, Paul Eggert, 2005/03/09
- [bug-grep] Re: length of dec. representation of a number, Paul Jarc, 2005/03/10
- Re: [bug-grep] Re: length of dec. representation of a number, Jim Meyering, 2005/03/10