f# sum a List of Int32 throws Arithmetic operation resulted in an overflow

Question

I'm trying to get the sum of all prime numbers from 0 to 2 000 000

this is my code:

let getPrimesUpTo (x : System.Int32) =
    let upperBound = Convert.ToInt32(Math.Sqrt(Convert.ToDouble(x)))

    let allNumbers = ref [1..x] in    
    for div = 2 to upperBound do allNumbers := List.filter (fun num -> (num % div <> 0 || div >= num)) !allNumbers    
    allNumbers

let sop = 
    let nums = !(getPrimesUpTo 2000000)
    List.sum nums

when I run it I get: "Arithmetic operation resulted in an overflow"

If I don't do List.sum I get the list of primes

score 3 · Answer 1 · answered May 24 '12 at 10:19

3

Presumably List.sum is going to try to sum the values to an Int32 value... and presumably the sum of the primes up to 2,000,000 is greater than Int32.MaxValue. I suspect Int64 would be okay though - so try just changing Convert.ToInt32 to Convert.ToInt64.

answered May 24 '12 at 10:19

Jon Skeet

1,421,763
867
9,128
9,194

and also, I get a List of Int32 numbers, the only problem is the List.Sum – Omu May 24 '12 at 10:24
@ChuckNorris: Without being familiar with F#, can you specify a transformation as part of the `List.sum` call? e.g. `List.sum nums Convert.ToInt64` – Jon Skeet May 24 '12 at 10:28
@JonSkeet - you could change to `List.sum (List.map int64 (!(getPrimesUpTo 2000000L))` – John Palmer May 24 '12 at 10:52

score 2 · Accepted Answer · edited May 23 '17 at 10:09

List.sum uses checked operators which throw on overflow. You can chase this through the source

List.sum calls Seq.sum
Seq.sum calls Checked.(+)

Checked.(+) throws an error on overflow. Side note: This is why List.Fold (+) is faster than List.sum

To fix this you would need to change your code to use 64 bit ints (which should be big enough), I also tidied up the conversion between double and int

let getPrimesUpTo (x : int64) =
    let upperBound = x |> float |>sqrt |> int64

    let allNumbers = ref [1L..x]    
    for div in 2L..upperBound do allNumbers := List.filter (fun num -> (num % div <> 0L || div >= num)) !allNumbers    
    allNumbers

let sop = 
    let nums = !(getPrimesUpTo 2000000L)
    List.sum nums

This method for calculating primes is very inefficient. I have written some quite good code to calculate large numbers of primes in F# - see here https://stackoverflow.com/a/8371684/124259

f# sum a List of Int32 throws Arithmetic operation resulted in an overflow

2 Answers2