4
$\begingroup$

After spending considerable amount of time to find an intuitive explanation, I've decided to come here and ask a question.

Aside of long division, there exist other methods of division. One of such methods is galley division, used widely before long division became popular in Europe. For those who aren't familiar with this method, click here for a short explanation of its algorithm.

Niccolo Tartaglia mentioned that it is possible to get roots by using the same method. Here, in his book, he has an example of extracting a square root. However, I couldn't find a general algorithm that makes it possible to extract $n$th roots by galley division, though according to same Tartaglia, such algorithm does exist.

The question is, what is the algorithm behind that, and how to extract $n$th roots using galley division?

Thanks in advance.

$\endgroup$
9
  • 2
    $\begingroup$ I've done cube roots in what I think was an analogous way, but it was a tremendous pain. Essentially, it involves applying the binomial theorem to the residuals. Is that enough to tell whether it's the same thing? I can't imagine fruitfully doing the same thing for fourth roots or any higher degree. $\endgroup$
    – Brian Tung
    Oct 7, 2022 at 18:22
  • $\begingroup$ @BrianTung Yes, it is the same thing. It uses the binomial theorem. If you explain how it is done, the bounty is all yours. $\endgroup$
    – Rusurano
    Oct 7, 2022 at 18:26
  • 2
    $\begingroup$ I just read some articles on galley division and it looks incredible - American schools don't see this. $\endgroup$ Oct 7, 2022 at 19:24
  • 1
    $\begingroup$ If I can get enough time, I'll look more closely at the links you posted, make sure we're talking about the same thing, and I'll write something up. No guarantees, though; I remember it being somewhat involved. I might have an answer somewhere here that talks about extracting square roots though. $\endgroup$
    – Brian Tung
    Oct 7, 2022 at 22:27
  • 2
    $\begingroup$ I've exceeded 30000 characters , so what I've written won't fit in one answer! I'll write a second answer and have it up by tomorrow. $\endgroup$ Oct 8, 2022 at 19:26

2 Answers 2

3
+150
$\begingroup$

This is part one of the answer , which covers just the Galley method for division and for square roots, the Tartaglia way. The second part will cover a procedure for nth roots.

Introduction

The Galley method of division , according to Prof. Lam Lay Yong[1], originated in the work Sunzi Suanjing, written in about $400$AD. It was also used by Al-Khwarizmi (for example, in a work completed in $825$AD), and by the likes of Galileo and Tartaglia. It was usurped by long division in ~ $1700$, but remained the primary method of division until then.

Consult [2] for some more details on the history of this method.

We will first see what Galley division is , in general. Then, we'll see how it can be used for square, and then general $n$th root-type calculations.

The idea behind galley division

Take a look at this picture :

This is galley division, as performed by hand. It doesn't look like a galley, does it? I say it does, and you must trust me. Otherwise, do your best to create a boat-like structure around the galley division I perform, and you'll see where the name comes from. (Do it in the comments!)

I picked up this image from [3], which is another excellent well-written resource. However, we should take a look at the idea behind this division now.

Indeed, the idea behind galley division is the same as with long division : begin with the most significant digit, reduce the dividend by a digit at each turn, and simplify.

The key insight, however, is the following : imagine that one is not doing calculations on paper, but on sand instead (or think about writing on paper, but with a pencil whose marks are erasable). In that case, one can "cancel" a particular expression by simply erasing it, and then replace it with another term. This allows us to forget about initial terms and keep our field of view very small, constantly.

