### ----------------------------------------------------
### -- Arithmetic::PaperAndPencil
### -- Licenses: Artistic-2.0
### -- Authors: Jean Forget
### -- File: doc/Description-en.md
### ----------------------------------------------------
### -- Chunk 2 of 4
 multiplication from  an anonymous treatise
published  in Trevise  in  1478, and  a B2  multiplication  and an  A2
multiplication from a treatise written by Luca Pacioli in 1494.

Multiplication  A1  is  cumbersome,  but  this  is  a  minor  problem.
Multiplication B1 is confusing,
with the  multiplier stuck to  the last  part of the  product. Lastly,
multiplication B3 is  barely legible, it does not  help understand the
mechanism of  multiplication (you cannot  easily guess how  to compute
the units  and the tens  of the product)  and it is  incompatible with
`Int` typed  line numbers and  column numbers. So the  module provides
only the  A2 and B2  variants, renamed `jalousie-A`  and `jalousie-B`,
and  the  A1  variant,  named  `jalousie-A`  but  with  an  additional
parameter `:product<straight>`. This parameter  can also be applied to
the `jalousie-B`  type. In  addition, the module  does not  draw inner
vertical and horizontal lines. These various possibilities look like:

```
   6 2 8               6 2 8             6 2 8          6 2 8
  --------            --------         --------       --------
 1|1/0/1/|            |1/0/1/|         |\4\8\2|       |\4\8\2|
  |/2/4/6|2           |/2/4/6|2       4|2\0\3\|2     4|2\0\3\|
 4|1/0/2/|           /|1/0/2/|         |\8\6\4|       |\8\6\4|
  |/8/6/4|3         / |/8/6/4|3       3|1\0\2\|5     3|1\0\2\|\
 6|2/0/3/|         / /|2/0/3/|         |\2\4\6|       |\2\4\6| \
  |/4/8/2|4       / / |/4/8/2|4       2|1\0\1\|9     2|1\0\1\|\ \
  --------       / /  --------         --------       -------- \ \
   9 5 2        1 4 6  9 5 2             1 4 6          1 4 6  9 5 2
```

A minor difference  with the final result: in  this Markdown document,
horizontal lines  appear as strings  of dashes.  In the  HTML version,
the  horizontal lines  will  be  generated by  `<u>`  tags to  display
underlined spaces  or underlined digits.  On the other  hand, vertical
and slant lines are drawn with pipes / slashes / backslashes as shown.

### "Boat" variant

This variant is described in _NWNS_ on  page 440. It is similar to the
"`boat`" variant of the division, which  is the reason why I gave them
the same name.

Karl Menninger begins with describing  the idea, regardless of the way
the  digits are  placed  on the  paper  sheet. Let  us  use again  the
multiplication 234 ×  628. The first step in the  computation of 234 ×
6. this gives:

```
  24
 18
12
------
   628
------
 234
```

The second step is 234 × 2, with the multiplier written a second time,
aligned with digit "2" of the multiplicand:

```
   08
  06
 04
------
  24
 18
12
------
   628
------
 234
  234
```

The third step is 234 × 8, with the multiplier aligned with digit "8":

```
    32
   24
  16
------
   08
  06
 04
------
  24
 18
12
------
   628
------
 234
  234
   234
```

Lastly, the partial products are added together:

```
146952
------
    32
   24
  16
------
   08
  06
 04
------
  24
 18
12
------
   628
------
 234
  234
   234
```

This is the theoretical side. Actually, the multiplication is executed
by writing each partial product digit  in the first available spot  in
the  proper  column. And  leading  zeroes  are  not written.  Here  is
side-by-side the theoretical view with  leading zeroes removed and the
actual view.

<pre>
  24
 18         12
12         1284
------     ------
   628        <strike>6</strike>28
------     ------
 234        <strike>234</strike>
</pre>

Second step.

<pre>
    8
   6
  4
