How to optimize?

General FreeBASIC programming questions.
Paragon
Posts: 131
Joined: Sep 09, 2005 19:17
Location: Temple University, Philly pa

How to optimize?

Postby Paragon » Nov 15, 2006 6:17

I was a bit confused at first when this code:

Code: Select all

t1 = timer
do while primeList(most) = 0
   Prime=TRUE
   num += 2
   for x = 1 to cMaxIndx
        if (num mod primeList(x)=0) then
           Prime=FALSE
           exit for
        end if
  next x
  if Prime then
     cMaxIndx += 1
     primeList(cMaxIndx)=num
  end if
loop
t2=timer


ran faster then this code:

Code: Select all

  t1 = timer
do while primeList(most) = 0
   Prime=TRUE
   num += 2
    r = (num \ 2)+1
   for x = 1 to cMaxIndx
        if (num mod primeList(x)=0)  and x < r then
           Prime=FALSE
           exit for
        end if
  next x
  if Prime then
     cMaxIndx += 1
     primeList(cMaxIndx)=num
  end if
loop
t2=timer


It actually ran MUCH faster. Finding the first 100000 prime numbers using method 1 took ~85 seconds while the second took ~170 seconds, shortcutting even futher by only going up to the sqroot of num (instead of half of num) took even LONGER... ~180 seconds. The less number of loops i tried to do the longer the program took!

I figure it must be something about checking two conditions per loop is slower then checking one condition many more times... but
A) Won't this eventually flip as the growth of checks increases, how to tell when this flip will occur?

and B) How to optimize further? Obviously adding a third check to see if that point has been reached will not help as that will only slow it down even more before that threshold is reached AND that threshold would increase.

I am going to try to test a few more things.... such as figuring out exactly how many more times the loop is being done for each method and stuff.

The code in its entierty is here:

Code: Select all

cls
Const FALSE = 0
const TRUE = not FALSE
const MOST = 100000
dim primeList(1 to most) as integer
dim as integer num,cMaxIndx,x,r
dim as integer Prime
dim as string k
dim as double t1,t2

num = 1
cMaxIndx = 1
primeList(1)=2
print "ready to go"
print "-----------"
sleep
t1 = timer
do while primeList(most) = 0
'k = inkey$
'if k = "q" then exit do   
   Prime=TRUE
   num += 2
   'r = (num \ 2)+1          
   for x = 1 to cMaxIndx
        if (num mod primeList(x)=0) then '  and x < r then
           Prime=FALSE
           exit for
        end if
  next x
  if Prime then
     cMaxIndx += 1
     primeList(cMaxIndx)=num
     '? num; " is prime."
  end if
loop
t2=timer
print "done"
print "found ";cMaxIndx;" prime numbers."
print "Time: ";t2-t1;" seconds.
print "The 1000th prime is: ";primeList(1000)
dim as integer f
f=freefile
open "d:\dev\freebasic\fbedit\myprojects\primes\pList.txt" for output as #f
   for x=1 to most
    print #f, primeList(x)
   next x
   print #f, t2-t1
close #f
sleep
Sterling Christensen
Posts: 142
Joined: May 27, 2005 6:13

Postby Sterling Christensen » Nov 15, 2006 6:29

One of the best ways to optimize code like that is to move things out of inner loops. Like the "And x < r" part:

Code: Select all

if r < cMaxIndx then smallerMax = t else smallerMax = cMaxIndx
for x = 1 to smallerMax
    if (num Mod primeList(x)=0) then
        Prime = FALSE
        exit for
    end if
next x


And all primes are odd, so you can skip even numbers with a "Step 2" on the For.
Paragon
Posts: 131
Joined: Sep 09, 2005 19:17
Location: Temple University, Philly pa

Postby Paragon » Nov 15, 2006 7:44

And all primes are odd


I am already only testing odd numbers. However with further tests I found out some weird stuff going on.

