Newbie questions

[Richard A. O'Keefe]

Nick Linker <xlcr@REDACTED> wrote:
	I'm sorry, but I meant quite different question:  given a big
	number N, how to compute the number of digits?
	
	There is obvious solution:  length(integer_to_list(N)), but it
	is not very efficient.  I wanted to have a bit faster
	solution... Ok, nevermind.
	
I'm aware of (and have used) several programming languages providing
as-long-as-necessary integer arithmetic.  Without consulting manuals
(everything is being moved out of my office so that new carpet can
be laid) it's hard to be sure, but from memory, NONE of them provides
an operation "how many decimal digits in this bignum".  Common Lisp
has HAULONG, which tells you about how many BITS, and Java's
BigInteger class offers bitLength(), which again tells you how many
BITS.  In Smalltalk, the obvious thing to do would be n printString size,
and in Scheme it would be (string-length (number->string n)).

It's not completely clear what you want.  Is the "number of digits"
in -123456890123456890 twenty (literally the number of digits) or
twenty-one (the number of characters in the minimal decimal representation)?

I must say that the Erlang reference material could be better organised.
Trying to answer the question "what are all the predefined operations on
numbers" is surprisingly hard.

One of the great things about Erlang is that it is open source.
emulator/big.c defines a function big_decimal_estimate() which gives an
*estimate* of the number of decimal digits; that may be close enough for
your needs.  If it's not close enough, big_to_decimal() does the character
conversion into a char* buffer, and doesn't build a list.
Using emulator/bif.c:integer_to_list as a model, it would be quite easy
to write a new BIF that gave you the number of decimal digits in a
number.

The question remains, WHY?  For what kind of problem is it useful to know
the number of decimal digits but NOT what the digits actually are?

And would avoiding the list construction actually buy you very much?
It must be O(#Digits) work to build the list, but finding out what the
digits are is O(#Digits**2).

I benchmarked the following code against length(integer_to_list(N)),
for the first however many factorials.  The two seemed to be about the
same speed.  Your mileage will of course vary.

integer_digits(N) when integer(N) ->
    if N >= 0 -> natural_digits_loop(N, 0)
     ; N <  0 -> natural_digits_loop(-N, 1)
    end.

natural_digits(N) when integer(N), N >= 0 ->
    natural_digits_loop(N, 0).

natural_digits_loop(N, D) when N >= 10000 ->
    natural_digits_loop(N div 10000, D + 4);
natural_digits_loop(N, D) when N >= 1000 ->
    D + 4;
natural_digits_loop(N, D) when N >= 100 ->
    D + 3;
natural_digits_loop(N, D) when N >= 10 ->
    D + 2;
natural_digits_loop(_, D) ->
    D + 1.