Shifting nth Root Algorithm - Paper-and-pencil nth Roots

Paper-and-pencil nth 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×(02)×1+30×0×(12)+13 - 2 000 1 744 = 300×(12)×4+30×1×(42)+43 ----- 256 000 241 984 = 300×(142)×4+30×14×(42)+43 ------- 14 016 000 12 458 888 = 300×(1442)×2+30×144×(22)+23 ---------- 1 557 112 000 1 247 791 448 = 300×(14422)×2+30×1442×(22)+23 ------------- 309 320 552 000 249 599 823 424 = 300×(144222)×4+30×14422×(42)+43 --------------- 59 720 728 576

Note that after the first iteration or two the leading term dominates the, so we can get an often correct first guess at β by dividing by .