Newbie questions

Nick Linker xlcr@REDACTED
Mon Mar 27 07:04:34 CEST 2006


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.



More information about the erlang-questions mailing list