Large array indexes scala

Question

(Language: scala)

I have a problem where I want to iterate over 1 million numbers, but for some reason I get an arrayindexOutofbounds exception. The function I am using works perfectly for 100 000 numbers, but I get the exception if I add a zero.

There cannot be a problem with the array size, because I have built a sort of flex-array, where the array is about 1000 elements and each element consists of a list of elements.

So the problem looks something like this:

for (x <- 1 to 1000000) {
  // Do a thing
  }     

Can for loops only handle a certain number of elements?

I have tried running the program with the "extra-space-flag"

I include the whole code below for reference, in case it makes a difference

object Problem14 {

  class FlexArray (n : Int){
    var array = new Array[List[Tuple2[Int, Int]]](n)
    val size = n

    for(x <- 0 until size) {
      array(x) = List()
    }

    def insert (n : Int, value : Int) {
      if (find(n) != -1) {
     val i = n % size
     array(i) = (n, value) :: array(i)
      }
    }

    def read (i : Int) : List[Tuple2[Int, Int]] = {
      (array(i))
    }

    def findAux (list : List[Tuple2[Int, Int]], n : Int) : Int = {
      if (list == Nil) {
    -1
      } else {
    val (num, value) = list.head
    if (n == num) {
      value
    } else {
      findAux(list.tail, n)
    }
      }
    }

    def find (n : Int) : Int = {
      val i = n % size
      findAux(array(i), n)
    }
  }

  var accArray = new FlexArray(10000)


// denna funktion bör kallas med 1 som andra argument
  def chainLength (n : Int, acc : Int) : Int = {
    if (n == 1) 
      acc
    else {
      val value = accArray.find(n)
    if (value != -1) 
  acc + value 
    else if (n % 2 == 0)
  chainLength(n/2, acc+1)
    else
  chainLength(3*n+1, acc+1)      
    }
  }



 def main(args: Array[String]) {
    var max = 0
    var maxnum = 0

    for (x <- 1 to 1000000) {
      var value = chainLength(x, 1)
      accArray.insert(x, value)
      if (max < value) { 
    max = value
    maxnum = x
      }      

    println(maxnum + ": " + max)

}

}

Answer 1

The problem isn't with array indexes, scala functions just like java and will go to Int.MaxValue 2,147,483,647. The problem is with this line of in your chainLength function:

chainLength(3 * n + 1, acc + 1)

Since chainLength is recursive on itself switching between n/2 and n * 3 + 1 you run into this with numbers larger than 113383. It leads to integer overflow so you end up with a negative value passed to the array index which throws your error. I'm guessing you'll need to add some integer overflow handling to your function.

Full output of calls to chainLength in chainLength(113383, 1) (it ends with overflow at the bottom):

Starting at 113383
3 * 113383 + 1 = 340150
340150 / 2 = 170075
3 * 170075 + 1 = 510226
510226 / 2 = 255113
3 * 255113 + 1 = 765340
765340 / 2 = 382670
382670 / 2 = 191335
3 * 191335 + 1 = 574006
574006 / 2 = 287003
3 * 287003 + 1 = 861010
861010 / 2 = 430505
3 * 430505 + 1 = 1291516
1291516 / 2 = 645758
645758 / 2 = 322879
3 * 322879 + 1 = 968638
968638 / 2 = 484319
3 * 484319 + 1 = 1452958
1452958 / 2 = 726479
3 * 726479 + 1 = 2179438
2179438 / 2 = 1089719
3 * 1089719 + 1 = 3269158
3269158 / 2 = 1634579
3 * 1634579 + 1 = 4903738
4903738 / 2 = 2451869
3 * 2451869 + 1 = 7355608
7355608 / 2 = 3677804
3677804 / 2 = 1838902
1838902 / 2 = 919451
3 * 919451 + 1 = 2758354
2758354 / 2 = 1379177
3 * 1379177 + 1 = 4137532
4137532 / 2 = 2068766
2068766 / 2 = 1034383
3 * 1034383 + 1 = 3103150
3103150 / 2 = 1551575
3 * 1551575 + 1 = 4654726
4654726 / 2 = 2327363
3 * 2327363 + 1 = 6982090
6982090 / 2 = 3491045
3 * 3491045 + 1 = 10473136
10473136 / 2 = 5236568
5236568 / 2 = 2618284
2618284 / 2 = 1309142
1309142 / 2 = 654571
3 * 654571 + 1 = 1963714
1963714 / 2 = 981857
3 * 981857 + 1 = 2945572
2945572 / 2 = 1472786
1472786 / 2 = 736393
3 * 736393 + 1 = 2209180
2209180 / 2 = 1104590
1104590 / 2 = 552295
3 * 552295 + 1 = 1656886
1656886 / 2 = 828443
3 * 828443 + 1 = 2485330
2485330 / 2 = 1242665
3 * 1242665 + 1 = 3727996
3727996 / 2 = 1863998
1863998 / 2 = 931999
3 * 931999 + 1 = 2795998
2795998 / 2 = 1397999
3 * 1397999 + 1 = 4193998
4193998 / 2 = 2096999
3 * 2096999 + 1 = 6290998
6290998 / 2 = 3145499
3 * 3145499 + 1 = 9436498
9436498 / 2 = 4718249
3 * 4718249 + 1 = 14154748
14154748 / 2 = 7077374
7077374 / 2 = 3538687
3 * 3538687 + 1 = 10616062
10616062 / 2 = 5308031
3 * 5308031 + 1 = 15924094
15924094 / 2 = 7962047
3 * 7962047 + 1 = 23886142
23886142 / 2 = 11943071
3 * 11943071 + 1 = 35829214
35829214 / 2 = 17914607
3 * 17914607 + 1 = 53743822
53743822 / 2 = 26871911
3 * 26871911 + 1 = 80615734
80615734 / 2 = 40307867
3 * 40307867 + 1 = 120923602
120923602 / 2 = 60461801
3 * 60461801 + 1 = 181385404
181385404 / 2 = 90692702
90692702 / 2 = 45346351
3 * 45346351 + 1 = 136039054
136039054 / 2 = 68019527
3 * 68019527 + 1 = 204058582
204058582 / 2 = 102029291
3 * 102029291 + 1 = 306087874
306087874 / 2 = 153043937
3 * 153043937 + 1 = 459131812
459131812 / 2 = 229565906
229565906 / 2 = 114782953
3 * 114782953 + 1 = 344348860
344348860 / 2 = 172174430
172174430 / 2 = 86087215
3 * 86087215 + 1 = 258261646
258261646 / 2 = 129130823
3 * 129130823 + 1 = 387392470
387392470 / 2 = 193696235
3 * 193696235 + 1 = 581088706
581088706 / 2 = 290544353
3 * 290544353 + 1 = 871633060
871633060 / 2 = 435816530
435816530 / 2 = 217908265
3 * 217908265 + 1 = 653724796
653724796 / 2 = 326862398
326862398 / 2 = 163431199
3 * 163431199 + 1 = 490293598
490293598 / 2 = 245146799
3 * 245146799 + 1 = 735440398
735440398 / 2 = 367720199
3 * 367720199 + 1 = 1103160598
1103160598 / 2 = 551580299
3 * 551580299 + 1 = 1654740898
1654740898 / 2 = 827370449
3 * 827370449 + 1 = -1812855948