Working with the set of real numbers

Marko Rauhamaa 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.


Marko



More information about the Python-list mailing list