Fibonnaci Sequence fast implementation

Posted by user2947615 on Stack Overflow See other posts from Stack Overflow or by user2947615
Published on 2013-11-05T21:24:27Z Indexed on 2013/11/05 21:53 UTC
Read the original article Hit count: 175

Filed under:

scala

|

fibonacci

I have written this function in Scala to calculate the fibonacci number given a particular index n:

 def fibonacci(n: Long): Long = {
 if(n <= 1) n
 else
   fibonacci(n - 1) + fibonacci(n - 2)     
}

However it is not efficient when calculating with large indexes. Therefore I need to implement a function using a tuple and this function should return two consecutive values as the result.

Can somebody give me any hints about this? I have never used Scala before. Thanks!

© Stack Overflow or respective owner

Related posts about scala

ensime scala errors (class scala.Array not found, object scala not found)

as seen on Stack Overflow - Search for 'Stack Overflow'
I've installed ensime according to the README.md file, however, I get errors in the inferior-ensime-server buffer with the following: INFO: Fatal Error: scala.tools.nsc.MissingRequirementError: object scala not found. scala.tools.nsc.MissingRequirementError: object scala not found. at scala… >>> More
infinite loop shutting down ensime

as seen on Stack Overflow - Search for 'Stack Overflow'
When I run M-X ensime-disconnect I get the following forever: string matching regex `\"((?:[^\"\\]|\\.)*)\"' expected but `^@' found and I see this exception when I use C-c C-c Uncaught exception in com.ensime.server.SocketHandler@769aba32 java.net.SocketException: Broken pipe at java… >>> More
How to resolve java.nio.charset.UnmappableCharacterException in Scala 2.8.0?

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm using Scala 2.8.0 and trying to read pipe delimited file like in code snipped below: object Main { def main(args: Array[String]) :Unit = { if (args.length > 0) { val lines = scala.io.Source.fromPath("QUICK!LRU-2009-11-15.psv") for (line <-lines) print(line) } … >>> More
Question on Scala Closure (From "Programming in Scala")

as seen on Stack Overflow - Search for 'Stack Overflow'
I don't understand why authors said that Code Listing 9.1 from "Programming in Scala" use closure. In chapter 9, they show how to refactor code into more less duplicated form, from this original code: object FileMatcher { private def filesHere = (new java.io.File(".")).listFiles def filesEnding(query:… >>> More
Common idiom in Java to Scala, traverse/Iterate Java list into Scala list

as seen on Stack Overflow - Search for 'Stack Overflow'
I am processing a XML document and iterating through nodes. I want to iterate through the nodes and build a new List of some type. How would I do this with Scala: Here is my XML traverse code: def findClassRef(xmlNode: Elem) = { xmlNode\"classDef" foreach { (entry) => val name… >>> More

Related posts about fibonacci

What is going on with the "return fibonacci( number-1 ) + fibonacci( number-2 )"?

as seen on Stack Overflow - Search for 'Stack Overflow'
I have problem understanding what the return fibonacci( number-1 ) + fibonacci( number-2 ) does in the following program: import sys def fibonacci( number ): if( number <= 2 ): return 1 else: return fibonacci( number-1 ) + fibonacci( number-2 ) The problem is that I… >>> More
Properties of bad fibonacci algorithm

as seen on Stack Overflow - Search for 'Stack Overflow'
I was looking at the canonical bad fibonacci algorithm the other day: public static int fib(int n) { // Base Case if (n < 2) return 1; else return fib(n-1) + fib(n-2); } I made the interesting observation. When you call fib(n), then for k between 1 and n fib(k)… >>> More
Code Chess: Fibonacci Sequence

as seen on Stack Overflow - Search for 'Stack Overflow'
Building upon the proven success of Code Golf, I would like to introduce Code Chess. Unlike Code Golf, which strives for concision, Code Chess will strive for cleverness. Can you create a clever or unexpected Fibonacci generator? Your code must print or return either the nth Fibonacci number or… >>> More
Test if a number is fibonacci

as seen on Stack Overflow - Search for 'Stack Overflow'
I know how to make the list of the Fibonacci numbers, but i don't know how can i test if a given number belongs to the fibonacci list - one way that comes in mind is generate the list of fib. numbers up to that number and see if it belongs to the array, but there's got to be another, simpler and faster… >>> More
Fibonacci numbers in F#

as seen on Geeks with Blogs - Search for 'Geeks with Blogs'
As you may have gathered from some of my previous posts, I've been spending some quality time at Project Euler. Normally I do my solutions in C#, but since I have also started learning F#, it only made sense to switch over to F# to get my math coding fix. This week's post is just a small snippet… >>> More