That seems to be the basic idea behind galley division : a lot of cancellations, but fewer numbers in total than long division. However, because cancellation marks were difficult to print (thankfully, they're not too difficult to MathJax!) , this method went out of sight, although it's not completely out of use : it's still taught in some parts of North Africa and the Middle East.

Note that in the figure above, figures are "cancelled" not by a strikethrough, but rather by having some other number written above them. That is one of three or four variants of this method, and the one that cancels properly (i.e. like writing on sand) is likely to give a better image of a boat.


A BABY example

Let's start with a baby example : take $858$ divided by $7$.

Step 1 : To begin, write the dividend below the divisor, in such a way that the leftmost digits of the dividend and divisor match up. Draw a vertical bar that is tall enough to capture both the dividend and divisor. This will be extended linearly if other rows are created, but it will be ensured that the quotient forms to the right of this bar, and the remainder will be what is left on the left-hand side, following cancellations.

$$ 858 | \\ 7\ \ \ \ | $$

Step 2 : The "temporary" dividend is formed as follows : as written, we find the position of the rightmost digit of the divisor. Then, everything to the left of that, in the dividend, forms the "temporary" dividend. In this case, that is only $8$. We will divide $8$ by $7$, and need only the quotient for now, which is $1$. Write a $1$ as the first digit of the quotient.

$$ 858 |1 \\ 7 \ \ \ \ | \ \ $$

Step 3 : Formally, we find the remainder of this division by using a cancellation. Note that $8 - 7 \times 1 = 1$, so we cancel the $8$ and write a $1$ above it, giving us a new dividend of $158$. Cancel out the divisor $7$ as well.

$$ \require{cancel} 1 \ \ \ \ |\\ \cancel{8} 58 |1 \\ \ \cancel{7} \ \ \ | \ \ $$

Step 4 : Shift the divisor one step to the right : this can be done by cancelling it and moving to a new line (which is what we do), or can be done by erasure. Now the $7$ will lie underneath the $5$. $$ 1 \ \ \ \ |\\ \cancel{8} 58 |1 \\ \cancel{7} \ \ \ \ | \ \ \\ \ \ 7 \ \ | $$

Step 5 : We are back to step 2. The position of the $7$ is now below the $5$, so taking everything to the right of $4$ gives us a temporary dividend of $15$. We know that $15$ divided by $7$ has a quotient of $2$. So write the $2$ now, after the $1$. $$ 1 \ \ \ \ |\\ \ \ \cancel{8} 58 |1 2 \\ \cancel{7} \ \ \ \ | \ \ \\ \ \ 7 \ \ | $$

Step 6 : The cancellation step gives $15 - (7 \times 2) = 1$. This is represented by cancelling the top $1$ entirely, and then crossing out the $5$ and writing a $1$ above it, so that effectively, $15$ has been rewritten as $1$. Cancel out the divisor $7$ in this process.

$$ \cancel{1} \ 1 \ \ \ | \ \ \\ \ \ \cancel{8} \cancel{5}8 |1 2 \\ \cancel{7} \ \ \ \ \ \ | \ \ \\ \ \ \cancel{7} \ \ | $$

Step 7 : Shift the divisor $7$ one step to the right, like in step 4.

$$ \cancel{1} \ 1 \ \ \ | \ \ \\ \ \ \cancel{8} \cancel{5}8 |1 2 \\ \cancel{7} \ \ \ \ \ \ | \ \ \\ \ \ \cancel{7} \ \ | \\ \ \ \ \ \ \ 7 | $$

Step 8 : The temporary dividend is given by everything to the right of $7$ as located, which leads to $18$ now. Clearly, the quotient is $2$, so we write that $2$ over there.

$$ \cancel{1} \ 1 \ \ \ | \ \ \\ \ \ \ \ \cancel{8} \cancel{5}8 |1 2 2 \\ \cancel{7} \ \ \ \ \ \ | \ \ \\ \ \ \cancel{7} \ \ | \\ \ \ \ \ \ \ 7 | $$

Step 9 : The cancellation step is performed, and $18 - (7 \times 2) = 4$. This is illustrated by cancelling the $1$, and writing a $4$ above the $8$. In effect, we have replaced the $18$ by a $4$. Cancel out the divisor $7$ again.

$$ \ \ \cancel{1} \ \cancel{1} \ 4\ | \ \ \ \ \ \ \ \\ \ \ \cancel{8} \cancel{5}\cancel{8} |1 2 2 \\ \cancel{7} \ \ \ \ \ \ \ \ | \ \ \ \ \\ \cancel{7} \ \ \ \ | \\ \ \ \ \ \cancel{7} | $$

Step 10 : Everything on the right hand side is the quotient in that order. Everything that's not struck out on the left hand side is the remainder in that order.$$ \frac{858}{7} \quad \rightarrow \quad \text{Quotient : } 122, \text{ Remainder : } 4 $$

That's just the baby example. Let's now do a bigger, more glamorous example that involves more cancellation (and as a corollary, a bigger MathJax alignment headache).

A large, super-illustrative example

Let's do, well, I don't know. My MSE ID is $316409$ (it's a semiprime!) , let's use it as a dividend. This is my $1825$th answer so the divisor will be $1825$.

Actually, nothing much changes. The only thing that does change is the cancellation step : because we don't have a small divisor anymore, we will have to deal in way more cancellations. However, that will be taken care of.

Step 1 : Write the dividend and divisor so that the leftmost digit of the divisor is directly underneath that of the dividend. Draw a bar to the left of the divisor. $$ \begin{matrix} 3&1&6&4&0&9&| \\ 1&8&2&5& & &| \end{matrix} $$

Step 2 : Form the temporary divisor. The rightmost digit of $1825$ is the $5$, and everything to the left of that is $3164$. So we get $3164$ as the temporary divisor. Clearly, $3164 / 1825$ has a quotient of $1$. Write the $1$. $$ \begin{matrix} 3&1&6&4&0&9&|&1 \\ 1&8&2&5& & &|& \end{matrix} $$

Step 3a : We have , now a very elaborate cancellation step. It begins as follows. The quotient digit is $1$. Multiply this with the first digit of the divisor i.e. $1$, and subtract it from the number above i.e. a $3$. This gives $3 - (1 \times 1) = 2$. Write that $2$ above the $3$ with a cancellation. Cancel the $1$ from the divisor, which has now been used in the subtraction.

$$ \begin{matrix} 2&&&&&&|&\\ \cancel{3}&1&6&4&0&9&|&1 \\ \cancel{1}&8&2&5& & &|& \end{matrix} $$

Step 3b : In the second part of the cancellation step, we now multiply the quotient digit with the next uncancelled digit of the divisor, and subtract it from the corresponding digit of the dividend. In this case, we have $1 - (1 \times 8)$. That's negative, though!

To counteract this, we borrow from the $2$ on the top right column, making it $21 - (1 \times 8) = 13$ instead. To show that the $2$ has been borrowed, we strike it out and write a $1$ above it. Write a $3$ above the $1$ , so that $21$ has been effectively replaced with $13$. Strike out the $8$.

$$ \begin{matrix} 1&&&&&&|& \\ \cancel{2}&3&&&&&|&\\ \cancel{3}&\cancel{1}&6&4&0&9&|&1 \\ \cancel{1}&\cancel{8}&2&5& & &|& \end{matrix} $$

Step 3c : The next divisor digit is $2$. Multiply that with the quotient digit $1$, and try to subtract it from the digit above the $2$, which is $6$. This leads to $6-(2 \times 1) = 4$. Cancel the $6$ and put a $4$ above it. Cancel the $2$.

$$ \begin{matrix} 1&&&&&&|& \\ \cancel{2}&3&4&&&&|&\\ \cancel{3}&\cancel{1}&\cancel{6}&4&0&9&|&1 \\ \cancel{1}&\cancel{8}&\cancel{2}&5& & &|& \end{matrix} $$

Step 3d : In the last of these cancellation steps, the remaining digit of the divisor $5$ is multiplied with the quotient digit $1$, and we attempt to subtract it from the number above the $5$, which is a $4$. However, $4 - (5 \times 1)$ is negative.

To counter this, we borrow the $4$ that's to the left and above this $4$, giving the number $44$. Now, subtraction gives $44 - (5 \times 1) = 39$. Cut the upper $4$ out and write a $3$ above it. Cut the lower $4$ out and write a $9$ above it. Cut the $5$ out.

$$ \begin{matrix} 1&&3&&&&|& \\ \cancel{2}&3&\cancel{4}&9&&&|&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&0&9&|&1 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|& \end{matrix} $$

Step 4 : The divisor $1825$ is now written on the last line, but it's now shifted one place to the right compared to the previous $1825$. That gives $$ \begin{matrix} 1&&3&&&&|& \\ \cancel{2}&3&\cancel{4}&9&&&|&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&0&9&|&1 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|& \\ &1&8&2&5&&|& \end{matrix} $$

We just need to repeat all these steps again, with $316409 \to 133909$ and a $1$ on the quotient. Let's do that!

Step 5 : Form the temporary divisor like so. The last digit of the divisor is a $5$, and everything to the above-left of that in the dividend results in $13390$ in this case.

We now need to divide $13390$ by $1825$. A rough grasp at a quotient may be done by seeing that $18 \times 8 = 144$ and $18 \times 7 = 126$, so we expect that $1825 \sim 1800$ will also yield a quotient of $7$. This is true, and we write the quotient $7$ after the $1$ now.

$$ \begin{matrix} 1&&3&&&&|& \\ \cancel{2}&3&\cancel{4}&9&&&|&&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&0&9&|&1&7 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|&& \\ &1&8&2&5&&|&& \end{matrix} $$

Step 6a : Begin the cancellation step. The quotient digit is a $7$, and we multiply it with the divisor's first digit, which is a $1$, and then try to remove that from the digit above a $1$ (in this case, a $3$). However, $3 - (1 \times 7)$ is negative. Borrowing the top $1$, however, makes this $13 - (1 \times 7) = 6$. The $1$ is cancelled (no point of writing a $0$ above it, although one should do so for completeness), we cancel $3$ and write a $6$ above it, and cancel the divisor digit $1$.

$$ \begin{matrix} \cancel{1}&6&3&&&&|& \\ \cancel{2}&\cancel{3}&\cancel{4}&9&&&|&&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&0&9&|&1&7 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|&& \\ &\cancel{1}&8&2&5&&|&& \end{matrix} $$

Step 6b : You've seen it many times now, so let's be a little snappy. $7 \times 8 =56$ which is bigger than the $3$, so borrow the $6$ to give $63 - (7 \times 8) = 7$. Cancel the $6$, replace the $3$ by a $7$, cancel the $8$.

$$ \begin{matrix} &&7&&&&|&\\ \cancel{1}&\cancel{6}&\cancel{3}&&&&|& \\ \cancel{2}&\cancel{3}&\cancel{4}&9&&&|&&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&0&9&|&1&7 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|&& \\ &\cancel{1}&\cancel{8}&2&5&&|&& \end{matrix} $$

Step 6c : $7 \times 2 =14$ which is bigger than the $9$, so borrow the $7$ to give $79- (7 \times 2) = 65$. Replace the $79$ by a $65$, cancel the $2$.

$$ \begin{matrix} &&6&&&&|&\\ &&\cancel{7}&&&&|&\\ \cancel{1}&\cancel{6}&\cancel{3}&5&&&|& \\ \cancel{2}&\cancel{3}&\cancel{4}&\cancel{9}&&&|&&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&0&9&|&1&7 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|&& \\ &\cancel{1}&\cancel{8}&\cancel{2}&5&&|&& \end{matrix} $$

Step 6d : $7\times 5 = 35>0$ (well, I mean, obviously, eh?) , so borrowing the $5$ gives $50 - (7 \times 5) = 15$, replace $50$ by $15$ and cancel the $5$.

$$ \begin{matrix} &&6&&&&|&\\ &&\cancel{7}&1&&&|&\\ \cancel{1}&\cancel{6}&\cancel{3}&\cancel{5}&&&|& \\ \cancel{2}&\cancel{3}&\cancel{4}&\cancel{9}&5&&|&&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&\cancel{0}&9&|&1&7 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|&& \\ &\cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}&&|&& \end{matrix} $$

Step 7 : Shift the divisor one place to the right and write it below the cancelled divisor. $$ \begin{matrix} &&6&&&&|&\\ &&\cancel{7}&1&&&|&\\ \cancel{1}&\cancel{6}&\cancel{3}&\cancel{5}&&&|& \\ \cancel{2}&\cancel{3}&\cancel{4}&\cancel{9}&5&&|&&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&\cancel{0}&9&|&1&7 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|&& \\ &\cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}&&|&& \\ &&1&8&2&5&|&& \end{matrix} $$