------
  24         4
 18         126
12         12848
------     ------
   628        <strike>62</strike>8
------     ------
 234        <strike>2344</strike>
  234        <strike>23</strike>
</pre>

Third step.

<pre>
    32
   24
  16
------
    8
   6
  4
------       12
  24         463
 18         1264
12         128482
------     ------
   628        <strike>628</strike>
------     ------
 234        <strike>23444</strike>
  234        <strike>233</strike>
   234        <strike>2</strike>
</pre>

And the addition of the partial products.

<pre>
  146952
  ------
      32
     24
    16
  ------
      8
     6
    4          69
  ------       <strike>12</strike>5
    24        4<strike>463</strike>
   18        1<strike>1264</strike>2
  12         <strike>128482</strike>
  ------     ------
     628        628
  ------     ------
   234        <strike>23444</strike>
    234        <strike>233</strike>
     234        <strike>2</strike>
</pre>

Actually,  _NWNS_  shows  a  multiplication in  which  the  elementary
products are computed right-to-left  for each multiplicand digit while
in  the  example  above  I have  computed  these  elementary  products
left-to-right. See the  difference below. The first line  uses the RTL
order, the second line uses the LTR order.

<pre>
               8         28
    24        124       1124
  ------     ------     ------
     628        628        <strike>6</strike>28
  ------     ------     ------
   23<strike>4</strike>        2<strike>34</strike>        <strike>234</strike>

              1          12
  12         128        1284
  ------     ------     ------
     628        628        <strike>6</strike>28
  ------     ------     ------
   <strike>2</strike>34        <strike>23</strike>4        <strike>234</strike>
</pre>

On page 441, _NWNS_ shows the middle-age variant of this operation. In
this  variant, each  elementary product  is immediately  added to  the
previous ones, instead of waiting for the end of the global operation.
There again, for each multiplicand  digit, the elementary products are
computed RTL. The intermediate computations are: `4 × 6 = 24`, `30 × 6 + 24  = 204`
and `200 × 6 + 204 = 1404`, and then  `4 × 2 + 14040 = 14048`, `30 × 2 + 14048  = 14108`
and `200  × 2 +  14108 = 14508`. The  last products,
with digit 8, are left as an exercise to the reader.

<pre>
                                                           5
                                                1          <strike>1</strike>
               0         40         40         4<strike>0</strike>0        4<strike>0</strike>0
    24        2<strike>2</strike>4       1<strike>22</strike>4       1<strike>22</strike>48      1<strike>224</strike>8      1<strike>224</strike>8
  ------     ------     ------     ------     ------     ------
     628        628        <strike>6</strike>28        <strike>6</strike>28        <strike>6</strike>28        <strike>62</strike>8
  ------     ------     ------     ------     ------     ------
   23<strike>4</strike>        2<strike>34</strike>        <strike>234</strike>        <strike>2344</strike>       <strike>2344</strike>       <strike>2344</strike>
                                     23         2<strike>3</strike>         <strike>23</strike>
</pre>

There  again, we  may prefer  computing the  elementary products  LTR.
Actually, this is  how the multiplication was computed  on the abacus.
So we  have `2 × 6  = 12`, `3  × 6 + 120  = 138` and  `4 × 6 +  1380 =
1404`, and then `2 × 2 × 10 + 1404  = 1444`, `3 × 2 + 1444 = 1450` and
`4 × 2 + 14500 = 14508`.

<pre>
                                               5         5
                         4          44        4<strike>4</strike>        4<strike>4</strike>
              3          <strike>3</strike>0         <strike>30</strike>        <strike>30</strike>0       <strike>30</strike>0
  12         1<strike>2</strike>8        1<strike>28</strike>4       1<strike>28</strike>4      1<strike>284</strike>      1<strike>284</strike>8
  ------     ------     ------     ------    ------    ------
     628        628        <strike>6</strike>28        <strike>6</strike>28       <strike>6</strike>28       <strike>62</strike>8
  ------     ------     ------     ------    ------    ------
   <strike>2</strike>34        <strike>23</strike>4        <strike>234</strike>        <strike>234</strike>4      <strike>234</strike>4      <strike>2344</strike>
                                     <strike>2</strike>3        <strike>23</strike>        <strike>23</strike>
