Newbie questions

[Richard A. O'Keefe]

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.