Win a copy of Event Streams in Action this week in the Java in General forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Knute Snortum
  • Rob Spoor
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Piet Souris
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Ganesh Patekar

How to handle extra large values for Fibonacci Series

 
Ranch Hand
Posts: 579
6
jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

I am solving a modified variant of Fibonacci problem. The problem here is the result after n=17, the bit size of result exceed even BigInteger. I do not get any result when I go for n>17.

How can I solve the problem?

Here is the result for n =17:

30472561784141115391778927604166923712591849685966371011034708006
91502127201206721753122686940948803915675049171249304581375612480
75408802874383211876387193591841783882946470798848933742976961158
38331116842007452420634057018632222917807893068357663018900774857
94933582184378775464518979959743359102141148662382408255253620650
48717684280153939433145836403159221313574064945481498204678603939
53488484457699664171336470648669491894910669375915189073456789097
73910972589196129055048855475649533694935951844856938244654313359
32046046951682178832468288857379107741159976401107578492093364134
88843569663514752614434662474550250192520867697146425065721269690
66430058968591788726159085446602156489564071886009742910372369813
27834221151194172213664891717021249452667109203048154408986293389
02719247231928693934095583511846989703390877944161601845284052802
93744029986132319011295653370647972229405001682588995176537774616
26214079505597951743377608571417785836316584332331064710138480933
45611965399095775043091396853787611894102227984110872236512194708
57113897310408007635740486554178410238800252689595412058577169081
10964590363552492825480539889179238677000296776107309055013296482
38503044646721037769628062328523706703098533959497375580328243616
32179843385017344627332557567731002041706039333732307635083529027
62353911644261132350304181816384191571674303828664573050412127829
31700601042062248364006584206436259351120492466112942421622084260
90364088712014313996176950078566752200488171301206916830452694729
10335722304027187567503375531657742716649538143292690927457343724
80799473895513785439167219092138284545830464822820468068720837095
75668506048054002975304955354985211211264938807844524101596601157
573495696477148722207235612102934659343107414922094915268812831377
465527333004052659892859694836384944379724097408146026356035228249
32066807851357180670024589227445583540184326961330435546656154680
38714550422345907649267223269321584532319864335591970239541766446
16281771591423693192241053854367228870530848941212609468718760569
83071945076289338152338232485239975292792036514561369956033958219
31796982229694736370816738943669187451586911047455838163791165112
64231523391848438332076385257639327634958086008038373519285878160
494014466992569962128829312384544261638207409040319211973417558257
01173580481461337717426457356285706293842378687323282816414580193
83989735267464173921522598025069283037878221484976324049935687191
580272705549381219178885382659847859408932833760951269040768387468
56868395360698781157946904241035371239813413865378011119242334202
40328030597138487422466960550149963959836145070858026713292053372
52765953771319355550020629967626601353981339752714219497836899846
95152216970215288517636587013754116660225980431165924802264920514
814718497095839445008940209313926548607849148861770208385773492749
322421938069218402860080627931640596164820210836911909853682716802
111864419391202780728776127406888459561125012448297364986056922255269

According to the problem, max range of test input n= 20.
 
author
Posts: 23835
140
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

s ravi chandran wrote:
I am solving a modified variant of Fibonacci problem....



Sheesh, how modified is this variant of Fibonacci?  And arguably, since the 17th member of the Fibonacci sequence, is only 1597 (I think), can you really even call it Fibonacci anymore?  

Henry
 
Saloon Keeper
Posts: 5710
144
Android Mac OS X Firefox Browser VI Editor Tomcat Server Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Indeed, not even factorials grow that fast.

IIRC, BigInteger is limited by available memory only, so unless you can provide the JVM with more memory -and you probably can, the JVM by default uses up to a quarter of available memory, IIRC-, or implement a less memory intensive multi precision integer arithmetic, you may be out of luck.
 
s ravi chandran
Ranch Hand
Posts: 579
6
jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the formatting.

Here is the sequence equation:


I am able to pass the initial test but it fails in boundary conditions.

 
s ravi chandran
Ranch Hand
Posts: 579
6
jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was thinking of using int[] to store the bits, but again BigInteger already does that.

Any other way to achieve this? What is the limit of a BigInteger considering a average system specs. I am solving this problem on a puzzle website. Not sure what is the benchmark of their analysis.
 
Henry Wong
author
Posts: 23835
140
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

s ravi chandran wrote:
Here is the sequence equation:



Based on a really rough estimate, I would say that each term of the sequence is about twice the size as the previous term (plus or minus a couple of digits ... ). So, if you can only get to the 17th term, and you need three more terms, then you probably need to give about 10 times more memory to the JVM, than what you are currently providing.

Henry
 
Marshal
Posts: 65046
247
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That figure you posted contains 2935 digits. I am very surprised that it won't fit into a big integer, which I would expect to have the capacity to hold several million digits.
 