</pre>

### Egyptian or Russian Multiplication

Long ago, some  school friends showed me  the Egyptian multiplication.
Years later, I  found other sources which showed me  that this was the
Russian  multiplication,  or  "Russian  peasant  multiplication".  The
actual  Egyptian multiplication  uses a  different set-up.  Suppose we
need to multiply 628  by 234. The two numbers are set  up side by side
(with a  sufficiently wide gap). Then  we divide the left  number by 2
and we multiply the right number by 2 until we reach number 1.

```
234     628
117    1256
 58    2512
 29    5024
 14   10048
  7   20096
  3   40192
  1   80384
```

On each  line in  which the left  number is even,  we cross  the right
number out.

<pre>
234     <strike>628</strike>
117    1256
 58    <strike>2512</strike>
 29    5024
 14   <strike>10048</strike>
  7   20096
  3   40192
  1   80384
</pre>

Then we add the uncrossed numbers.

<pre>
234     <strike>628</strike>
117    1256
 58    <strike>2512</strike>
 29    5024
 14   <strike>10048</strike>
  7   20096
  3   40192
  1   80384
     ------
     146952
</pre>

We can consider  that the multiplications by 2 and  the divisions by 2
are simple enough, so we need not write them fully as:

```
234|2        628     117|2      1256
03 |---        2      17|--        2   etc
 14|117     ----       1|58     ----
  0|        1256                2512
```

Even  with this  simplification, the  Russian multiplication  is long.
This  means resolving  a binary  multiplication  even if  you work  in
decimal or hexadecimal. So I nearly discarded this variant. But in the
end, I included it into the module.

Another difficulty.  The method is  based on classifying  numbers into
even numbers and odd numbers. In decimal, it is easy, just look at the
unit digit. If the digit is even,  the number is even. If the digit is
odd, the number is odd. This  criterion applies to any even radix, but
it is wrong for odd radices. We must find something else.

In radix  10, the  divisibility by 3  or 9 is  checked by  summing the
digits of the number. If the  total is itself a multi-digit number, we
iterate the process until we have  a single-digit number. Then we have
the conclusion.  If the  last result  is 3, 6  or 9,  the number  is a
multiple of  3. If it is  9, the number is  a multiple of 9.  The same
method applies in radix 9 to divisibility by 2, 4 and 8. It applies in
radix 11 to divisibility by 2, 5 and  A and in radix 13, it applies to
divisibility by 2, 3, 4, 6 and C.

Consider for  example number 45269  in radix 11.  The sum of  its five
digits is 26 in  decimal, that is, 24 in radix  11. A second iteration
gives the sum  2+4 = 6, which is  an even number. So 45269  is an even
number. This is fortunate, because in decimal, this is 65536. So 45269
is even, but it is not a multiple of 5 or 10.

Likewise, for  45268, the sum  of digits  is 25 in  radix 10 or  23 in
radix  11 in  the first  iteration and  5 in  radix 11  in the  second
iteration. So  45268 (or  65535 in radix  10) is an  odd number  and a
multiple of 5.

More generally, if radix _b_ is odd,  2 is a divisor of _b_-1. So, for
any odd  radix, the  "sum of  digits" method works  to determine  if a
number is even or odd.

For  divisibility  by 2,  the  criterion  can  be simplified.  In  the
original number, we  count the odd digits, without  bothering with the
even digits. And we need only count them, we need not add them. If the
count is even, the number is even.  If the count is odd, the number is
odd. With number 45269  in radix 11, we find two odd  digits, 5 and 9.
Therefore the number  is even. With number 45268 in  radix 11, we find
only one odd digit, therefor the number is odd.