Step 8: The temporary dividend is $6159$, and upon division by $1825$ it gives a quotient of $3$. Write the $3$ to the right of the $7$ : $$ \begin{matrix} &&6&&&&|&\\ &&\cancel{7}&1&&&|&\\ \cancel{1}&\cancel{6}&\cancel{3}&\cancel{5}&&&|& \\ \cancel{2}&\cancel{3}&\cancel{4}&\cancel{9}&5&&|&&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&\cancel{0}&9&|&1&7&3 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|&& \\ &\cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}&&|&& \\ &&1&8&2&5&|&& \end{matrix} $$

The last cancellation step is left as an exercise, with only the diagrams shown.

Step 9a : $$ \begin{matrix} &&3&&&&|& \\ &&\cancel{6}&&&&|&\\ &&\cancel{7}&1&&&|&\\ \cancel{1}&\cancel{6}&\cancel{3}&\cancel{5}&&&|& \\ \cancel{2}&\cancel{3}&\cancel{4}&\cancel{9}&5&&|&&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&\cancel{0}&9&|&1&7&3 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|&& \\ &\cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}&&|&& \\ &&\cancel{1}&8&2&5&|&& \end{matrix} $$

Step 9b : $$ \begin{matrix} &&\cancel{3}&&&&|& \\ &&\cancel{6}&7&&&|&\\ &&\cancel{7}&\cancel{1}&&&|&\\ \cancel{1}&\cancel{6}&\cancel{3}&\cancel{5}&&&|& \\ \cancel{2}&\cancel{3}&\cancel{4}&\cancel{9}&5&&|&&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&\cancel{0}&9&|&1&7&3 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|&& \\ &\cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}&&|&& \\ &&\cancel{1}&\cancel{8}&2&5&|&& \end{matrix} $$

Step 9c :

$$ \begin{matrix} &&\cancel{3}&6&&&|& \\ &&\cancel{6}&\cancel{7}&&&|&\\ &&\cancel{7}&\cancel{1}&&&|&\\ \cancel{1}&\cancel{6}&\cancel{3}&\cancel{5}&9&&|& \\ \cancel{2}&\cancel{3}&\cancel{4}&\cancel{9}&\cancel{5}&&|&&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&\cancel{0}&9&|&1&7&3 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|&& \\ &\cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}&&|&& \\ &&\cancel{1}&\cancel{8}&\cancel{2}&5&|&& \end{matrix} $$

Step 9d :

$$ \begin{matrix} &&\cancel{3}&6&&&|& \\ &&\cancel{6}&\cancel{7}&&&|&\\ &&\cancel{7}&\cancel{1}&8&&|&\\ \cancel{1}&\cancel{6}&\cancel{3}&\cancel{5}&\cancel{9}&&|& \\ \cancel{2}&\cancel{3}&\cancel{4}&\cancel{9}&\cancel{5}&4&|&&\\ \cancel{3}&\cancel{1}&\cancel{6}&\cancel{4}&\cancel{0}&\cancel{9}&|&1&7&3 \\ \cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}& & &|&& \\ &\cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}&&|&& \\ &&\cancel{1}&\cancel{8}&\cancel{2}&\cancel{5}&|&& \end{matrix} $$

Step 10 : The quotient is everything to the right, in that order. The remainder is everything not cancelled to the left, in that order. $$ \frac{316409}{1825} \quad\rightarrow \quad \text{Quotient : } 173 , \text{ Remainder : } 684 $$

While you're at it, take a look at [4] for another example, and some more methods of division. [5] looks at variants of this method (including the "erasure" method which is convenient for sand-based calculations, and the printer method where cancellation is just avoided as a convention).

What about square roots?

We know that long division, or a variant of it, can be used for square roots. It is not surprising that the long division method can be used for $n$th roots as well. It's just a variant of the binomial theorem, a brief discussion can be found at [6].

It turns out that the square root Galley method of Tartaglia is the same as that of modified long-division, but suited to cancellation. We describe only square roots below : first, an easy version, then a hard one.

Square roots, the galley method

Let's start with a baby example, as usual. Say I want the square root of $7056$.

Step 1 : Split $7056$ into blocks of $2$ from the right : in that case, it would be $(70)(56)$. If the number were $361$, it'd be grouped like $(3)(61)$ instead.

