CODEWITHSUNDEEP
javaalgorithmfor-looprecursion
Francisco Ochoa
Francisco Ochoa

Reputation: 1

I need to print the 215th Lucas Numbers using an efficient algorithm. Using recursion takes way too long.

The purpose of this class is to calculate the nth number of the Lucas Sequence. I am using data type long because the problems wants me to print the 215th number. The result of the 215th number in the Lucas Sequence is: 855741617674166096212819925691459689505708239. The problem I am getting is that at some points, the result is negative. I do not understand why I am getting a negative number when the calculation is always adding positive numbers. I also have two methods, since the question was to create an efficient algorithm. One of the methods uses recursion but the efficiency is O(2^n) and that is of no use to me when trying to get the 215th number. The other method is using a for loop, which the efficiency is significantly better. If someone can please help me find where the error is, I am not sure if it has anything to do with the data type or if it is something else.

Note: When trying to get the 91st number I get a negative number and when trying to get the 215th number I also get a negative number. 

import java.util.Scanner;

public class Problem_3 
{
    static long lucasNum;
    static long firstBefore;
    static long secondBefore;

    static void findLucasNumber(long n)
    {

        if(n == 0)
        {
            lucasNum = 2;
        }
        if(n == 1)
        {
            lucasNum = 1;
        }
        if(n > 1)
        {
            firstBefore = 1;
            secondBefore = 2;

            for(int i = 1; i < n; i++)
            {
                lucasNum = firstBefore + secondBefore;
                secondBefore  = firstBefore;
                firstBefore = lucasNum;
            }
        }
    }

    static long recursiveLucasNumber(int n)
    {
        if(n == 0)
        {
             return 2;
        }
        if(n == 1)
        {
            return 1;
        }

      return recursiveLucasNumber(n - 1) + recursiveLucasNumber(n - 2);
    }

    public static void main(String[] args)
    {
        System.out.println("Which number would you like to know from "
            + "the Lucas Sequence?");
        Scanner scan = new Scanner(System.in);
        long num = scan.nextInt();

        findLucasNumber(num);

        System.out.println(lucasNum);

        //System.out.println(recursiveLucasNumber(num));
    }
}

Upvotes: 0

Views: 657

Answers (3)

lwi
lwi

Reputation: 1712

I wasn't aware of the lucas numbers before this thread, but from wikipedia it looks like they are related to the fibonacci sequence with (n = nth number, F = fibonacci, L = lucas):

Ln = F_(n-1) + F_(n+1)

Thus, if your algorithm is too slow, you could use the closed form fibonacci and than compute the lucas number from it, alternative you could also use the closed form given in the wikipedia article directly (see https://en.wikipedia.org/wiki/Lucas_number).

Example code:

public static void main(String[] args) {

    long n = 4;

    double fibo = computeFibo(n);
    double fiboAfter = computeFibo(n + 1);
    double fiboBefore = computeFibo(n - 1);

    System.out.println("fibonacci n:" + Math.round(fibo));
    System.out.println("fibonacci: n+1:" + Math.round(fiboAfter));
    System.out.println("fibonacci: n-1:" + Math.round(fiboBefore));
    System.out.println("lucas:" + (Math.round(fiboAfter) + Math.round(fiboBefore)));

}

private static double computeFibo(long n) {
    double phi = (1 + Math.sqrt(5)) / 2.0;
    double psi = -1.0 / phi;
    return (Math.pow(phi, n) - Math.pow(psi, n)) / Math.sqrt(5);
}

To work around the long size limit you could use java BigDecimal (https://docs.oracle.com/javase/7/docs/api/java/math/BigDecimal.html). This is needed earlier in this approach as the powers in the formula will grow very quickly.

Upvotes: 0

MBo
MBo

Reputation: 80197

Java data type long can contain only 64-bit numbers in range -9223372036854775808 .. 9223372036854775807. Negative numbers arise due to overflow.

Seems you need BigInteger class for arbitrary-precision integer numbers

Upvotes: 1

Stephen C
Stephen C

Reputation: 718996

Two observations:

  1. The answer you are expecting (855741617674166096212819925691459689505708239) is way larger than you can represent using a long. So (obviously) if you attempt to calculate it using long arithmetic you are going to get integer overflow ... and a garbage answer.

    Note: this observation applies for any algorithm in which you use a Java integer primitive value to represent the Lucas numbers. You would run into the same errors with recursion ... eventually.

    Solution: use BigInteger.

  2. You have implemented iterative and pure recursion approaches. There is a third approach: recursion with memoization. If you apply memorization correctly to the recursive solution, you can calculate LN in O(N) arithmetical operations.

Upvotes: 2

Related Questions