[Edu-sig] Brute force solutions

[David Handy]

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] 
> http://altreligion.about.com/library/glossary/symbols/bldefswiccasymbols.htm
> 
> 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/