s ravi chandran wrote:
I am solving a modified variant of Fibonacci problem....
s ravi chandran wrote:
Here is the sequence equation:
it fails in boundary conditions.
Don't know, but I wouldn't be confident about 1,000,000,000 digits. You should get into millions of digits before you hit any problems. I have got as far ass ravi chandran wrote:. . . What is the limit of a BigInteger considering a average system specs.
Nor how much memory they have available? It might be much less than you have available.I am solving this problem on a puzzle website. Not sure what is the benchmark of their analysis.
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 should retrieve it from cache and use that to calculate non‑Fib18.My program from yesterday wrote:non-Fib20 has 155971 binary digits in.
Campbell Ritchie wrote:
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 should retrieve it from cache and use that to calculate non‑Fib18.My program from yesterday wrote:non-Fib20 has 155971 binary digits in.
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.
Don't know.s ravi chandran wrote:. . . Okay, what am I doing wrong here? . . .
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.
Feels like about a million digits, but I am sure it isn't. No, it's only 23476.743484176868282745396968391107989101...4330343871
s ravi chandran wrote:
Strangely, the website shows that 46006 people have successfully submitted solution. I wonder how many used Java to solve it.
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.Henry Wong wrote:. . . With a time complexity of O(N^2) . . .
Error occurred during initialization of VM
Too small initial heap
Campbell Ritchie wrote:
It doesn't run in quadratic time. It runs in exponential complexity, in fact ...Henry Wong wrote:. . . With a time complexity of O(N^2) . . .
s ravi chandran wrote:. . . my personal laptop which has i7 processor and 12 GB RAM . . .
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.Tim Cooke wrote:. . . My machine is a 2012 MacBook Pro, 2.3GHz i7, 16GB. . . .
Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters? |