When I use Newton's method , I encounter long division problem.mf wrote:Binary search isn't fast enough for this problem. You need something more clever (e.g. Newton's method.)
Pell's equation how do I use it?little joey wrote: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.
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!
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!?
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, 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.
?!?IRA wrote:When input value is 10^1000,pell's equation must do 10^1000 Add and 10^500 Sub.
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.