Why BigInteger Ends StackOverflowError in Java in 19635 with Integer in Fibonacci Sequence
I used the following code to calculate the Fibonacci sequence to an arbitrarily large digit. The code worked as expected until I asked him to call the function 4,000,000 times (previously I only did a few hundred) and the computer ran for a short time, and then the console in Eclipse threw exceptions, which I inserted below the code.
My question is, what happened here? Has my computer been completely disconnected from memory or memory allocated for a thread? If so, why did it stop there?
Additionally: how would I calculate further digits of the Fibonacci sequence?
import java.math.BigInteger;
public class fibonacci2 {
public static void main(String[] args) {
calculate(p,q);
}
static long i = 0;
static BigInteger p = BigInteger.valueOf(0);
static BigInteger q = BigInteger.valueOf(1);
static BigInteger temp = BigInteger.valueOf(1);
public static void calculate(BigInteger s,BigInteger t){
while(i<4000000){
System.out.printf("%d\t%d\n", p, i);
temp = p;
p = p.add(q);
q = temp;
i++;
calculate(p,q);
}
}
}
Exceptions:
Exception in thread "main" java.lang.StackOverflowError
at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556)
at java.util.regex.Pattern$Branch.match(Pattern.java:4502)
at java.util.regex.Pattern$Branch.match(Pattern.java:4500)
at java.util.regex.Pattern$Branch.match(Pattern.java:4500)
at java.util.regex.Pattern$BranchConn.match(Pattern.java:4466)
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615)
at java.util.regex.Pattern$Curly.match0(Pattern.java:4177)
at java.util.regex.Pattern$Curly.match(Pattern.java:4132)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556)
at java.util.regex.Pattern$Branch.match(Pattern.java:4502)
at java.util.regex.Pattern$Branch.match(Pattern.java:4500)
at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715)
at java.util.regex.Pattern$Start.match(Pattern.java:3408)
at java.util.regex.Matcher.search(Matcher.java:1199)
at java.util.regex.Matcher.find(Matcher.java:618)
at java.util.Formatter.parse(Formatter.java:2517)
at java.util.Formatter.format(Formatter.java:2469)
at java.io.PrintStream.format(PrintStream.java:970)
at java.io.PrintStream.printf(PrintStream.java:871)
at fibonacci2.calculate(fibonacci2.java:19)
at fibonacci2.calculate(fibonacci2.java:24)
The last digit generated is 19635 - Quite a lot.
1326878955489024661813666359786489363862597596267841591984718441133687207625589984392446472136708362660021932584888435387175864913621007686907449488726146555339634440057581462744837894455258320181715917058010972459381316662624912515730463333990641248252946263758273263733494371408111666799248602654348374354575665103468235220997087827622833404218721529679546971496790702917758525593195304109707419091078545322602997139876040898483317207843245418460519839008799415039506028557215025158316547186838949994567284348168594751558774303437749976614353207719266172152800399335999724653093452545671783394362809521746195418258628847670756075496906506408478219476651845888891029108480100775783181552094778774012075581174246291938776732162276663007926660261885810696159684398850766130466749892237961368978537350659503384887184590728029938940346029664854098332325276075803004668683973663911965166244655623288976669353392684493773256538286461459851109985316594218567036331110620166503752002858960345948009368720912948399001910916986997220265362436664785799943439109476201817926328307787101903111393961567358800741253975114089666055055524228641035695722576137495918892142897156898692503277114086972203590845394136976627990477392702658110021633029375928452344175961619342446425577692017919828289892965169608439214185058259299428142136392927087694363606632396200712038762846401146176174076235731427999509341540670365435936962421082118957427657335120940572568809553108575779038595645790567465317987384989418130735215352197044454938184041888560239803018686185164698294191217575912300961041471253846379016838111539458503199340650847925170830041308909104620240254727212719485695991233607012305400097152820930170671679996786586356630874116104885500024255459477605145001560253013083063279986591643691042690736681570178761819746743173953554120842173406141182594650400199425331759112442700843083895835534479431045465147823905718446040188027219369044044746881890870957355941697346047645615951422282812765475741979140916948545544135891590984994421316253565099062872856720500802150529267476814926424230164415350607018124223826506073697804855986838795616061858990069414489351684205622356265998357458277002952267142463147340178104029647253698606524737761991314593712079503620243981528814537131637840662080425635436629256828427760152622305203916156796520899705174167734296908408451452996267056297190423572495130025952233672779014693448214053794642266680348738753076814915686552049097744959133183755554117599807331717127993229460524444705293414669111386007825708760814674565393333141407712337885110266102454353626702176503518620051234948824403128974016646652219343874086819779597902080011587822724591572161127633161983485420787099991506475649649141348635764866611237460038161609482811505459056720984164773312306226519377687422592991372909415867189115572873426942350835299418196448301454636928945763893711948642521939444172498975766802963900365371603321939228537069005044727697739908321738511622159719090223157395485131117488001035010770959822271311614904002754731071143329127520116109925804900365113570423880772195955015954683664323073573758800063285346161098584230363709170767300665124111908136212219882256188015145743813833566993241136920947969709074494693708400490165266626524438095822913197901853424142552914665703325721588414339753286621643113380168519173704794299920070190363642592959509902815769095947607009395818564394761404808083068108231669038621271175725129657162933085831476237663497229542220441135404939843524604551125465551727771898390053083332018851141421114669809053522545352296654101220414382424845364910057872482868831034816012362120945852895104734425583332803841289316437938705590169080297273992811432751620915492434343381305821590387308774845623139514680881624670510462853843145158840488067973557869621802645999603731851364427155579976322158436721846089173289826579664038171218473867618979447795005708240732801965744843651457112159188844806487240388585027463071736206026836829079695983829205181777389176553032 1338100015317662176621747937103286696865
source to share
This has nothing to do with BigInteger
, it is because your method calculate()
is calling itself. Once you get a high enough call stack, you run out of memory and the JVM throws out StackOverflowError
.
You don't have any termination condition in your method calculate()
. Each time you enter a loop while
, you start a different call.
It actually seems like you are trying to solve this problem iteratively and recursively at the same time.
You don't need to use a while loop and recursive call in your code. It seems to me that if you just call the call calculate()
, your program will work fine:
public static void calculate(BigInteger s, BigInteger t) {
while (i < 4000000) {
System.out.printf("%d\t%d\n", p, i);
temp = p;
p = p.add(q);
q = temp;
i++;
// calculate(p, q); // you don't need this
}
}
source to share
As others have pointed out, the error occurs because you are using recursion and never return to the recursive call.
This is a classic example of why you shouldn't use recursion when iteration will work. The Fibonacci sequence is mathematically defined recursively, but calculating it recursively is very memory intensive due to the number of stack frames you end up using. You can go further by increasing the available memory, but at some point you will be exhausted.
Given the way you coded it, there is no way around this limit other than rewriting it as an iterative calculation.
source to share
Your code is infinitely recursive. You need to remove: calculate(p, q);
from your code. Since your code is infinitely recursive, a StackOverflowError will be thrown even if you add more memory in Java (which just delays the throw of this error) because you are using too many stack frames (and therefore too much memory).
source to share