Step 2 : Following grouping, the notation is to write the number (remembering the grouping mentally, we'll forget the brackets) , followed by a bar, after which the answer will appear. $$ \begin{matrix} 7&0&5&6&| \end{matrix} $$

Step 3 : Find the single digit number $x$, whose square is the largest one below the first group ( from the left) of numbers. In this case, the first group is $70$, so that number is $8$. Write $8$ on the right side of the bar. Then, write $8$ below the rightmost digit of the group (in this case, below the $0$). $$ \begin{matrix} 7&0&5&6&|&8 \\ &8&&&& \end{matrix} $$

Step $4$ : we subtract the product of $8$ with itself from the first group, in this case $70$. By the choice of $8$, this will always be negative, and we'll get $70 - 8^2 = 6$. The $7$ and $0$ will be cancelled out to reflect this. $$ \begin{matrix} &6&&&|&\\ \cancel{7}&\cancel{0}&5&6&|&8 \\ &8&&&|& \end{matrix} $$

Step 5 : Double the $8$ in the last row to get $16$. Write the $1$ below the $8$ (by cancellation) and write the $6$ next to the $8$. You've basically shifted the divisor one to the right by doing this, and that's exactly what's done in galley division as well.

$$ \begin{matrix} &6&&&|&\\ \cancel{7}&\cancel{0}&5&6&|&8 \\ &\cancel{8}&6&&|& \\ &1&&&|& \end{matrix} $$

Step 6 : This is the "doubling" step of the algorithm. We must now find the next digit of the quotient. However, how do we do that? The answer is to look back to the long method. We must find $x$ such that $16x \times x$ (where $16x$ is treated as a three digit number) is smaller than $656$. Suppose we find the biggest such value of $x$. Then we place $x$ in the positions shown below $$ \begin{matrix} &6&&&|&&\\ \cancel{7}&\cancel{0}&5&6&|&8&x \\ &\cancel{8}&6&x&|&& \\ &1&&&|&& \end{matrix} $$

In our case, $x=4$ works out. We write $$ \begin{matrix} &6&&&|&&\\ \cancel{7}&\cancel{0}&5&6&|&8&4 \\ &\cancel{8}&6&4&|&& \\ &1&&&|&& \end{matrix} $$

Step 7 : Now, we do the cancellation step of the galley method, but with divisor $164$ , dividend $656$ and quotient digit $4$. However, there is one key difference : we DO NOT cancel out the divisor digits (in this case, $164$), we ONLY cancel digits from the dividend (in this case, $656$). The divisor cancellation will be done following a "doubling step" in the next stage.

That leads to the following sequence of steps. $$ \begin{matrix} &2&&&|&& \\ &\cancel{6}&&&|&&\\ \cancel{7}&\cancel{0}&5&6&|&8&4 \\ &\cancel{8}&6&4&|&& \\ &1&&&|&& \end{matrix} $$

Then

$$ \begin{matrix} &\cancel{2}&&&|&& \\ &\cancel{6}&1&&|&&\\ \cancel{7}&\cancel{0}&\cancel{5}&6&|&8&4 \\ &\cancel{8}&6&4&|&& \\ &1&&&|&& \end{matrix} $$

Finally $$ \begin{matrix} &\cancel{2}&&&|&& \\ &\cancel{6}&\cancel{1}&&|&&\\ \cancel{7}&\cancel{0}&\cancel{5}&\cancel{6}&|&8&4 \\ &\cancel{8}&6&4&|&& \\ &1&&&|&& \end{matrix} $$

Step $8$ : We have exhausted all the digits of the original number. Now, we strike out the entire divisor as written (which is $164$) and look at what is left over $$ \begin{matrix} &\cancel{2}&&&|&& \\ &\cancel{6}&\cancel{1}&&|&&\\ \cancel{7}&\cancel{0}&\cancel{5}&\cancel{6}&|&8&4 \\ &\cancel{8}&\cancel{6}&\cancel{4}&|&& \\ &\cancel{1}&&&|&& \end{matrix} $$

In Galley division, this leads to a "quotient" of $84$ (the square root of the biggest perfect square smaller than $7056$) and a "remainder" (the discrepancy between those two numbers) of $0$. This basically means that $7056 = 84^2+0 = 84^2$.

We'll do another example for good measure.

A bigger, bolder example

Let's do one of the examples that Tartaglia himself uses, in his reference "General Tratto di Numeri", whose untranslated version can be found at [7].

Tartaglia is dealing with the number $968372$.

Step 1 : The grouping , in groups of $2$, leads to $(96)(83)(72)$. Write down the number with a bar at the end.

$$ \begin{matrix} 9&6&8&3&7&2&| \end{matrix} $$

Step 2 : Deal with the first group i.e. $96$. The number $9$ is the largest one-digit number such that $9^2 \leq 96$, so we write $9$ down both in the quotient and in the divisor position.

$$ \begin{matrix} 9&6&8&3&7&2&|&9 \\ &9&&&&&|& \end{matrix} $$

Step 3 : The square of $9$ is $9^2 = 81$. This can't be subtracted from $6$ so we borrow the $9$ to get $96-9^2 = 15$. Cancellations ensue, as usual.

$$ \begin{matrix} 1&5&&&&&|& \\ \cancel{9}&\cancel{6}&8&3&7&2&|&9 \\ &9&&&&&|& \end{matrix} $$

Step 4 : Double the bottommost $9$ to get $18$. Cancel the $9$ and write $18$ below the $9$, so that it is shifted one to the right (just like how the divisor is shifted one space to the right in the usual galley division procedure).

$$ \begin{matrix} 1&5&&&&&|& \\ \cancel{9}&\cancel{6}&8&3&7&2&|&9 \\ &\cancel{9}&8&&&&|& \\ &1&&&&&|& \end{matrix} $$

Step 5 : Now, we will search for the next quotient digit. Mimicking the earlier example, we need the largest single digit $x$ so that $18x \times x \leq 1583$. That $x$ would be inserted at the position $$ \begin{matrix} 1&5&&&&&|& \\ \cancel{9}&\cancel{6}&8&3&7&2&|&9&x \\ &\cancel{9}&8&x&&&|& \\ &1&&&&&|& \end{matrix} $$

That $x$ can be found. Indeed, $x=8$ has $188 \times 8 = 1504$, while $x=9$ gives $189 \times 9 = 1701$, so $x=8$ fits the bill. Write the $8$ in place of $x$.

$$ \begin{matrix} 1&5&&&&&|& \\ \cancel{9}&\cancel{6}&8&3&7&2&|&9&8 \\ &\cancel{9}&8&8&&&|& \\ &1&&&&&|& \end{matrix} $$

Step 6 : Now, just like the cancellation step in the original galley division, we will use $8$ as the last quotient digit, $188$ as the divisor, and $1583$ as the dividend. However, recall the key difference : we DO NOT cancel out the divisor digits (in this case, $188$), we ONLY cancel digits from the dividend (in this case, $1583$). The divisor cancellation will be done following a change to a new divisor in the next stage.

For the digit $1$ : $$ \begin{matrix} &7&&&&&|&& \\ \cancel{1}&\cancel{5}&&&&&|& \\ \cancel{9}&\cancel{6}&8&3&7&2&|&9&8 \\ &\cancel{9}&8&8&&&|& \\ &1&&&&&|& \end{matrix} $$ For the first $8$ : $$ \begin{matrix} &1&&&&&|&& \\ &\cancel{7}&&&&&|&& \\ \cancel{1}&\cancel{5}&4&&&&|& \\ \cancel{9}&\cancel{6}&\cancel{8}&3&7&2&|&9&8 \\ &\cancel{9}&8&8&&&|& \\ &1&&&&&|& \end{matrix} $$

For the second $8$ : here, even if we borrow the digit $4$ which comes before the $3$, we still end up with $43 < 8 \times 8$, so we must borrow the $1$ before the $4$ as well. We get $143-64 = 79$, so $$ \begin{matrix} &\cancel{1}&&&&&|&& \\ &\cancel{7}&7&&&&|&& \\ \cancel{1}&\cancel{5}&\cancel{4}&9&&&|& \\ \cancel{9}&\cancel{6}&\cancel{8}&\cancel{3}&7&2&|&9&8 \\ &\cancel{9}&8&8&&&|& \\ &1&&&&&|& \end{matrix} $$

Step 7 : We will now create a new divisor as follows : the existing divisor is $188$. The last digit of the current quotient is an $8$. Their sum is $196$ : and that's the new divisor. The $196$ will be created by shifting $188$ one step to the right, as usual. NOW, we cancel the $188$.

$$ \begin{matrix} &\cancel{1}&&&&&|&& \\ &\cancel{7}&7&&&&|&& \\ \cancel{1}&\cancel{5}&\cancel{4}&9&&&|& \\ \cancel{9}&\cancel{6}&\cancel{8}&\cancel{3}&7&2&|&9&8 \\ &\cancel{9}&\cancel{8}&\cancel{8}&6&&|& \\ &\cancel{1}&1&9&&&|& \end{matrix} $$

Step 8 : Once again, we seek a largest possible single digit $y$ , this time such that $196y \times y \leq 7972$. That value can be found using the heuristic that $20 \times 4 = 80$, so $y=4$ is tested and we find that $1964 \times 4 = 7856$ is very close to $7972$. Hence, $y=4$ is used, and when we substitute it we get

$$ \begin{matrix} &\cancel{1}&&&&&|&& \\ &\cancel{7}&7&&&&|&& \\ \cancel{1}&\cancel{5}&\cancel{4}&9&&&|& \\ \cancel{9}&\cancel{6}&\cancel{8}&\cancel{3}&7&2&|&9&8&4 \\ &\cancel{9}&\cancel{8}&\cancel{8}&6&4&|& \\ &\cancel{1}&1&9&&&|& \end{matrix} $$

Step 9 : Cancellation , with the divisor as $1964$, the dividend as $7972$ and the last digit of the quotient as $4$. As a reminder that it isn't done in the middle, we don't cancel the divisor digits, only the dividend digits.

The $1$ :

$$ \begin{matrix} &\cancel{1}&3&&&&|&& \\ &\cancel{7}&\cancel{7}&&&&|&& \\ \cancel{1}&\cancel{5}&\cancel{4}&9&&&|& \\ \cancel{9}&\cancel{6}&\cancel{8}&\cancel{3}&7&2&|&9&8&4 \\ &\cancel{9}&\cancel{8}&\cancel{8}&6&4&|& \\ &\cancel{1}&1&9&&&|& \end{matrix} $$

The $9$ :$$ \begin{matrix} &\cancel{1}&\cancel{3}&&&&|&& \\ &\cancel{7}&\cancel{7}&3&&&|&& \\ \cancel{1}&\cancel{5}&\cancel{4}&\cancel{9}&&&|& \\ \cancel{9}&\cancel{6}&\cancel{8}&\cancel{3}&7&2&|&9&8&4 \\ &\cancel{9}&\cancel{8}&\cancel{8}&6&4&|& \\ &\cancel{1}&1&9&&&|& \end{matrix} $$

The $6$ :$$ \begin{matrix} &\cancel{1}&\cancel{3}&1&&&|&& \\ &\cancel{7}&\cancel{7}&\cancel{3}&&&|&& \\ \cancel{1}&\cancel{5}&\cancel{4}&\cancel{9}&3&&|& \\ \cancel{9}&\cancel{6}&\cancel{8}&\cancel{3}&\cancel{7}&2&|&9&8&4 \\ &\cancel{9}&\cancel{8}&\cancel{8}&6&4&|& \\ &\cancel{1}&1&9&&&|& \end{matrix} $$

The $4$ : $$ \begin{matrix} &\cancel{1}&\cancel{3}&1&&&|&& \\ &\cancel{7}&\cancel{7}&\cancel{3}&1&&|&& \\ \cancel{1}&\cancel{5}&\cancel{4}&\cancel{9}&\cancel{3}&6&|& \\ \cancel{9}&\cancel{6}&\cancel{8}&\cancel{3}&\cancel{7}&\cancel{2}&|&9&8&4 \\ &\cancel{9}&\cancel{8}&\cancel{8}&6&4&|& \\ &\cancel{1}&1&9&&&|& \end{matrix} $$

Step 10 : All the dividend digits have been struck out. At this point, we strike out all the digits of the divisor first :

$$ \begin{matrix} &\cancel{1}&\cancel{3}&1&&&|&& \\ &\cancel{7}&\cancel{7}&\cancel{3}&1&&|&& \\ \cancel{1}&\cancel{5}&\cancel{4}&\cancel{9}&\cancel{3}&6&|& \\ \cancel{9}&\cancel{6}&\cancel{8}&\cancel{3}&\cancel{7}&\cancel{2}&|&9&8&4 \\ &\cancel{9}&\cancel{8}&\cancel{8}&\cancel{6}&\cancel{4}&|& \\ &\cancel{1}&\cancel{1}&\cancel{9}&&&|& \end{matrix} $$

To be left with $$ 968372 = 984^2 + 116 $$

Check also that this matches directly with Tartaglia's working.

In the second answer

In the second answer (give me a day!) I'll discuss the potential to incorporate $n$th root calculations into this framework.

References

[1] Lam, Lay-Yong, On the Chinese origin of the Galley method of arithmetical division, Br. J. Hist. Sci. 3, 66-69 (1966). ZBL0143.24202.

[2] https://en.wikipedia.org/wiki/Galley_division

[3] https://3010tangents.wordpress.com/2015/02/17/galley-division/

[4] http://www.ams.org/publicoutreach/feature-column/fc-2013-05

[5] https://www.ms.uky.edu/~droyster/courses/fall06/PDFs/Galley%20Method.pdf

[6] Is there a process, similar to long division, to do nth roots where n is any positive integer?

[7] https://echo.mpiwg-berlin.mpg.de/ECHOdocuView?tocMode=thumbs&start=51&url=/mpiwg/online/permanent/library/MRV5C34S/pageimg&viewMode=images&wh=0.6038&ww=0.5219&tocPN=1&searchPN=1&mode=imagepath&characterNormalization=reg&pn=53&wy=0.249

[8] Why is square root by long division found so?

$\endgroup$
6
  • 1
    $\begingroup$ +1 to both answers for the sheer effort $\endgroup$
    – Ant
    Oct 9, 2022 at 12:12
  • 2
    $\begingroup$ @Ant Thank you so much! I hope that you can take something useful away from both answers after reading them. $\endgroup$ Oct 9, 2022 at 12:14
  • $\begingroup$ @SarveshRavichandranIyer Such an impressive answer! Thank you for helping me to understand what is behind this. Now I can peacefully move on with this knowledge in my mind! :) $\endgroup$
    – Rusurano
    Oct 9, 2022 at 13:52
  • $\begingroup$ @Rusurano Thank you very much! The important part of this answer, for you, is part 2 of my answer which provides a proper framework for cube roots, and outlines how it can be extended to nth roots. I will try to attach a worked-out example of a fourth-root calculation when I can! It seems the total character count is $47508$, which is the longest answer I've written on MSE. $\endgroup$ Oct 10, 2022 at 6:11
  • 1
    $\begingroup$ @SarveshRavichandranIyer Even though the cube root example by itself is very illustrative, having another example involving a fourth-root calculation will make your answer completely comprehensive. $\endgroup$
    – Rusurano
    Oct 10, 2022 at 10:37
