## 10023 - Square root

**Moderator:** Board moderators

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

Pell's equation: x^2 - ny^2 = 1

from Wikipedia.org

The problem is: this equation can only be solved if n is not a perfect square like 1,4,9,16 and so on.

Could you explain how you used this equation to compute square root of integers which are perfect squares as well as those that are not perfect squares?

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

http://en.wikipedia.org/wiki/Methods_of ... s_equation

I used this to solve this problem, and it also works for perfect squares!

I used this to solve this problem, and it also works for perfect squares!

The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

I have some problem is the Pell's equation is fast than binary search!?little joey wrote:http://en.wikipedia.org/wiki/Methods_of ... s_equation

I used this to solve this problem, and it also works for perfect squares!

sqrt(16)

binary search

(0+16)/2=8 8*8>=16

(0+8 )/2=4 4*4==16 finish (only two steps)

sqrt(16)

Pell's equation

16-1=15

15-3=12

12-5=7

7-7=0 (has four steps)

The steps of Pell's equation method is more than binary search method.

Is Pell's equation fast than binary search!?

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

Well, your program using binary search times out, and my program using Pell finishes in time, so I would say yes. There is theoretical foundation for this statement, because Pell's method only uses addition and subtraction which have a time complexity linear in the number of digits, and binary search uses multiplication which has a time complexity quadratic in the number of digits. Even though the number of additions/subtractions in the first method is bigger than the number of multiplications in the second, the first method will be faster than the second for enough digits.IRA wrote:I have some problem is the Pell's equation is fast than binary search!?

You might get this problem solved in time using fast multiplication algorithms (like Karatsuba); I don't know, I haven't tried. I think Newtons method (like mf suggested) is faster for this problem then Pell's, but requires you to implement long division (correct me anybody if I'm wrong), and you asked for a method that avoided this, so I suggested Pell's.

As I already told you two times before: I used Pell's method to solve this problem, and my program passes the time limit, so

**YES**it is possible to use it to solve the problem in time. It will not give you the fastest time possible, but FAIK it is the simplest method in terms of manipulating big numbers.

The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

### So what is the algorithm?

Tell please the algorithm.

Your link does not tell the exact algorithm.

Thanks.

Your link does not tell the exact algorithm.

Thanks.

Thank you!little joey wrote:Well, your program using binary search times out, and my program using Pell finishes in time, so I would say yes. There is theoretical foundation for this statement, because Pell's method only uses addition and subtraction which have a time complexity linear in the number of digits, and binary search uses multiplication which has a time complexity quadratic in the number of digits. Even though the number of additions/subtractions in the first method is bigger than the number of multiplications in the second, the first method will be faster than the second for enough digits.IRA wrote:I have some problem is the Pell's equation is fast than binary search!?

You might get this problem solved in time using fast multiplication algorithms (like Karatsuba); I don't know, I haven't tried. I think Newtons method (like mf suggested) is faster for this problem then Pell's, but requires you to implement long division (correct me anybody if I'm wrong), and you asked for a method that avoided this, so I suggested Pell's.

As I already told you two times before: I used Pell's method to solve this problem, and my program passes the time limit, soYESit is possible to use it to solve the problem in time. It will not give you the fastest time possible, but FAIK it is the simplest method in terms of manipulating big numbers.

I will try it!

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

?!?IRA wrote:When input value is 10^1000,pell's equation must do 10^1000 Add and 10^500 Sub.

Looks like you didn't understand the algorithm. Let's work out an example:

Code: Select all

```
Take the square root of 148996.
Preparation:
- make groups of two digits, starting from the right: 14-89-96. (if the number of digits was odd, the leftmost group would have only one digit);
- initialise the variables remain, odd and answer with 0.
Loop for every group of two digits, from left to right:
- odd = 20 * answer +1;
- remain = 100 * remain + group;
- count = 0;
- loop while remain >= odd:
- count = count + 1;
- remain = remain - odd;
- odd = odd + 2;
- answer = 10 * answer + count.
In our example we have 3 iterations of the outer loop:
Iteration 1 (group = 14):
initial: odd = 20 * 0 + 1 = 1, remain = 100 * 0 + 14 = 14;
inner loops: remain = 14 - 1 - 3 - 5 = 5, count = 3;
finaly: answer = 10 * 0 + 3 = 3.
Iteration 2 (group = 89):
initial: odd = 20 * 3 +1 = 61, remain = 100 * 5 + 89 = 589;
inner loops: remain = 589 - 61 - 63 - 65 - 67 - 69 - 71 - 73 - 75 = 45, count = 8;
finaly: answer = 10 * 3 + 8 = 38.
Iteration 3 (group = 96):
initial: odd = 20 * 38 + 1 = 761, remain = 100 * 45 + 96 = 4596;
inner loops: remain = 4596 - 761 -763 - 765 - 767 - 769 - 771 = 0, count = 6;
finaly: answer = 10 * 38 + 6 = 386.
So the square root of 148996 is 386. This answer is exact, because the last remainder is 0.
```

The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

### Why number 20?

Why number 20 is used here? What does this number mean?

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

(10 * answer +1)^2 - (10 * answer)^2 = 20 * answer +1, the distance to the next square to test. If you understand how the algorithm works, it is not hard to see why you do this.

In the first iteration in the example you discovered that 3^2 <= 14 < (3+1)^2, so you know that 30^2 <= 1400. In the first step of the second iteration you will try to discover if (30+1)^2 <= 1489. You already know that 14 - 3^2 = 5 (remain), so you also know 1400 - 30^2 = 500, and therefor 1489 - 30^2 = 589. Now you subtract (31^2 - 30^2) from 589 to discover that 1489 - 31^2 = 589 - (31^2 - 30^2) = 528, and therefor 31^2 <= 1489.

In the first iteration in the example you discovered that 3^2 <= 14 < (3+1)^2, so you know that 30^2 <= 1400. In the first step of the second iteration you will try to discover if (30+1)^2 <= 1489. You already know that 14 - 3^2 = 5 (remain), so you also know 1400 - 30^2 = 500, and therefor 1489 - 30^2 = 589. Now you subtract (31^2 - 30^2) from 589 to discover that 1489 - 31^2 = 589 - (31^2 - 30^2) = 528, and therefor 31^2 <= 1489.