3
\$\begingroup\$

This is a Swift program I wrote to calculate the sum of primes below 2 million, but it is tediously slow.

I am curious about what makes it so slow. My theory is that copying the filtered array is the heavy operation. Any other ideas on how to speed it up?

func initArray (p:Array<UInt32>)  -> Array<UInt32> {

    var arr = Array<UInt32>()
    arr.reserveCapacity(2000000)

    func isDiv(p:Array<UInt32>, val:UInt32) ->Bool {

        for i in p {

            if val % i == 0 {
                return true
            }
        }

        return false
    }

    for i:UInt32 in 2...2000000 {

        if !isDiv(p, val: i) {
            arr.append(i)
        }

    }

    return arr

}


var primes:Array<UInt32> = [2,3,5,7]

primes.reserveCapacity(20000)

var numbers = initArray(primes)

while numbers.count != 0 {
    numbers = numbers.filter( { return ($0 % primes[primes.count - 1] != 0 )} )

    if !numbers.isEmpty {
        primes.append(numbers[0])
    }

}


let result = primes.reduce(0, combine: +)

print (result)
\$\endgroup\$
2
  • \$\begingroup\$ Have a look at Project Euler #10 in Swift - Summation of primes. \$\endgroup\$ – Martin R Jun 7 '16 at 18:02
  • \$\begingroup\$ If the 12 milliseconds linked by Martin R are too slow for you then you can find 0,8 milliseconds in prime number summing still slow after using sieve over on Stack Overflow... In any case, the most important thing is that you remember 200_success's advice - if you want to do primes in bulk, fast, then Erastothenes is your man. To misquote Hoare: the Sieve of Eratosthenes was quite an improvement over all of its successors... \$\endgroup\$ – DarthGizka Jun 7 '16 at 19:41
1
\$\begingroup\$

Your algorithm is indeed slow because of the array copying.

I looked up some numbers on primes - number of primes below 2 million are 148000-something. You make a copy of at least that many numbers that many times. If you had a perfectly culled list of primes, you'd first filter and copy 148000 numbers, then 147999 numbers...

This is called a Triangular Number and can be calculated by (N*N)/2 + (N/2). So 148000 to the power of 2, divided by 2, plus 148000 divided by 2. Gives you 10,952,074,000. Each number is 4 bytes, so for all the primes below 2 million, you are shifting and copying 40 gigabytes of memory.

You should alter your algorithm to filter in place.


Another suggestion from a linked question is that all primes are expressible as "6x+1" or "6x-1", so you could use that to perhaps iterate over every 2nd number, or over every 6th number -+1.


Another idea I just thought of - if you're not gonna filter in place, STOP filtering after the first number multiplied by itself is bigger than 2 million. That way you stop before a 10000 iterations - this should vastly increase performance.

\$\endgroup\$
3
  • \$\begingroup\$ Quick question, I did consider using inplace removal but I thought that would lead to numerous amounts of array resizing making it even slower is that the case in swift? \$\endgroup\$ – JKRT Jun 8 '16 at 14:27
  • \$\begingroup\$ @JKT you should just limit the checking - once you're at 1415, all of the remaining numbers are prime. If anything was divisible by a higher number, it was also divisible by a lower number. This change alone should vastly speed things up, as now the upper limit on pumping memory would be (148000 + 1479999 + ... + 1478570) * 4. Or basically; only 8 gigabytes of data. \$\endgroup\$ – Pimgd Jun 8 '16 at 14:57
  • \$\begingroup\$ @JKT, you could set the found composite numbers to 0 instead of removing them from the array. (or use optionals and set them to nil) \$\endgroup\$ – overactor Jun 9 '16 at 7:33
3
\$\begingroup\$

This is a bit of a brute-force solution using trial division, with an optimization that you try dividing by just the previously discovered primes.

When you want to find many primes, though, a much faster algorithm is the .

\$\endgroup\$
5
  • \$\begingroup\$ Have a look at the main loop, he is filtering out all elements that are divisible by the highest found primes until there are no elements left. Then he adds the lowest number to the array of primes. Is that not exactly what the sieve of eratosthenes is? \$\endgroup\$ – overactor Jun 8 '16 at 7:26
  • \$\begingroup\$ This is a sieve, although there is a slight difference in when the filtering occurs. \$\endgroup\$ – Pimgd Jun 8 '16 at 7:49
  • 2
    \$\begingroup\$ @overactor But it is not the Sieve of Eratosthenes, an algorithm that involves no division operations at all. \$\endgroup\$ – 200_success Jun 8 '16 at 7:51
  • \$\begingroup\$ @200_success chat.stackexchange.com/transcript/message/30203536#30203536 \$\endgroup\$ – Pimgd Jun 8 '16 at 7:52
  • \$\begingroup\$ @200_success that seems like an implementation detail to me, but I get your point and see that that is likely why there is such a huge difference in performance. Perhaps you should make this explicit in your answer. \$\endgroup\$ – overactor Jun 9 '16 at 7:35
0
\$\begingroup\$

I did two revisions of the solution above, first I tried to use a mutable array to filter in place, although slightly faster on my machine it was not good enough.

Then I looked at the sieve of Sieve of Eratosthenes , it seemed very similar to the approach I came up with except that it did not involve trial division, and for this solution no array copy operation vastly increasing performance.

var numbers = Dictionary<Int,Bool>()

for i in  2...2000000 {
    numbers[i] = true
}


var max =  Int ( sqrt(Double(numbers.count)) )

for i in numbers.keys.sort().minElement()!...max {
    if numbers[i] == true {
        var j = i * i
        while(j <= numbers.count + 1) {
            numbers[j] = false
            j += i
        }
    }
}

var sum:IntMax = 0

for i in numbers.keys {

    if(numbers[i] == true) {
        sum += i
    }
}

print(sum)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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