programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Questions about primitive types - Fibonacci sequence calculator

Alix Ollivier
Ranch Hand
Posts: 71
I wrote a program to calculate the Fibonacci sequence numbers, but once it gets too high, the data gets messy. Can anyone tell me why? I believe it is because I am using int to hold large numbers, as I remember learning something about limits, but I am not sure. Can you please look at it? Also, I realized that if the number inputted is negative or lower than 3, it will always give out 0,1 as the output, because I told the program to output like that. Please help. Thanks!

Ivan Jozsef Balazs
Rancher
Posts: 999
5
The Fibonacci series grows exponentially.

"long" would be a somewhat better choice for the data type and java.math.BigInteger. the right one.

Alix Ollivier
Ranch Hand
Posts: 71
I'm sorry. Is BigInteger a class? Can I import it? Also, does long have limits as well?

Ivan Jozsef Balazs
Rancher
Posts: 999
5
Alix Ollivier wrote:Is BigInteger a class? Can I import it? Also, does long have limits as well?

The answer to all your questions is "yes".

Integer
MAX_VALUE
A constant holding the maximum value an int can have, 2^31-1 = 2147483647

Long
MAX_VALUE
A constant holding the maximum value a long can have, 2^63-1 = 9223372036854775807L

java.math.BigInteger
Immutable arbitrary-precision integers. All operations behave as if BigIntegers were represented in two's-complement notation (like Java's primitive integer types).
BigInteger provides analogues to all of Java's primitive integer operators, and all relevant methods from java.lang.Math.

dennis deems
Ranch Hand
Posts: 808
Alix Ollivier wrote:Also, I realized that if the number inputted is negative or lower than 3, it will always give out 0,1 as the output, because I told the program to output like that.

In general I advise against displaying anything to the user before the necessary calculations have been performed. Here you are spitting out 0 and 1 before you even know what value the user has given you. A much cleaner approach is: 1. validate user input 2. perform logic 3. display result. Keep these tasks in their own lanes.

Campbell Ritchie
Marshal
Posts: 56595
172
• 1
Welcome to the Ranch

As you have been told, the common Fibonacci numbers increase exponentially, in fact increasing by approx 1.618× each number. 1.618 is of course the Golden Ratio. There are all sorts of interesting things about Fibonacci numbers here. Even a BigInteger will run out of capacity eventually; I once tried it and got as far as Fib(5000) approx and got a stack overflow. That was using a recursive algorithm, rather than the iteration you are using.

I shall have to edit your post because those long comments are difficult to read. I shall also refer you to some conventions, because your names are wrongly formatted.

Ivan Jozsef Balazs
Rancher
Posts: 999
5
Campbell Ritchie wrote:
Even a BigInteger will run out of capacity eventually.

Actually the JVM might run of free memory but BigInteger has no inherent limitation - as opposed to a primitive type of a given limited value range set.

Campbell Ritchie
Marshal
Posts: 56595
172
Although it says
BigIntegers are made as large as necessary
... a BigInteger is probably based on an int[] array, which cannot have an index larger than 2147483647. If you need more digits than that . . .

Winston Gutkowski
Bartender
Posts: 10575
66
Campbell Ritchie wrote:a BigInteger is probably based on an int[] array, which cannot have an index larger than 2147483647. If you need more digits than that...

Not forgetting that each "digit" is base-4294967296...

Winston

Ivan Jozsef Balazs
Rancher
Posts: 999
5
Campbell Ritchie wrote: a BigInteger is probably based on an int[] array, which cannot have an index larger than 2147483647. If you need more digits than that . . .

Does it live up to the first sentence of its description in the Javadoc then?

Immutable arbitrary-precision integers

Campbell Ritchie
Marshal
Posts: 56595
172
Ivan Jozsef Balazs wrote: . . . Does it live up to the first sentence of its description in the Javadoc then?

Immutable arbitrary-precision integers

Yes, as long as arbitrary means not more than 2147483647. If you are going to be really precise, no.
The same applies to BigDecimal where it does give you a limit: the scale is a 32‑bit two’s complement integer. So that determines the maximum number of digits after the decimal point.

Ivan Jozsef Balazs
Rancher
Posts: 999
5
The API does not impose these limits, they are implementation details. If need be, the implementation can be exchanged for one providing more room.

Winston Gutkowski
Bartender
Posts: 10575
66
Ivan Jozsef Balazs wrote:Does it live up to the first sentence of its description in the Javadoc then?
Immutable arbitrary-precision integers

No. And if you think about it, nothing could, because you'll always run up against other arbitrary boundaries imposed by memory or storage...or time.

