CODEWITHSUNDEEP
go
Da Frenk
Da Frenk

Reputation: 295

Index suddenly out of range in Go

I am trying to implement an algorithm to find all primes below a certain limit. However, when the limit reaches 46350 i suddenly get an out of range error message:

panic: runtime error: index out of range

goroutine 1 [running]:
main.main()
    /tmpfs/gosandbox-433...fd004/prog.go:16 +0x1a8

Any help to point me to what is wrong here is appreciated (and were does this magic number 46350 come from?).

To reproduce drop the following code into googles sandbox and uncomment limit++ (or use this link):

package main

func main() {
    limit := 46349
    //limit++
    sieved_numbers := make([]bool, limit)
    var j = 0
    var i = 2

    for ; i < limit; i++ {
        if !sieved_numbers[i] {
            for j = i * i; j < limit;j += i {
                sieved_numbers[j] = true
            }
        }
    }
}

Upvotes: 2

Views: 276

Answers (3)

weberc2
weberc2

Reputation: 7908

i*i = 2148229801 when i==46349. A signed 32 bit integer can only reach ~2^31 (32 bits - 1 bit for the sign) before it becomes negative. Specifically, your variable would have taken on the value of (2^32)/2 - (46349^2) which is -746153.

If you'd like to perform this computation, try using an unsigned int or an int64.

package main

// import "fmt"

func main() {
    var limit uint
    limit = 46349
    limit++
    sieved_numbers := make([]bool, limit)
    var j uint = 0
    var i uint = 2

    for ; i < limit; i++ {
        if !sieved_numbers[i] {
            for j = i * i; j < limit; j += i {
                sieved_numbers[j] = true
            }
        }
    }
}

Try it on the playground

Upvotes: 4

Kara
Kara

Reputation: 6226

i * i produces a number which is greater than the maxiumum size of a 32 bit signed integer.

You should use a larger data type for j.

Read about integers on Wikipedia

Upvotes: 2

Jimmy Sawczuk
Jimmy Sawczuk

Reputation: 13614

Because when i == 46349, j = i * i overflows and you're left with a negative number. The loop condition is still true, but it's outside the boundaries of the array, so you get a panic.

Add a fmt.Println(i, j) as the first statement in your nested loop, and run it on your local machine (it'll time out on the sandbox) and you'll see it happen.

Upvotes: 9

Related Questions