10023 - Square root

[mf]

Binary search isn't fast enough for this problem. You need something more clever (e.g. Newton's method.)

[IRA]

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.
Please, give me a hint.
Thanks!

[little joey]

Did you read the previous posts about this problem?
I once gave a hint about Pell's equation. You can take a square root only using addition and subtraction.

[IRA]

Did you read the previous posts about this problem?
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]

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]

http://en.wikipedia.org/wiki/Methods_of ... s_equation
I used this to solve this problem, and it also works for perfect squares!

[IRA]

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]

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.

[medv]

Tell please the algorithm.
Your link does not tell the exact algorithm.
Thanks.

[IRA]

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]

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]

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.

Did we need 148996 additions and 386 subtractions, as your statement would suggest? Far from that!

[chunyi81]

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]

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

[little joey]

(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.