none
Seive of Eratosthenes Algorithm RRS feed

  • General discussion

  • Hi,
    I just recently discovered Small Basic. It takes me back to the days in Junior High school learning to code in BASIC on an 8K Commodore PET! Those were the days!  I still remember spending hours cutting out whitespace in code to squeeze in "just a few more lines"! Great work guys. Even though I code mainly for fun and do most of my coding in C++ or C#, I have always loved the ease of whipping together a quick BASIC program to test algorithm ideas.
    I put together this little program to give some of the Small Basic features a test drive. It does a Seive of Eratosthenes sift for Prime numbers from 2 to 120,000. It represents the ongoing results of the Seive graphically with each pixel representing one integer. At the end, if the pixel is still white, it represents a Prime Number. It is very memory intensive since you need an array with 120,000 elements, but works just fine. It takes about 2 and a half minutes to run on my 2.4 Ghz P4 machine. (Note this is due to the graphics processing overhead. A TextWindow version I wrote takes only 8 seconds to do the same sift and print all the found Primes!) So without further ado, here is my code. Hope you like it and for you beginners out there, it demonstrates many of the features of Small Basic.

    'Seive of Eratosthenes
    'Written by Ed Dunaway
    '****************************************************************
    ' This program shows a graphical representation of the Seive of Eratosthenes
    'method of finding prime numbers. Each integer is represented as 1 pixel.
    'As the algorithm eliminates a number as not a Prime, it's representative
    'pixel is set to black. The top row represents 0 - 399, the next row is 400 -799
    'and so forth.

    'It is actually a very fast, but very memory intensive way of finding all
    'prime numbers from 2 to N.

    'The Seive works by starting with 2, the lowest prime number,
    'and then eliminating all multiples of 2 from the list. Then you go to the
    'next lowest prime remaining (which would be 3, and repeat, eliminating
    'all multiples of three.

    ' After each loop, the next lowest number will be a prime number
    'and you eliminate all multiples of that number.

    'Continue until you get to the square root of N, after which your list
    'will only contain Prime Numbers.

    'On a side note, this takes about 2 and a half minutes to finish on
    'my computer. This is due to all the graphics. The same algorithm
    'without the graphical representation can find and print all primes
    'from 2 to 120,000 in just 8 seconds.
    '****************************************************************
    screenWidth = 400
    screenHeight = 400

    GraphicsWindow.Width = screenWidth
    GraphicsWindow.Height = screenHeight
    GraphicsWindow.BackgroundColor = "White"

    'Set N = width * (height - 100) ( bottom 100 pixels reserved for text)
    N = screenWidth * (screenHeight - 100)

    'Get Starting time in Minutes and Seconds'
    minute = Clock.Minute
    second = Clock.Second

    'Set Array prime[0] and  prime[1] to 0. 0 and 1 are not prime by definition.'

    Array.SetValue("prime",0,0)
    GraphicsWindow.SetPixel(0,0,"Black")
    Array.SetValue("prime",1,0)
    GraphicsWindow.SetPixel(1,0,"Black")

    'Initialize all the rest of the numbers to -1. If they are still -1 at the end,
    'then they are Prime numbers.
    for i=2 to N
      Array.SetValue("prime",i,-1)
    EndFor
    'The heart of the Seive. Checks all numbers from 2 to the Square Root of  N.
    for i=2 to Math.SquareRoot(N)
    'erase text area
      GraphicsWindow.BrushColor = "White"
      GraphicsWindow.FillRectangle(5,325,350,25)
      GraphicsWindow.BrushColor = "Black"
      
    'show which number we are removing multiples of
       GraphicsWindow.DrawText(5,325,"Removing Multiples of " + i)
      
       isPrime = Array.GetValue("prime",i)
      
    ' i at this point is the lowest Prime number left in the Array.
      if isPrime = -1 then
     
    ' we start eliminating multiples of i at i*i since any non-Prime number smaller
    ' than that has already been eliminated.
        for k=i*i to N step i

    'eliminate k from the list since it is a multiple of i.
          Array.SetValue("prime",k,0)

    'get x and y values to eliminate graphically
          y = Math.Floor(k/screenWidth)
          x = Math.Remainder(k,screenWidth)
          GraphicsWindow.SetPixel(x,y,"Black")
         
       EndFor
      EndIf
    EndFor

    'Get ending time for time elapsed calculation
    minute = Clock.Minute - minute
    second = Clock.Second - second
    time = 60 * minute + second

    'erase text area
    GraphicsWindow.BrushColor = "White"
    GraphicsWindow.FillRectangle(5,325,350,25)
    GraphicsWindow.BrushColor = "Black"

    'write out elapsed time.
    GraphicsWindow.DrawText(5,325,"Done!!!  " + time + "seconds")

    '*****************************************************
    Monday, March 30, 2009 1:32 AM

All replies

  • Hi Bodeddie,
    I have been looking through your code and would like to suggest a couple of efficiency improvements. It is actually quicker to use
     GraphicsWindow.FillRectangle(x,y,1,1)
     than
     GraphicsWindow.SetPixel(x,y,"Black")
     For an explanation of this see Vijaye's comments on the "star field" program in the "Post your sample source code here and get featured on our blogs!" thread.
     I didn't bother changing the 0 and 1 pixels but when used in a loop it makes a difference.
     
     GraphicsWindow.DrawRectangle(x,y,1,1) doesn't work as it draws a border around the rectangle which means the whole area goes black while eliminating multiples of 2.

    As all graphics commands are inherently slow (because of the processing you don't see going on in the background) it's better to only draw something if it needs to be drawn. i.e. don't draw it if it's already there. I used this principle to test each number to see it it was already non-prime and didn't draw it if it was. This speeded up the process considerably. The results on my PC are given below.

    127 seconds using SetPixel
    119 seconds with FillRectangle
    55 seconds with FillRectangle only when necessary

    Import PXZ131 for the code with the changes.

    Saturday, April 4, 2009 4:01 PM
  • Nice optimizations, Stendec. 
    Sunday, April 5, 2009 8:47 PM
    Moderator