# [Edu-sig] Brute force solutions

David Handy david at handysoftware.com
Wed Sep 21 15:33:29 CEST 2005

```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 at 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 at 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]
>
> PS:  happy birthday Dawn Wicca (9/20/2005)
>
>
> _______________________________________________
> Edu-sig mailing list
> Edu-sig at python.org
> 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/
```