### ----------------------------------------------------
### -- Arithmetic::PaperAndPencil
### -- Licenses: Artistic-2.0
### -- Authors: Jean Forget
### -- File: doc/Description-en.md
### ----------------------------------------------------
### -- Chunk 3 of 4
 --------            13170|
   25882222
    258888
     2588
      25
```

I scanned  both divisions to  extract common elements. Lo  and behold!
common elements  do exist. For example,  if you look closely,  you can
find the second partial dividend 081660:

<pre>
      13            -----
     1421           34048000|25882
    040157          <strong>081660</strong>  |-----
   <strong>08166</strong>480          040140 |1315
   34048<strong>0</strong>00{1315      142580|
   --------            13170|
   25882222
    258888
     2588
      25
</pre>

or the third partial dividend 040140:

<pre>
      13            -----
     1421           34048000|25882
    <strong>0401</strong>57          081660  |-----
   08166<strong>4</strong>80          <strong>040140</strong> |1315
   340480<strong>0</strong>0{1315      142580|
   --------            13170|
   25882222
    258888
     2588
      25
</pre>

I guessed  that a snapshot  of the  division, just after  lowering the
first digit  to build the  second partial dividend, or  after lowering
the second digit  to build the third partial dividend  would look like
this, with a big question about what exists below the horizontal line:

<pre>
                    -----
                    34048000|25882
                    081660  |-----
   08166                    |1...
   <strike>34048</strike>000{1...            |
   --------                 |
   ????????
    ??????
     ????
      ??

                    -----
                    34048000|25882
    0401            081660  |-----
   <strike>08166</strike>0            040140 |13..
   <strike>340480</strike>00{13..            |
   --------                 |
   ????????
    ??????
     ????
      ??
</pre>

Since the  first partial dividend 34048  is crossed out and  since the
second partial  dividend 081660  is read in  two parts,  an horizontal
first part and an oblique second  part, I supposed the same applied to
the divisor: a  first instance crossed out and a  second instance with
an horizontal first part and an oblique second part.

<pre>
                    -----
                    34048000|25882
                    081660  |-----
   08166                    |1...
   <strike>34048</strike>000{1...            |
   --------                 |
   <strike>25882</strike>2
    2588

                    -----
                    34048000|25882
    0401            081660  |-----
   <strike>08166</strike>0            040140 |13..
   <strike>340480</strike>00{13..            |
   --------                 |
   <strike>258822</strike>2
    <strike>2588</strike>8
     258
</pre>

Yet,  there might  have been  traps to  avoid. First,  some operations
might have  been wrong. I  did not  find any, fortunately.  Then, some
operations  might have  been  imperfectly computed,  giving the  right
result but with a slightly wrong  mechanism. This is the case with the
other division I have shown as an  example. Here it is again, with the
corresponding "gallows"  division. I  have separated  the subtractions
from  the  multiplications  to  emphasize the  minor  problem  in  the
computation.

```
   04            -----
  1085           24696000|25882
 140217          00000   |-----
