[RESOLVED] [2008] Sieve_of_Eratosthenes

[dbasnett]

the attached project has two methods of calculating primes. the one using linq appears to run faster but... it is noticeable only when calculating large number of primes i.e. the primes between 1 and 1,000,000. i don't understand the odd behavior of the linq method.

Sieve_of_Eratosthenes.zip

[wy125]

That's a cool way of utilizing LINQ. I never would have thought of that.

One thing I notice is that when you're using the non-LINQ method you 'cross-out' some non-primes repeatedly. For example, when you start off with 2 you cross out 2, 4, 6, 8, ... by assigning the corresponding index in thePrimes to -1. But when you go by 3, you will cross out 3, 6, 9, 12, 15, 18 ... half of which were already crossed out when you did the multiples of 2. This is true for other numbers too. With the LINQ method once a number is removed as a prime it's gone for good.

We need to write the non-LINQ method in a way that doesn't recheck numbers that have already been determined to be nonprime.

EDIT: I didn't even ask but I assumed that the odd behavior was that the LINQ method ran significantly faster. Is that what you meant?

[dbasnett]

on my pc the linq method, according to the stopwatch, ran significantly faster, but the overall time was significantly slower. that was what i found to be odd.

[dbasnett]

i also noticed that linq code produced:
2,3,5,7 for the prime numbers from 1 - 6

[MaximilianMayrhofer]

I had the same experience:

No LINQ
Execution - 70ms
Total Time - 2s

LINQ
Execution - 12ms
Total Time 15s

[dbasnett]

@max - that is what i saw.

[Jenner]

The loss of speed happens when you collapse the IEnumerable in the line:
Label1.Text = searchnumbers.Count.ToString("N0")

Remember, LINQ uses lambdas to define itself. Lambdas are just meta-code until you evaluate it.
All that LINQ is essentially setting up the structure of meta code to be processed. The actual processing and filling of the IEnumerable doesn't come until you do something with it.

[dbasnett]

as a function

    'Sieve of Eratosthenes 
    'http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 
    '1. Create a contiguous list of numbers from two to some highest number n. 
    '2. Strike out from the list all multiples of two (4, 6, 8 etc.). 
    '3. The list's next number that has not been struck out is a prime number. 
    '4. Strike out from the list all multiples of the number you identified in the previous step. 
    '5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list). 
    '6. All the remaining numbers in the list are prime. 
    Private Function Sieve_of_Eratosthenes(ByVal MaxNum As Integer) As List(Of Integer)
        'tested to MaxNum = 10,000,000 - on 1.8Ghz Laptop it took 1.4 seconds
        Dim thePrimes As New List(Of Integer)
        Dim toNum As Integer = MaxNum, stpw As New Stopwatch
        If toNum > 1 Then 'the first prime is 2
            stpw.Start()
            thePrimes.Capacity = toNum 'size the list
            Dim idx As Integer
            Dim stopAT As Integer = CInt(Math.Sqrt(toNum) + 1)
            '1. Create a contiguous list of numbers from two to some highest number n.
            '2. Strike out from the list all multiples of 2, 3, 5. 
            For idx = 0 To toNum
                If idx > 5 Then
                    If idx Mod 2 <> 0 _
                    AndAlso idx Mod 3 <> 0 _
                    AndAlso idx Mod 5 <> 0 Then thePrimes.Add(idx) Else thePrimes.Add(-1)
                Else
                    thePrimes.Add(idx)
                End If
            Next
            'mark 0,1 and 4 as non-prime
            thePrimes(0) = -1
            thePrimes(1) = -1
            thePrimes(4) = -1
            Dim aPrime, startAT As Integer
            idx = 7 'starting at 7 check for primes and multiples 
            Do
                '3. The list's next number that has not been struck out is a prime number. 
                '4. Strike out from the list all multiples of the number you identified in the previous step. 
                '5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list). 
                If thePrimes(idx) <> -1 Then ' if equal to -1 the number is not a prime
                    'not equal to -1 the number is a prime
                    aPrime = thePrimes(idx)
                    'get rid of multiples 
                    startAT = aPrime * aPrime
                    For mltpl As Integer = startAT To thePrimes.Count - 1 Step aPrime
                        If thePrimes(mltpl) <> -1 Then thePrimes(mltpl) = -1
                    Next
                End If
                idx += 2 'increment index 
            Loop While idx < stopAT
            '6. All the remaining numbers in the list are prime. 
            thePrimes = thePrimes.FindAll(Function(i As Integer) i <> -1)
            stpw.Stop()
            Debug.WriteLine(stpw.ElapsedMilliseconds)
        End If
        Return thePrimes
    End Function

[dbasnett]

i commented out the count. now it seems that this has the same issue

            ListBox1.BeginUpdate()
            For Each i As Integer In searchnumbers
                ListBox1.Items.Add(i)
            Next
            ListBox1.EndUpdate()

[wy125]

On my machine

NO LINQ

Execution Time: 25 ms
Total Time: 1.1 seconds


LINQ

Execution Time: 76 ms
Total Time: 7.8 seconds

EDIT: Brain Fart (not enough coffee numbers were reversed, I just fixed it)