2

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
            }
        }
    }
}
0

3 Answers 3

9

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.

2
  • 1
    Oh boi what a stupid mistake. Thanks! Changing all variables to unit64 solve the issue.
    – Da Frenk
    Apr 4, 2013 at 21:47
  • Rather than use uint64, you can break from the i for-loop when i*i >= limit. This makes the code faster too! Apr 6, 2013 at 15:23
4

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

2

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.