Search code examples
scalafunctional-programmingout-of-memory

Solving project Euler 25 in a functional manner using Scala

I am currently using Project Euler to learn Scala.
I am stuck on problem 25 with a java.lang.OutOfMemoryError exception.

Here is the question:

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

What I have come up with:

def fibonacciIndex(numOfDigits: Int): Option[Int] = {
  lazy val fibs: LazyList[Int] = 0 #:: fibs.scanLeft(1)(_ + _)
  fibs.find(_.toString.length == numOfDigits)
}

I am trying to do this in a purely functional way.
Has anyone got some suggestions to improve the memory usage?

Thanks in advance!

EDIT: I was overflowing the Int type. Solved like so:

def fibonacciIndex(numOfDigits: Int): Int = {
    lazy val bigFibs: LazyList[BigInt] = BigInt(0) #:: bigFibs.scanLeft(BigInt(1))(_ + _)
    bigFibs.indexWhere(_.toString.length == numOfDigits)
}
Solution

  • Let's run your program in parts.

    lazy val fibs: LazyList[Int] = 0 #:: fibs.scanLeft(1)(_ + _)
fibs.take(100).foreach(println)

    It prints:

    0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
-298632863
-1109825406
-1408458269
1776683621
368225352
2144908973
-1781832971
363076002
-1418756969
-1055680967
1820529360
764848393
-1709589543
-944741150
1640636603
695895453
-1958435240
-1262539787
1073992269
-188547518
885444751
696897233
1582341984
-2015728079
-433386095
1845853122
1412467027
-1036647147
375819880
-660827267
-285007387
-945834654
-1230842041
2118290601
887448560
-1289228135
-401779575
-1691007710
-2092787285
511172301
-1581614984
-1070442683
1642909629
572466946
-2079590721
-1507123775
708252800
-798870975
-90618175
-889489150

    As you can see integer overflows, and so it never outputs more than certain number of digits (11 I think including -). So it keep in computing next value.

    Additionally LazyList remembers each value that it computed. It is lazy but memoizes. So each new number that is computed here

    fibs.find(_.toString.length == numOfDigits)

    is also remembered. It continues until you run out of memory.

    To fix that you should replace LazyList with e.g. Iterator or Iterable and store numbers as BigInts.