Shifting nth Root Algorithm - Algorithm - Main Loop

Main Loop

On each iteration we shift in n digits of the radicand, so we have and we produce 1 digit of the root, so we have . We want to choose β and r' so that the invariants described above hold. It turns out that there is always exactly one such choice, as will be proved below.

The first invariant says that:


So, pick the largest integer β such that

and let

Such a β always exists, since if then the condition is, but, so this is always true. Also, β must be less than B, since if then we would have

but the second invariant implies that

and since and are both multiples of the difference between them must be at least, and then we have

but by definition of α, so this can't be true, and is a monotonically increasing function of β, so it can't be true for larger β either, so we conclude that there exists an integer γ with such that an integer r' with exists such that the first invariant holds if and only if .

Now consider the second invariant. It says:


Now, if β is not the largest admissible β for the first invariant as described above, then is also admissible, and we have

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'.

To summarize, on each iteration:

  1. Let α be the next aligned block of digits from the radicand
  2. Let
  3. Let β be the largest β such that
  4. Let
  5. Let

Now, note that, so the condition

is equivalent to


is equivalent to

Thus, we don't actually need, and since and, or, or, so by using instead of we save time and space by a factor of 1/n. Also, the we subtract in the new test cancels the one in, so now the highest power of y we have to evaluate is rather than .

Read more about this topic:  Shifting nth Root Algorithm, Algorithm

Other articles related to "main loop, main":

Xiaolin Wu's Line Algorithm
... gradient * (xend - x0) xgap = rfpart(x0 + 0.5) xpxl1 = xend // this will be used in the main loop ypxl1 = ipart(yend) if steep then plot(ypxl1, xpxl1, rfpart(yend) * xgap) plot(ypx ...
Event-driven Programming - Event Handlers - Creating Event Handlers
... These routines handle the events to which the main program will respond ... an event-driven program is to write the main loop ... event-driven programming environments already provide this main loop, so it need not be specifically provided by the application programmer ...

Famous quotes containing the word main:

    Whether or not his newspaper and a set of senses reduced to five are the main sources of the so-called “real life” of the so- called average man, one thing is fortunately certain: namely, that the average man himself is but a piece of fiction, a tissue of statistics.
    Vladimir Nabokov (1899–1977)