How Fast Does this Run? A Real-World Example

How Fast Does this Run? A Real-World Example!

The greatest common divisor (GCD) of two integers is the largest integer that divides both integers with no remainder. For example, the GCD of 6 and 9 is 3. The numbers 1 and 3 both divide the numbers 6 and 9 (see Table 7 ). The greatest of these is 3.

Table 7: Numbers divisible by 6 and 9.

Number	Divides 6	Divides 9	Divides Both
1	6	9	Yes
2	3	4 remainder 1	No
3	2	3	Yes
4	1 remainder 2	2 remainder 1	No
5	1 remainder 1	1 remainder 4	No
6	1	1 remainder 3	No
7	0 remainder 6	1 remainder 2	No
8	0 remainder 6	1 remainder 1	No
9	0 remainder 6	1	No

This example begins around the year 300 B.C. with a guy living in ancient Greece named Euclid. Euclid was a pretty smart guy who wrote numerous books, including Data, concerning the solution of problems through geometric analysis, On Divisions (of Figures), the Optics, the Phenomena, a paper on spherical geometry for astronomers, the Elements, a 13-volume textbook on geometry, and several lost works on higher geometry. His impact on society was huge. One of his most well-known contributions is an extremely efficient algorithm to solve the GCD problem. Now jump ahead a few thousand years to Olivier Bietzer, who noticed that I had an impractically slow algorithm for solving the GCD problem. Olivier, who certainly knows a lot about these things, wrote the macro in Listing 13 that solves the GCD problem using Euclid's algorithm, and sent it to me.

Listing 13: GCD_1 is found in the Date module in this chapter's source code files as SC05.sxw.

 'Author: Olivier Bietzer 'e-mail: [e-mail] 'This uses Euclid's algorithm and it is very fast! Function GCD_1(ByVal x As Long, ByVal y As Long) As Long   Dim pgcd As Long, test As Long   ' We must have x >= y and positive values   x=abs (x) : y=abs (y)   If (x < y) Then    test = x : x = y : y = test   End If   If y = 0 Then Exit Function                   ' Euclid says ....   pgcd = y        ' by definition, PGCD is the smallest   test = x MOD y  ' remainder after division   Do While (test) ' While not 0    pgcd = test    ' pgcd is the remainder    x = y          ' x,y and current pgcd permutation    y = pgcd    test = x MOD y ' test again   Loop   GCD_1 = pgcd    ' pgcd is the last non 0 rest  ! Magic ... End Function 

 

In general, the best way to speed up a solution to a computational problem is by using a better algorithm. The algorithm in Listing 13 runs roughly 1000 times faster than the routine that I had. If a faster algorithm is not available, you can look for other ways to improve performance. (Sometimes it's possible to invent a wholly new and improved algorithm; but that is quite a trick! If you succeed in developing a new, faster algorithm for a widely known problem, you may have great career potential as a professional mathematics or computer science professor .) The code in Listing 13 is already pretty lean. There isn't a whole lot to remove, but I thought that I could reduce the number of assignments (see Listing 14 ).

Listing 14: GCD_2 is found in the Date module in this chapter's source code files as SC05.sxw.

 Function GCD_2 (ByVal x As Long, ByVal y As Long) As Long   Dim pgcd As Long, test As Long   ' We must have x >= y and positive values   x=abs (x) : y=abs (y)   If (x < y) Then    test = x : x = y : y = test   End If   If y = 0 Then Exit Function   Do While (y)    ' While not 0    pgcd = y       ' pgcd is the remainder    y = x MOD pgcd ' test again    x = pgcd       ' x,y and current pgcd permutation   Loop   GCD_2 = pgcd    ' pgcd is the last non 0 remainder  ! Magic ... End Function 

 

Now the question is, which function is faster? If you use a stopwatch to see how quickly I can blink, the results aren't likely to be very accurate because of measurement errors. It's much easier to tell me to blink as many times as I can in four seconds or to time how quickly I can blink 50 times. The code in Listing 15 does something similar. It sits in a tight loop and calls each GCD implementation 5000 times. I want to know how long it takes to call the GCD function 5000 times, but I'm actually timing how long it takes to loop 5000 times, generate 10,000 random numbers, and call the GCD function 5000 times. To compensate for this, the amount of time required to loop 5000 times and generate 10,000 random numbers is measured.

Listing 15: GCD_2 is found in the Date module in this chapter's source code files as SC05.sxw.

 Sub testGCD   Dim nStartTicks As Long        'When I started timing   Dim nEndTicks As Long          'When I stopped timing   Dim nLoopTicks As Long         'Ticks to do only the loop   Dim nGCD_1_Ticks As Long       'Ticks for GCD_1   Dim nGCD_2_Ticks As Long       'Ticks for GCD_2   Dim nMinIts As Long            'Number of iterations   Dim x&, y&, i&, n&             'Temporary long numbers   Dim s$                         'Hold the output string   nMinIts = 5000                 'Set the number of iterations   Randomize(2)                   'Set to a known state   nStartTicks = GetSystemTicks() 'Start ticks   For i& = 1 To nMinIts          'Control the number of iterations     x = 10000 * Rnd()            'Generate the random data     y = 10000 * Rnd()            'Generate the random data   Next   nEndTicks = GetSystemTicks()   nLoopTicks = nEndTicks - nStartTicks   Randomize(2)                   'Set to a known state   nStartTicks = GetSystemTicks() 'Start ticks   For i& = 1 To nMinIts          'Control the number of iterations     x = 10000 * Rnd()            'Generate the random data     y = 10000 * Rnd()            'Generate the random data     GCD_1(x, y)                  'Do the work we really care about   Next   nEndTicks = GetSystemTicks()   nGCD_1_Ticks = nEndTicks - nStartTicks - nLoopTicks   Randomize(2)                   'Set to a known state   nStartTicks = GetSystemTicks() 'Start ticks   For i& = 1 To nMinIts          'Control the number of iterations     x = 10000 * Rnd()            'Generate the random data     y = 10000 * Rnd()            'Generate the random data     GCD_2(x, y)                  'Do the work we really care about   Next   nEndTicks = GetSystemTicks()   nGCD_2_Ticks = nEndTicks - nStartTicks - nLoopTicks   s = "Looping " & nMinIts & " iterations takes " & nLoopTicks &_       " ticks" & CHR$(10) &_       "Calling GCD_1 takes " & nGCD_1_Ticks & " ticks or " &_       Format(nMinIts * 100 /nGCD_1_Ticks, "#####00.00") &_       " Iterations per second" & CHR$(10) &_       "Calling GCD_2 takes " & nGCD_2_Ticks & " ticks or " &_       Format(nMinIts * 100 /nGCD_2_Ticks, "#####00.00") &_       " Iterations per second"   MsgBox s, 0, "Compare GCD" End Sub 

 

One problem in writing timing routines is determining how many iterations to do. I frequently use computers of different speeds. The results in Figure 4 are based on my home computer running the macro in Listing 15 on an AMD Athlon at 1.4Ghz; it takes about 7 seconds. To avoid this problem, a typical solution uses some method of limiting the iterations based on time rather than number of iterations. This complicates the measurement of overhead and is left as an interesting, but not overly difficult, problem for the reader.

Figure 4: The improvement is about 10 percent.