Brute force solutions

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Brute force solutions

Kirby Urner

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
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

david-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

Kirby Urner
> (Yes, I know the original version wasn't claimed to be optimized, but it
> was crying to be optimized...)
>

Yes.  This is a valuable addition to the thread.  Thanks for taking the
time.

Reminds me of when Tim Peters used to swing by in the early days of edu-sig
and optimize the hell out of my algorithms.

I just agreed to teach Python to 8th graders for 9 weeks (one session per
week) in my daughter's school, starting in November.  There's a good chance
I'll be using this phi stuff.  

Mine original draft makes sense to set the stage, cuz the reasoning is so
dang primitive.  Yours adds a layer of sophistication more reflective of how
real world programmers learn to squeeze the most out of their cycles.

Of course all of this requires temporarily ignoring the fact that algebraic
methods give us a way to compute phi as simply (1 + math.sqrt(5))/2.0.

Kirby


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

Peter Bowyer
In reply to this post by david-2
At 14:33 21/09/2005, you wrote:
>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.

Psyco also makes a very noticeable difference:

Without:
Slow method -- result: 1.61803406588 time: 1.40232660855 seconds
Faster method -- result: 1.6180333003 time: 0.000200135212716 seconds
2 digits more precision -- result: 1.61803398295 time:
0.000242882824493 seconds

With psyco.full()
Slow method -- result: 1.61803406588 time: 0.256314531595 seconds
Faster method -- result: 1.6180333003 time: 3.65800681372e-005 seconds
2 digits more precision -- result: 1.61803398295 time:
4.53755994128e-005 second


--
Maple Design - quality web design and programming
http://www.mapledesign.co.uk 

_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

david-2
On Wed, Sep 21, 2005 at 06:44:01PM +0100, Peter Bowyer wrote:

> At 14:33 21/09/2005, you wrote:
> >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.
>
> Psyco also makes a very noticeable difference:
>
> Without:
> Slow method -- result: 1.61803406588 time: 1.40232660855 seconds
> Faster method -- result: 1.6180333003 time: 0.000200135212716 seconds
> 2 digits more precision -- result: 1.61803398295 time:
> 0.000242882824493 seconds
>
> With psyco.full()
> Slow method -- result: 1.61803406588 time: 0.256314531595 seconds
> Faster method -- result: 1.6180333003 time: 3.65800681372e-005 seconds
> 2 digits more precision -- result: 1.61803398295 time:
> 4.53755994128e-005 second

Thanks for bringing up Psyco. This is an example of something Psyco can
speed up, with about a 5.5x improvement for both my algorithm and Kirby's.

However, it doesn't change the fact that original agorithm doesn't scale
well.  Try 12 digits of precision instead of 6:

Slow method -- result: 1.61803406588 time: 0.753984212875 seconds
Faster method -- result: 1.6180333003 time: 0.000110749006271 seconds
2 digits more precision -- result: 1.61803398295 time: 0.000144357919693
seconds
6 digits more precision -- result: 1.61803398875 time: 0.000229076862335
seconds

6 more digits of precision takes the optimized algorithm only 2x more time.

With the original algorithm, 6 digits more precision takes 1000000x more
time. Even with Psyco, it would take about three days to calculate phi to
12 decimal places on your machine.

--
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
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

david-2
In reply to this post by david-2
On Wed, Sep 21, 2005 at 09:31:41AM -0700, Kirby Urner wrote:
> Mine original draft makes sense to set the stage, cuz the reasoning is so
> dang primitive.  Yours adds a layer of sophistication more reflective of how
> real world programmers learn to squeeze the most out of their cycles.

Your original draft was a great baseline. That's one good reason not to
prematurely optimize: it makes you look like a hero when you optimize
later. :)

>
> Of course all of this requires temporarily ignoring the fact that algebraic
> methods give us a way to compute phi as simply (1 + math.sqrt(5))/2.0.

The technique is generally useful to solve any equation of one variable,
given:

1. You have an interval in which the solution lies
2. You have an error function that is monotonically increasing over the
interval the further you get from the solution (and goes to zero at the
solution)

I think exposing students to numerical equation solving using Python can
give them an understanding that will help them later when they are trying
to, i.e. figure out how to solve a problem with their fancy caculator,
spreadsheet functions, etc.

>
> Kirby
>
>

--
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
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

John Zelle


David Handy wrote:

> On Wed, Sep 21, 2005 at 09:31:41AM -0700, Kirby Urner wrote:
>
>>Mine original draft makes sense to set the stage, cuz the reasoning is so
>>dang primitive.  Yours adds a layer of sophistication more reflective of how
>>real world programmers learn to squeeze the most out of their cycles.
>
>
> Your original draft was a great baseline. That's one good reason not to
> prematurely optimize: it makes you look like a hero when you optimize
> later. :)
>
>
>>Of course all of this requires temporarily ignoring the fact that algebraic
>>methods give us a way to compute phi as simply (1 + math.sqrt(5))/2.0.
>
>
> The technique is generally useful to solve any equation of one variable,
> given:
>
> 1. You have an interval in which the solution lies
> 2. You have an error function that is monotonically increasing over the
> interval the further you get from the solution (and goes to zero at the
> solution)
>

If you have the sign of the error, you can also make use of simple
bisection (aka binary search). Here's a version:

def findphi3(tolerance=0.01):
     low = 0.0
     high = 1.0
     while True:
         a = (low + high)/2.0
         b = 1.0-a
         e = b/a - 1/b
         if abs(e) < tolerance:
             break
         if  e > 0:
             low = a
         else:
             high = a
     return b/a

Which turns out to be a bit more efficient than the adaptive stepsize
version in this case:

Slow method -- result: 1.61803406588 time: 0.756837797165 seconds
Faster method -- result: 1.6180333003 time: 0.000106906890869 seconds
Bisection -- result: 1.61803328419 time: 3.86953353882e-05 seconds


> I think exposing students to numerical equation solving using Python can
> give them an understanding that will help them later when they are trying
> to, i.e. figure out how to solve a problem with their fancy caculator,
> spreadsheet functions, etc.
>
>
>>Kirby
>>
>>
>
>

--
John M. Zelle, Ph.D.             Wartburg College
Professor of Computer Science    Waverly, IA
[hidden email]          (319) 352-8360
_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

John Zelle
In reply to this post by david-2

> On Wed, Sep 21, 2005 at 09:31:41AM -0700, Kirby Urner wrote:
>

>Of course all of this requires temporarily ignoring the fact that algebraic
>methods give us a way to compute phi as simply (1 + math.sqrt(5))/2.0.

I've been considering this a bit. The closed form here begs the
question, what is math.sqrt(5)? Sure, we have a built-in function that
computes this, but someone had to write the algorithm that computes
sqrt. That calculation makes use of numerical techniques similar to what
we are discussing w.r.t. phi (much more efficient ones, of course).

In a sense, you could view your discussion as a look under the hood at
possible implementations. In fact, I would think a good problem to
tackle in a math class is to develop some algorithms for approximating
square roots. Various "guess and check" techniques can be successful.
Newton's method is vary good, and can easily be "derived"/motivated
without actually looking at any of the calculus.

--John

--
John M. Zelle, Ph.D.             Wartburg College
Professor of Computer Science    Waverly, IA
[hidden email]          (319) 352-8360
_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

Daniel Ajoy
In reply to this post by Kirby Urner
On 22 Sep 2005 at 12:00, (Kirby Urner) wrote:

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


My approach to teaching about phi is by asking kids to draw
construction #78

http://mondragon.angeltowns.net/paradiso/Construcciones.html 

Daniel





*****************************
OpenWorld Learning
http://www.openworldlearning.org


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

Arthur-27


> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]] On
> Behalf Of Daniel Ajoy
> Sent: Thursday, September 22, 2005 10:07 AM
> To: [hidden email]
> Subject: Re: [Edu-sig] Brute force solutions
>
> My approach to teaching about phi is by asking kids to draw
> construction #78
>
> http://mondragon.angeltowns.net/paradiso/Construcciones.html


That would be more my approach as well.

My learning theory - yes I am repeating myself - is that it is absolutely
disorienting and ineffective to loose all sense of history when approaching
these things.  

It is great to get to the algorithmics, but we can't get there effectively
by skipping over 30 centuries of history.

Start by drawing pictures in the sand. But certainly don't stop there.

And there comes appoint when there are no pictures in the sand to be drawn.
The necessary pictures became too complex.  Mathematicians - 17th century,
say  - began drawing the pictures in their head.  But they were in fact
still drawing pictures.

With computers we can begin to draw those pictures, and better pick their
brains.  That's essentially what PyGeo is about.

Art


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

Kirby Urner
In reply to this post by John Zelle
> I've been considering this a bit. The closed form here begs the
> question, what is math.sqrt(5)? Sure, we have a built-in function that
> computes this, but someone had to write the algorithm that computes
> sqrt. That calculation makes use of numerical techniques similar to what
> we are discussing w.r.t. phi (much more efficient ones, of course).
>

Good point.  A mathematician gets around this with a certain philosophy of
language that says "if I just write sqrt(5) -- using a surd -- that's
already infinitely precise."  Then he gets to look down his nose at those
imprecise computer people who traffic in floating point evaluations.  

Those floating point people don't have the benefit of "real numbers."

> In a sense, you could view your discussion as a look under the hood at
> possible implementations. In fact, I would think a good problem to
> tackle in a math class is to develop some algorithms for approximating
> square roots. Various "guess and check" techniques can be successful.
> Newton's method is vary good, and can easily be "derived"/motivated
> without actually looking at any of the calculus.
>
> --John

I've a couple times implemented the old manual algorithm for finding square
roots.  I might be able to dig those up for discussion.  The longer it runs,
the more digits you get.

Kirby


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

Kirby Urner
In reply to this post by Kirby Urner
> I've a couple times implemented the old manual algorithm for finding
> square roots.  I might be able to dig those up for discussion.  The longer
> it runs, the more digits you get.
>
> Kirby

But instead, this steaming unoptimized octopus of a code specimen spits back
the repeating digits for any positive integer, as needed to generate the
ongoing continued fraction, for said integer's square root.

def sqrtcf(n):
    orig = n
    denom = 1
    addterm = 0
    cflist = []
    while True:
        m = int(pow(n,0.5)) # <-- replace with function call
        cflist.append(m)
        if len(cflist)>1 and denom == 1:
            break        
        addterm = -(addterm - m*denom)
        denom = (orig - addterm**2)/denom
        n = ((pow(orig,0.5) + addterm)/denom)**2
    return cflist

IDLE 1.1      
>>> from gonzo import sqrtcf
>>> sqrtcf(19)
[4, 2, 1, 3, 1, 2, 8]
>>> sqrtcf(13)
[3, 1, 1, 1, 1, 6]
>>> sqrtcf(2)
[1, 2]

