Question: van Vliet: proc log10 and op EXPLENGTH

[Jose E. Marchesi]

> 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.

Probably not worthwile, no :)
You may beable to exploit sppp to avoid writing all the conditionals though.

> 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.