24696202         -----   |0954
24696000{0954    246960  |
--------         232938  |
25882222         ------  |
 258888           140220 |
  2588            129410 |
   25             ------ |
                   108100|
                   103528|
                   ------|
                    04572|
```

In this  division, the schoolboy  did not align properly  the dividend
and the divisor, so the first quotient  digit was a zero and he had to
compute  an  intermediate  remainder   with  a  useless  and  slightly
time-consuming mult-and-div operation.

This is really an error, not  a standard procedure, because on another
page, the schoolboy has properly shifted  the divisor to the right, so
the first  quotient digit would  not be zero.  The "8" of  the divisor
"87" is aligned with the "4" of the dividend "14076", not with the "1"
digit.

![Example of division in which the divisor is shifted from the dividend](boat-with-shift.webp)

<pre>
  <strike>1</strike>6
 <strike>535</strike>9
<strike>14076</strike>{161
-----
 <strike>8777</strike>
  <strike>88</strike>
</pre>

Remark: in the  division hard-copy, you may notice  that the schoolboy
went on to  compute the fractional part of the  quotient. You can read
the digits of  the intermediate remainders (which do not  appear in my
transcription), but there is no 4th / 5th instances of the divisor.

Another trap to avoid is choosing a division with not enough different
digits. Here is an example of  a division which would not have enabled
me to guess the actual mechanism.

![Example of division with many zeros, with on the right side the same division in "gallows" mode](boat-and-gallows.webp)

As you  see, on the  right side of the  "boat" division, you  find the
same  division  in  "gallows"  mode,  with  a  comment  written  by  a
schoolmate of  the owner of  the exercise  book (sorry for  the French
spelling mistakes).

<pre>
   09                   38400000{19100
  <strike>009</strike>0                  002000  {-----
 <strike>02000</strike>0                  020000 {2010
<strike>0020000</strike>0                  009000
<strike>38400000</strike>{2010              09000
--------
<strike>19100000</strike>
 <strike>191000</strike>
  <strike>1911</strike>
   <strike>19</strike>
</pre>

> Voila comme on la fait en dessus et sans bârer les chiffres

> Translation: Here is how it is done above without crossing out the digits.

As you may notice, within  the intermediate remainders, there are very
few digits others than  zero. This make it hard to  someone like me to
identify similarities between both versions.

Square Root
-----------

The root extraction algorithm is described  in _HAL_ pages 234 to 237.
There  is a  first description  for the  abacus and  a second  one for
someone  using  paper  and  pencil.  The  second  description's  title
translates to English as "practical computation setup". Here it is.

```
6554900|2
255    |---
       | c(c+40)<255

6554900|25
255    |---
 3049  | 5(5+40)<255
       | c(c+500)<3049

6554900|256
255    |---
 3049  | 5(5+40)<255
   1300| 6(6+500)<3049
       | c(c+5120)<1300
```

Despite its  name, this  setup is  not practical.  How do  you compute
formula `c(c+40)` with  `c=6` and with `c=5`? It can  be done, but not
simply. This is  even more the case when  computing formula `c(c+500)`
with `c=6`. On the other hand, using the setup I learned in 1976:

```
6554900|2
255    |---
       |46
       | 6

6554900|2
255    |---
       |45
       | 5

6554900|25
255    |---
 3049  |45
       | 5
       |---
       |506
       |  6
```

the  operations `6×46`,  `5×45` and  `6×506` are  very similar  to the
computations of intermediate remainders  in divisions. So an important
part  of  the square  root  technique  was  already  known to  us.  In
addition, instead  of doubling  25 and multiplying  to obtain  500, or
doubling 256 and multiplying  it by 10 to obtain 5120,  we just had to
compute the  simple additions  `45+5` and `506+6`  and then,  stick to
these numbers the candidate digits.

So I  stick with the setup  I learned in 1976  and I see no  reason to
include the setup described in _HAL_ page 237.

By the  way, _HAL_ affirms that  the gallows method to  extract square
roots  was taught  in France  until the  1960's. Yet,  I learned  this
technique in 1976.

Implementation
==============

Coordinates
-----------

Coordinates are line numbers and  column numbers. The variation is the
usual one, line numbers increase from top to bottom and column numbers
increase  from left  to  right.  In some  cases,  it  is difficult  to
determine   the   final   footprint    of   the   operation   ("galea"
multiplication, for example).  So we allow negative  coordinates if we
need to insert a  new line above the operation of a  new column on the
left of the operation.

This  lead  us to  the  distinction  between logical  coordinates  and
physical coordinates. The HTML  renderer uses physical l-c coordinates
which are  always positive  or zero. The  coordinates computed  by the
various operation  generators are  logical coordinates. Each  time the
HTML renderer displays the operation,  it checks the minimum values of
the l-c numbers to determine how  to shift the logical coordinates and
obtain physical coordinates.

Another shift between physical and  logical coordinates comes from the
vertical lines. Vertical  lines are rendered as  pipe characters. They
are full-fledged characters, when  compared with horizontal lines that
are rendered  as "underline"  attributes. This means  that we  need to
allocate a physical column for vertical lines.

Example (with the proviso that  I could not use "underline" attributes
in a Markdown document and `31` should  be on the same line as `0160`;
the line coordinates in this example are not significant):

```
+--------------- logical = -8, physical =  0
|       +------- logical =  0, physical =  8
|       |+------ logical =  0, physical =  9
|       ||+----- logical =  1, physical = 10
|       ||| +--- logical =  3, physical = 12

355000000|133
0160     |---
 057     |31
```

For a multi-character  string, the coordinates are  the coordinates of
the  last character  (usually  the units  digit, if  the  string is  a
number). In the example above, logical coordinates of the dividend are
`l=0, c=0` and the logical coordinates  of the divisor are `l=0, c=3`.
For a  vertical line,  the logical  column number is  the same  as the
column number of the left neighbour character. For an horizontal line,
the  logical  line number  is  the  same as  the  line  number of  the
underlined character.

Paper Sheet
-----------

The main class, `Arithmetic::PaperAndPencil`, represents a paper sheet
(or two, for a prepared division).  For the moment, the only attribute
is    a    list    of    actions,    from    the    auxiliary    class
`Arithmetic::PaperAndPencil::Action` described below.

Actions
-------

An action usually consists in:

1. read one or two already written digits,

2. possibly strike them,

3. do a mental computation with these two digits,

4. say the formula associated with this computation,

5. write the result on the sheet of paper.

Sometimes, an action is just  drawing a line, without saying anything.
Or it  consists in copying several  contiguous digits from a  place to
another  (multiplications with  shortcuts or  prepared divisions).  Or
erasing contiguous digits.

The attributes  of class  `Arithmetic::PaperAndPencil::Action` are:

* `level` a level described in the following chapter.

* `label` code of the spoken formula accompanying some computations or some actions

* `val1`, `val2`, `val3` variable values interpolated in the spoken formula.

* `r1l` and `r1c` logical coordinates of the first read digit.

* `r1val` value of the first read digit.

* `r1str` boolean indicating if the digit is striken or not.

* `r2l`, `r2c`, `r2val`, `r2str` the equivalent for the second read digit.

* `w1l`, `w1c`, `w1val` the equivalent for the first written digit.

* `w2l`, `w2c`, `w2val` the equivalent for the second written digit.

Example for the following action:

```
        c → 0 123456 7     0 123456 7

l → 0         6 2 8          6 2 8
             --------       --------
    1        | / / /|       |1/ / /|
    2        |/ / / |2      |/2/ / |2
    3        | / / /|    →  | / / /|
    4        |/ / / |3      |/ / / |3
    5        | / / /|       | / / /|
    6        |/ / / |4      |/ / / |4
             --------       --------
    7
```

The corresponding action contains:

* `level = 5` (see below)

* `label = MUL01` code for message "#1# fois #2#, #3#" (or "#1# times #2#, #3#")

* `val1 = 6`, `val2 = 2`, `val3 = 12` for the final message "6 fois 2, 12" (or "6 times 2, 12")

* `r1l = 0`, `r1c = 1`, `r1val = 6`, `r1str = False`

* `r2l = 2`, `r2c = 7`, `r1val = 2`, `r1str = False`

* `w1l = 1`, `w1c = 1`, `w1val = 1`

* `w2l = 2`, `w2c = 2`, `w2val = 2`

Second example with a full string instead of single digits:

```
        c → 0123456      0123456 7

l → 1          628          628
    2          333   →      333
              ----         ----
    3         1884         1884
    4            .        1884.
```

The corresponding action contains:

* `level = 3` (see below)

* `label = WR05` code for "Je recopie la ligne #1#" (or "Copying line #1#")

* `val1 = 1884` for final message "Je recopie la ligne 1884" (or "Copying line 1884")

* `w1l = 4`, `w1c = 4`, `w1val = 1884`, the column is the column of the last digit.

* other attributes: whatever

When a line  is drawn, the code starts with  `DR` for "draw". Usually,
this does not correspond to an actual message, because we are not used
to say anything when drawing the line. The coordinates of the starting
and stopping locations  are stored into `w1l`, `w1c`,  `w2l` et `w2c`.
Example:

```
        c → 0 123456 7     0 123456 7

l → 0         6 2 8          6 2 8
             --------       --------
    1        |      |       |     /|
    2        |      |2      |    / |2
    3        |      |    →  |   /  |
    4        |      |3      |  /   |3
    5        |      |       | /    |
    6        |      |4      |/     |4
             --------       --------
    7
```

* `level = 5` (see below)

* `label = DRA04` code for an slant line

* `w1l = 1`, `w1c = 6`

* `w2l = 6`, `w2c = 1`

* other attributes: whatever

### Attribute `level`

The  attribute  `level` controls  the  time  when the  HTML  procedure
actually renders the partially written operaton. The higher the value,
the more frequent the operation is rendered. The typical values are:

* 0 display the operation only when complete.

* 1  display the  operation each  time the  page change  (for prepared
multiplications and prepared divisions).

* 2 display when changing phase.  E.g., for multiplications, there are
three  phases:  set-up, computing  the  partial  products, adding  the
partial products to compute the final product.

* 3  full processing  of  a digit.  E.g. for  divisions,  this is  the
computation of  a new  valid quotient  number, with  the corresponding
partial remainder. Since this ia a trial-and-error mechanism, only the
last successful trial is level-3.

* 4 for the operation with a trial-and-error process such as division,
this level correspond to the full processing of a fruitless value.

* 5 for the writing of each digit of a partial product or of a partial
remainder.

* 6 intermediate computation, without writing.

In the  case of the  conversion for a  radix to another  with Horner's
schema, the complete operation  includes several basic multiplications
alternating with basic additions.  The levels of these multiplications
and additions are shifted when  compared with the level of stand-alone
multiplications and additions. For example, level 2 for the transition
of phase becomes level  5, level 3 for the full  processing of a digit
of the multipler becomes level 6 and so on.

For  a given  action, the  level is  function of  this action,  but it
depends also of the next action. For example, most `WRI01` actions are
level 5,  but if this action  is the last, or  if it is followed  by a
`TITnn` action, the level of the `WRI01` action is 0.

### Special Action Codes

These codes are not directly linked to an arithmetical operation. They
are utility functions.

| Code  | Explanation                        |
|-------|:-----------------------------------|
| DRA01 | Vertical line                      |
| DRA02 | Horizontal line                    |
| DRA03 | Slant line, shown as backslashes   |
| DRA04 | Slant line, shown as slashes       |
| ERA01 | Erasing characters                 |
| HOO01 | Hook over a dividend               |
| NXP01 | Changing page                      |
| TITnn | Title for an operation             |

Why four  different codes  for drawing  lines? It  would be  better to
deduce the orientation of the  line by checking the coordinate values,
wouldn't it? For example, if `w1c == w2c`, that means that the line is
vertical, if  `w1l ==  w2l`, it  is horizontal. The  answer is  no, we
cannot  just compare  the  coordinates.  There is  the  case of  lines
occupying a single cell. For  those lines, we have simultaneously `w1c
== w2c`, `w1l == w2l`, `w1c - w2c ==  w1l - w2l` and `w1c - w2c == w2l - w1l`,
so we  cannot infer  the line  angle from  the coordinates,  we cannot
determine if we must  write a single pipe, a single  slash or a single
backslash or if we tag a single digit with an underline HTML tag.

The hook over a dividend is a way to remember the column-coordinate of
the first intermediate remainder during a division. At first, I wanted
to  use `U+0305`  (`COMBINING  OVERLINE`), but  my  attempts were  not
successful. So I made this a variant of `DRA02`.

Various Remarks
---------------

Among the quality advices when writing programmes, one decrees that we
must not use  "magical" numeric values. We must  use symbolic constant
with self-documenting names instead. I did not apply this advice. Yet,
at some times I wrote:

```
  my $zero = Arithmetic::PaperAndPencil::Number.new(:radix($radix), :value<0>);
  my $one  = Arithmetic::PaperAndPencil::Number.new(:radix($radix), :value<1>);
```

This  leads to  a  more  concise and  more  readable  function in  the
following lines.

```
    given $result {
      when 'quotient'  { return $zero; }
      when 'remainder' { return $dividend; }
      when 'both'      { return ($zero, $dividend); }
    }
    [...]
          $act-quo ☈-= $one;
```

For your information, it happens often that
[this advice is abused](https://thedailywtf.com/articles/constant-adventure).

Ideas I gave up
===============

Dropped Functionnalities
------------------------

### Fractional parts

At the very  beginning, I wanted to include numbers  with a fractional
part. Then I realised that would need many additional programme lines,
for a small benefit. So all the numbers this module uses are integers.

### Casting the Nines

During the 1960's, my schoolbook  contained a lesson about casting the
nines, but  my school teacher refused  to teach it to  us. Casting the
nines can  prove there is an  error in the computation,  but it cannot
prove the computation  is right, all it does is  _suggesting_ that the
computation  _might  be_ correct.  And  false  positives are  easy  to
obtain, you just have to misalign a digit and the result is wrong.

I did  not (officially) learn  the casting of the  nines, so I  do not
implement it in my module.

### Abacus

For some time,  I hoped to include the abacus  methods (_Suan Pan_ and
_Soroban_). The  visualisation function would need  a complete rewrite
and the computation methods would actually have few common points with
the paper methods,  so I discarded this idea. If  necessary, this will
be in another module, most certainly written by someone else.

On the other hand,  some variants that I have read  in _NWNS_ or _HAL_
and that I have included in the module may be computation methods used
with  the abacus,  and  converted by  the  author of  the  book to  be
readable in his book.

### Cross Multiplication

K. Menninger describes this method in  _NWNS_ on pages 441 and 442. He
gives an example for two numbers with 2 digits each, and mentions that
this method can extend, somewhat  with difficulty, to two numbers with
4 digits  each. Let us  compute `34 × 78`.  The numbers are  set-up in
this way:

```
3 4
|×|
7 8
```

First, the human operator multiplies the unit digits: "4 times 8 equal
32, write  2, carry  3". Then he  executes two  cross multiplications,
adding the two results  and the carry: "3 times 8 equal  24, 7 times 4
equal 28,  24 plus 28 equal  52, plus 3  equal 55, write 5,  carry 5".
Then he  multiplies the tens' digits  and adds the carry:  "3 times 7,
21, plus 5 equal 26". The final result is 2652.

This method is specified for numbers with up to 4 digits, while I want
to show multiplications with any  numbers of digits. In addition, this
multiplication  requires a  mental addition  of two  numbers with  two
digits  each, in  the  example  24 and  28,  while  I restrict  mental
additions so at least one of the two numbers is a single-digit number.
So I do not include this method.

### Other arithmetic operations

The  primary goal  of  this  module was  to  present  the square  root
extraction. It  was obvious that the  module would need also  the four
basic operations: addition,  subtraction, multiplication and division.
We  may consider  other  computation methods,  such  as prime  factors
extractions,  conversion  from  a  radix to  another  (either  with  a
polynomial  calculation  using  Horner's  scheme,  or  with  cascading
divisions), GCD extraction (with  cascading divisions, a.k.a. Euclid's
algorithm). I  discarded the prime  factors extraction and I  kept the
radix conversion with Horner's scheme and with cascading divisions and
the GCD extraction.

For what it's worth, here is the prime factors extraction for 28:

```
28 | 2
14 | 2
 7 | 7
 1 |
```

What is missing in this example is that on other sheets of papers, you
have  28 divided  by  2, 14  divided  by 2,  7 divided  by  2 (with  a
remainder), 7  divided by 3  (also with a  remainder), 7 divided  by 5
(still a remainder) and 7 divided  by 7 (and no remainder). Because of
all these  new pages, the  display is  cumbersome, so I  discarded the
idea.

In   _NWNS_   page  442,   K.   Menninger   describes  still   another
multiplication method, multiplication by factors. The example he gives
is  the multiplication  `23 ×  14`. In  this case,  the first  step is
multiplying  23 by  2, which  gives 46.  The second  step consists  in
multiplying 46 by 7, which gives  322, the final result. This requires
that  the multiplier  has small  prime factors  and this  requires the
human  computer  to compute  a  prime  factors extraction  before  the
multiplication. So I discarded this method too.

### Numeric bases 37 and beyond

I  adopted a  limit with  radix 36  because the  alphabet provides  26
letters that can be added to the  10 usual digits. We cannot go beyond
while keeping this system. Yet, there are two important numeric bases,
which are radix 60 (for the time  of day and for angles) and radix 256
(for IPv4 addresses, among others). I  had already written a big chunk
of  the module  when I  remembered there  are ways  to write  radix-60
numbers and radix-256 numbers while using the digits 0 to 9 and little
more: the  dotted notation  and the  "decimal-coded" notation  (not an
official    designation,   based    on   the    well-known   BCD    or
"binary-coded-decimal").

| domain  | radix 10   | dotted notation | decimal-coded |
|:--------|-----------:|:---------------:|--------------:|
| time    | 71120      |  19:45:20       | 194520        |
| time    | 68585      |  19:3:5         | 190305        |
| IPv4    | 2130706433 | 127.0.0.1       | 127000000001  |
| IPv4    | 3232235777 | 192.168.1.1     | 192168001001  |

As you  can see, the dotted  notation generally uses a  dot separator,
but it may  use another separator, such  as the colon for  the time of
day.  Also,  you  may  have  been susprised  by  the  "radix  10"  and
"decimal-coded" notations of the IPv4 address. The "radix 10" notation
is a perfectly valid one, even if  it is seldom used. While under your
web browser, you can open  the address `http://3232235777` and it will
work. Or  you can ping  address `2130706433`.  On the other  hand, the
"decimal-coded" notation is never used, but  it could be, if we find a
way to remove the confusion with the "radix 10" notation.

I have also discarded variants  of the numeric positional systems. For
example mixed-radix systems,  such as the `20-18`  mixed-radix used in
the long  count of the  Maya calendar, or the  factorial-radix system,
shown in
[xkcd](https://xkcd.com/2835/).
There  is also  the  `i-1` number  system, created  by  W. Penney  and
explained  by  D.E.  Knuth  in  chapter 4  of  _The  Art  of  Computer
Programming_ (pages 189  and 190), which uses only digits  `0` and `1`
and yet, covers  all the complex numbers with integer coordinates, not
only the  ray of positive numbers.  And there is the  balanced ternary
system, a system with radix 3, but instead of digits `0`, `1` and `2`,
this system  uses digits `0`,  `1` and "`1`-overbar", with  a negative
value. This system is presented by D.E. Knuth on pages 190 to 192.

A last remark.  Usually, when digits and upper-case  letters are mixed
in a system, we leave out letters  "O" and "I", because they look very
much like digits  "0" and "1". See for example  license plates in some
countries. In this module, I have kept them. Actually, when HTML files
are rendered by  my Internet browser, I have  more trouble identifying
digit "8" and letter "B" than dealing  with the "0" / "O" pair or with
the "1" / "I" pair.

### Extensions of the Arithmetic Operations

Arithmetic  operations easily  extend to  other mathematical  entities
such  as  vectors  and  matrices. If  additions  and  subtractions  of
matrices are  easily understood,  the multiplications of  matrices are
much more  interesting. Yet, they  do not  fit in the  current module.
Likewise, you can  easily add, subtract and  multiply polynomials, but
dividing  polynomials   (and  even  computing  a   GCD  with  Euclid's
algorithm) is interesting, but it does not fit in the module. So these
operations are left out.

Discarded implementations
-------------------------

### Layout of the `Arithmetic::PaperAndPencil::Action` class

Let us consider again the action used as an example above:

```
        c → 0 123456 7     0 123456 7

l → 0         6 2 8          6 2 8
             --------       --------
    1        | / / /|       |1/ / /|
    2        |/ / / |2      |/2/ / |2
    3        | / / /|    →  | / / /|
    4        |/ / / |3      |/ / / |3
    5        | / / /|       | / / /|
    6        |/