Ok a, i must admit to being dumb...
If (num Mod primeList(x)=0) And x < r Then
-should have been -
if (primeList(x)>r) then exit for
if (num mod primeList(x)=0 then

So i guess it was a logic thing... um... *looks around bashfully*

The new code spit out 100000 in ~50 seconds almost 26 seconds faster then the old way and almost 40 seconds faster then the bad logic way.
jofers
Posts: 1525
Joined: May 27, 2005 17:18
Contact:

Postby jofers » Nov 15, 2006 8:01

Supposedly, a number should have no factors larger than its square root (because if you can factor a larger number, the other factor will be smaller than its square root).
Paragon
Posts: 131
Joined: Sep 09, 2005 19:17
Location: Temple University, Philly pa

Postby Paragon » Nov 15, 2006 8:13

Whoa... ok...
Seems I made another bone head mistake with that last iteration... turns out i was still using num/2 as the kickout... changed it to sqr(num) and i got 100000 primes in less then half a second.

Final code (i think):

Code: Select all

const fileName = "PrimeNumbers.txt"
const MOST = 100000

'Fold
cls
Const FALSE = 0
const TRUE = not FALSE
dim primeList(1 to most) as integer
dim as integer num,cMaxIndx,x,lcount
dim as integer Prime
dim as double t1,t2,r
dim as integer f

lcount = 0
num = 1
cMaxIndx = 1
primeList(1)=2

print "ready to go"
print "-----------"
sleep
t1 = timer

'END FOLD

do while primeList(most) = 0
   Prime=TRUE
   num += 2
   r = sqr(num)+1
  for x=1 to cMaxIndx
      if primeList(x)>r then exit for
        if (num mod primeList(x)=0) then
           Prime=FALSE
           exit for
        end if
     next x
  if Prime then
     cMaxIndx += 1
     primeList(cMaxIndx)=num
  end if
loop

'FOLD
t2=timer
print "done"
print "found ";cMaxIndx;" prime numbers."
print "Time: ";t2-t1;" seconds."
print "The last prime found was: ";primeList(most)
f=freefile
open FILENAME for output as #f
   print #f, MOST; " primes found."
   print #f, "The loop ran "; lcount; " times."
   print #f, "In ";t2-t1; " Seconds."
   for x=1 to most
    print #f, primeList(x)
   next x
close #f
sleep
'END FOLD



Man... I was WAAAYYY of with that first post... sry bout all the posting and junk.
1000101
Posts: 2556
Joined: Jun 13, 2005 23:14
Location: SK, Canada

Postby 1000101 » Nov 15, 2006 13:34

You could try testing against this method too.

Code: Select all

   Function IsPrime( ByVal Value As UInteger ) As UInteger
     
      Dim X As Long
     
      If ( Value <> 2 And ( Value And 1 ) = 0 ) Then Return FALSE 'test if div 2
      If ( Value <> 3 And Value Mod 3 = 0 ) Then Return FALSE   'test if div 3
      For X = 6 To Sqr( X ) Step 6
         If Value Mod ( X - 1 ) = 0 Then Return FALSE
         If Value Mod ( X + 1 ) = 0 Then Return FALSE
      Next X
     
      Return TRUE
     
   End Function
yetifoot
Posts: 1710
Joined: Sep 11, 2005 7:08
Location: England
Contact:

Postby yetifoot » Nov 15, 2006 22:08

Heres some code I entered for a contest on QBN recently, it gets the 1 millionth prime in just under a second here, Antoni came up with something even faster though If i remember correctly, this shows a whole bunch of methods i played with.

Code: Select all

Const MaxPrime = 1000000             ' The max value for P
Const MaxVal   = MaxPrime * 16       ' The max value for N (a bit of a cheat using * 16...)
Const Max32    = (MaxVal \ 32) + 1   ' The number of 32-bit vars needed to store bit array

Dim Shared BitsArray(0 To Max32) As uInteger
Dim As uInteger n1, n2, count, p, o, n1x2, n1x3
Dim As uInteger steps(0 To 47) = { _
 2,  4,  2,  4,  6,  2,  6,  4,  2,  4,  6,  6,  2,  6,  4,  2, _
 6,  4,  6,  8,  4,  2,  4,  2,  4,  8,  6,  4,  6,  2,  4,  6, _
 2,  6,  6,  4,  2,  4,  6,  2,  6,  4,  2,  4,  2, 10,  2, 10  _
} ' This lookup table is used to calculate the step, to avoid multiples of 2, 3, 5, and 7
  ' any more that that and the table becomes very large (the one inc. 11 is 480 entrys)
Dim As Integer curr_step
Dim As Integer prime_to_find = 1000
Dim As uInteger powers(0 To 31)
Dim As Integer i

For i = 0 To 31
  powers(i) = 1 shl i
Next i

count = 4 ' start count offset to account for 2, 3, 5 and 7 being prime

n1 = 11   ' start at 11 due to count starting at 4
While n1 <= MaxVal
  p = n1 shr 5  ' \ 32      'p is integer postition in bitarray
  o = n1 and 31 ' mod 32    'o is bit offset
  If (BitsArray(p) AND powers(o)) = 0 Then ' If the bit isn't set then it hasn't been struck out
    count += 1
    If count = prime_to_find Then
      Print Using "###,###,###th prime - ###,###,###"; prime_to_find; n1
      If prime_to_find = 1000000 Then Exit While
      prime_to_find *= 10
    End If
    If n1 <= (sqr(MaxVal) + 1) Then ' Only strike out multiples of primes <= sqr(MaxVal)
      n1x2 = n1 + n1                ' (the +1 is just to account for any rounding, may not
      n1x3 = n1 * n1             '  be needed?)
      ' we don't need to step by n1, as that will wastefully look at even numbers (odd+odd=even)
      ' same goes for start pos, can start at n^2
      For n2 = n1x3 To MaxVal Step n1x2  ' work from n^2 to max marking off multiples
        p = n2 shr 5  ' \ 32      'p is integer postition in bitarray
        o = n2 and 31 ' mod 32    'o is bit offset
        BitsArray(p) OR= powers(o) ' Set the bit to show its bad
      Next n2
    End If
  End If
  ' we can step by set amounts, to avoid multiples of 2, 3, 5, and 7
  n1 += steps(curr_step)
  curr_step += 1
  If curr_step = 48 Then curr_step = 0
Wend
Antoni
Posts: 1393
Joined: May 27, 2005 15:40
Location: Barcelona, Spain

Re: How to optimize?

Postby Antoni » Nov 15, 2006 22:32

First of all, use the best method you can afford.

The contest at QBN yetifoot is talking about is at http://forum.qbasicnews.com/viewtopic.php?t=12403
The sieve in my last post there goes up to 1,300,000,000 int 75 seconds in my old P4 1.4. but it requires a lot of memory.

And a C Atkin' sieve I don't dare to translate to FB because I don't understand it can do it in 8 seconds...

Return to “General”

Who is online

Users browsing this forum: No registered users and 9 guests