Tim Moores
Saloon Keeper
Posts: 5710
144
Android Mac OS X Firefox Browser VI Editor Tomcat Server Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

it fails in boundary conditions.


What boundary conditions are those?
 
Campbell Ritchie
Marshal
Posts: 65046
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

s ravi chandran wrote:. . . What is the limit of a BigInteger considering a average system specs.

Don't know, but I wouldn't be confident about 1,000,000,000 digits. You shou‍ld get into millions of digits before you hit any problems. I have got as far as
non-Fib31 has 319427201 binary digits in.
You are looking at something in the region of 95,000,000 decimal digits, and counting.

I am solving this problem on a puzzle website. Not sure what is the benchmark of their analysis.

Nor how much memory they have available? It might be much less than you have available.

BTW: an earlier version of my program gave a number starting 304 and ending 269 for non‑Fib17, so if it is wrong we have both made the same mistake
 
s ravi chandran
Ranch Hand
Posts: 579
6
jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hard to find whether the value is correct. It is so loonnnnggg that I would just assume the value is correct to the precision.

There are many submissions to this problem on the site. I do not know how they were able to achieve that.

The boundary condition is n=20. I am closer at 17, but last 3 iterations are missing.

I even tried caching of values to optimize it. Here is my code:



Not sure if this can be optimized further to make it work. What should be the size of the integer if I have to hold the result bits for n=20?
 
Campbell Ritchie
Marshal
Posts: 65046
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

My program from yesterday wrote:non-Fib20 has 155971 binary digits in.

I don't think you are caching things correctly. If you are going to use a cache, you don't need to start your calculations from 1 again. If you cache non‑Fib17 you shou‍ld retrieve it from cache and use that to calculate non‑Fib18.
Henry was right that the number of digits approximately doubles each time. My non‑Fib31 had about twice as many bits as non‑Fib30. I got fed up with waiting for 32, so I killed the program as taking too long to run.
 
s ravi chandran
Ranch Hand
Posts: 579
6
jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

My program from yesterday wrote:non-Fib20 has 155971 binary digits in.

I don't think you are caching things correctly. If you are going to use a cache, you don't need to start your calculations from 1 again. If you cache non‑Fib17 you shou‍ld retrieve it from cache and use that to calculate non‑Fib18.
Henry was right that the number of digits approximately doubles each time. My non‑Fib31 had about twice as many bits as non‑Fib30. I got fed up with waiting for 32, so I killed the program as taking too long to run.



Okay, what am I doing wrong here?

The boundary condition is n=20. If you reached n=31, that is good enough.
 
Campbell Ritchie
Marshal
Posts: 65046
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

s ravi chandran wrote:. . . Okay, what am I doing wrong here?  . . .

Don't know.

What happens when you run the code on your own computer rather than the website? How much heap space have you got to play with? Do you get any exceptions?
 
s ravi chandran
Ranch Hand
Posts: 579
6
jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am not getting any response after n=17. The program just exits without any exception.

I tried using -Xms512m -Xmx1024m and -Xms1024m -Xmx1024m, same behavior as before.
 
Campbell Ritchie
Marshal
Posts: 65046
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I really don't know why I can get it to run up to 31 and you have enough heap space and your program stops at 17. Please post your whole code.
 
s ravi chandran
Ranch Hand
Posts: 579
6
jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:I really don't know why I can get it to run up to 31 and you have enough heap space and your program stops at 17. Please post your whole code.


The code I posted above is the whole code. I am giving the inputs statically. you can run it directly.
 
Campbell Ritchie
Marshal
Posts: 65046
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

743484176868282745396968391107989101...4330343871

Feels like about a million digits, but I am sure it isn't. No, it's only 23476.
Ran all right for me. No problems. I did have to change 17 to 20 in line 11, but I don't think that made any real difference.
 
s ravi chandran
Ranch Hand
Posts: 579
6
jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So, you were able to run n=20?

Seems like my system specs are below the required specs. As this is failing on the website also, this might be their limitation too.

Strangely, the website shows that 46006 people have successfully submitted solution. I wonder how many used Java to solve it.
 
Henry Wong
author
Posts: 23835
140
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

s ravi chandran wrote:
Strangely, the website shows that 46006 people have successfully submitted solution. I wonder how many used Java to solve it.



... perhaps, they didn't use the recursive algorithm?  The recursive Fibonacci algorithm, while incredibly popular in teaching recursion, isn't really a good algorithm. In fact, it is a horrible algorithm.

With a time complexity of O(N^2), when compared with the time complexity of O(N), done just by iterating, the recursive algorithm does a lot of "needless" work.

Henry  
 
Campbell Ritchie
Marshal
Posts: 65046
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Henry Wong wrote:. . . With a time complexity of O(N^2) . . .

