|
|
| (530 intermediate revisions by more than 100 users not shown) |
| Line 1: |
Line 1: |
| {{DISPLAYTITLE:Shifting ''n''th root algorithm}}
| | This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users. |
| {{unreferenced|date=May 2010}}
| |
| The '''shifting ''n''th root algorithm''' is an [[algorithm]] for extracting the [[nth root|''n''th root]] of a positive [[real number]] which proceeds iteratively by shifting in ''n'' [[numerical digit|digits]] of the radicand, starting with the most significant, and produces one digit of the root on each iteration, in a manner similar to [[long division]].
| |
|
| |
|
| ==Algorithm==
| | If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]] |
| ===Notation===
| | * Only registered users will be able to execute this rendering mode. |
| | * Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere. |
|
| |
|
| Let ''B'' be the [[radix|base]] of the number system you are using, and ''n'' be the degree of the root to be extracted. Let ''x'' be the radicand processed thus far, ''y'' be the root extracted thus far, and ''r'' be the remainder. Let α be the next ''n'' digits of the radicand, and β be the next digit of the root. Let ''x''<nowiki>'</nowiki> be the new value of ''x'' for the next iteration, ''y''<nowiki>'</nowiki> be the new value of ''y'' for the next iteration, and ''r''<nowiki>'</nowiki> be the new value of ''r'' for the next iteration. These are all [[integer]]s.
| | Registered users will be able to choose between the following three rendering modes: |
|
| |
|
| ===Invariants===
| | '''MathML''' |
| At each iteration, the [[invariant (mathematics)|invariant]] <math>y^n + r = x</math> will hold. The invariant <math>(y+1)^n>x</math> will hold. Thus ''y'' is the largest integer less than the ''n''th root of x, and ''r'' is the [[remainder]].
| | :<math forcemathmode="mathml">E=mc^2</math> |
|
| |
|
| ===Initialization===
| | <!--'''PNG''' (currently default in production) |
| The initial values of ''x'', ''y'', and ''r'' should be 0. The value of α for the first iteration should be the most significant aligned block of ''n'' digits of the radicand. An aligned block of ''n'' digits means a block of digits aligned so that the decimal point falls between blocks. For example, in 123.4 the most significant aligned block of 2 digits is 01, the next most significant is 23, and the third most significant is 40.
| | :<math forcemathmode="png">E=mc^2</math> |
|
| |
|
| ===Main loop===
| | '''source''' |
| On each iteration we shift in ''n'' digits of the radicand, so we have <math>x' = B^n x + \alpha</math> and we produce 1 digit of the root, so we have <math>y' = B y + \beta </math>. We want to choose β and ''r''<nowiki>'</nowiki> so that the invariants described above hold. It turns out that there is always exactly one such choice, as will be proved below.
| | :<math forcemathmode="source">E=mc^2</math> --> |
|
| |
|
| The first invariant says that:
| | <span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples]. |
|
| |
|
| :<math>x' = y'^n + r'</math>
| | ==Demos== |
|
| |
|
| or
| | Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]: |
|
| |
|
| :<math>B^n x + \alpha = (B y + \beta)^n + r'.</math>
| |
|
| |
|
| So, pick the largest integer β such that
| | * accessibility: |
| | ** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)] |
| | ** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]]. |
| | ** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]]. |
| | ** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode. |
|
| |
|
| :<math>(B y + \beta)^n \le B^n x + \alpha</math>
| | ==Test pages == |
|
| |
|
| and let | | To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages: |
| | *[[Displaystyle]] |
| | *[[MathAxisAlignment]] |
| | *[[Styling]] |
| | *[[Linebreaking]] |
| | *[[Unique Ids]] |
| | *[[Help:Formula]] |
|
| |
|
| :<math>r' = B^n x + \alpha - (B y + \beta)^n.</math>
| | *[[Inputtypes|Inputtypes (private Wikis only)]] |
| | | *[[Url2Image|Url2Image (private Wikis only)]] |
| Such a β always exists, since if <math>\beta = 0</math> then the condition is <math>B^n y^n \le B^n x + \alpha</math>, but <math>y^n \le x</math>, so this is always true. Also, β must be less than ''B'', since if <math>\beta = B</math> then we would have
| | ==Bug reporting== |
| | | If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de . |
| :<math>(B(y+1))^n \le B^n x + \alpha\,</math>
| |
| | |
| but the second invariant implies that
| |
| | |
| :<math>B^n x < B^n (y+1)^n\,</math>
| |
| | |
| and since <math>B^n x</math> and <math>B^n (y+1)^n</math> are both multiples of <math>B^n</math> the difference between them must be at least <math>B^n</math>, and then we have
| |
| | |
| :<math>B^n x + B^n \le B^n (y+1)^n\,</math>
| |
| :<math>B^n x + B^n \le B^n x + \alpha\,</math>
| |
| :<math>B^n \le \alpha\,</math>
| |
| | |
| but <math>0 \le \alpha < B^n</math> by definition of α, so this can't be true, and <math>(B y + \beta)^n</math> is a monotonically increasing function of β, so it can't be true for larger β either, so we conclude that there exists an integer γ with <math>\gamma<B</math> such that an integer ''r''<nowiki>'</nowiki> with <math>r' \ge 0</math> exists such that the first invariant holds if and only if <math>0 \le \beta \le \gamma</math>.
| |
| | |
| Now consider the second invariant. It says:
| |
| | |
| :<math>(y'+1)^n > x' \,</math>
| |
| | |
| or
| |
| | |
| :<math>(B y + \beta + 1)^n>B^n x + \alpha\,</math>
| |
| | |
| Now, if β is not the largest admissible β for the first invariant as described above, then <math>\beta + 1</math> is also admissible, and we have
| |
| | |
| :<math>(B y + \beta + 1)^n \le B^n x + \alpha\,</math>
| |
| | |
| This violates the second invariant, so to satisfy both invariants we must pick the largest β allowed by the first invariant. Thus we have proven the existence and uniqueness of β and ''r''<nowiki>'</nowiki>.
| |
| | |
| To summarize, on each iteration:
| |
| # Let α be the next aligned block of digits from the radicand
| |
| # Let <math>x' = B^n x + \alpha</math>
| |
| # Let β be the largest β such that <math>(B y + \beta)^n \le B^n x + \alpha</math>
| |
| # Let <math>y' = B y + \beta</math>
| |
| # Let <math>r' = x' - y'^n</math>
| |
| | |
| Now, note that <math>x = y^n + r</math>, so the condition
| |
| | |
| :<math>(B y + \beta)^n \le B^n x + \alpha</math>
| |
| | |
| is equivalent to
| |
| | |
| :<math>(B y + \beta)^n - B^n y^n \le B^n r + \alpha</math>
| |
| | |
| and
| |
| | |
| :<math>r' = x' - y'^n = B^n x + \alpha - (B y + \beta)^n</math>
| |
| | |
| is equivalent to
| |
| | |
| :<math>r' = B^n r + \alpha - ((B y + \beta)^n - B^n y ^n)</math>
| |
| | |
| Thus, we don't actually need <math>x</math>, and since <math>r = x - y^n</math> and <math>x<(y+1)^n</math>, <math>r<(y+1)^n-y^n</math> or <math>r<n y^{n-1}+O(y^{n-2})</math>, or <math>r<n x^{{n-1}\over n} + O(x^{{n-2}\over n})</math>, so by using <math>r</math> instead of <math>x</math> we save time and space by a factor of 1/''n''. Also, the <math>B^n y^n</math> we subtract in the new test cancels the one in <math>(B y + \beta)^n</math>, so now the highest power of ''y'' we have to evaluate is <math>y^{n-1}</math> rather than <math>y^n</math>.
| |
| | |
| ===Summary===
| |
| # Initialize ''r'' and ''y'' to 0.
| |
| # Repeat until desired [[decimal precision|precision]] is obtained:
| |
| ## Let α be the next aligned block of digits from the radicand.
| |
| ## Let β be the largest β such that <math>(B y + \beta)^n - B^n y^n \le B^n r + \alpha.</math>
| |
| ## Let <math>y' = B y + \beta</math>.
| |
| ## Let <math>r' = B^n r + \alpha - ((B y + \beta)^n - B^n y^n).</math>
| |
| ## Assign <math>y \leftarrow y'</math> and <math>r \leftarrow r'.</math>
| |
| # <math>y</math> is the largest integer such that <math>y^n<x B^k</math>, and <math>y^n+r=x B^k</math>, where <math>k</math> is the number of digits of the radicand after the decimal point that have been consumed (a negative number if the algorithm hasn't reached the decimal point yet).
| |
| | |
| ==Paper-and-pencil ''n''th roots== | |
| As noted above, this algorithm is similar to long division, and it lends itself to the same notation:
| |
| | |
| 1. 4 4 2 2 4
| |
| ----------------------
| |
| _ 3/ 3.000 000 000 000 000
| |
| \/ 1 = 300×(0<sup>2</sup>)×1+30×0×(1<sup>2</sup>)+1<sup>3</sup>
| |
| -
| |
| 2 000
| |
| 1 744 = 300×(1<sup>2</sup>)×4+30×1×(4<sup>2</sup>)+4<sup>3</sup>
| |
| -----
| |
| 256 000
| |
| 241 984 = 300×(14<sup>2</sup>)×4+30×14×(4<sup>2</sup>)+4<sup>3</sup>
| |
| -------
| |
| 14 016 000
| |
| 12 458 888 = 300×(144<sup>2</sup>)×2+30×144×(2<sup>2</sup>)+2<sup>3</sup>
| |
| ----------
| |
| 1 557 112 000
| |
| 1 247 791 448 = 300×(1442<sup>2</sup>)×2+30×1442×(2<sup>2</sup>)+2<sup>3</sup>
| |
| -------------
| |
| 309 320 552 000
| |
| 249 599 823 424 = 300×(14422<sup>2</sup>)×4+30×14422×(4<sup>2</sup>)+4<sup>3</sup>
| |
| ---------------
| |
| 59 720 728 576
| |
| | |
| Note that after the first iteration or two the leading term dominates the
| |
| <math>(B y + \beta)^n - B^n y^n</math>, so we can get an often correct first guess at β by dividing <math>r + \alpha</math> by <math>n B^{n-1} y^{n-1}</math>.
| |
| | |
| ==Performance==
| |
| On each iteration, the most time-consuming task is to select β. We know that there are ''B'' possible values, so we can find β using <math>O(\log(B))</math> comparisons. Each comparison will require evaluating <math>(B y +\beta)^n - B^n y^n</math>. In the ''k''th iteration, y has ''k'' digits, and the polynomial can be evaluated with <math>2 n - 4</math> multiplications of up to <math>k(n-1)</math> digits and <math>n - 2</math> additions of up to <math>k(n-1)</math> digits, once we know the powers of ''y'' and β up through <math>n-1</math> for ''y'' and ''n'' for β. β has a restricted range, so we can get the powers of β in constant time. We can get the powers of ''y'' with <math>n-2</math> multiplications of up to <math>k(n-1)</math> digits. Assuming ''n''-digit multiplication takes time <math>O(n^2)</math> and addition takes time <math>O(n)</math>, we take time
| |
| <math>O(k^2 n^2)</math> for each comparison, or time <math>O(k^2 n^2 \log(B))</math> to pick β. The remainder of the algorithm is addition and subtraction that takes time <math>O(k)</math>, so each iteration takes <math>O(k^2 n^2 \log(B))</math>. For all ''k'' digits, we need time <math>O(k^3 n^2 \log(B))</math>.
| |
| | |
| The only internal storage needed is ''r'', which is <math>O(k)</math> digits on the ''k''th iteration. That this algorithm doesn't have bounded memory usage puts an upper bound on the number of digits which can be computed mentally, unlike the more elementary algorithms of arithmetic. Unfortunately, any bounded memory state machine with periodic inputs can only produce periodic outputs, so there are no such algorithms which can compute irrational numbers from rational ones, and thus no bounded memory root extraction algorithms.
| |
| | |
| Note that increasing the base increases the time needed to pick β by a factor of <math>O(log(B))</math>, but decreases the number of digits needed to achieve a given precision by the same factor, and since the algorithm is cubic time in the number of digits, increasing the base gives an overall speedup of <math>O(\log^2(B))</math>. When the base is larger than the radicand, the algorithm degenerates to [[binary search]], so it follows that this algorithm is not useful for computing roots with a computer, as it is always outperformed by much simpler binary search, and has the same memory complexity.
| |
| | |
| ==Examples==
| |
| ===Square root of 2 in binary===
| |
| | |
| 1. 0 1 1 0 1
| |
| ------------------
| |
| _ / 10.00 00 00 00 00 1
| |
| \/ 1 + 1
| |
| ----- ----
| |
| 1 00 100
| |
| 0 + 0
| |
| -------- -----
| |
| 1 00 00 1001
| |
| 10 01 + 1
| |
| ----------- ------
| |
| 1 11 00 10101
| |
| 1 01 01 + 1
| |
| ---------- -------
| |
| 1 11 00 101100
| |
| 0 + 0
| |
| ---------- --------
| |
| 1 11 00 00 1011001
| |
| 1 01 10 01 1
| |
| ----------
| |
| 1 01 11 remainder
| |
| | |
| ===Square root of 3===
| |
| 1. 7 3 2 0 5
| |
| ----------------------
| |
| _ / 3.00 00 00 00 00
| |
| \/ 1 = 20×0×1+1^2
| |
| -
| |
| 2 00
| |
| 1 89 = 20×1×7+7^2
| |
| ----
| |
| 11 00
| |
| 10 29 = 20×17×3+3^2
| |
| -----
| |
| 71 00
| |
| 69 24 = 20×173×2+2^2
| |
| -----
| |
| 1 76 00
| |
| 0 = 20×1732×0+0^2
| |
| -------
| |
| 1 76 00 00
| |
| 1 73 20 25 = 20×17320×5+5^2
| |
| ----------
| |
| 2 79 75
| |
| | |
| ===Cube root of 5===
| |
| 1. 7 0 9 9 7
| |
| ----------------------
| |
| _ 3/ 5.000 000 000 000 000
| |
| \/ 1 = 300×(0^2)×1+30×0×(1^2)+1^3
| |
| -
| |
| 4 000
| |
| 3 913 = 300×(1^2)×7+30×1×(7^2)+7^3
| |
| -----
| |
| 87 000
| |
| 0 = 300×(17^2)*0+30×17×(0^2)+0^3
| |
| -------
| |
| 87 000 000
| |
| 78 443 829 = 300×(170^2)×9+30×170×(9^2)+9^3
| |
| ----------
| |
| 8 556 171 000
| |
| 7 889 992 299 = 300×(1709^2)×9+30×1709×(9^2)+9^3
| |
| -------------
| |
| 666 178 701 000
| |
| 614 014 317 973 = 300×(17099^2)×7+30×17099×(7^2)+7^3
| |
| ---------------
| |
| 52 164 383 027
| |
| | |
| ===Fourth root of 7===
| |
| 1. 6 2 6 5 7
| |
| ---------------------------
| |
| _ 4/ 7.0000 0000 0000 0000 0000
| |
| \/ 1 = 4000×(0^3)×1+400×(0^2)×(1^2)+40×0×(1^3)+1^4
| |
| -
| |
| 6 0000
| |
| 5 5536 = 4000×(1^3)×6+600×(1^2)×(6^2)+40×1×(6^3)+6^4
| |
| ------
| |
| 4464 0000
| |
| 3338 7536 = 4000×(16^3)×2+600*(16^2)×(2^2)+40×16×(2^3)+2^4
| |
| ---------
| |
| 1125 2464 0000
| |
| 1026 0494 3376 = 4000×(162^3)×6+600×(162^2)×(6^2)+40×162×(6^3)+6^4
| |
| --------------
| |
| 99 1969 6624 0000
| |
| 86 0185 1379 0625 = 4000×(1626^3)×5+600×(1626^2)×(5^2)+
| |
| ----------------- 40×1626×(5^3)+5^4
| |
| 13 1784 5244 9375 0000
| |
| 12 0489 2414 6927 3201 = 4000×(16265^3)×7+600×(16265^2)×(7^2)+
| |
| ---------------------- 40×16265×(7^3)+7^4
| |
| 1 1295 2830 2447 6799
| |
| ==External links==
| |
| *[http://www.homeschoolmath.net/teaching/sqr-algorithm-why-works.php Why the square root algorithm works] "Home School Math". Also related pages giving examples of the long-division-like pencil and paper method for square roots.
| |
| | |
| [[Category:Root-finding algorithms]]
| |
| | |
| [[de:Schriftliches Wurzelziehen]]
| |
| [[fr:Algorithme de décalage n-racines]]
| |
| [[nl:Worteltrekken]]
| |
