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
> 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.
More information about the erlang-questions