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?

smartin wrote:
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?se...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/~vfd.../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!)

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



smartin wrote:
smartin wrote:
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?se...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/~vfd.../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!)

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" wrote in message
...
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?

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!



Peter T wrote:
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

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

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

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


Jim Cone wrote:
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.

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



"smartin" 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

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


"Peter T" <peter_t@discussions wrote in message
...
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



"smartin" 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

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?se...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 wrote:
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



"smartin" 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

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

Peter T wrote:
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



"smartin" 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

On Sun, 07 Jun 2009 18:20:40 -0400, smartin wrote:

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