Iterative Fibonacci number generator in Kotlin

Question

I have very limited experience in Java and slightly more in C# (just doing Advent of Code problems last month), so I'm not familiar with how to write idiomatic Kotlin.

This class implements an infinite generator for the Fibonacci sequence.

import java.math.BigInteger

class FibonacciGenerator {
    private var fibs = arrayListOf<BigInteger>(BigInteger.ZERO, BigInteger.ONE)
    fun get(idx: Int): BigInteger {
        while (fibs.size <= idx) {
            val nextNum: BigInteger = fibs[fibs.size - 1] + fibs[fibs.size - 2]
            fibs.add(nextNum)
        }
        return fibs[idx]
    }
}

Answer 1

A few points:

• It is common practice to create mutable list without specifying implementation details using mutableListOf. Also I'd expect LinkedList to perform better than ArrayList, but that is very JVM-specific - there is no linkedListOf, but you can create it using Java API and use it. ArrayList would have to constantly reallocate more memory as the list grows bigger and you are not really using advantages of it (fast access), since you are always accessing only last 2 items in the array.

• Get method name is pretty generic. It doesn't say if you always cache it, calculate, etc. Not sure what would be better - maybe calculateUntil, with parameter index or generateUntil, since you are using Generator suffix.

• In some cases you don't need to specify type, it is already assumed from the code:

  arrayListOf(BigInteger.ZERO, BigInteger.ONE)
  ...
  val nextNum = fibs[fibs.size - 1] + fibs[fibs.size - 2]
  

• Use .last() method for accessing last element in the list. Consider creating extension function for accessing second last to improve readability and for consistency reasons (that may be an overkill :) ):

  return fibs.last()
  

• If using last is not appropriate, you can use lastIndex property rather than fibs.size - 1.

• I'd rename fibs to something more obvious like calculatedList (or generated.

• I assume you never wanna reassign fibs, in that case var is not necessary and you can use val.

• Think is is good idea to extract the functionality, that adds new item to the sequence into a separate method.

Overall, I imagine final code to something close to this (not sure about naming):

import java.math.BigInteger


fun <T> List<T>.secondLast(): T {
    if (size < 2)
        throw NoSuchElementException("List is not big enough to return second last")
    return this[lastIndex - 1]
}

class FibonacciGenerator {
    private val generatedList = mutableListOf(BigInteger.ZERO, BigInteger.ONE)
    private fun addAnotherItem() {
        generatedList.add(generatedList.last() + generatedList.secondLast())
    }

    fun generateUntilIndex(index: Int): BigInteger {
        while (generatedList.size <= index) {
            addAnotherItem()
        }
        return generatedList[index]
    }
}