Newbie questions

[Nick Linker]

Richard A. O'Keefe wrote:

>	2. It is impossible to know how many digits in an integer _efficiently_ 
>	(i.e. with O(1) or O(log(n)), where n - number of digits). 
>	length(number_to_list(N)) appears to have O(n).
>
>Anything else you can do with a number has to be at least O(n),
>so *in the context of a real use* of bignum arithmetic, why does
>measuring the size have to be O(lg n) rather than O(n)?
>  
>
I did exactly this: N is a number, n - is the number of digits = 
log(N).  I have a big number N with n digits, and I am searching a way 
of computing n without enumerating all the digits.

>This is a SPECTACULARLY INEFFICIENT way to compute fibonacci numbers
>in *any* programming language.
>  
>

>	Is there a way to compute fib(N), N>=100 without side effects?
>	
>Yes, and it's easy.  In fact, there are two ways.  The simple obvious
>tail recursion does O(N) integer additions.  The less obvious way treats
>it as a matrix exponentiation problem and does O(lg N) 2x2 integer
>matrix multiplies.
>
>    fib(0) -> 1;
>    fib(N) when N > 0 -> fib(N, 1, 1).
>
>    fib(1, X, _) -> X;
>    fib(N, X, Y) -> fib(N-1, X+Y, X).
>
>This and the matrix exponentiation version generalise in fairly obvious
>ways to recurrences of any order.
>
Unfortunately right after asking the question to the mailing list I got 
the same idea. (Unfortunately = because it is too late to get the 
question back). But thank you for the comprehensive explanation of my 
problem with recursion.

Best regards,
Linker Nick.