Working with the set of real numbers

[Chris Angelico]

On Wed, Mar 5, 2014 at 7:55 AM, Oscar Benjamin
<oscar.j.benjamin at gmail.com> wrote:
> I don't quite follow your reasoning here. By "cut-and-try" do you mean
> bisection? If so it gives the first N decimal digits in N*log2(10)
> iterations. However each iteration requires a multiply and when the
> number of digits N becomes large the multiplication is worse than
> linear. So the result is something like N**2 log(N)log(log(N)),

By "cut and try" I'm talking about the really REALLY simple algorithm
for calculating square roots. It's basically brute force.

epsilon = 0.0001
def sqrt(n):
    guess1, guess2 = 1, n
    while abs(guess1-guess2) > epsilon:
        guess1 = n/guess2
        guess2 = (guess1 + guess2)/2
   return guess1

It's generally going to take roughly O(n*n) time to generate n digits,
give or take. That's the baseline against which anything else can be
compared. There are plenty of better ways to calculate them.

ChrisA