Re: Analysis ToolPak Function in VBA is sloooow

FWIW, the algorithm you offered is (in my testing) the best performer of all the solutions offered in this thread so far.

My *ware notes: 1.8 MHz Dual Core Intel, 1 GB RAM, XP Pro SP3, Excel 2003.

I set up one loop to time Totient(N) (where each call to Totient() requires essentially N calls to GCD) for 1 <= N <= 10000. Yours competes nicely with the recursive function, but the quantization effect of Timer's precision makes the real results unclear.

So next, I set up three scenarios in a new loop:
- Call Totient(100) 10,000 times
- Call Totient(1000) 1,000 times
- Call Totient(10000) 100 times

Thus each scenario calls Totient() (and therefore GCD) 1,000,000 times. Each scenario was run 10 times in succession, and an average timing in seconds was determined.

Your algorithm gave the following average timings for these three scenarios:
0.50703125 0.4171875 0.49375

Next best was the recursive GCD function:
0.86484375 1.1015625 1.3039063

Then, Dana D's:
19.542971 22.956252 28.414845


Even after uncommenting the debug.print statements in ATP's native GCD function, timings were in the 80's. I am still mystified why ATP's performance on my machine is so poor.


Clearly, your algorithm scales well. It really starts to pull away for the killer values of N:
- Call Totient(100000) 10 times
- Call Totient(1000000) 1 time

With these timings:
0.5671875 0.6515625

Compared to the recursive function:
1.4382813 1.6546876


An observation about my timings with Dana D's algorithm... the 10 timings always start smaller and grow, whereas the other algorithms tend to produce timings that hover about the mean. I wonder if this is a consequence of using variants?


Again, thanks to all who participated in this thread. This has been most educational for me.


Rick Rothstein wrote:
Is GCD3 the Euler #69 you are talking about? If so, I am really surprised that a recursive function would be faster than "straight" code. Just out of curiosity, how does this old standby function I use for GCD stack up against it?

Function GCD(ByVal Num1 As Long, ByVal Num2 As Long) As Long
Dim Remainder As Long
Do
Remainder = (Num2 Mod Num1)
Num2 = Num1
Num1 = Remainder
Loop While Remainder
GCD = Num2
End Function

While I'm guessing you are only interested in finding the GCD of two numbers, here is a general routine which will find the GCD of two or more numbers that I thought you might find interesting...

Function GCD(ParamArray Number()) As Long
Dim X As Long
Dim Num As Long
Dim Remainder As Long
If UBound(Number) > LBound(Number) + 1 Then
GCD = Number(LBound(Number))
For X = Num + 1 To UBound(Number)
Num = GCD
Do
Remainder = (Number(X) Mod Num)
Number(X) = Num
Num = Remainder
Loop While Remainder
GCD = Number(X)
Next
Else
GCD = -1
End If
End Function

.

Relevant Pages

  • Re: GCD of multivariate polynomials
    ... the most efficient method for computing the gcd. ... What does work is a more generalized Euclidean gcd algorithm (divide ... the remainder before you get 0 is the gcd). ...
    (sci.math.symbolic)
  • Re: GCD of polynomials
    ... It looks just like Euclid's algorithm. ... Divide the largest by the ... smallest and replace the largest with the remainder. ... the smallest is the gcd. ...
    (comp.lang.cpp)
  • Re: I was right, surrogate factoring proof
    ... >> factor 9 via gcd. ... > There's a proof that the method does not work for primes squared. ... To prove that, mess with the algorithm. ... No, I'm not estimating anything. ...
    (sci.crypt)
  • Re: Analysis ToolPak Function in VBA is sloooow
    ... how does this old standby function I use for GCD stack up against it? ... Dim Remainder As Long ... Dim Num As Long ...
    (microsoft.public.excel.programming)
  • Re: how to rotate an array
    ... You can easily find the explanation of Euclidean algorithm on the Internet. ... gcd of original a,b values. ... > loops through the number of elements in the series, ...
    (comp.lang.cpp)
Loading