2
$\begingroup$

This is the second part of my answer, which discusses the nth root situation.

Why does the square root method work, and how can we modify this for higher roots?

The idea behind the square root method can be found in [8], but for completeness, suppose that you have to find the square root of $y$. You begin with an initial guess $x$ such that $x^2<y$, and wish to find an $h>0$ such that $(x+h)^2 <y$ as well, so that $x+h$ is an improved guess.

How we do this is as follows : if $(x+h)^2 < y$ then $x^2+2xh+h^2 < y$, so that $h(2x+h) < y-x^2$. After the first step of galley division, for example, the dividend reflects the quantity $y-x^2$, so we double $x$ to get $2x$ and then the next digit $h$ is found by precisely checking when $h(2x+h)$ is less than that dividend, which is $y-x^2$! This is the crux of the procedure.

Now, let's think about cube roots similarly. If we need to get the cube root of $y$, then we start with $x$ such that $x^3<y$, and then improve it by adding an $h$ so that $(x+h)^3 < y$. That reduces to $$ y-x^3 > \boxed{h^3+3xh^2+3x^2h} $$ and therefore, the "next digit of the quotient" $h$ must be found in such a way that $h^3+3xh^2+3x^2h < y-x^3$, where $x$ is the initial guess (which is basically the quotient up till the point where $h$ is to be chosen).

If we're looking at $n$th roots, then calculations get a lot more involved, because the estimate changes to $$ y-x^n > \boxed{\sum_{k=0}^{n-1} \binom{n}{k} x^kh^{n-k}} $$

The big problem here is that one needs terms like $x^2,x^3$ and so on : so we must spare some space for extra calculations, which will be outside our field of view. This can't be avoided (it can be reduced using a rough and unfortunately sometimes incorrect heuristic which is expounded on in [9]), but it is satisfying to know that , providing one can compute this sum in some way, one can still execute the Galley method.

Merely for cube roots, first

Let's stick with cube roots for now. Observe the term $$ h^3+3x^2h+3xh^2 = h(h^2+3xh+3x^2) = h(h(h+3x)+3x^2) $$

This means that , given $x$, we definitely need the terms $3x^2$ and $3x$ before we can even start talking about $h$. We need a place to "keep" the $3x^2$ and $3x$. Thankfully, if one is willing to clutter the workspace a little more, the $3x^2$ can be kept on the right hand side of the bar, underneath the forming quotient. Then, we can use it as and when needed, and employ the formula.

So let's see how the Galley method would work for cube roots. We will try to find the cube root of $571787$.

Step 1 : This is the cube root, so split the number into blocks of three starting from the right. In this case, that's $(571)(787)$. Write the usual first step of Galley division.