I suppose it would be possible to design a BigInteger whose "digits" were based on linked storage and therefore theoretically unbounded; but it would be infernally slow and a space hog.

Sometimes, it's reasonable to use the word 'arbitrary' to mean "to all intents and purposes, unbreakable"; and if you can even break the bitLength() method (which isn't arbitrary, even in the context of BigInteger) you'll be doing well - ask Campbell

Winston

Winston Gutkowski
Bartender
Posts: 10575
66
Ivan Jozsef Balazs wrote:The API does not impose these limits...

Yes it does. (See above).

Winston

Ivan Jozsef Balazs
Rancher
Posts: 999
5
The API does not preclude an implementation not subject to the array-size limitation.

For example the digits being stored in a linked list of max-sixed arrays.

Winston Gutkowski
Bartender
Posts: 10575
66
Ivan Jozsef Balazs wrote:The API does not preclude an implementation not subject to the array-size limitation.

Yes it does. In fact, the bitLength() method (as I suggested to look at) limits the size even further because it returns an int.

What the API does not do (nor should any API) is mandate the use of arrays. But personally, I don't know of a better, faster or more compact form of random storage (which is used by many of the internal algorithms) for primitives.

Winston

Ivan Jozsef Balazs
Rancher
Posts: 999
5
Right: it should be BigInteger as well ;-)

Winston Gutkowski
Bartender
Posts: 10575
66
Ivan Jozsef Balazs wrote:Right: it should be BigInteger as well ;-)

Correct.

I've actually sent two bug reports about it - one to Sun, the 2nd to Oracle - but I guess they haven't got enough people that have run into the problem...

If it was a long, I could live with it.

Winston

Campbell Ritchie
Marshal
Posts: 56595
172
Winston Gutkowski wrote:. . . and if you can even break the bitLength() method (which isn't arbitrary, even in the context of BigInteger) you'll be doing well - ask Campbell

Winston
Surely you can get it to have 0xffffffff bits . . . which comes to -1

Ivan Jozsef Balazs
Rancher
Posts: 999
5
Winston Gutkowski wrote:

If it was a long, I could live with it.

Maybe once we'll have long long in Java ;-)

Winston Gutkowski
Bartender
Posts: 10575
66
Ivan Jozsef Balazs wrote:Maybe once we'll have long long in Java ;-)

Ooof. Hope not. That would mean a java.lang.LongLong class; and a whole new section in the JLS; and then some schmuck'll want a LongDouble; and then we'll need Atomic versions of 'em all......

Winston

Campbell Ritchie
Marshal
Posts: 56595
172
You could have 128-bit two’s complement numbers, or unsigned numbers, or 128-bit IEEE754 numbers; C# has two out of those three. But when you have BigInteger and BigDecimal, you don’t need them.

Ivan Jozsef Balazs
Rancher
Posts: 999
5
Campbell Ritchie wrote:But when you have BigInteger and BigDecimal, you don’t need them.

When there will be widespread native support for those wider types, Java primitives corresponding to them would yield much better performance then these Big guys.

Winston Gutkowski
Bartender
Posts: 10575
66
Ivan Jozsef Balazs wrote:When there will be widespread native support for those wider types, Java primitives corresponding to them would yield much better performance then these Big guys.

Heed the words of Wulf (below); he speaketh truth.

Winston

Marcio Duran
Greenhorn
Posts: 21
“Truth is so obscure in these times, and falsehood so established, that, unless we love the truth, we cannot know it.”

Winston Gutkowski
Bartender
Posts: 10575
66
Marcio,

I split up the very long line in your code. It screws up the windowing here. Please read the new guidelines on the UseCodeTags page.

Thanks

Winston

PS: Nice quote. I like a bit of Blaise with me morning coffee.

Alix Ollivier
Ranch Hand
Posts: 71
Alright, I'm sorry to say that I have no clue what most of the above posts mean. I'll take Marcio's example.

Winston Gutkowski
Bartender
Posts: 10575
66
Alix Ollivier wrote:Alright, I'm sorry to say that I have no clue what most of the above posts mean.

Don't worry, it's mostly geeky stream-of-consciousness stuff.

I'll take Marcio's example.

OK, but make sure you understand it before you use it; and if this is for a school project, you should also attribute the source.

Winston

Alix Ollivier
Ranch Hand
Posts: 71
Don't worry, this is just an exercise I am doing to further my learning of Java. I have already modified my code from before a bit, I just needed to know how BigInteger works. And this describes it perfectly.

 With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.