Analysis ToolPak Function in VBA is sloooow

[smartin]

Excel 2003.

I am puzzled by the implementation of ATP function(s) called from VBA.
First, after sorting out how to add the references etc., I now see this
cryptic text in the debug/immediate window when I open my project:

[auto_open] <
[SetupFunctionIDs] <
[SetupFunctionIDs] >
[PickPlatform] <
[PickPlatform] >
[VerifyOpen] <
[VerifyOpen] > 1
[RegisterFunctionIDs] <
[RegisterFunctionIDs] >
[auto_open] >


So I am using the GCD function. It seems every time I call GCD() I get
this interesting information added to the debug window (not put there by
me!):

[GetMacroRegId] 'GCD' <
[GetMacroRegId] 'GCD' -> '1412038696' >

To my question.. the ATP code runs /many times/ slower compared to my
hand-rolled VBA GCD function. I expected a performance improvement. What
is going on? Could it be that writing so much garbage to the debug
window is slowing things down? Is there a way to turn off the verbose
messaging?

 

[Peter T]

Those debugs are normal though I'm sure a [sic] design flaw. They must
degrade performance but I wouldn't think to the extent of being much slower
than an equivalent VBA function. Why not post your VBA function, your code
that calls the ATP equivalent, and an example of the data.

Regards,
Peter T

 

[smartin]

Excel 2003.

I am puzzled by the implementation of ATP function(s) called from VBA.
First, after sorting out how to add the references etc., I now see this
cryptic text in the debug/immediate window when I open my project:

[auto_open] <
[SetupFunctionIDs] <
[SetupFunctionIDs] >
[PickPlatform] <
[PickPlatform] >
[VerifyOpen] <
[VerifyOpen] > 1
[RegisterFunctionIDs] <
[RegisterFunctionIDs] >
[auto_open] >


So I am using the GCD function. It seems every time I call GCD() I get
this interesting information added to the debug window (not put there by
me!):

[GetMacroRegId] 'GCD' <
[GetMacroRegId] 'GCD' -> '1412038696' >

To my question.. the ATP code runs /many times/ slower compared to my
hand-rolled VBA GCD function. I expected a performance improvement. What
is going on? Could it be that writing so much garbage to the debug
window is slowing things down? Is there a way to turn off the verbose
messaging?

Here is a somewhat more quantified explanation of what I mean by "slow".

