Question: van Vliet: proc log10 and op EXPLENGTH

[chris hermansen]

Thanks for the reply, Jose.

On Sat, Mar 14, 2026 at 4:36 AM Jose E. Marchesi <jemarch@gnu.org> wrote:

>
> Hi Chris.
>
> > Hello again;
> >
> > van Vliet defines the procedure log10 as:
> >
> > proc {ℵ₀} log10 = (Number v) int:
> >   int(pseudo46) { A number P such that, given a value V, P = 0 if |V| <
> 1.0,
> >     and, if |V| >= 1.0, then P is such that
> >
> >         ENTIER(log[10](|V|)) + 1 <= P <= ENTIER(log[10](|V|)) + 2.
> >
> >     Thus, P is an estimate of the number of digits in the integral part
> >     of V; this estimate may be at most 1 too large. This definition
> >     should allow efficient computation of P; e.g., using the normal
> >     floating point_representation of V with a mantissa M and base 2
> >     exponent E (E = ENTIER(log[2]|V| )), P may be given the value
> >     (ENTIER(log[10]2 * (E+1))+1) MAX 0. Obviously also, 'log10' is a
> >     typical candidate for inline expansion. };
> >
> > and the operator EXPLENGTH as:
> >
> > prio {ℵ₀} EXPLENGTH = 9;
> > op EXPLENGTH = (bool sign, int exp) int:
> >   int(pseudo47) { The smallest E such that 'whole(exp, ABS sign * E)'
> > succeeds.
> >     This operator is used to estimate the length needed to convert the
> >     exponent in 'float'. This is probably easier and faster than actually
> >     converting the exponent and subsequently testing its width, since on
> >     most implementations the exponent will be a relatively small integer
> >     (<= 322, say). };
> >
> > For the time being, I propose that for these types of calculations - "the
> > number of digits needed by the integral value X" - we simply use a set of
> > if - then - else - fi.
> >
> > So we could proceed along the lines of:
> >
> > proc {ℵ₀} num_digits = (union (
> >   {iter L {short short} {short} {} {long} {long long}}
> >   {L} int
> >   {reti {,}}
> >   ) i) int:
> > begin
> >   long long int test =
> >     case ABS i in
> >     {iter L {short short} {short} {} {long} {long long}}
> >     {iter K {LENG LENG LENG LENG} {LENG LENG LENG} {LENG LENG} {LENG} {}}
> >     ({L} int ii}: {K} ii
> >     {reti {,}}
> >     esac;
> >   if test < long long 10
> >   then 1
> >   elif test < long long 100
> >   then 2
> >   elif test < long long 1000
> >   ...
> >   elif test < long long 1000000000000000000
> >   then 18
> >   else 19
> >   fi
> > end;
> >
> > Clearly this might not be the most efficient.  However, given its use is
> > for formatting, it's probably not too bad as a first cut, and it does
> have
> > the advantage of not requiring logarithms nor ENTIER.
> >
> > Any thoughts?
> > ...
>
> Seems sensible to me.
> This approach is fast if you binary search.
>

I thought about a binary search; do you think it worthwhile?  Obviously, if
the numbers passed to num_digits() are uniformly distributed throughout
[0,long_long_max_int] then binary search is the way to go; but I wonder if
most numbers sent to it are clumped closer to zero.

Also I have this idea (unsupported by fact) that there are some kinds of
instructions in the x86 instruction set that make this sort of linear table
lookup very fast.


-- 
Chris Hermansen · clhermansen "at" gmail "dot" com

C'est ma façon de parler.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/algol68/attachments/20260314/0c34f855/attachment-0001.htm>