## How to optimize?

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

### How to optimize?

I was a bit confused at first when this code:

Code: Select all

`t1 = timerdo 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 ifloopt2=timer`

ran faster then this code:

Code: Select all

`  t1 = timerdo 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 ifloopt2=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

`clsConst FALSE = 0const TRUE = not FALSEconst MOST = 100000dim primeList(1 to most) as integerdim as integer num,cMaxIndx,x,rdim as integer Primedim as string kdim as double t1,t2num = 1cMaxIndx = 1primeList(1)=2print "ready to go"print "-----------"sleept1 = timerdo 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 ifloopt2=timerprint "done"print "found ";cMaxIndx;" prime numbers."print "Time: ";t2-t1;" seconds.print "The 1000th prime is: ";primeList(1000)dim as integer ff=freefileopen "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-t1close #fsleep`
Sterling Christensen
Posts: 142
Joined: May 27, 2005 6:13
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 = cMaxIndxfor x = 1 to smallerMax    if (num Mod primeList(x)=0) then        Prime = FALSE        exit for    end ifnext 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
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:
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
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'FoldclsConst FALSE = 0const TRUE = not FALSEdim primeList(1 to most) as integerdim as integer num,cMaxIndx,x,lcountdim as integer Primedim as double t1,t2,rdim as integer flcount = 0num = 1cMaxIndx = 1primeList(1)=2print "ready to go"print "-----------"sleept1 = timer'END FOLDdo 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 ifloop'FOLDt2=timerprint "done"print "found ";cMaxIndx;" prime numbers."print "Time: ";t2-t1;" seconds."print "The last prime found was: ";primeList(most)f=freefileopen 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 xclose #fsleep'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
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:
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 PConst 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 arrayDim Shared BitsArray(0 To Max32) As uIntegerDim As uInteger n1, n2, count, p, o, n1x2, n1x3Dim 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_stepDim As Integer prime_to_find = 1000Dim As uInteger powers(0 To 31)Dim As Integer iFor i = 0 To 31  powers(i) = 1 shl iNext icount = 4 ' start count offset to account for 2, 3, 5 and 7 being primen1 = 11   ' start at 11 due to count starting at 4While 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 = 0Wend`
Antoni
Posts: 1393
Joined: May 27, 2005 15:40
Location: Barcelona, Spain

### Re: How to optimize?

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...