Working with the set of real numbers
marko at pacujo.net
Tue Mar 4 20:49:03 CET 2014
Chris Angelico <rosuav at gmail.com>:
> As far as I know, there's no simple way, in constant space and/or
> time, to progressively yield more digits of a number's square root,
> working in decimal.
I don't know why the constant space/time requirement is crucial. Anyway,
producing more digits simple: <URL: http://nrich.maths.org/5955>.
I believe producing the nth digit is O(n) in time and space.
Still, there's more to arithmetics than that. For example, if you have
two generated decimal expansions, you don't have an effective algorithm
to generate the decimal expansion of their ratio. That's because there's
no effective algorithm to decide if a < b.
More information about the Python-list