Division
--------

### Standard Division

When I learned the standard division, partial remainders were computed
with  an   operation  mixing  a  multiplication   and  a  subtraction:
multiplying the divisor by the  current quotient digit and subtracting
it  from  the  partial  dividend.   Much  later,  I  heard  that  this
multiplication and this subtraction were now separate operations. When
working  on the  present module,  I  watched a  few tutorials  (French
speaking, of course),  to know which was the exact  method used: do we
prepare  the division  by  computing  the first  10  multiples of  the
divisor? Or  do we compute  each multiplication when required  and not
before?

For these two
[French-speaking](https://www.youtube.com/watch?v=BC_QZjyEdpw)
[tutorials](https://www.youtube.com/watch?v=eIo9tZ6T5CY),
the authors posit  that the pupil knows by heart  the multiples of the
divisor (the multiples of  52 in one case, the multiples  of 35 in the
other). I am very sceptical. A side remark about the first tutorial is
that the many stops between successive sentences and the fact that the
zero is processed  like any other digit make me  think that this video
was generated  with a programme  similar to my module  (yet generating
MPEG or MP4 instead of HTML).

In this [tutorial](https://www.youtube.com/watch?v=IQFKMnvwFPM),
the author clearly states that the  pupil must prepare the division by
computing the first  ten multiples of 23 or 16  or, more generally the
divisor.  Also,  the tutorial  acknowledges that  there is  no  single
division method.  There are several  methods and the pupil  must stick
with one of them and practice it.

This [tutorial](https://www.youtube.com/watch?v=bn-IZD-jgl8),
is also interesting. Among other things, it uses "hooking" as shown in
the chapter  below. The  hooks are  drawn with  curved lines,  while I
learned to  draw them with  straight lines  and right angles.  And the
hooks are  named _chapeau_ or  _parapluie_ (hat or  umbrella). Another
interesting  point is  that it  shows the  trial-and-error process  by
computing a first candidate digit with a 1-by-1 or 2-by-1 division and
then,  decrementing  the  candidate  digit until  successful.  A  last
interesting point is that at each step, we must check that the partial
remainder is  less than the divisor.  If greater or equal,  that means
there was a mistake in the operation.  I learned to do this check, but
I chose not to implement it in the module.

And lastly a  [tutorial](https://www.youtube.com/watch?v=pbwoawMMEhU)
which teaches  the division the way  I learned it, or  nearly so, with
combined multiplication  and subtraction. There are  also hooks, drawn
with curved lines  as in the tutorial above.  A significant difference
with the way I learned is that carries are written and stricken in the
tutorial, while  I learned to  keep the  carries in my  memory without
writing them on the paper.

The conclusion  is that  I should  not decide all  by myself  which is
_the_ single division method. Instead,  I must define a few parameters
to  allow the  module  users  to choose  which  variant  they want  to
generate.

### "Hook" in the Standard Division

A topic  that most certainly deserves  a mention is the  "hook" on the
first line. Note: this word "hook" or its translation _harpon_ are not
official words,  they are words I  picked up when writing  this module
and its  documentation. A  French-speaking tutorial  that I  saw later
name this thing _chapeau_ or _parapluie_ ("hat" or "umbrella").

The hook does not appear in the December 1970 example at the beginning
of this text, but it can be seen below.

![Examples of divisions with hooks](division-hooks.png)

First, a special case with the centre  division. This is a 27000 ÷ 250
division. We  were told  to simplify  by 10, so  we would  compute the
simpler division  2700 ÷ 25.  This is why the  hook is present  on the
second line instead of the first one.

The simple  hook allows the pupil  to know where he  will subtract the
first digit of the first intermediate remainder. So, when dividing 270
by 25 or  18, the first digit  of the first remainder  will be written
under the "7".

The double hook has the same usage, plus it shows which portion of the
dividend  will be  used for  the  computation of  the first  candidate
digit.  Remember that  this computation  uses a  single-digit divisor.
Thus, when dividing 2700 by 25, the  first computation will be "2 ÷ 2"
and the remainder rightmost digit will be under the "7". When dividing
11340 by 108, the first computation will  be "1 ÷ 1" and the remainder
rightmost digit will  be written under the "3". When  dividing 2700 by
375,  the  first computation  will  be  "27  ÷  3" and  the  remainder
rightmost digit will be written under the second "0".

As you can see, when the  dividend has a double-barb hook, the divisor
also has a hook, always covering  a single digit. This hook is useless
and I have not included it in the `division` method.

The use of a hook is also shown in these
[(French speaking)](https://www.youtube.com/watch?v=bn-IZD-jgl8)
[tutorials](https://www.youtube.com/watch?v=pbwoawMMEhU),
where it is  used in all successive partial dividends  instead of only
the first partial  dividend. In my opinion, hooking is  useful only on
the first  line, where the  partial dividend  is embedded in  the full
dividend,  while on  other  lines the  partial dividends are  standing
alone.  Additionally,  when  the multiplication  and  subtraction  are
separate,  drawing the  hook interferes  with drawing  the subtraction
line.

My tests  to generate HTML  and use  a Unicode combining  character to
create  an  overline  did  not   succeed.  I  have  bypassed  this  by
underlining spaces characters  on the previous line. The  barbs do not
appear. Too bad, but we have to live with it.

### Division and computing the GCD

In 1978,  my math professor  showed us a  new set-up for  division, in
which the  quotient is written  _above_ the divisor instead  of below.
Here is on  the left the traditional  set-up and on the  right the new
set-up.

```
                                   3141592
                                   ---
 355000000|113           355000000|113
 0160     |---           0160     |
  0470    |3141592        0470    |
   0180   |                0180   |
    0670  |                 0670  |
     1050 |                  1050 |
      0330|                   0330|
       104|                    104|
```

Why this alternate setup? Because at the same time,
the math teacher taught us Euclid's  algorithm to compute the GCD of
two integers. This algorithm uses cascading divisions. The dividend of
the second  division is  the divisor  of the first  one. Below  it, we
would find both the first  quotient and the intermediate remainders of
the second division. You cannot write  both numbers at the same place,
one has to move away. This is the reason why the quotient of the first
division is written above. Here is how we compute the GCD of 355000000
and 113:

```
          3141592 1   14 1
          ---     --- -- -
355000000|113    |104|7 |6
0160     |  7    | 34|1
 0470    |          6|
  0180   |
   0670  |
    1050 |
     0330|
      104|
```

Euclid's Algorithm executes the following operations:

1. 355000000 ÷ 113 = 3141592, remain 104

2. 113 ÷ 104 = 1, remain 7

3. 104 ÷ 7 = 14, remain 6

4. 7 ÷ 6 = 1, remain 1

### Standard Division and Separate Multiplication and Subtraction

There was a bug in the standard division when you opted for a separate
multiplication and subtraction.  The bug is fixed, but  it deserves to
be remembered, because  it explains some API checks.  Take for example
the division `724 ÷ 16`.

```
--
724|16
   |--
   |..
```

The tens digit  is computed with `72 ÷ 16`.  The first candidate digit
is `7 ÷ 1 = 7`. The division looks like:

```
--
724|16
   |--
   |7.
```

The  intermediate  product   is  `7  ×  16  =  112`,   which  must  be
right-aligned with the hooked part `72`. This gives:

```
 --
 724|16
112 |--
    |7.
```

Digit `7`  is too  big, so  we erase the  intermediate product  and we
replace  the  candidate digit  with  the  next  lower digit  `6`.  But
actually, only  the chars under  `724` are  erased: digits `12`  and a
space char. This gives:

```
 --
 724|16
1   |--
    |6.
```

Computing the intermediate product with candidate digit `6` gives:

```
 --
 724|16
196 |--
    |6.
```

To make  a long story short,  the same problem happens  with the units
digits. The final division is the following:

```
 --
 724|16
164 |--
 -- |45
  84|
 180|
  --|
   4|
```

Actually, the problem  does not occur for the second  and next digits,
only the first one.  To keep the code simple, when I  need to erase an
intermediate product (combined multiplication  and substraction) or an
intermediate remainder (separate multiplication and substraction), the
erasure is applied to the whole  line, aligned with the main dividend.
In  the example  below, all  erasures  are aligned  with the  dividend
`72526` and  therefore 5-column long, while  all intermediate products
are 2- or 3-digit long.

```
 --
 72426|16
164   |--
 --   |4526
  84  |
  80  |
  --  |
   42 |
   32 |
   -- |
   102|
    96|
   ---|
    06|
```

For stand-alone divisions, the bug has been fixed by erasing "one more
digit". But for radix conversion or  for GCD computation, it cannot be
fixed. Take the GCD of 2912 and 724. The first division is:

```
     4
     ---
2912|724
2896|
----|
  16|
```

The next division sets up as:

```
     4   ..
     --- --
2912|724|16
2896|   |
----|   |
  16|
```

As seen above,  the first candidate digit is `7`  and the intermediate
product  is  `112`. How  do  you  write  this  product in  the  second
division? The hundreds digit overflows  into the first division, which
turns `2896` into `2891`:

```
     4   7.
     --- --
2912|724|16
2891|12 |
----|   |
  16|
```

When iterating  to the next candidate  digit `6`, we can  either erase
two digits (plus the space char under digit `4`) or erase three digits
(plus a space char). In both cases, this is wrong:

```
     4   45 4           4   45 4
     --- -- -           --- -- -
2912|724|16|4      2912|724|16|4
2891|64 |16|       289 |64 |16|
----|-- |--|       ----|-- |--|
  16| 84| 0|         16| 84| 0|
    |180|              | 80|
      --|                --|
       4|                 4|
```

So, for radix  conversion and for GCD, the division  type `"std"` does
not allow option `"separate"` for the `mult-and-sub` parameter.

### Boat Division

As you have  seen in the examples  at the beginning of  this text, the
1822-style division looks like a rhombus or like an hexagon, depending
on the respective lengths of the dividend and of the divisor.

<pre>
   0<u>4</u>                   <u>13</u>
  <strike>108</strike><u>5</u>                 <strike>142</strike><u>1</u>
 <strike>14021</strike><u>7</u>               <strike>04015</strike><u>7</u>
<strike>2469620</strike><u>2</u>             <strike>0816648</strike><u>0</u>
<u><strike>24696000</strike></u>{0954        <u><strike>34048000</strike></u>{1315
--------           --------
<strike>25882222</strike>             <strike>25882222</strike>
 <strike>258888</strike>               <strike>258888</strike>
  <strike>2588</strike>                 <strike>2588</strike>
   <strike>25</strike>                   <strike>25</strike>
</pre>

Since the word "hexagon" would  create a confusion with "hexadecimal",
I decided to call this type of division the _rhombic_ division.

Later,  I read  again pages  330 and  331 of  _NWNS_ and  I noticed  a
sentence I did  not pay attention to until now.  For the Italians, the
division looks like a boat or a  galley with the sail spread. So their
phrase for the division was  _divisione per batello_ or _divisione per
galea_. I  adopted the English  translation `"boat"` to  describe this
type of division.

How  did I  guess the  mechanism? When  you know  the proper  angle of
attack, it is very  easy. To tackle this task, I  just took a division
and I  recalculated it in  the way I already  knew, that is,  with the
"gallows" method. Example:

```
      13            -----
     1421           34048000|25882
    040157          081660  |-----
   08166480          040140 |1315
   34048000{1315      142580|
  