Suggestion For mpz_sizeinbase() Function

[David T. Ashley]

Hi,

I do not know how quick floating-point instructions are on most machines, or
if they typically have hardware support.  I know that the 80x87 (the
floating-point chip) exists, but I don't know how fast this is.  Most of my
experience is with microcontrollers, which do not have hardware support for
floating point (and of course doing it in software is somewhat expensive).

With this in mind, looking at the mpz_sizeinbase() function, it seems that
floating point arithmetic isn't necessary.

I'm assuming that the entries in the table __mp_bases[] are of the form:
   ln(2)/ln(base)

With this in mind, one can just find a good rational approximation and skip
the floating point arithmetic.  For example, my HP calculator tells me that
ln(2)/ln(10) is about:

0.301029995665

This differs slightly from the value in the table but I'll use it for the
purposes of example.

The two best rational approximations to this with numerator an denominator
not exceeding 65535 are:

8651/28738

and

12655/42039

Picking the larger one to use as a rational approximation leads to:

chars_required = (12655 * bits_required)/42039 + 1

Most machines will do this blindingly fast:  one integer multiply as a
processor instruction followed by one integer divide as a processor
instruction.

The other issue to cover is in general if this method is used, whether the
claim that the value returned will be exact or one greater will be met.
This has to do with spacing of terms in the Farey series, but in general a
number would need to be tens of thousands of bits long before the result can
be two over rather than one over.  Most users won't complain if they waste
one byte out of tens of thousands--but the important point is that the value
returned must never be less than what is required.

The details of how to go from 0.301029995665 to 12655/42039 are contained in
chapters 4 and 5 of a book I'm working on.  You can download this from:

http://sourceforge.net/project/showfiles.php?group_id=28508

(just get the book .PDF).

So, what does everyone think of using rational approximations instead of
floating-point arithmetic?  Do most machines provide floating point support,
and is there any speed or code savings here?

Pls. let me know your thoughts.

Thanks, Dave.