|
Project Euler Homework
|
Do square root of a large number. More...
Public Member Functions | |
| largeN (int w, int x, int y, int z) | |
| unsigned | remainder (unsigned k) |
| largeN | divide (unsigned k) |
| double | sq_root () |
| void | print () |
Public Attributes | |
| unsigned | sqrtN |
Do square root of a large number.
Since C++ cannot handle integer larger than 32bits, we need to split the number to smaller parts. I have chosen to split it to 4 digits because it is easier to handle. a=0,b=6008,c=5147, d=5143 so 
To find the smallest prime factor, we can check by division of N using integers from 1 to sqrt(N). Since N is split up, we need to implement special division and modulo algorithm.
After finding the smallest prime factor, the 2nd and 3rd prime factor can be found and eventually the last and largest factor can be found.
To estimate sqrt(N):
![\[ N^{1/2}=(x+y)^{1/2}=x^{1/2}(1+\frac{y}{x})^{1/2}=x^{1/2}(1+\frac{y}{2 x}+\ldots) \]](form_1.png)
If x>>y, the higher order terms can be omitted without affecting the accuracy of sqrt(N) This formula can be applied several times until x is small enough.
1.7.3
