I'm sorry, but I couldn't help taking Kirby's findphi() function as a

personal challenge.

At the cost of roughly doubling the complexity of the code (19 lines instead

of ten lines in the function body), I was able to improve the performance by

a factor of more than 6500, while basically still using the same

"brute-force" approach of guessing a number, adjusting the guess by a delta,

and noticing which number gets the lowest error.

Why bother optimizing, when phi is a constant? Because using my approach,

you can add two digits more precision to the answer with less than 30% more

time, whereas the original approach would cost 100x (10000% as much) time

for 2 more digits of precision. This refines Kirby's statement that "you get

greater accuracy for more cycles" - it doesn't have to be a linear trade-off.

(Yes, I know the original version wasn't claimed to be optimized, but it was

crying to be optimized...)

# phi.py

def findphi(step = 0.01):

"""

step

->

-----|---------- (a+b)=1

a b

Lengthen a stepwise, while testing how closely

b/a approaches 1/b, and return b/a for the least

difference.

"""

diff = b = 1.0

a = phi = 0

while a < b:

a += step

b = 1 - a

e = abs(b/a - 1/b)

if e < diff:

phi = b/a

diff = e

return phi

def findphi2(tolerance=0.01):

a = tolerance

N = 8.0

step = (0.5 - a) / N

last_e = INFINITY = 1e+30

while True:

b = 1.0 - a

e = abs(b/a - 1/b)

if e < tolerance:

break

if e > last_e:

a -= 2.0 * step # tricky! must go back 2 steps

if a < tolerance:

a = tolerance

step /= N

last_e = INFINITY

else:

a = a + step

last_e = e

return b / a

def test():

import timeit

print "Slow method -- result:", findphi(0.000001),

n = 10

timer1 = timeit.Timer(stmt='findphi(0.000001)',

setup='from phi import findphi')

t1 = timer1.timeit(number=n)

print "time:", t1/n, "seconds"

print "Faster method -- result:", findphi2(0.000001),

timer2 = timeit.Timer(stmt='findphi2(0.000001)',

setup='from phi import findphi2')

n = 1000

t2 = timer2.timeit(number=n)

print "time:", t2/n, "seconds"

print "2 digits more precision -- result:", findphi2(0.00000001),

timer2 = timeit.Timer(stmt='findphi2(0.00000001)',

setup='from phi import findphi2')

n = 1000

t2 = timer2.timeit(number=n)

print "time:", t2/n, "seconds"

if __name__ == '__main__':

test()

# end-of-file

david@arno2:~$ python phi.py

Slow method -- result: 1.61803406588 time: 0.755390405655 seconds

Faster method -- result: 1.6180333003 time: 0.000112377882004 seconds

2 digits more precision -- result: 1.61803398295 time: 0.000145354032516

seconds

david@arno2:~$ python -c "print 0.755390405655/0.000112377882004"

6721.87793705

On Tue, Sep 20, 2005 at 04:58:32PM -0700, Kirby Urner wrote:

>

> Per my 'Pentagon math' thread, I think the golden ratio (phi) is an

> important one to explore in K-12.[1] It's one of those key nodes in our

> curriculum network.

>

> Given a regular pentagon, the ratio of a diagonal to an edge is phi. In

> other words, that famous pentacle pattern is phi-edged, vis-?-vis a

> containing pentagon of edges 1.[2]

>

> Although we have many closed form algebraic methods for deriving phi,

> computers give us this power to solve through brute force. Some may frown

> on using such "mindless methods" but I'm thinking to go ahead and introduce

> them -- not exclusively, but as an exhibit along the way.

>

> In the Python function below, we're looking for a way to break a line of

> unit length into two segments, the shorter 'a' and the longer 'b', such that

> the ratio b:a is as close as feasible to the ratio of the whole to b (1:b).

>

>

> We move 'a' to the right by tiny increments, and keep track of which value

> minimizes the difference between these two ratios:

>

> >>> def findphi(step = 0.01):

> """

> step

> ->

> -----|---------- (a+b)=1

> a b

>

> Lengthen a stepwise, while testing how closely

> b/a approaches 1/b, and return b/a for the least

> difference.

> """

> diff = b = 1.0

> a = phi = 0

> while a < b:

> a += step

> b = 1 - a

> e = abs(b/a - 1/b)

> if e < diff:

> phi = b/a

> diff = e

> return phi

>

> >>> findphi(0.000001)

> 1.6180340658818939

>

> Some lessons that might be learned from this approach:

>

> (1) when working with floats, you want to compare differences, not check for

> equalities, e.g. looking for when b/a == 1/b would be a bad idea.

>

> (2) you get greater accuracy in exchange for more cycles

>

> (3) visualization helps

>

> The last point is especially important. The code itself says nothing about

> lines. The diagram is what explains the logic behind the algorithm -- which

> is why it's included right in the comments, as primitive ASCII art (bad

> form, or a good idea?).

>

> Kirby

>

> [1]

>

http://mathforum.org/kb/message.jspa?messageID=3867841&tstart=0>

> [2]

>

http://altreligion.about.com/library/glossary/symbols/bldefswiccasymbols.htm>

> PS: happy birthday Dawn Wicca (9/20/2005)

>

>

> _______________________________________________

> Edu-sig mailing list

>

[hidden email]
>

http://mail.python.org/mailman/listinfo/edu-sig>

--

David Handy

Computer Programming is Fun!

Beginning Computer Programming with Python

http://www.handysoftware.com/cpif/----- End forwarded message -----

--

David Handy

Computer Programming is Fun!

Beginning Computer Programming with Python

http://www.handysoftware.com/cpif/_______________________________________________

Edu-sig mailing list

[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig