>Carl Banks wrote:
>> For instance, say you are using an implementation that uses
> > floating point, and you define a function that uses Newton's
> > method to find a square root:
>>
>> def square_root(N,x=None):
>> if x is None:
>> x = N/2
>> for i in range(100):
>> x = (x + N/x)/2
>> return x
>>
>> It works pretty well on your floating-point implementation.
> > Now try running it on an implementation that uses fractions
> > by default....
>>
>> (Seriously, try running this function with N as a Fraction.)
In article <mailman.2376.1306950997.9059.python-l...@python.org>
Ethan Furman <et...@stoneleaf.us> wrote:
>Okay, will this thing ever stop? It's been running for 90 minutes now.
> Is it just incredibly slow?
The numerator and denominator get very big, very fast.
Try adding a bit of tracing:
for i in range(100):
x = (x + N/x) / 2
print 'refinement %d: %s' % (i + 1, x)
and lo:
>>> square_root(fractions.Fraction(5,2))
refinement 1: 13/8
refinement 2: 329/208
refinement 3: 216401/136864
refinement 4: 93658779041/59235012928
refinement 5: 17543933782901678712641/11095757974628660884096
refinement 6:
615579225157677613558476890352854841917537921/389326486355976942712506162834130868382115072
refinement 7:
757875564891453502666431245010274191070178420221753088072252795554063820074969259096915201/479322593608746863553102599134385944371903608931825380820104910630730251583028097491290624
refinement 8:
1148750743719079498041767029550032831122597958315559446437317334336105389279028846671983328007126798344663678217310478873245910031311232679502892062001786881913873645733507260643841/726533762792931259056428876869998002853417255598937481942581984634876784602422528475337271599486688624425675701640856472886826490140251395415648899156864835350466583887285148750848
In the worst case, the number of digits in numerator and denominator
could double on each pass, so if you start with 1 digit in each,
you end with 2**100 in each. (You will run out of memory first
unless you have a machine with more than 64 bits of address space. :-) )
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: gmail (figure it out) http://web.torek.net/torek/index.html
--
http://mail.python.org/mailman/listinfo/python-list
