`int`is a 32-bit number, which can store values between -2^32 and 2^32 - 1, so you won't be able to store numbers larger than 2^32 - 1 = 4,294,967,295 in an

`int`.

You could use a

`long`which has 64 bits, but the Fibonacci sequence grows so fast that you'll quickly run out of the range of the

`long`type too.

To store integer numbers with an arbitrary number of digits, you can use class BigInteger.

Shamsudeen Akanbi wrote:Hi ranchers, i'm having fibonacci numbers in an array of type int[]. The numbers are up to 4million. Since I generated it with a loop, i have no idea of what the 3999998 element will be. On invoking println, i knew the answer was wrong because it printed a negative number. But i'm very sure it works for like the 1st 1000 elements or very much more. Thanks in advance!

This sounds like one of those Euler Project problems.

A nice property to remember about the Fibonacci series is that F(n)/F(n-1) approaches the Golden Ratio: (√5+1)/2 ≈ 1.618...

Therefore, results are going to progress in powers of 1.618, which is

*larger*than √2 (1.414...), and that means that they are going to

*more*than double for every other result. So, in order to get F(3999998) you need a number that holds at least 2 million bits (and probably a lot more).

Luckily, there is a class that can hold such values easily: BigInteger.

What may not be so easy is waiting for the result of F(3999998)...but good luck in your quest.

Winston

[Edit] Actually, the "therefore" above may be wrong; but the rest of what I said

*is*correct.

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Stevens Miller wrote:Nice analysis, Winston! I love to see people apply mathematics to computation. Not enough of that in our field, imho.

Cheers mate...although in my case it's more 'geek' than Maths (only got to A-level). I still like it though (when I can follow it ).

And I think your use of "therefore" is okay, fwiw...

And

*that's*where my Maths fails. I believe (but I may be wrong here) that Fibonacci produces 'progressive closest integral fractions to G' and, if that's right, then the rest would be right by inference; but if not, I think it would be a lot more difficult to prove the "therefore" bit.

But I'd love to know if I'm wrong...and therefore right.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Winston Gutkowski wrote:I believe (but I may be wrong here) that Fibonacci produces 'progressive closest integral fractions to G'...

Actually, I think I may have worked it out for myself: If F(n) == F(n-1) + F(n-2), then it doesn't matter if progressive results of F(n)/F(n-1) produce the clos

__est__fraction to G or not; simply that they produce a

*closer*one - and

*that*I'm pretty certain they do.

Mathematicians, please put me out of my ignorance. My tools are teenage Maths and logic.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

"Il y a peu de choses qui me soient impossibles..."

Stevens Miller wrote:Here's a proof that meets your needs, I think.

Yup. That'd be it. Cheers. Logic had basically sorted it for me; but sometimes you like the Linus blanket of a mathematical proof.

Winston

Articles by Winston can be found here

Shamsudeen Akanbi wrote:I got an error that: BigInteger(long) has private access in BigInteger. BigInteger total=new BigInteger(0);. And an arrow was pointed at 'n' in new.

Shamsudeen, have a look at the list of constructors available when you use the BigInteger class. BigInteger(long) isn't one of them. BigInteger("0") might get you going, but read the documentation before you assume that will work for you.

*Hey! This is my 30'th post! I'm a Ranch Hand!*

"Il y a peu de choses qui me soient impossibles..."

Stevens Miller wrote:Hey! This is my 30'th post! I'm a Ranch Hand!

Stevens, let me be the first, mate....

*Congratulations.*

Now go poke a few more cows.

Winston

Articles by Winston can be found here

Winston Gutkowski wrote:Stevens Miller wrote:Hey! This is my 30'th post! I'm a Ranch Hand!

Stevens, let me be the first, mate....

Congratulations.

Why, thank you, Winston!

We don't say "mate" much here on the American Atlantic Coast (well, not as a noun, anyway). Where are you located?

"Il y a peu de choses qui me soient impossibles..."

Stevens Miller wrote:We don't say "mate" much here on the American Atlantic Coast (well, not as a noun, anyway). Where are you located?

Currently: Brussels (for the last 8 years); but originally a Canuck, brought up on the 'Sarf' coast of England.

Before 'La belle Belgique', had split my life pretty much equally between the UK and Canada - with 18 months in the US (NYC, IL and MN) back in '79-80 as my re-intro to 'Norf' America.

So you'll forgive any confusion (comes out in my posts sometimes) when it comes to "nationhood". Personally, I see myself as a "Brit with other bits".

Winston

Articles by Winston can be found here

Stevens Miller wrote:Cool! How's the market for programmers out there? Need any help?

What, me personally, or my "nation" (UK, I guess) as a whole?

In general, I'd say that the economy over here isn't quite as healthy as yours; but there are jobs out there for people with the "right" skills.

What's "right"? Dunno. These days, it seems to involve a lot of TLA's on your CV; and it also helps if you ain't 55 (like me) and perceived as a dinosaur.

I'll be a programmer until they curl me up and chuck me in the furnace, job or no job; but if you're looking for pastures new, have a look at the ads - you guys can get the Times or the FT same day can't you?

Britain's a wonderful country; but be prepared for some changes if you do decide to make the hop. It's more prosaic, more wordy, and much,

*much*smaller. And it's GREEN. Living on the East Coast you may be used to it, but I lived in Vancouver, BC for most of my 22 years in Canada; just south of 300-odd thousand square miles of pine forest. And believe me, you

*notice*it when you're on the glide path into Heathrow.

Winston

Articles by Winston can be found here

I live in the glide-path for Dulles International, so I can relate.

Say, back to Java for a moment: I'm having a heck of a time with an interface I added to a .jar file that is already working well as a source of classes for a different project. I added an interface to the .jar, and now my main project can't find the interface when I compile the main project. Any pointers for me to some guidance?

"Il y a peu de choses qui me soient impossibles..."

Accordingly, I've created a new topic to ask how to get informational message out of build.xml. If anyone knows, please say so at http://www.coderanch.com/t/589286/java/java/Make-build-xml-File-Print#2683450

"Il y a peu de choses qui me soient impossibles..."

Stevens Miller wrote:Well, solved my own problem, sort of...

Yeah, sorry about that. You caught me Olympics-ing.

Glad you got it sorted anyway.

Winston

Articles by Winston can be found here

It is sorta covered in the JavaRanch Style Guide. |