On Wed, Mar 5, 2014 at 7:55 AM, Oscar Benjamin
<[email protected]> 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
--
https://mail.python.org/mailman/listinfo/python-list
