## 10023 - Square root

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Binary search isn't fast enough for this problem. You need something more clever (e.g. Newton's method.)

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
mf wrote:Binary search isn't fast enough for this problem. You need something more clever (e.g. Newton's method.)
When I use Newton's method , I encounter long division problem.
How can I do to avoid long division problem.
Thanks!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I once gave a hint about Pell's equation. You can take a square root only using addition and subtraction.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
I once gave a hint about Pell's equation. You can take a square root only using addition and subtraction.
Pell's equation how do I use it?
Can you show the equation for me,please.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
This is what I found:

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!
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
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!
I have some problem is the Pell's equation is fast than binary search!?

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
IRA wrote:I have some problem is the Pell's equation is fast than binary search!?
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.

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.

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

### So what is the algorithm?

Thanks.

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
little joey wrote:
IRA wrote:I have some problem is the Pell's equation is fast than binary search!?
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.

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.
Thank you!
I will try it!

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
I try pell's equation method but still too late...
When input value is 10^1000,pell's equation must do 10^1000 Add and 10^500 Sub.
I still have some problem is the Pell's equation is fast than binary search!?

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;

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.``````
Did we need 148996 additions and 386 subtractions, as your statement would suggest? Far from that!
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
That makes sense now. It seems that some big integer multiplications are involved but you don't need big integer multiplications at all, since you are multiplying by either 20 or 100. To multiply by 20, multiply by 10 and then 2. Multiplying by 2 can be done with 1 additions.

Thank you little joey.

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

### 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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.