The computational cost of calculating Euler's Totient (phi) function of
an integer N (see
http://projecteuler.net/index.php?section=problems&id=69 and
http://en.wikipedia.org/wiki/Relatively_prime) is primarily the result
of the cost of determining the GCD of N and all numbers less than N.

Here is a graph showing the calculation times to determine Totient(N)
for N < 1800 using ATP's native GCD function vs. my own GCD under
essentially identical circumstances:

http://vfdrake.home.comcast.net/~vfdrake/files/excel/gcd.png

Both runs were done with application.screenupdating = false and the
debug window hidden. The step nature of the results is a consequence of
the precision of the Timer function. The outliers are probably where I
got bored and switched windows to do something else.

Clearly, for higher values of N, the native ATP GCD is nearly an order
of magnitude slower than my own GCD code (which is nothing remarkable).

How shall I ever resolve Euler problem 69 with this handicap? <BG> (No
hints, please!)

 

[smartin]

Thanks for your input. I posted a follow-up to my first message that
sets the background and quantifies the results.


If you would like to see details (or try it out for yourself) here is
the code in question...


In this first function, the call
GCD2(i, N)
is to my own function, pasted further down. Change this to
GCD(i, N)
to get ATP's GCD (assuming appropriate references set, of course).

Public Function Totient(ByVal N As Long) As Long
' Returns Euler's Totient (Phi) function of N such that
' Totient = the number of numbers less than N that are relatively prime
' to N.

Dim i As Long
Dim Result As Long

Result = 1
i = 2
Do While i < N
If GCD2(i, N) = 1 Then Result = Result + 1
i = i + 1
Loop
Totient = Result
End Function


This is my hand-rolled GCD function. It's nothing special, but it blows
away ATP's version of GCD by a factor of (almost) 10...

Public Function GCD2(ByVal a As Long, ByVal b As Long) As Long
' greatest common divisor
' as structured, it is advantageous to pass the lower of the two numbers
' as a
Dim i As Long
Dim Found As Boolean
i = a + 1
Do Until Found
i = i - 1
If a / i = a \ i And b / i = b \ i Then Found = True
Loop
GCD2 = i
End Function


To produce the test results I have a simple Sub that calls Totient(N)
for 1 <= N <= whatever, with timings captured.

Thanks again!

 

[smartin]

For giggles, this optimization of my hand-rolled GCD is 2x faster
compared to my previous version... perhaps 20x or more faster than ATP's
GCD for {a,b} around 1800. Alas, it is still far too slow to handle
Euler #69:

Public Function GCD2(ByVal a As Long, ByVal b As Long) As Long
' greatest common divisor
' as structured, it is advantageous to pass the lower of the two numbers
as a
Dim i As Long
Dim Found As Boolean
i = a + 1
Do Until Found
i = i - 1
'If a / i = a \ i And b / i = b \ i Then Found = True
If a / i = a \ i Then
If b / i = b \ i Then Found = True
End If
Loop
GCD2 = i
End Function

 

[Jim Cone]

I saved this post from Dana DeLouis.
I would say that "fast" describes it...

Function GCD(a, b)
' = = = = = = = = = =
'// Greatest Common Divisor
'// By: Dana DeLouis - July 24, 2004
' = = = = = = = = = =
Dim v As Variant
v = Array(a, b)
Do While v(1) <> 0
v = Array(v(1), v(0) Mod v(1))
Loop
GCD = v(0)
End Function
'--
Also, you can open the ATP module and remove the ~ 18 debug print statements.
Post back if you want the password.
--
Jim Cone
Portland, Oregon USA




"smartin" <[email protected]>
wrote in message
For giggles, this optimization of my hand-rolled GCD is 2x faster
compared to my previous version... perhaps 20x or more faster than ATP's
GCD for {a,b} around 1800. Alas, it is still far too slow to handle
Euler #69:

Public Function GCD2(ByVal a As Long, ByVal b As Long) As Long
' greatest common divisor
' as structured, it is advantageous to pass the lower of the two numbers
as a
Dim i As Long
Dim Found As Boolean
i = a + 1
Do Until Found
i = i - 1
'If a / i = a \ i And b / i = b \ i Then Found = True
If a / i = a \ i Then
If b / i = b \ i Then Found = True
End If
Loop
GCD2 = i
End Function

 

[smartin]

Thanks for that. I just found a similar algorithm... "fast" is
definitely the key word! It totally blows away everything else I've
tried. Still not fast enough to beat Euler #69, but nonetheless worthy
of saving.

Public Function GCD3(ByVal a As Long, ByVal b As Long) As Long
' adapted from http://tausiq.wordpress.com/2009/05/
If b = 0 Then
GCD3 = a
Else
GCD3 = GCD3(b, a Mod b)
End If
End Function


So, what of the ATP module? I would be interested to know how to
manipulate it. If you don't mind, please post the PW or PM it to me at

smartin108@x
WHERE x = gmail.com

 

[Rick Rothstein]

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

 

[Dana DeLouis]

How shall I ever resolve Euler problem 69 with this handicap? <BG>

Just an alternative...According to the third comment (only inverted)
=PRODUCT(2, 3, 5, 7, 11, 13, 17)
is the last primorial before exceeding the problem size of 1,000,000

http://www.research.att.com/~njas/sequences/A002110
= = = = =
HTH
Dana DeLouis

Excel 2003.

I am puzzled by the implementation of ATP function(s) called from VBA.
First, after sorting out how to add the references etc., I now see
this cryptic text in the debug/immediate window when I open my project:

[auto_open] <
[SetupFunctionIDs] <
[SetupFunctionIDs] >
[PickPlatform] <
[PickPlatform] >
[VerifyOpen] <
[VerifyOpen] > 1
[RegisterFunctionIDs] <
[RegisterFunctionIDs] >
[auto_open] >


So I am using the GCD function. It seems every time I call GCD() I get
this interesting information added to the debug window (not put there
by me!):

[GetMacroRegId] 'GCD' <
[GetMacroRegId] 'GCD' -> '1412038696' >

To my question.. the ATP code runs /many times/ slower compared to my
hand-rolled VBA GCD function. I expected a performance improvement.
What is going on? Could it be that writing so much garbage to the
debug window is slowing things down? Is there a way to turn off the
verbose messaging?

Here is a somewhat more quantified explanation of what I mean by "slow".

The computational cost of calculating Euler's Totient (phi) function of
an integer N (see
http://projecteuler.net/index.php?section=problems&id=69 and
http://en.wikipedia.org/wiki/Relatively_prime) is primarily the result
of the cost of determining the GCD of N and all numbers less than N.

Here is a graph showing the calculation times to determine Totient(N)
for N < 1800 using ATP's native GCD function vs. my own GCD under
essentially identical circumstances:

http://vfdrake.home.comcast.net/~vfdrake/files/excel/gcd.png

Both runs were done with application.screenupdating = false and the
debug window hidden. The step nature of the results is a consequence of
the precision of the Timer function. The outliers are probably where I
got bored and switched windows to do something else.

Clearly, for higher values of N, the native ATP GCD is nearly an order
of magnitude slower than my own GCD code (which is nothing remarkable).

How shall I ever resolve Euler problem 69 with this handicap? <BG> (No
hints, please!)

 

[Peter T]

Here are my test results in Excel 2003 in a fairly old system (you'll
probably get faster results)

Sub test()
Dim nn As Long, x As Long
Dim t As Double
t = Timer
nn = 10000

x = Totient(nn) ' see OP's earlier post
t = Timer - t
Debug.Print nn, x, t
End Sub

with nn = 10000 the Gcd functions get called 9998 times in the Totient loop

Calling smartin's GCD2 version1
22.6 sec ' state of the VBE not relevant

Calling smartin's GCD2 version2
13.9 sec ' a worthwhile improvment

Calling ATP's Gcd function with loads of debugs
with a reference to atpvbaen.xls in Tools Ref's
4.3 sec ' with the VBE closed
6.4 sec ' with the VBE open but hidden
9.0 sec ' with the VBE active

Clearly I do not replicate the OP's results. For me the ATP function is much
faster, particularly with the VBE closed.

Following Jim's suggestion I opened the atpvbaen.xla nd commented all Debug
lines (why didn't I ever think of that before - thanks Jim!)

Calling ATP's Gcd with no debugs
1.0 sec ' WOW - how could MS have shipped it with those debugs!

For curiosity I tried Dana DeLouis's version which I renamed to gcdDL
0.3 sec ' holy crap !

and Rick's which I renamed gcdRR
0.02 sec ' can't be right, need to double check that
0.02 sec ' the prize goes to Rick !

Using Rick's in the OP's Totient function to solve the OP's "Euler problem
69" took 2.13 sec to return 400000 (outstanding Rick)

That said, I can think of more interesting ways....

Regards,
Peter T

 

[Charles Williams]

If you use GCD and GCD3 as worksheet functions called from cells the ATP
function is faster according to my tests

5000 calls to ATP GCD takes 110 millisecs
5000 calls to GCD3 takes 150 millisecs

Charles
___________________________________
The Excel Calculation Site
http://www.decisionmodels.com

 

[Ron Rosenfeld]

Excel 2003.

I am puzzled by the implementation of ATP function(s) called from VBA.
First, after sorting out how to add the references etc., I now see this
cryptic text in the debug/immediate window when I open my project:

[auto_open] <
[SetupFunctionIDs] <
[SetupFunctionIDs] >
[PickPlatform] <
[PickPlatform] >
[VerifyOpen] <
[VerifyOpen] > 1
[RegisterFunctionIDs] <
[RegisterFunctionIDs] >
[auto_open] >

Microsoft left some "debug"'s in the VBA code portion of the ATP. I'm now
using xl2007, but, if IIRC, if you can get the password to the ATP VBA project
and open it, you will see these debug lines and can comment them out.
--ron

 

[Peter T]

I forgot to test GCD3 (in smartin's reply to Jim)
very fast but only half as fast as Rick's

I also found Rick's used as a UDF faster than ATP's GCD as worksheet
function in 1000 formulas.

Charles - for testing worksheet calls to Rick's & ATP's GCD I did this

A1: 2
B1: 2
A2: =A1+1
B2: =B1+$E$1
C2: =gcd(A2,B2) ' similar with Rick's & GCD3

copy A2:C2 down to say row 1000

When I changed the value in E1 manually recalc took a long time (seconds).
But when using VBA to change E1 recalc was very fast. Any idea why the
difference?

Regards,
Peter T

 

[Charles Williams]

Hmmm... I get different results (Excel 2003)

fill A1:B5000 with random integers (sized about 1000, no formulae).
switch to manual mode

Download & install my RangeCalc addin from
http://www.decisionmodels.com/downloads.htm

Analysis Toolpack GCD in C1:C5000
Ricks GCDR in D15000
GCD3 in E1:E5000
Dana's GCDD in F1:F5000

select each column in turn and use Rangecalc to calculate the time
ATP GCD 126 millisecs
GCDR 544 millisecs
GCD3 151 millisecs
GCDD 279 millisecs

I am surprised that the recursive solution is fastest.

Manual recalc or automatic recalc would be very slow with this number of UDF
calls if you did not bypass the VBE refresh bug:
see http://www.decisionmodels.com/calcsecretsj.htm

regards
Charles
___________________________________
The Excel Calculation Site
http://www.decisionmodels.com

 

[Dana DeLouis]

Using Rick's in the OP's Totient function to solve the OP's "Euler
problem

69" took 2.13 sec to return 400000 (outstanding Rick)

Hi. I may be wrong, but I understand that with your solution of
n = 400,000, the Ratio of n / Phi(n) is the greatest.

Problem:
http://projecteuler.net/index.php?section=problems&id=69

If this is correct, than without doing any math, your solution is a
little peculiar. From Number theory, powers of 10 have special
properties. For example, the Phi number of {10,100,1000...) are
{4, 40, 400}. Phi of {40, 400, 4000} are {16, 160, 1600}, or the
constant 2.5.
So, without math, we know that the ratio of your solution is 2.5
From the problem, we were given that the number 6 has the ratio 3.
Therefore, without math, we know that 400,000 can not be the correct
solution.

= = = = =
HTH :>)
Dana DeLouis

 

[Peter T]

Hmmm... I get different results to yours and I get a different set of
relative results in cells with your test vs a very different test in VBA
only

Excel 2003 with manual calculation, I selected each range in turn and
pressed the RangeCalc button

ATP GCD 311 millisecs
GCDR 573 millisecs
GCD3 151 millisecs
GCDD 281 millisecs

It's probably not meaningful to look at the ATP GCD xll/cells version which
will obviously be very different to the VBA version (which I didn't try as a
UDF in cells)

In cells GCD3 was twice as fast as Dana's and 4x faster than Rick's. This is
the opposite in relative terms to the VBA test I made, with Dana's being
much slower (although Dana's was 3x faster than the ATP-VBA version with all
debugs commented out).

I can only assume the difference in results between my VBA and cells is due
to a radically different set of arguments being passed in the respective
tests. Maybe that also explains the difference in your and my test in cells,
ie different random integers in A:B between 1-1000.

Regards,
Peter T

 

[Peter T]

I may be guilty of testing code without bothering to figure what it was I
was actually testing!

Sub test()
Dim nn As Long, result As Long
Dim t As Double

t = Timer
nn = 1000000

result = Totient(nn)
t = Timer - t
Debug.Print nn, result, Format(t, "0.00")

End Sub

Public Function Totient(ByVal N As Long) As Long
' Returns Euler's Totient (Phi) function of N such that
' Totient = the number of numbers less than N that are relatively prime
' to N.
Dim i As Long
Dim result As Long
Dim k As Long
result = 1
i = 2
Do While i < N
k = k + 1
'If gcdRR(i, N) = 1 Then Result = Result + 1
'If GCD3(i, N) = 1 Then result = result + 1
If gcdDL(i, N) = 1 Then result = result + 1
i = i + 1
Loop
Totient = result
'Debug.Print , k
End Function

Function gcdRR(ByVal Num1 As Long, ByVal Num2 As Long) As Long
' Rick Rothstein
Dim Remainder As Long
Do
Remainder = (Num2 Mod Num1)
Num2 = Num1
Num1 = Remainder
Loop While Remainder
gcdRR = Num2
End Function

Function gcdDL(a, b)
' = = = = = = = = = =
'// Greatest Common Divisor
'// By: Dana DeLouis - July 24, 2004
' = = = = = = = = = =
Dim v As Variant
v = Array(a, b)
Do While v(1) <> 0
v = Array(v(1), v(0) Mod v(1))
Loop
gcdDL = v(0)
End Function

Public Function GCD3(ByVal a As Long, ByVal b As Long) As Long
' adapted from http://tausiq.wordpress.com/2009/05/
If b = 0 Then
GCD3 = a
Else
GCD3 = GCD3(b, a Mod b)
End If
End Function


All three versions, Rick's, yours and GCD3 end up returning the same result
to the test routine of 400,000 with 1,000,000 passed to the Totient function

Regards,
Peter T

 

[smartin]

Remarkable! I was at the point of thinking this problem could not be
solved by brute force, but indeed it can.

 

[smartin]

Many thanks to you and everyone else for all the tips and comments! I
shall have to repeat my experiments with all the interesting GCD
algorithms.

BTW you are only missing one thing in your solution -- Euler #69 asks
for the largest ratio N/Totient(N) (^:

 

[Dana DeLouis]

shall have to repeat my experiments with all the interesting GCD

algorithms.

Hi. In the quest for speed to solve the max ratio problem, consider
looking into your Totient function as well.
If (a,b) are Coprime, is (2*a, b) coprime as well? How about (3*a,b).

Here is your Totient function. (I just modified it a little here)

Public Function Totient(ByVal n As Long) As Long
' Returns Euler's Totient (Phi) function of N such that
' Totient = the number of numbers less than N that are relatively prime
' to N.

Dim i As Long
Dim Result As Long
With WorksheetFunction
Result = 1
For i = 2 To n - 1
Result = Result - (.Gcd(i, n) = 1)
Next i
Totient = Result
End With
End Function

When you have a number like say 50, you scan each number 1 - 49.
Let's look at this same thing in a different order...

Sub Demo()
Dim n
For n = 1 To 25
Debug.Print WorksheetFunction.Gcd(n, 50);
Next n
Debug.Print
For n = 49 To 26 Step -1
Debug.Print WorksheetFunction.Gcd(n, 50);
Next n
End Sub

Returns:
1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 25
1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2

Do you notice anything on the Coprimes?

So, with Version #1, we could start with:

Sub ShowIt()
'We could do this...
Debug.Print Totient(1000)
'Or this...
Debug.Print 2 * Totient(500)
End Sub

Returns:
400
400

You get the idea with the other primes as well.
brute force,

If interested in a brute-force approach in another program...

m = Table[n/EulerPhi[n], {n, 1000000}];

' The Max Value is:

Max[m]
17017/3072

'Or
N[%]
5.539388020833333

'Which comes from the number:

Ordering[m, -1]
{510510}

'Whose reference already mentioned pointed to:

2*3*5*7*11*13*17
510510

= = = = =
HTH :>)
Dana DeLouis