I have tried to find it with the help of BigInterger, but it is extremely slow, and with the current speed, it will take days to find the number.

So my question is:

**What is the fastest way to find F(12345678) using java?**

Posted 12 April 2011 - 12:40 PM

I have been working with fibonacci numbers, and I want to find F(12345678) which, of course, result in a very big number.

I have tried to find it with the help of BigInterger, but it is extremely slow, and with the current speed, it will take days to find the number.

So my question is:**What is the fastest way to find F(12345678) using java?**

I have tried to find it with the help of BigInterger, but it is extremely slow, and with the current speed, it will take days to find the number.

So my question is:

Posted 12 April 2011 - 02:24 PM

Are you familiar with solving linear recurrences? Or how about homogenous linear differential equations? You solve them the same way, basically.

Start by setting up the recurrence.

Now set up the characteristic equation:

Now just solve the quadratic:

From there, we set up our solution:

Where r(1) is root 1, and r(2) is root 2. You know F(0) is 0, and F(1) is 1. Now just set up a system of equations and solve given those values. Whatever you get for A and B, you plug into the equation, and now you can solve for your large Fibonacci number with a formula that we solved by hand.

Happy coding.

Start by setting up the recurrence.

F(n) = F(n-1) + F(n-2)

Now set up the characteristic equation:

x^2 - x - 1 = 0

Now just solve the quadratic:

x = [1 +- sqrt(1 - 4(-1)(1))]/2 x = [1 +- sqrt(5)]/2

From there, we set up our solution:

F(n) = Ar(1)^n + Br(2)^n

Where r(1) is root 1, and r(2) is root 2. You know F(0) is 0, and F(1) is 1. Now just set up a system of equations and solve given those values. Whatever you get for A and B, you plug into the equation, and now you can solve for your large Fibonacci number with a formula that we solved by hand.

Happy coding.

Posted 12 April 2011 - 04:13 PM

Solve it by hand first to find the equation, as I showed you above. Then just use that formula programatically. It will make your life much easier.

Posted 12 April 2011 - 05:37 PM

joeydog, on 12 April 2011 - 03:59 PM, said:

Are you using recursion? If not, try it. It seems the best way to me.

Not really, never seen a case where recursion is faster than iteration (well documented in the litterature). Recursion adds the method call overhead and with that large number you will exhausted the stack quite fast.

@op: sure that it will be slower with BigInteger but you have to realize that you work with very large number

Posted 12 April 2011 - 05:40 PM

Quote

@op: sure that it will be slower with BigInteger but you have to realize that you work with very large number

Not only that, but BigIntegers are immutable as well, meaning a new BigInteger is created each time you want to perform a mathematical operation on it, etc.

Posted 13 April 2011 - 03:05 AM

Recursion for fibonacci is slow. Say you are calculating fib 6, the tree looks like this:

You have to calculate fib(4) twice, fib(3) three times. Fib(2) is a base case but it's accessed 5 times. This only gets worse for larger numbers.

You want to do it iteratively, and that sounds like what you've done. I did a quick implementation and it's got to 7200000 in half an hour. It's beginning to slow down now that it's working with bigger numbers but I doubt it'll take more than a couple of hours.

Maybe post your code and we can look for the bottlenecks?

Another option is to look at the wikipedia page which gives you a formula to calculate Fibonacci numbers quickly.

~~Macos actually for fibonacci, using an immutable structure isn't that big a performance penalty since you need the previous two numbers to calculate the next one.~~

Actually, that last bit is nonsense.

6 5 4 4 3 3 2 3 2 2 1 2 1 2 1

You have to calculate fib(4) twice, fib(3) three times. Fib(2) is a base case but it's accessed 5 times. This only gets worse for larger numbers.

You want to do it iteratively, and that sounds like what you've done. I did a quick implementation and it's got to 7200000 in half an hour. It's beginning to slow down now that it's working with bigger numbers but I doubt it'll take more than a couple of hours.

Maybe post your code and we can look for the bottlenecks?

Another option is to look at the wikipedia page which gives you a formula to calculate Fibonacci numbers quickly.

Actually, that last bit is nonsense.

This post has been edited by **cfoley**: 13 April 2011 - 03:36 AM

Posted 13 April 2011 - 04:58 AM

Uhm ok.. please show me how. This is what I've done:

int x=12345678; BigInteger result = new BigInteger( "1" ); BigInteger før3 = new BigInteger( "1" ); BigInteger før4 = new BigInteger( "1" ); for ( int nr=3; nr<=x; nr++ ) { result = før3.add( før4 ); før3 = før4.abs(); før4 = result.abs(); if ( nr % 10000 == 0 ) log( new Date() + " " + nr ); }

Posted 13 April 2011 - 05:08 AM

I did it pretty much like that!. Those calls to abs() might be killing you. Also, depending on what your log() method does, that could be expensive.

Here is my method for comparison. I used the convention fob(0) = 0; fib(1) = 1 but that should make little difference to the time:

Here is my method for comparison. I used the convention fob(0) = 0; fib(1) = 1 but that should make little difference to the time:

public static BigInteger fib(int n) { BigInteger fibLast = new BigInteger("0"); if (n == 0) return fibLast; BigInteger fibI = new BigInteger("1"); for(int i = 1; i <= n; i++) { BigInteger next = fibI.add(fibLast); fibLast = fibI; fibI = next; if (i%100000 == 0) System.out.println(i); } return fibI; }

Posted 13 April 2011 - 05:51 AM

cfoley, on 13 April 2011 - 05:08 AM, said:

I did it pretty much like that!. Those calls to abs() might be killing you. Also, depending on what your log() method does, that could be expensive.

Here is my method for comparison. I used the convention fob(0) = 0; fib(1) = 1 but that should make little difference to the time:

Here is my method for comparison. I used the convention fob(0) = 0; fib(1) = 1 but that should make little difference to the time:

public static BigInteger fib(int n) { BigInteger fibLast = new BigInteger("0"); if (n == 0) return fibLast; BigInteger fibI = new BigInteger("1"); for(int i = 1; i <= n; i++) { BigInteger next = fibI.add(fibLast); fibLast = fibI; fibI = next; if (i%100000 == 0) System.out.println(i); } return fibI; }

I do not believe the abs() make any big difference, and the log 100% doesn't.

Also I have tried and run it on a different computer with the same result. It takes days for it to find the number :S

- Caffeine Lounge
- Corner Cubicle
- Student Campus
- Software Development
- Industry News
- Introduce Yourself
- Nightmare.In.Code

- C and C++
- VB.NET
- Java
- C#
- Python
- PHP
- Mobile Development
- ASP.NET
- .NET Framework
- Ruby
- Game Development
- Assembly
- Databases
- ColdFusion
- VB6
- Other Languages
- 52 Weeks Of Code

- Web Development
- HTML & CSS
- JavaScript
- Graphic Design
- Flash & ActionScript
- Blogging
- SEO & Advertising
- Web Servers & Hosting
- Site Check

- I need help with this Array Question
- Dijkstra's Algorithm
- Book Review: Murach's Beginning Java with NetBeans
- Graph Data Structure Tutorial
- Swing, Passive Model-View-Presenter in 5 minutes.
- Book Review: Murach's Java Servlets and JSP
- Phobos - A JavaFX Games Engine: Part 2 - JavaFX Scene API and the FSM
- Maven Tutorial 2 - Adding Dependencies
- Maven Tutorial 1 - Installation and Getting Started
- Phobos - A JavaFX Games Engine: Part 1 - Intro to Threading and DP
**221 More Java Tutorials...**

- C Snippets
- C++ Snippets
- Java Snippets
- Visual Basic Snippets
- C# Snippets
- VB.NET Snippets
- ASP.NET Snippets
- PHP Snippets
- Python Snippets
- Ruby Snippets
- ColdFusion Snippets
- SQL Snippets
- Assembly Snippets
- Functional Programming Snippets
- Perl Snippets
- HTML/CSS Snippets
- Javascript Snippets
- Flash/ActionScript Snippets
- ASP Snippets
- Linux, Unix, and Bash Snippets
- Other Languages Snippets
- Regex

Copyright 2001-2017 **MediaGroup1 LLC**, All Rights Reserved

A**MediaGroup1 LLC** Production - Version 6.0.2.1.36

Server: secure3

A

Server: secure3