Newbie questions

[Raimo Niskanen]

Regarding your problem about determining the number of decimal
digits in a number, I just came to think of a simple enough
brute force O(log(N)) or rather O(NN) where NN is the
number of digits in the number:

    digits(N) when is_integer(N), N >= 0 -> digits(N, 1, 0).

    digits(N, M, D) when M > N -> D;
    digits(N, M, D) -> digits(N, M*10, D+1).

Or did I misunderstand what you ment by O(log(N)),
was N the number of decimal digits in the number?



xlcr@REDACTED (Nick Linker) writes:

> Kostis Sagonas wrote:
> 
> >Nick Linter wrote:
> >
> >An example would have helped us understand better what the issue is.
> >Currently, I get:
> >
> >Eshell V5.5  (abort with ^G)
> >1> math:log(...).
> >480.407
> >
> Well, I get the following result:
> 
>     43> math:log10(test:fib(1476)).
>     308.116
>     44> math:log10(test:fib(1477)).
>        =ERROR REPORT==== 27-Mar-2006::10:57:47 ===
>     Error in process <0.181.0> with exit value:
>     {badarith,[{math,log10,[16#00012D269
>     C3FA9D767CB55B0DDF8E6A2DE7B1D967FF8D0BE61EB16ACD02D1A53C95A370ABD95285998D226919
> 
>     D95DCA54298D92C348C27E635E1690E7858060F0DC14E885F0217413C55A1F820D6EB051F87C7C73
> 
>     818AC23E4A9A00A2072C08C6697A2FAD66FC7DEBEEB7A5F582D7639A431B9C99CEC6315A9ED1C652
> 
>     A81A6B59A39]},{erl_eval,do_apply,5},{shell,exprs,6},{shell,eval_loop,3}]}
> 
>        ** exited: {badarith,[{math,log10,
>                                  [211475298697902185255785861961179135570552502746803
>     25217495622655863402432394766663713782393252439761186467156621190833026337742520
> 
>     45520741882086869936691237540043402509431087092122991804222930097654049305082429
> 
>     75773774612140021599477983006713536106549441161323499077298115887067363710153036
> 
>     315849480388057657]},
>                           {erl_eval,do_apply,5},
>                           {shell,exprs,6},
>                           {shell,eval_loop,3}]} **
> 
> My system is Windows XP, Erlang R10B.
> 
> >fib(N) ->
> >  trunc((1/sqrt(5)) * (pow(((1+sqrt(5))/2),N) - pow(((1-sqrt(5))/2),N))).
> >
> Good solution :-)
> Now I also have different idea without using recursion. It is based on
> the following equation
> [F_n  ]   [1  1]   [F_n-1]
> [     ] = [    ] * [     ]
> [F_n-1]   [1  0]   [F_n-2]
> And we just have to calculate k-th power of the matrix
> [[1,1],[1,0]]. It is possible to do within O(log(k)).
> 
> >PS. The performance you are experiencing in your version of fib/1
> >    has nothing to do with tail recursion...
> >
> Yes, exponential number of recursive calls... Thank you.
> 
> I'm sorry, but most interesting question (2nd, about number of digits
> in an integer) remains unanswered. But I guess it is very rare problem
> with numbers, so if there is no answer, I will understand.
> 
> Best regards,
> Linker Nick.

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB