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?

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?

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!)

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.

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

--
Rick (MVP - Excel)


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

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!)

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

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

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

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

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

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 D1:D5000
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

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

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

"Charles Williams" wrote in message
...
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 D1:D5000
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

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

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



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

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) (^:

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



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

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.

I was at the point of thinking this problem could not be solved by
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



smartin wrote:
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) (^:

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



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

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

One thing I learned early on from the Euler puzzles is that
understanding and applying number theory can transform a seemingly
impossible problem into a fairly trivial computation. I approach each
problem with this belief, but seldom have the experience to make the
transformation myself. I definitely appreciate the insights you have
given here!

Dana DeLouis wrote:
sequential prime factors have a product less than or equal to a given
power of ten to solve Euler 69
... But, I have no idea why this should work

Hi. Glad you find this interesting. :)

Let's find the Totient of a large number ...100000000000000
We really don't want to loop this many times calling the GCD function.
Instead, this function relies on Number Theory.
The real key is to have a program that finds the prime factors of a
number. Just being able to divide by the prime number 2 saves a lot of
time. Powers of 10 factor into 2 and 5. (That's why we can do this by
inspection) Once we have the prime factors, the rest is easy. Here's s
small demo:

Sub Demo()
'// = = = = = = = = = = = = = = = = = = =
'// By: Dana DeLouis
'// The EulerPhi of 100000000000000 (1E14)
'// Factors: 2^14 * 5^14
'// = = = = = = = = = = = = = = = = = = =

Dim n As Double

n = Fx(2, 14) * Fx(5, 14)
Debug.Print FormatNumber(n, 0, , , vbTrue)
End Sub

returns:
40,000,000,000,000

Private Function Fx(n As Double, p As Double) As Double
Fx = (n - 1) * n ^ (p - 1)
End Function


(We note that for a Prime number p, the EulerPhi is just p-1.)
So, for the puzzle n / EulerPhi[n].
We want the numerator as large as possible, and the denominator as small
as possible. So, from number theory above, we want the Prime factors to
be as small as possible.(basically, sequential). We also want the power
of each prime to be as small as possible also, which would be 1. So,
basically, we want 2^1 * 3^1 * 5^1 *...etc

BTW, what language were you demonstrating below?
The best I can manage is solving for N < 20,000 or
so in less than 60 seconds.

The Brute-Force method was in Mathematica... in 7 seconds.

HTH
Dana DeLouis
= = = = = = = = =


smartin wrote:
Thanks Dana -- This is very interesting, and makes sense.

BTW, what language were you demonstrating below?

[I'm going completely off-topic now...]

Even if I extend your method to odd numbers and optimize my
Totient/Phi function to cut the GCD calls in half I see I still have a
O(N^2) solution for Euler 69, which is prohibitive to solve by brute
force over 1 <= N <= 1,000,000. The best I can manage is solving for N
< 20,000 or so in less than 60 seconds.

However (and you hinted at this), I observe that solving problems like
Euler 69 for various limits that are powers of ten produces a
tantalizing pattern of results...

N <= N having Max N / Phi(N) = (? not coincidentally ?)
10 6 2 * 3
100 30 2 * 3 * 5
1000 210 2 * 3 * 5 * 7
10000 2310 2 * 3 * 5 * 7 * 11

So I might jump to the conclusion that all I need to know is the
sequential prime factors have a product less than or equal to a given
power of ten to solve Euler 69, indeed many POT beyond the
requirement. But, I have no idea why this should work, as my knowledge
of number theory is slim at best. But again, it seems likely this is
the discovery I am supposed to make here?



Dana DeLouis wrote:
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.

I was at the point of thinking this problem could not be solved
by 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



smartin wrote:
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) (^:

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



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