World's Fastest Square Root: Newton's Method
HTML-код
- Опубликовано: 18 дек 2021
- Newton's method, from 1670, is a crazy fast way of generating square roots. The number of accurate digits in the square root doubles every single step.
It is derived by taking the Newton Raphson equation
en.wikipedia.org/wiki/Newton%...
and plugging in the equation for a square as the function x^2 = a
Images I used
newton pixabay.com/vectors/isaac-new...
telescope en.wikipedia.org/wiki/File:Ne...
prism en.wikipedia.org/wiki/File:Di...
Mercury commons.wikimedia.org/wiki/Fi...
calculus commons.wikimedia.org/wiki/Fi...
Newton Apple commons.wikimedia.org/wiki/Fi...
laws of motion commons.wikimedia.org/wiki/Fi...
quarter pixabay.com/photos/coin-quart...
chemistry pixabay.com/photos/test-tube-...
binomial pixabay.com/vectors/bayesian-... 
Наука
Halley's method is Newton's method but uses the second derivative as well as the first and gives third order convergence instead of second.
When your other works are so gigantic that such massive discoveries are ignored! Newton the goat.
I know right! Newton has done so much in his time, from the laws of motion to optics and to literally calculating π, these sort of things are never mentioned.
@@DeJay7 adding philosophical, theological and Others.
Oh my god I literally discovered this formula on paper using the average inequality an hour ago because I was just pissed off that my square root approximation program worked too slowly
We know that, the iterative formula to find bth root of a is given by:
Xn+1 = ( (b-1)*Xn + a/(Xn^(b-1)) ) / b
a=12
a^(1/6) = 1.513085749
1.513085749^6 = 12
12의 6제곱근 구하기
초기 x=1.513085749 로 잡았을 때,
x = ( (5)*x+ a/(x^5) )/6 = 1.513085749
a=12
a^(1/2.5) = 2.701920077
2.701920077^2.5 = 12
x=2.701920077
x = ( (2.5-1)*x+ a/(x^(2.5-1)) )/2.5 = 2.701920077
great video, straight to the point
super useful way, will use it all the time
Lies again? Sexist Racist
@@NazriB u ok bruh?
@@NazriB i am indeed a sexist racist, and many more on top of that
@@glasceur me too lmao
It does work with complex numbers too, for example 2-i with x0 = 1+i give us the following sequence
{.75-.25i, 1.775-0.325i, 1.4825096- 0.3352447i, 1.4555284-0.3433672i, 1.4554667-03435607i
1.4553467-0.3435607i } and ( 1.4553467-0.3435607i)^2 is 2-0.9999999i
unless you get a 0 during process
Very good explanation!
Nice video!
Quake 3 developer: I’m gonna ruin this man‘s entire career.
Vote up, nice video, thanks for sharing :)
Vey nice explanation. Loved the graphics. Thank you
Great insight
Thanks for making the video. The "average" part was the part I was missing in my intuition. This helped me!
I don't get it still. I don't get how we can know if something is bigger/smaller than 'real square root' if we don't know its value. How do we know if xn is too small then a/xn will be bigger than real root?
@@PinkeySuavo We don't need to know whether the guess is bigger or smaller, we just know that one term is bigger and one term is smaller than the real square root. Thus, taking the average of the two gets us closer to the real square root, and doing this process over and over again approaches the square root over time.
n/sqrt(n) = sqrt(n). If we overestimate the square root, n/guess will be smaller than the square root because a/BIG = small. On the other hand, if we underestimate the square root, n/guess will be bigger than the square root because a/small = BIG.
Does that help?
Another way...
Let C = number we want the square root of, G= our guess, and E = the error
If C = (G+E)^2, then C=G^2+2GE+E^2.
With a small error, E^2 is approximated as 0 so
C is approximately G^2+2GE and E is approximately (C-G^2)/(2G). You get the error value and you refine your original guess with it. A similar formula can be derived for solving cube roots, 4th roots, etc because all the powers of E greater than 1 drop out.
Thanks!
Newton was really genius. Discoveris of him are very very helpful. But you are doing very nice work such spreading this knowledge all over world keep it up bro 👌👏
AWESOME...🔥🔥
thank you
감사합니다 😍😍😍
Thnx, nice insights.
Finally an AC of Moriarty the Patriot.
@@animecartoon6545 You like that anime too?
@@animecartoon6545 ikr
I want to ask one thing...not related to this...
But how can you give an ad on RUclips as u r not eligible currently?
Ok so i want to tell you something...
I was working on finding values of negative factorials and a formula for that from like 1and ½ years maybe... I want help from you so that i can tell everyone what i found...
Maybe it's not true but i had discussed my theory with my sir and he agreed... Also it gives value of 1/0 and amazingly, 1/0 isn't infinity.... I want to publish this if it's all true....
Why would you say 1/0 isn’t infinity? That implies it’s finite, or not defined.
Because division would involve partitioning 1 into groups of 0, how many groups would there be?
Did you mean 1/0 is not defined? I’ve tried negative factorials as well and I got the same result as you
Looks like narrowing the variance with each successive iteration.
Good luck dividing 3 by 1.732
@@notroboteva7601good luck dividing that
what do you mean
thanks
Interesting
Very Well explained
Is it possible any number may square root? It is in what ways? My brain was exploding when it comes of rooting.
damn that's so simple and beautiful newton is the true og
X=(X+A/X)/2 X= Square Root ( A ) | X=A/X X= Square Root ( A )
Huh, that division method for square root yields answers with same accuracy but 10x faster.
1:51
Isn't it easier to do it this way, compared to the longer formula?
Working on an FPGA and I found the best general approximator is [(a+b) >> 1] for sqrt(a*b).
how do you make those write on effect in the beginning? looks epic! I want to know how if you don't mind
manim i suppose
@@stashkoilia3954 thanks man you are right!
is this method built into calculators for roots or is there another method?
Not sure, but taylor's polynomial expansion is also a common way to approximate some functions. Not sure how well it works with the square root function, but for exponentials, sines, cosines, it's a very good method
@@nycan7725 thanks for the clarification.
maybe for basic calculators, more advanced probably use sqrt(x) == x^½
@@dudono1744 a computer understands x^2 as x times x, so x^(1/2) would result in an error if there is not a specific square root algorithm programmed in the computer. You know cuz you can't multiply x (1/2) times by x
@@takeuchi5760 convert x^n into e^(n ln(x)) then use taylor series. This works for all real number n larger than 0. Ofc it does require a computation of ln(x) too, so depending on the situation may not be as efficient.
When we average between our previous guess and the square divided by our previous guess, one of the guesses (guess, and square / guess) will be smaller than the solution, one will be larger, and the average will be somewhere inbetween, closer to the answer
If you notice, x / sqrt(x) == sqrt(x), so as a sanity check, if we have the solution, and we iterate again, what we get is (sqrt(x) + x / sqrt(x))/2 which == (sqrt(x) + sqrt(x))/2 == sqrt(x)
This is really neat.
Qual deles?
It walks for functions.
Thank you that was useful
Is there a method to calculate best estimate of x0 ?
Buy an old engineer’s slide rule and get your initial estimate from the R scales. Or, use the Babylonian method.
I am more eager to know how Newton's eq of square roots have been derived from Newton-Raphson eq
If you'll make a video on the same I'll be grateful ... Thanks
look on the top of the second page here
math.mit.edu/~stevenj/18.335/newton-sqrt.pdf
the general equation is
xn+1 = xn - f(x) / f'(x)
we use f(x) = x^2 - a because x^2 - a = 0 is the general form for a square root
@@dubiousinsights4008thank you so much for this ❤
Wait, I'm confused. Newton's method (as shown at the beginning of the video) is used to solve the roots (zeroes) of an equation. Not to get the square root of a number. The equation you showed later in the video is different. Is Newton's method just more general then the one in the later half? And how does the square root relate to the zeroes of an equation?
Newton Raphson method is used to find any value of any function if you know the inverse of the function. For example, the inverse of sqrt is known which is square so square root of any number can be calculated. Similarly inverse of cube root is cube so it does too. Same goes of other function like logarithm, trignometric functions, because we can easily calculate the values of inverse of logarithm i.e exponential function or the same does for trigo functions. But it can only be done with Genralised Newton Rhapson method. Every function yield different formula for approximation which depends upon inverse of that function
@@rishabhsemwal4180 Thank you!
Couldn't understand 😑. Please explain me!
911th subscriber present!
Man this is a life saver
I think I'll stick to just pressing the √ button on the calculator.
love me some quality content
Fastest? Not so sure. When you have to divide a huge number, it seems more complicated than doing a simple extraction.
sigma rule no 314:Use calculator
Sorry... Not anymore!
It is Heron’s method
The Only person who made our life Hell🙂🖐️
*My freind in the examination room* : "Oh no, I forgot the calculator, what am I supposed to do!
*Me, an intellectual* : "I saw this video yesterday that shall help me in solving this surd in only 15 steps, calculator I need not!"
I just use the long division method.
That's because calculators are banned here in exams.
So, it only takes 20 minutes to get to the estimate! How convenient can Math get? No, never mind.
OMG this just saved me like tens and hundreds of marks which I would have lost because of not knowing the actual method of finding square roots
dude you saved my life, I am so stupid. Now i see why it works (5 years of programming experience lol)
You started off by showing Newton-Raphson formula.
But you ended up showing the Babylonian method.
In fact the Babylonian method is a particular case for Newton's method.
I don't know how they derived it in ancient times, but solving x²-a=0 using Newton's method will give you the same formula for sqrt(a).
@@victorpaesplinio2865 I have a ‘theory’ (conjecture, speculation) on how the Babylonians derived their method.
Let the unknown quantity be X and the square be S.
X^2=S
X=S/X (we’ve divided both sides by X)
X/2=S/2X (divided both sides by 2)
X=X/2+S/2X (adding 2 halves to make whole)
X’=1/2(X+S/2X) after taking out the common term.
That is the way I independently stumbled on the method long before I knew it had a name.
I might be wrong, but some say this is the Babylonian method, not Newton's discovery.
Ain't that heron's algorithm?
Yeah, thought so too...
Yes, Heron of Alexandria (10-70 AD), but might also have been known to the ancient Babylonians.
@@ScottMorgan88 ah, thank you for explaining
@@noname_panda2836 NP. Newton's method is more general than Heron's, as it applies to any differentiable function, but reduces to Heron's formula for square roots.
Newton was the greatest
You need to talk much faster. When you sound like a mosquito, you will have achieved success.
Fastest way for sure. Kappa.
Please get a better mic that doesn’t pick up your mouth sounds
Disagreed
The world's fastest computer based (java or C#) 'Newton's method' can be found by searching "NewtonPlus Square root".
Vote up, nice video, thanks for sharing :)
Thanks!
Ok so i want to tell you something...
I was working on finding values of negative factorials and a formula for that from like 1and ½ years maybe... I want help from you so that i can tell everyone what i found...
Maybe it's not true but i had discussed my theory with my sir and he agreed... Also it gives value of 1/0 and amazingly, 1/0 isn't infinity.... I want to publish this if it's all true....
My maternal uncle is a writer and he also published some book he may help you ..