Newbie questions
Richard A. O'Keefe
ok@REDACTED
Mon Mar 27 05:26:06 CEST 2006
Nick Linker <xlcr@REDACTED> wrote:
1. math:log fails with "badarg" for big integers.
math:log/1 was designed to work on floating-point arguments;
I suspect that it's the integer->float conversion that is failing here.
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)?
3. Let me define the following function:
fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).
This is a SPECTACULARLY INEFFICIENT way to compute fibonacci numbers
in *any* programming language.
I have failed to convert this function _without_ put/get to be able to
compute even fib(100) within reasonable period of time (I guess I did it
wrong so that tail recursion was not here).
It's not a tail recursion issue. It is simply that the computation you
have specified does about 2**N function calls for argument N (*regardless*
of language). So when you demand that fib(100) be computed that way,
you are demanding about 1,267,650,600,228,229,401,496,703,205,376
(10**30) function calls. Assuming a machine that could do 10**10
function calls per second, that's 10**20 seconds, or about
three million million years.
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.
More information about the erlang-questions
mailing list