$$ \begin{matrix} 5&7&1&7&8&7 & | \end{matrix} $$

Step 2 : The first group is $571$, so for an initial guess we find the largest single digit number $x$ such that $x^3 \leq 571$. That number is found to be $8$, so we take $8$ as the first digit of the quotient. Write the divisor $8^2 = 64$ so that its last digit is underneath the last digit of the first group of numbers (in this case, that's a $1$).

$$ \begin{matrix} 5&7&1&7&8&7 & | &8 \\ &6&4&&&&|& \end{matrix} $$

Step 3 :Borrowing as many digits as needed, subtract $64\times 8$ from $571$ using the cancellation method from Galley division. Don't cancel the $64$ just as yet. $$ \require{cancel} \begin{matrix} &5&9&&&&|& \\ \cancel{5}&\cancel{7}&\cancel{1}&7&8&7 & | &8 \\ &6&4&&&&|& \end{matrix} $$

Step 4 : We need to plan very carefully now. $x^2 = 64$ has found a place, so let's find a place for $3x^2$ and $3x$ as follows. Take the quotient digit, (in this case $8$), multiply it by $3$ (to give $24$ in this case) and place it underneath the quotient $8$, in the same line as the $64$ (this is to keep track of the situation).

$$ \begin{matrix} &5&9&&&&|& \\ \cancel{5}&\cancel{7}&\cancel{1}&7&8&7 & | &8 \\ &6&4&&&&|&2&4 \end{matrix} $$

Step 5 : Triple the $64$ to get $192$. Where do we write the $192$? In the line under $64$, but in the following fashion : the last digit of the triple number (in this case $192$) should be exactly two positions to the left of the rightmost digit in the next group of numbers (in this case, two positions to the left of the second $7$ in $787$). Cancel the $64$ now. $$ \begin{matrix} &5&9&&&&|& \\ \cancel{5}&\cancel{7}&\cancel{1}&7&8&7 & | &8 \\ &\cancel{6}&\cancel{4}&&&&|&2&4 \\ &1&9&2&&&|&& \end{matrix} $$

Step 6 : Now we are going to find the next digit of the quotient. Here's how : suppose that $h$ is the next digit of the quotient. Then we first get $z = 24h \times h$ : (this is basically $h(3x+h)$). Then we add $z$ to the $192$ term, and finally need to multiply by $h$ again, to get what needs to be smaller than the temporary dividend (in this case , $59787$).

Instead of explaining how $h$ is found, let me just go through a particular $h$ very slowly. Take $h=3$. First, we write the $3$ in two places : the quotient place, and after the $24$. $$ \begin{matrix} &5&9&&&&|&&& \\ \cancel{5}&\cancel{7}&\cancel{1}&7&8&7 & | &8&3& \\ &\cancel{6}&\cancel{4}&&&&|&2&4&3 \\ &1&9&2&&&|&&& \end{matrix} $$ Then, we multiply the number $243$ with $3$, and write the answer so that its right most digit appears directly below the last digit of the next group of numbers (in this case, the $787$). $$ \begin{matrix} &5&9&&&&|&&& \\ \cancel{5}&\cancel{7}&\cancel{1}&7&8&7 & | &8&3& \\ &\cancel{6}&\cancel{4}&&&&|&2&4&3 \\ &1&9&2&&&|&&& \\ &&&7&2&9&|&&& \end{matrix} $$

That's what we would do if $h=3$. If $h=5$, say , then we would get $245 \times 5 = 1225$. That would be written, for example, as $$ \begin{matrix} &5&9&&&&|&&& \\ \cancel{5}&\cancel{7}&\cancel{1}&7&8&7 & | &8&5& \\ &\cancel{6}&\cancel{4}&&&&|&2&4&5 \\ &1&9&2&&&|&&& \\ &&1&2&2&5&|&&& \end{matrix} $$

Step 7 : However, I haven't talked about how $h$ is found. That is found as follows. If you pick an $h$ such that the below "double cancellation" step that I'm about to do goes through, then the largest such value of $h$ is what you need. For example, the cancellation for $h=5$ will fail (the $19$ and $1$ together give a $20$ and $20 \times 3 > 59$, causing the failure).

However, we'll go through the cancellation step for $h=3$ in detail. It turns out that $h=3$ is the correct choice of $h$. Once again, the key step : don't cancel the digits of the divisors at any stage below. Only dividend digits are cancelled.

7a : We will scan the numbers $192$ and $729$ from column to column. The first column contains a $1$. Perform galley cancellation with the quotient digit $3$, so that $5 - (1 \times 3) = 2$. $$ \begin{matrix} &2&&&&&|&&& \\ &\cancel{5}&9&&&&|&&& \\ \cancel{5}&\cancel{7}&\cancel{1}&7&8&7 & | &8&3& \\ &\cancel{6}&\cancel{4}&&&&|&2&4&3 \\ &1&9&2&&&|&&& \\ &&&7&2&9&|&&& \end{matrix} $$

7b : The next column contains a $9$. Note that $3\times 9 = 27 > 9$. So we borrow the $2$ to get $29-27 = 2$. This is reflected as $$ \begin{matrix} &\cancel{2}&2&&&&|&&& \\ &\cancel{5}&\cancel{9}&&&&|&&& \\ \cancel{5}&\cancel{7}&\cancel{1}&7&8&7 & | &8&3& \\ &\cancel{6}&\cancel{4}&&&&|&2&4&3 \\ &1&9&2&&&|&&& \\ &&&7&2&9&|&&& \end{matrix} $$

7c : The next column contains both a $2$ and a $7$. Add those numbers to get $9$. We will treat $9$ as the next digit of the "divisor" and perform galley cancellation. Again, $9 \times 3 = 27>7$, so we borrow the $2$ to get $27-27 = 0$. We get $$\begin{matrix} &\cancel{2}&\cancel{2}&&&&|&&& \\ &\cancel{5}&\cancel{9}&&&&|&&& \\ \cancel{5}&\cancel{7}&\cancel{1}&\cancel{7}&8&7 & | &8&3& \\ &\cancel{6}&\cancel{4}&&&&|&2&4&3 \\ &1&9&2&&&|&&& \\ &&&7&2&9&|&&& \end{matrix} $$

7d,7e : Just like steps 7a and 7b, we perform galley cancellation. What we get at the end is $$ \begin{matrix} &\cancel{2}&\cancel{2}&&&&|&&& \\ &\cancel{5}&\cancel{9}&&&&|&&& \\ \cancel{5}&\cancel{7}&\cancel{1}&\cancel{7}&\cancel{8}&\cancel{7} & | &8&3& \\ &\cancel{6}&\cancel{4}&&&&|&2&4&3 \\ &1&9&2&&&|&&& \\ &&&7&2&9&|&&& \end{matrix} $$

Step 8 : All digits of the original number have been cancelled out. Now, cross out every single digit that is below the original number OR below the quotient.

$$ \begin{matrix} &\cancel{2}&\cancel{2}&&&&|&&& \\ &\cancel{5}&\cancel{9}&&&&|&&& \\ \cancel{5}&\cancel{7}&\cancel{1}&\cancel{7}&\cancel{8}&\cancel{7} & | &8&3& \\ &\cancel{6}&\cancel{4}&&&&|&\cancel{2}&\cancel{4}&\cancel{3} \\ &\cancel{1}&\cancel{9}&\cancel{2}&&&|&&& \\ &&&\cancel{7}&\cancel{2}&\cancel{9}&|&&& \end{matrix} $$

According to Galley division, the "quotient" is $83$ and the "remainder" is zero. Remembering the square situation, the answer is $$ 571787 = 83^3 + 0 $$

A larger cube root example

Let's find the cube root of $77400112$.

Step 1 : Groups of $3$ gives $(77)(400)(112)$. Write the first line of Galley division.$$ \begin{matrix} 7&7&4&0&0&1&1&2&| \end{matrix} $$

Step 2 : We have $4^3 \leq 77$, so $4$ is the first digit of the quotient. We write the square of $4$ i.e. $16$ so that its last digit aligns with the last digit of the current group. Then we perform galley cancellation with divisor $16$, quotient digit $4$ and dividend $74$.

Before cancellation : $$ \begin{matrix} 7&7&4&0&0&1&1&2&|&4 \\ 1&6&&&&&&&|& \end{matrix} $$

After cancellation : $$ \begin{matrix} 1&3&&&&&&&|& \\ \cancel{7}&\cancel{7}&4&0&0&1&1&2&|&4 \\ 1&6&&&&&&&|& \end{matrix} $$

Step 3 : Triple both the quotient digit $4$ and the current divisor $16$ and write them in their respective places like the small example. Cancel the $16$.

$$ \begin{matrix} 1&3&&&&&&&|& \\ \cancel{7}&\cancel{7}&4&0&0&1&1&2&|&4 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2 \\ &4&8&&&&&&|&& \end{matrix} $$

Step 4 : We need to guess the next digit. Heuristics from [9] tell us to look at $\frac{13400}{4800}$, which is between $2$ and $3$. Hence, we expect $h=2$ to work. Keeping this in mind, write $2$ next to the $12$, perform $122 \times 2 = 244$, and write the $244$ appears below the second $7$ in $787$ (just like last time). Of course, write $2$ next to the quotient as well.

$$ \begin{matrix} 1&3&&&&&&&|& \\ \cancel{7}&\cancel{7}&4&0&0&1&1&2&|&4&2 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2&2 \\ &4&8&&&&&&|&& \\ &&2&4&4&&&&|&& \end{matrix} $$

Step 5 : The extended cancellation step. We have four columns that the $48$ and $244$ take up, so we go column by column. As usual, don't cancel the divisor.

The first column has only a $4$, and $2 \times 4 >3$, so borrowing the $1$ gives $13-(2 \times 4) = 5$. $$ \begin{matrix} &5&&&&&&&|& \\ \cancel{1}&\cancel{3}&&&&&&&|& \\ \cancel{7}&\cancel{7}&4&0&0&1&1&2&|&4&2 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2&2 \\ &4&8&&&&&&|&& \\ &&2&4&4&&&&|&& \end{matrix} $$

The next column is effectively $8+2 = 10$. So the next divisor digit is "$10$", and following borrowing we get $54-(2 \times 10) = 34$. $$ \begin{matrix} &3&&&&&&&|& \\ &\cancel{5}&&&&&&&|& \\ \cancel{1}&\cancel{3}&&&&&&&|& \\ \cancel{7}&\cancel{7}&4&0&0&1&1&2&|&4&2 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2&2 \\ &4&8&&&&&&|&& \\ &&2&4&4&&&&|&& \end{matrix} $$

The next two columns are routine and lead to $$ \begin{matrix} &3&&&&&&&|& \\ &\cancel{5}&&&&&&&|& \\ \cancel{1}&\cancel{3}&3&1&2&&&&|& \\ \cancel{7}&\cancel{7}&\cancel{4}&\cancel{0}&\cancel{0}&1&1&2&|&4&2 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2&2 \\ &4&8&&&&&&|&& \\ &&2&4&4&&&&|&& \end{matrix} $$

We're done with the $48$ and $244$ now. They're part of previous calculations and we cancel them.

$$ \begin{matrix} &3&&&&&&&|& \\ &\cancel{5}&&&&&&&|& \\ \cancel{1}&\cancel{3}&3&1&2&&&&|& \\ \cancel{7}&\cancel{7}&\cancel{4}&\cancel{0}&\cancel{0}&1&1&2&|&4&2 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2&2 \\ &\cancel{4}&\cancel{8}&&&&&&|&& \\ &&\cancel{2}&\cancel{4}&\cancel{4}&&&&|&& \end{matrix} $$

Step 6 : Recalling that we need to square the entire quotient to create the $x^2$, we square $42$ to get $42^2 = 1764$. Triple this number to get $1764 \times 3 = 5292$. We also triple $42$ to get $42 \times 3 = 126$.

As usual, $5292$ is written so that the last $2$ is two positions to the left of the rightmost digit of the next block (which is also a $2$ in this case). We write the $126$ on the right side of the bar next to the $5292$.

$$ \begin{matrix} &3&&&&&&&|& \\ &\cancel{5}&&&&&&&|& \\ \cancel{1}&\cancel{3}&3&1&2&&&&|& \\ \cancel{7}&\cancel{7}&\cancel{4}&\cancel{0}&\cancel{0}&1&1&2&|&4&2 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2&2 \\ &\cancel{4}&\cancel{8}&&&&&&|&& \\ &&\cancel{2}&\cancel{4}&\cancel{4}&&&&|&& \\ &&5&2&9&2&&&|&1&2&6 \\ \end{matrix} $$

Step 7 : We will now find the next quotient digit. Using the heuristic from [9], we look at $\frac{3312112}{529200}$ : this is a number between $6$ and $7$, so $h=6$ should work. Start by writing $6$ in the quotient digits' place. Then write $6$ next to the $126$. We do $1266 \times 6 = 7596$, and place the $7596$ so that its last digit is directly below the last digit in the next group of numbers (which is the $2$ in $112$). $$ \begin{matrix} &3&&&&&&&|& \\ &\cancel{5}&&&&&&&|& \\ \cancel{1}&\cancel{3}&3&1&2&&&&|& \\ \cancel{7}&\cancel{7}&\cancel{4}&\cancel{0}&\cancel{0}&1&1&2&|&4&2&6 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2&2 \\ &\cancel{4}&\cancel{8}&&&&&&|&& \\ &&\cancel{2}&\cancel{4}&\cancel{4}&&&&|&& \\ &&5&2&9&2&&&|&1&2&6&6 \\ &&&&7&5&9&6&|&&&& \end{matrix} $$

Step 8 : The cancellation step, as usual. The $5292$ and $7596$ form six columns in total.

The first column has just a $5$. After borrowing, $33 - (6 \times 5) = 3$. $$ \begin{matrix} &\cancel{3}&&&&&&&|& \\ &\cancel{5}&&&&&&&|& \\ \cancel{1}&\cancel{3}&3&1&2&&&&|& \\ \cancel{7}&\cancel{7}&\cancel{4}&\cancel{0}&\cancel{0}&1&1&2&|&4&2&6 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2&2 \\ &\cancel{4}&\cancel{8}&&&&&&|&& \\ &&\cancel{2}&\cancel{4}&\cancel{4}&&&&|&& \\ &&5&2&9&2&&&|&1&2&6&6 \\ &&&&7&5&9&6&|&&&& \end{matrix} $$

The second column has a $2$, so after borrowing, we have $$ \begin{matrix} &\cancel{3}&&&&&&&|& \\ &\cancel{5}&1&9&&&&&|& \\ \cancel{1}&\cancel{3}&\cancel{3}&\cancel{1}&2&&&&|& \\ \cancel{7}&\cancel{7}&\cancel{4}&\cancel{0}&\cancel{0}&1&1&2&|&4&2&6 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2&2 \\ &\cancel{4}&\cancel{8}&&&&&&|&& \\ &&\cancel{2}&\cancel{4}&\cancel{4}&&&&|&& \\ &&5&2&9&2&&&|&1&2&6&6 \\ &&&&7&5&9&6&|&&&& \end{matrix} $$

The third column has a $9$ and a $7$, so we get $9+7=16$ as the effective "digit" in that position. We have, after borrowing, $192 - (6 \times 16) = 96$.

$$ \begin{matrix} &\cancel{3}&&&&&&&|& \\ &\cancel{5}&\cancel{1}&9&6&&&&|& \\ \cancel{1}&\cancel{3}&\cancel{3}&\cancel{1}&\cancel{2}&&&&|& \\ \cancel{7}&\cancel{7}&\cancel{4}&\cancel{0}&\cancel{0}&1&1&2&|&4&2&6 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2&2 \\ &\cancel{4}&\cancel{8}&&&&&&|&& \\ &&\cancel{2}&\cancel{4}&\cancel{4}&&&&|&& \\ &&5&2&9&2&&&|&1&2&6&6 \\ &&&&7&5&9&6&|&&&& \end{matrix} $$

Then comes $2+5 = 7$, and after borrowing,

$$ \begin{matrix} &\cancel{3}&&&1&&&&|& \\ &\cancel{5}&\cancel{1}&9&\cancel{6}&&&&|& \\ \cancel{1}&\cancel{3}&\cancel{3}&\cancel{1}&\cancel{2}&9&&&|& \\ \cancel{7}&\cancel{7}&\cancel{4}&\cancel{0}&\cancel{0}&\cancel{1}&1&2&|&4&2&6 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2&2 \\ &\cancel{4}&\cancel{8}&&&&&&|&& \\ &&\cancel{2}&\cancel{4}&\cancel{4}&&&&|&& \\ &&5&2&9&2&&&|&1&2&6&6 \\ &&&&7&5&9&6&|&&&& \end{matrix} $$ Polishing off the last two columns, $$ \begin{matrix} &\cancel{3}&&&1&&&&|& \\ &\cancel{5}&\cancel{1}&9&\cancel{6}&3&&&|& \\ \cancel{1}&\cancel{3}&\cancel{3}&\cancel{1}&\cancel{2}&\cancel{9}&3&6&|& \\ \cancel{7}&\cancel{7}&\cancel{4}&\cancel{0}&\cancel{0}&\cancel{1}&\cancel{1}&\cancel{2}&|&4&2&6 \\ \cancel{1}&\cancel{6}&&&&&&&|&1&2&2 \\ &\cancel{4}&\cancel{8}&&&&&&|&& \\ &&\cancel{2}&\cancel{4}&\cancel{4}&&&&|&& \\ &&5&2&9&2&&&|&1&2&6&6 \\ &&&&7&5&9&6&|&&&& \end{matrix} $$

Finally, we're done with all the dividend digits. Cancel anything and everything below both the original number and the current quotient, and we get $$ \begin{matrix} &\cancel{3}&&&1&&&&|& \\ &\cancel{5}&\cancel{1}&9&\cancel{6}&3&&&|& \\ \cancel{1}&\cancel{3}&\cancel{3}&\cancel{1}&\cancel{2}&\cancel{9}&3&6&|& \\ \cancel{7}&\cancel{7}&\cancel{4}&\cancel{0}&\cancel{0}&\cancel{1}&\cancel{1}&\cancel{2}&|&4&2&6 \\ \cancel{1}&\cancel{6}&&&&&&&|&\cancel{1}&\cancel{2}&\cancel{2} \\ &\cancel{4}&\cancel{8}&&&&&&|&& \\ &&\cancel{2}&\cancel{4}&\cancel{4}&&&&|&& \\ &&\cancel{5}&\cancel{2}&\cancel{9}&\cancel{2}&&&|&\cancel{1}&\cancel{2}&\cancel{6}\cancel{6} \\ &&&&\cancel{7}&\cancel{5}&\cancel{9}&\cancel{6}&|&&&& \end{matrix} $$

Which helps us read off the answer as $$ 77400112 = 426^3+91336 $$


What about higher variants? It seems just the three-variant alone is quite complicated, although it is completely correct, thankfully.

I'm not going to describe higher variants. I'm just going to say at this point that it can be done, but requires a lot more work.

Here's what one needs to do.

  • Corresponding to $n$, we first write down the term $R_n(x,h) = \sum_{k=0}^{n-1} \binom{n}{k} x^kh^{n-k}$. For example, if $n=4$, that looks like $$ R_4(x,h) = 4x^3h+6x^2h^2+4xh^3+h^4 $$

  • Next, we write this in "Horner's form" with respect to $h$. That is, at each stage, we factorize $h$ out from the inside and keep doing this till the outside. For example,$$ 4x^3h+6x^2h^2+4xh^3+h^4 = h(h(h(h+4x)+6x^2)+4x^3) $$

  • Given the current quotient as $x$, we must always have to compute all the terms involving $x$ , and store them in various parts of the galley. For example, with $n=3$ we put the $3x$ term on the right hand side of the bar. Maybe we can put everything on the right hand side, but we need all those terms for sure.

Great, we know what the complexities involved are. Now let me , in much detail as I can, define the algorithm for finding the $n$th root of a number $D$, using the Galley method.

  • Break $D$ into groups of $n$ digits, starting from the rightmost digit. Then, for the leftmost group, say $L_1$, find the largest single digit number $x$ such that $x^n \leq L_1$. Calculate $x^{n-1}$ and write it down so that the last digit of this number coincides with the last digit of $L_1$. Perform galley cancellation and obtain a new dividend.

  • Suppose that the current quotient is $x$. Find all the quantities linked with $R_n(x,h)$ that involve only $x$ (for example, in $R_4$ we find $4x^3,6x^2$ and $4x$). Write down all these numbers on the right hand side of the bar, except the largest term $nx^{n-1}$, which we write on the left hand side of the bar, below the last number from the previous calculations, such that its last digit is $n-1$ digits to the left of the last digit of the next block.

  • Now, we must guess $h$. Here's the heuristic from [9], except it's extended. What we do, is approximate $\frac{c.d.}{nx^{n-1}}$, where $c.d.$ is the current divisor, and $x$ is the current quotient. IF this number has a significantly large decimal part (like $6.8$, or $7.5$ : even something like $9.1$ may be okay), then one can take the digit formed by removing the decimal part as $h$ (So if $\frac{c.d.}{nx^{n-1}} \approx 6.8$ then you take $h=6$). Otherwise, go to its predecessor. (for example, with $\frac{c.d.}{nx^{n-1}} \approx 6.04$, go to $h=5$). If you are doubtful, then always take the digit formed by removing the decimal part : eventually, this will fail and then you can go back and replace this number by its predecessor.

  • We will calculate each of the quantities involved in $R_n(x,h)$ on the right hand side. For example, take say $n=4$. Then, the inner most term is $4x$, followed by $6x^2$ and then $4x^3$. So what you'd do is :

    • Write $h$ after $4x$ to get $4xh$. Find the quantity $h(4x+h)$.

    • You add $6x^2$ to this to get $6x^2+h(4x+h)$. Multiply this quantity by $h$.

    • Add $6x^3$ to this quantity. DON"T multiply by $h$ at the last step.

  • After the last addition, you have a number. Write down this number so that its last digit is directly below the last digit of the current group.

  • You now have two numbers written down (like $5292$ and $7596$ in the earlier example). Perform "group cancellation". Proceed to the new divisor.

  • Finally, when all digits of the original number are cancelled, then you cancel everything that's below the original number and the existing quotient. We have $$ \text{ Original Number } = (\text{Existing Quotient})^n + \text{ Whatever is left on the LHS} $$

Thus, we've shown that

One can perform $n$th root calculations using the Galley method.

However, it suffices to say that I've lost the patience to perform a full-fledged fourth root calculation. Perhaps I'll prepare one, but it won't fit in this answer so I'll link an image of it.

References

[9] https://www.youtube.com/watch?v=y0qWHMmCY4E

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .