Working with the set of real numbers
Chris Angelico
rosuav at gmail.com
Tue Mar 4 16:18:29 EST 2014
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
More information about the Python-list
mailing list