Skip to content

Instantly share code, notes, and snippets.

@kencan
Created May 30, 2011 15:12
Show Gist options
  • Select an option

  • Save kencan/999037 to your computer and use it in GitHub Desktop.

Select an option

Save kencan/999037 to your computer and use it in GitHub Desktop.
Fast Fibonacci implementation
def fibFast1(num: Int): BigInt = {
var a: BigInt = 1
var b: BigInt = 0
var c: BigInt = 1
for(bit <- bits(num)){
bit match {
case 1 => {
a = (a+c)*b
b = b*b + c*c
}
case 0 => {
val prevA = a
a = a*a + b*b
b = (prevA+c)*b
}
}
c = a + b
}
return b
}
def bits(num: Int, builder: Builder[Int, Seq[Int]] = Seq.newBuilder[Int]): Seq[Int] = {
if(num > 0){
bits(num / 2, builder += (num % 2))
}
return builder.result.reverse
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment