# Newbie questions

Richard A. O'Keefe ok@REDACTED
Mon Mar 27 05:26:06 CEST 2006

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,
(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.