Newbie questions
Raimo Niskanen
<>
Thu Mar 30 15:01:38 CEST 2006
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?
(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
More information about the erlang-questions
mailing list