Fibonacci Sequence Algorithm

Question

I am attempting to find the first number in the Fibonacci sequence to contain N digits (N being somewhere in the range of 500 and 2000). I attempt to do this with the following code:

BigInteger num = BigInteger.valueOf(2);
BigInteger num1 = BigInteger.ONE;
BigInteger num2 = BigInteger.ONE;
int record = 0;
BigInteger TEN = BigInteger.valueOf(10);

public BigInteger run()
{
    BigInteger temp = BigInteger.ZERO;
    while(num2.compareTo(TEN.pow(SomeN - 1)) < 0)
    {
        if(num2.compareTo(TEN.pow(record + 1)) >= 0)
        {
            System.out.println(""+record);
            record++;
        }

        temp = num1.add(num2);
        num1 = num2;
        num2 = temp;

        num = num.add(BigInteger.ONE);
    }
    System.out.println(""+num);
    System.out.println(""+num2);
    return num2;
}

The problem is, when I test for 1500 digits, the answer I get is apparently wrong. I do not know what the answer is supposed to be, and I have even checked the answers immediately around it in case my algorithm is off by a power of 10 (i.e. I checked 1499 digits and 1501), but to no avail. Anyone see what is wrong?

This is not homework. This is a problem (problem 25) from projecteuler (projecteuler.net). I am not looking for the solution, but for what is wrong here. I tested my answer by putting it in as a result for the problem. I think it would be highly unlikely that projecteuler as an incorrect result here, especially considering some number of people have answered correctly. — Jonathan
– Jonathan, Commented Dec 15, 2009 at 21:02
Sorry for the homework thing. I can't tell what's wrong with this code, but I can give a working solution using a different approach — Paco
– Paco, Commented Dec 15, 2009 at 21:16
@Paco: +1 for the apology. Not enought of us are willing to admit when we're wrong, nonetheless apologize for it. — Jonathan
– Jonathan, Commented Dec 15, 2009 at 21:36
Offtopic, you can write System.out.println(record) without the cargo-cult quotes. — akuhn
– akuhn, Commented Dec 15, 2009 at 22:17

Peter Recore · Accepted Answer · 2009-12-15 22:21:12Z

1

(deleted way off base hint)

EDIT: EP web site is back up, and the answer I get when using your code matches what the web site accepted as correct for me, way back when.

edited Dec 15, 2009 at 22:21

answered Dec 15, 2009 at 21:02

Peter Recore

14.2k5 gold badges44 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Bozho Over a year ago

it seems to work fine till at least the 500th number in the sequence :)

Jonathan Over a year ago

I double checked (again), and I do get 13 for input N=2, and 144 for N=3.

user85109 · Accepted Answer · 2009-12-16 11:43:04Z

0

Of course, there is no reason to use a biginteger form here at all. log10 will suffice in one line of code. binet there, done that...

answered Dec 16, 2009 at 11:43

user85109

Collectives™ on Stack Overflow

Fibonacci Sequence Algorithm

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related