What's especially inelegant is that it uses pow, whereas with some
Zelle-style numeric method, we could compute successive m's with more
primitive primitives (e.g. Newton's method).  Then we'd have a bona fide
square root generator that didn't use any built-in square root generator.

The only remaining piece is to feed the repeating lists, e.g. [4, 2, 1, 3,
1, 2, 8] in the case of sqrt(19), to a continued fraction evaluator.  I've
recently shared a recursive one, based on building a rational number class
and using its objects.  However, a non-recursive cf algorithm exists, as Tim
Peters mentioned way early in the archives of edu-sig (we played with it
then, if memory serves).

So....

(a) To get the square root of integer N, write a Zelle-style optimized
approximater to get the biggest m = integer sqrt of N (i.e. m**2 < N <
(m+1)**2).

(b) call this in an implementation of the algorithm at this web page (with
lots of check data):
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/cfINTRO.html (the
algebraic algorithm).

(c) use the returned list to feed a continued fractions evaluator.  

The fun part here is we can use numerator/denominator syntax with open-ended
precision integers, to like express sqrt of 19 as some humongous fraction
(as many digits as memory will allow).  This lets us far surpass the
floating point barrier.

This is *not* a super-efficient way of getting 2nd roots, just a way that
meanders through a lot of interesting math (continued fractions have a lot
of cool features).

Math through programming, we call it.

Kirby


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

Kirby Urner
In reply to this post by Kirby Urner
>The fun part here is we can use numerator/denominator syntax with
open-ended
>precision integers, to like express sqrt of 19 as some humongous fraction
>(as many digits as memory will allow).  This lets us far surpass the
>floating point barrier.

For example, the sqrt of 19 is rougly:

745969084203762918506900171
6630770611758990188906918072
4013315460866431392624885605
5112125808098871177881508095
4010864598095
----------------------------
1711370448973571545640915466
3001505416992487326376156603
4301985589644920244770721090
4993017822174818974832607428
966608330904

(that's a numerator over a denominator).

Here's the code behind it (still need to replace int(pow(x,0.5))
with a numerical method that doesn't do all the work to find
an actual floating point sqrt -- overkill):

"""
gonzo.py
"""
from mathteach import cf2
# http://www.4dsolutions.net/ocn/python/mathteach.py

def sqrtcf(n):
    orig = n
    denom = 1
    addterm = 0
    cflist = []
    while True:
        m = int(pow(n,0.5)) # <-- replace with function call
        cflist.append(m)
        if len(cflist)>1 and denom == 1:
            break
        addterm = -(addterm - m*denom)
        denom = (orig - addterm**2)/denom
        n = ((pow(orig,0.5) + addterm)/denom)**2
    return cflist

def getsqrt(n,default=30):
    thelist = sqrtcf(n)
    while len(thelist)<default:
        thelist += thelist[1:]
    thelist = thelist[:default]
    return cf2(thelist * 10)

>>> from gonzo import getsqrt
>>> getsqrt(19)
...

Kirby

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


--------------------------------------------------------------------
mail2web - Check your email from the web at
http://mail2web.com/ .


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

Kirby Urner
In reply to this post by Kirby Urner
>        n = ((pow(orig,0.5) + addterm)/denom)**2

Hmmmm, this may be the Achilles heal of my project, to not use any sqrt
finder in the process of finding a sqrt using continued fractions.  Back to
the drawing board?

Kirby


--------------------------------------------------------------------
mail2web - Check your email from the web at
http://mail2web.com/ .


_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: Brute force solutions

Scott David Daniels
In reply to this post by Kirby Urner
[hidden email] wrote:
>>The fun part here is we can use numerator/denominator syntax with
>
> open-ended
>
>>precision integers, to like express sqrt of 19 as some humongous fraction
>>(as many digits as memory will allow).  This lets us far surpass the
>>floating point barrier.

OK, here we go:


def test_sqrt(numerator, denominator, trial):
     '''True iff trial (a num,den pair) over-estimates the sqrt(n/d)'''
     root_n, root_d = trial
     # return numerator / denominator >= root_n ** 2 / root_d ** 2
     return root_d ** 2 * numerator >= root_n ** 2 * denominator

# since we don't have 2.5 yet, here's a version of partial:

def partial(function, *args):
     '''Simple no-kwargs version of partial'''
     def andthen(*final_args):
         return function(*(args + final_args))
     return andthen

def farey_trials(tester):
     '''Binary search for fraction.  value must be between 0 and +Inf
     tester((num, den)) returns True if fract is high, False if Low
     '''
     low_n, low_d = low = 0, 1    # 0/1 = 0 ..
     high_n, high_d = high = 1, 0  # 1/0 = Infinity
     while True:
         mediant_n = low_n + high_n
         mediant_d = low_d + high_d
         mediant = mediant_n, mediant_d
         yield mediant
         if tester(mediant):
             low_n, low_d = low = mediant
         else:
             high_n, high_d = high = mediant



# Now here is a cute reporter that relies on another trick:
# n & -n == n only if n is either 0 or a power of 2.

for n, fraction in enumerate(farey_trials(partial(test_sqrt, 19, 1))):
     if n & -n == n:  # report increasingly rarely
         print n, fraction
         if n > 4096:
              break



-- Scott David Daniels
[hidden email]

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