Computer Science Teacher
Computer Science Teacher - Thoughts and Information from Alfred Thompson

May, 2009

  • Computer Science Teacher - Thoughts and Information from Alfred Thompson

    Prime Numbers, Code Challenges, and Programming Languages

    • 4 Comments

    Clint Rutkas and I have some friendly back and forth about a couple of things. One is the worth of Visual Basic as a programming language and the other is over who is the better coder. Don’t tell Clint but I have a secret suspicion that he may be the better coder (because he is in his prime and I am past mine) but I will never give up on Visual Basic. In any case we have been talking about a small coding challenge to complicate the discussion. After all facts seldom solve anything but they do add to the discussion. Someone suggested that we both write a program to find the next prime number after 2.2 billion. Sounded like fun to us so we went at it. Now let the discussion begin.

    My solution was written in Visual Basic – of course. Clint’s in C# – not a bad choice at all. Clint went for complication and sophistication (there is an option to use threading in his) while I went for simple, basic and old school. My code looks like this:

     Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
            Dim i As Long
            Dim timePerParse As Stopwatch
            Dim ticksThisTime As Long = 0
    
            timePerParse = Stopwatch.StartNew()
            For i = Val(txtStart.Text) To Val(txtEnd.Text) ‘ Could use Step 2 here
                If IsPrime(i) Then
                    Exit For
                End If
            Next
    
            timePerParse.Stop()
            ticksThisTime = timePerParse.ElapsedTicks
            Dim ts As TimeSpan = timePerParse.Elapsed
            lblPrime.Text = i.ToString("###,###,###,###")
            lblTime.Text = ts.TotalMilliseconds
    
    
        End Sub
        Function IsPrime(ByVal n As Long) As Boolean
            If (n Mod 2 = 0) Then Return False
            If (n < 2) Then Return False
            If (n < 4) Then Return True
    
    
            Dim iMax As Long = Math.Sqrt(n) + 1
            Dim i As Integer
            For i = 3 To iMax Step 2
                If (n Mod i = 0) Then Return False
            Next
            Return True
        End Function

    The primary optimization is the line that uses the square root of n plus 1 to set the bounds of the loop that brut forces through finding if the number is divisible by something. I use the StopWatch object (I blogged about that some time ago) for the timing. I also display the results outside the timed area because I/O takes too much time and isn’t really part of the problem anyway. I played with using Step 2 to pass half as many numbers through the IsPrime function but that didn’t seem to make a whole lot of difference in the time. I was surprised by that and want to look into that some more. It may be that the first compare in the IsPrime function may be faster than I expected or perhaps the compiler is doing some behind the scenes optimization. I’d have to look at the generated IL (Intermediate Language) code to really know for sure.

    So what do you think? Is Clint’s code better? How do you define “better” when comparing code like this?

  • Computer Science Teacher - Thoughts and Information from Alfred Thompson

    Interesting Links May 4th 2009

    • 2 Comments

    I haven’t been twittering much for a while. Most of last week I was at sea on the conference which was not conducive to regular Twittering or anything else on the Internet. But since then I have been catching up on blog reading and other things and I have a few interesting and hopefully useful links to share today.

    Fun training against phishing scams http://phishguru.org/ I wonder if teachers need this as much (or more?) than their students? This is from a research project at Carnegie Mellon and I have blogged about it before but it deserves to be brought up again.

    One of the things I have in my queue to watch when things settle down this week is this Introduction to F# on Channel 9's 10-4 show. If you are at all interested in functional languages you may want to check it out. There are a lot of useful  F# links at that page as well.

    64 things a geek should know  I know quite a few of them but nowhere near all 64. You? How about your students? Anything you think should be on this list? Or dropped from it?

    I found an interesting post titled Attracting Young Women and Minorities To Computing on the CSTA blog this week as well. Looks like regional CSTA chapters are starting to spring up and one of them is in southern New Jersey. There is a list of chapters at the CSTA web site. Anyone interested in getting one going in New Hampshire or Massachusetts? I’d love to help.

    I also recommended the the Are You Certifiable web site during the week.

    My friend Hilary Pike blogged about 10 Programming Proverbs Every Software Student Should Know. Compare that with my series on programming proverbs I wrote some time ago. Looking at things from a different angle is often a good thing. I’m sure that Hilary would welcome your comments there as much as I welcome them here. Hilary is also on twitter at @HilaryP

Page 6 of 6 (17 items) «23456