On Wednesday, June 1, 2011 11:10:33 AM UTC-7, Ethan Furman wrote: > 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.) > > Okay, will this thing ever stop? It's been running for 90 minutes now. > Is it just incredibly slow? > > Any enlightenment appreciated!
Fraction needs to find the LCD of the denominators when adding; but LCD calculation becomes very expensive as the denominators get large (which they will since you're dividing by an intermediate result in a loop). I suspect the time needed grows exponentially (at least) with the value of the denominators. The LCD calculation should slow the calculation down to an astronomical crawl well before you encounter memory issues. This is why representation simply cannot be left as an implementation detail; rationals and floating-points behave too differently. Carl Banks -- http://mail.python.org/mailman/listinfo/python-list
