How to calculate the lucas number?

Question

Lucas numbers are numbers in a sequence defined like this:

L(n) = 2 if n = 0

L(n) = 1 if n = 1

otherwise

L(n) = L(n - 1) + L(n - 2)

Here is my code:

public class Lucas {
    public static int lucasnum(int n) {
        if (n >= 0) {
            if (n == 0)
                return 2;
            else if (n == 1)
                return 1;
            else
                return lucasnum(n - 1) + lucasnum(n - 2);
        }
        else{
            if (n == 0)
                return -2;
            else if (n == -1)
                return -1;
            else
                return lucasnum(n + 1) - lucasnum(n + 2);
        }
    }

    public static void main(String[] args) {
        System.out.println(Lucas.lucasnum(-5));
    }
}

But I have some problem with negative number. If n == -5 it must return -11 but my code above return 3.

Rohcana · Accepted Answer · 2015-08-03T17:41:54.067

3

I think You got the formula for negative indexes backward.

Since,

L(n+2)=L(n+1)+L(n)

=> L(n)=L(n+2)-L(n+1)

So, change

return lucasnum(n + 1) - lucasnum(n + 2);

to

return lucasnum(n + 2) - lucasnum(n + 1);

Faster Algorithms

Your Algorithm is an O(n) algorithm, which is slow for large n. You can do it faster.

O(1). Use Binet's Formula for Lucas Numbers, However, This doesn't give exact results for large values of n due to fixed precision floating point arithmetic.
O(log n) using recursion:

Let f(n) be the Fibonacci sequence
```
f(0) = 0, f(1) = 1,
f(n) = f(n-1) + f(n-2)
```
Calculate Fibonacci numbers in O(log n) time with the recursion:
```
f(2n-1) = f(n)^2 + f(n-1)^2
  f(2n) = f(n)^2 + 2*f(n-1)*f(n)
```
Then Calculate Lucas numbers with:
```
 L(n) = f(n-1) + f(n+1)
```
You can find the formulas here:

edited Aug 03 '15 at 17:41

answered Aug 03 '15 at 17:07

Rohcana

359
4
13

Okey, tks! Similar to @pbabcdefp – Twitter khuong291 Aug 03 '15 at 17:11
I know, He beat me by seconds. :( – Rohcana Aug 03 '15 at 17:12
Is there any way faster with the sort completed time? – Twitter khuong291 Aug 03 '15 at 17:14
@Anachor: how is Binet's formula O(1)? You still have to exponentiate phi. – Edward Doolittle Aug 03 '15 at 18:32
@Edward Note that this is not integer exponentiation, since phi is irrational. For floating point exponentiation, complexity depends on implementation. I generally use C++ and [its library pow() is O(1)](http://stackoverflow.com/questions/13418180/time-complexity-of-c-math-library-pow-function) – Rohcana Aug 03 '15 at 19:01
Hmm, I guess, but calculations of asymptotic time complexity will also depend on the model of computation, some of which are more realistic than others. Also, if you want a correct integer answer, the number of digits of accuracy of `pow` will have to grow as `n` grows, which will (for large n) increase the time required. – Edward Doolittle Aug 04 '15 at 20:31
I did mention that Binet's formula is unreliable for an accurate result for large enough values for n. So, if you want an accurate integer result for large n, it is preferable to use the matrix exponentiation or recursion method. – Rohcana Aug 05 '15 at 05:15

score 2 · Answer 2 · answered Aug 03 '15 at 17:07

2

Change

return lucasnum(n + 1) - lucasnum(n + 2);

to

return lucasnum(n + 2) - lucasnum(n + 1);

answered Aug 03 '15 at 17:07

Paul Boddington

37,127
10
65
116

Tks! Solved. Btw, is there any way faster? – Twitter khuong291 Aug 03 '15 at 17:09
1

@khuong291 Matrix exponentiation (the writeups are for Fibonacci but can be adapted easily). – David Eisenstat Aug 03 '15 at 17:18
1

@khuong291 The usual way to speed this up is to put results in an array or map, so that the same answers are not computed repeatedly. Search for questions on memoization. – Paul Boddington Aug 03 '15 at 17:20

How to calculate the lucas number?

2 Answers2