It doesn't run in quadratic time. It runs in exponential complexity, in fact approximately O(φⁿ) where this (=the Golden Ratio, approx 1.618) is φ. As n increases, you reach a point where (2 + 1 ÷ n) ÷ n < 0.618 and after that point, exponential complexity increases faster than quadratic. At least that is if my schoolboy maths from when I was twelve is correct.
 
Campbell Ritchie
Marshal
Posts: 65046
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Don't use new BigInteger("1"). Use BigInteger.valueOf(1L) or even better BigInteger.ONE. I got your program (with those changes) to run with
java -Xmx1M ModifiedFibonacci
but I got an error with -Xmx512k.

Error occurred during initialization of VM
Too small initial heap

 
Henry Wong
author
Posts: 23835
140
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Henry Wong wrote:. . . With a time complexity of O(N^2) . . .

It doesn't run in quadratic time. It runs in exponential complexity, in fact ...



So... it is even worse that I stated... Definitely, don't use the recursive algorithm !!

Henry
 
Campbell Ritchie
Marshal
Posts: 65046
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I once tried the inefficient recursive algorithm on an old Thinkpad with 32MB of RAM, and it took about 3 minutes to calculate fib(34). I added a long called count and each recursion involved count++;
This is where the fun starts. If I printed the counts, they turned out to be Fibonacci numbers themselves, and (as all members of the common Fibonacci series do) increased by proportions of approx 1.618. There is a strong relationship between Fibonacci numbers and φ.

Thank you for the cow

There are efficient recursive algorithms. I think there is one where you pass two arguments to the method and add them, and I think that runs in linear complexity. I don't know whether you can convert the algorithm in Kaldewaij to a recursive one, but that runs in logarithmic complexity.
 
s ravi chandran
Ranch Hand
Posts: 579
6
jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay. I will create a non recursive solution for this problem and check.

Thanks for the detailed analysis.  
 
s ravi chandran
Ranch Hand
Posts: 579
6
jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One more observation. I was able to run n=20 series when running from command line. All this time i was trying from eclipse, it did not work even on my personal laptop which has i7 processor and 12 GB RAM. but from command line i got the result instantly.
 
Campbell Ritchie
Marshal
Posts: 65046
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

s ravi chandran wrote:. . . my personal laptop which has i7 processor and 12 GB RAM . . .

 
Campbell Ritchie
Marshal
Posts: 65046
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I tried it with Eclipse and it ran all right. I think I have done something wrong because the output seems different from yesterday's, but I cannot understand why you can't get the program to run beyond 17.
 
Sheriff
Posts: 4648
300
IntelliJ IDE Clojure Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I had a play with this yesterday, just for fun. I slightly modified your program to take n as an argument rather than hard coding it. I used only the command line and a simple text editor and I got bored recompiling between each run.

For reference, the code I used was this:

For analysis I used the Unix commands time (a command duration timer) and wc (word count).
Which says the output of the program with n=17 had 2936 characters and took 0 minutes 0.143 seconds to complete.

My machine is a 2012 MacBook Pro, 2.3GHz i7, 16GB.
I tested up to n=32

Given that my 4 year old laptop can compute n<25 in under a second I am having a hard time figuring out why you seem to be having so much trouble with much smaller values of n. Perhaps you could perform similar analysis on your machine for comparison? Start at n=17 and get as far as you can.
 
s ravi chandran
Ranch Hand
Posts: 579
6
jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay. I tried the iterative solution and the solution passes all the tests in the website.

Here is the code:



Now coming back to the recursive solution. Well, I was able to run till n=31. I waited few mins for n=32 but got impatient and killed the process. But all this is working with CLI. Now, when I say nothing above n=17 worked, I meant from Eclipse 64 bit neon edition. This is consistent result in eclipse, even now I am not able to run it. And all my programs were run on windows. My personal laptop has windows 10 pro, not sure if that effects the execution timeline.

Found this link: fibonacci - iterative vs recursive. As you have already stated, the branching overhead outweighs the benefit for recursive solution after certain value of n. And this is for normal fibonacci, the current problem is like the extreme version of a fibonacci. I had hoped that caching values might have reduced the overhead of branching to a certain extent, but my assumption has proved to be wrong.
 
s ravi chandran
Ranch Hand
Posts: 579
6
jQuery Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Updated code to reflect the change of initial value of i =1.

 
Campbell Ritchie
Marshal
Posts: 65046
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Cooke wrote:. . . My machine is a 2012 MacBook Pro, 2.3GHz i7, 16GB. . . .

A lot posher than the machine I used, which has all the athleticism of a dead snail. But I still had no difficulty with the program. I did tell is to count up to 1000 but not having 1000000 years' worth of patience to watch the output, crashed it at (I think) 31. I was using JDK8u112 with an AMD A1 with 2 cores at 1.0GHz and 4GB of RAM on Fedora24.
 
Oh. Hi guys! Look at this tiny ad:
Java Code Review and Psychology
https://coderanch.com/t/714798/java/Java-Code-Review-Psychology
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!