### ----------------------------------------------------
### -- Arithmetic::PaperAndPencil
### -- Licenses: Artistic-2.0
### -- Authors: Jean Forget
### -- File: doc/Description-en.md
### ----------------------------------------------------
### -- Chunk 1 of 4
-*- encoding: utf-8; indent-tabs-mode: nil -*-

Introduction
============

The  purpose  of  the  module is  simulating  the  basic  arithmetical
operations as  executed by a human  equipped with nothing more  than a
few sheets of paper and a pencil.

History
=======

During  the 1960's  (extending into  the 1970's),  I learned  the four
basic operations, addition, subtraction, multiplication and division.

![Example page from my exercise book](calcul-1970-12-02.png)

In 1976, I learned square root computation, with a method very similar
to the standard "gallows" method for the division.

```
200000000|14142
100      |-----
 0400    |24
  11900  | 4
   060400|---
    03936|281
         |  1
         |----
         |2824
         |   4
         |-----
         |28282
         |    2
         |
```

In 1979, my  father was given a copy of  an arithmetics exercise book,
used in 1822. This exercise  book contained divisions much unlike what
my father  and I knew.  I did some reverse  engineering and I  think I
found  the method  that  was  used. Yet,  this  is  nothing more  than
guesswork.

![Example page from the exercise book](calcul-1822.jpeg)

The first two divisions is the page above are 2469600 divided by 25882
gives 954, remainder  13170 and 34048000 divided by  25882 gives 1315,
remainder 13170. These divisions are part  of the rules of three (7000
×  3528) /  25882 and  (7000 ×  4864)  / 25882.  By the  way, you  may
recognise the corresponding  multiplications in the page,  next to the
divisions. The  divisions are reproduced  below, but without  the fact
that the remainders 4572 and 13170 are underlined with an slant line.

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

If the  stricken digits  are unreadable, here  are the  same divisions
without striking the digits.

```
   04                 13
  1085               1421
 140217             040157
24696202           08166480
24696000{0954      34048000{1315
--------           --------
25882222           25882222
 258888             258888
  2588               2588
   25                 25
```

In 1982, for  a science history project, I borrowed  _Number Words and
Number Symbols, A Cultural History of Numbers_, from Karl Menninger, I
read it and I gave it back to the library.

In 1996, I bought and I  read _Histoire d'Algorithmes, du caillou à la
puce_.

In 2000  or 2001, I  wrote a Perl programme  to compute a  square root
with the  "gallows" method. There  are no back-ups of  this programme,
which is a good thing.

In 2005, during the
[French Perl Workshop in Marseille](https://journeesperl.fr/fpw2005/)
I gave a lightning talk about
[square root computation](https://journeesperl.fr/fpw2005/talk/201).
The  demo used  a marker  (instead of  a pencil)  and a  rhodoid sheet
(instead  of paper),  but no  computer  and no  programme. The  future
programme was  announced for "some  time in  the future". Here  is the
rhodoid sheet from this lightning talk.

![square root computation](racine-carree.jpeg)

```
6554900|256,0
255    |-----
 3049  |45
  01300| 5
       |--
       |506
       |  6
       |---
       |5120
       |   0
```

In  2009, I  bought a  copy  of _Number  Words and  Number Symbols,  A
Cultural  History of  Numbers_  and I  could read  it  and consult  it
without bothering about library late fees.

In 2023,  I began  working on  the programme I  had promised  in 2005,
although this will not be a Perl programme, but a Raku module.

Purpose
=======

A computation is a two-tier process. Let us consider a multiplication.
The first  tier is mental computation,  in which the child  is able to
multiply two single-digit numbers and get a 1- or 2-digit number.  And
the  second tier  is paper-and-pencil  computing, in  which the  child
writes  in  an  organised  way  the  partial  results  of  the  mental
computations, to execute  a full multiplication of  a _n_-digit number
by a _n'_-digit number.

The module  has two main classes.  The first one is  the number class,
which simulates mental computation and  in which operations  have very
strict limits.  For example,  multiplication in  allowed only  if both
factors are single-digits numbers.

The  second  main  class  simulates  a   sheet  of  paper  (or  a  few
sheets). The  main attribute of  this class is  a list of  actions, to
simulate the child reading some already written digits, doing a mental
computation, and  writing the result on  the sheet , while  saying the
proper formulas such as:

```
  6 fois 8, 48
  je pose 8 et je retiens 4
```

(sorry, I only know the french version).

The  class  includes several  methods  for  the  various  arithmetical
operations, addition, subtraction, multiplication, division and square
root.  These  methods feed  the "list  of actions"  attribute. Another
method reads this list of actions  and renders them as HTML. Depending
on the method  parameters, the HTML text can contain  only the written
part of the operation, or it can include in addition the formulas said
by the simulated human.

Future versions of the module may include other rendering formats such
as plain text  or L<sup>A</sup>T<sub>E</sub>X + Metapost.  But this is
deep in the to-do stack.

What the module will not do
---------------------------

When I was 10, I knew a few things that will not appear in the module.
For example, I learned (and I  still know) how to compute with numbers
with   a   fractional  part.   The   module   will  deal   only   with
integers. Dealing  with the decimal  point would need  many additional
programme lines for  a limited benefit.  So, my 2005  demo will not be
possible with the module.  Either  the computation stops after dealing
with the units  digits, or the module user bypasses  the limitation by
asking  the square  root  of  6554900 and  by  manually inserting  the
decimal point.  Likewise, if you want  to compute π with  6 fractional
digits using the  well-known fraction 355/113, you  will have actually
to compute 355_000_000 / 113 and insert a decimal point just after the
leftmost digit.

Another  point. When  dividing  two numbers,  finding each  successive
digits for the  quotient is a trial-and-error process.  Let us suppose
we want to divide 654000 by 1852. For the mental division, we focus on
the first digit of  both dividend and divisor, in this  case, 6 and 1.
So the first candidate digit of the quotient is 6. Then I would try to
compute the partial remainder and I would find that 6 is too big. So I
would try a second time with 5 and  it would still be too big. Then 4,
then 3, which would eventually  succeed. This was basic training, when
I was maybe 8.  Then, when I turned 10, I learned that  I should get a
look at the second digit of the divisor.  If this digit is a 9 or even
a 8, you  can compute the first candidate by  dividing the first digit
of the  dividend by the  first digit of the  divisor _plus 1_,  In the
case of 65400 and 1852, you would divide 6 by 2 and obtain directly 3.
My module does not do this. Yet,  there is a "cheat" mode in which the
module hides the attempts  with 6, 5 and 4 and  shows only the attempt
with 3. This gives the following:

```
  En 6, combien de fois 1, il y va 6 fois.
  Mais je triche et j'essaie directement 3. (tr: but I cheat and I immediately try 3)
```

Actually, it  is nearly the same,  except that my module  executes all
the computations, even  if they are discarded.  Another difference, as
shown with the  division of 74500 by 1852 is  that the first candidate
is 7/2 = 3, which is too small,  the first digit of the quotient is 4.
The module tries  7, 6, 5 and  then 4, without considering  3 which is
too   low.  Thus,   the  module   only  checks   "too-bigness",  never
"too-smallness".

Do  we require  a  plus sign  (or  several)  on the  left  side of  an
addition? A minus sign on the left side of a subtraction? A times sign
on the left  side of a multiplication?  This is what I  learned at the
very beginning  of my arithmetic  lessons, but soon it  was discarded.
From  time  to time,  I  would  write a  times  sign,  but usually  my
multiplications would have  no signs. The module will  not print these
signs.   An   exception:    the   radix-to-radix   conversions   stack
multiplications  on  top   of  additions  and  additions   on  top  of
multiplications. To  improve readability,  the module will  print plus
and times signs when appropriate.

The  module uses  only indo-arabo-latin  numerals (0,  1, 2,  3, etc).
There is no plan to use indo-arab numerals (٠ for 0, ١ for 1, ٢ for 2,
٣  for 3,  ٤ for  4, etc)  nor chinese  numerals nor  other positional
number systems.  Even more,  the additional systems  (egyptian, roman)
are not dealt with.

A sufficiently experienced human (my younger  self at 10 year old, for
example,   but  not   8  year   old)  understands   that  under   some
circumstances, some shortcuts are possible,  such as when a multiplier
or a  multiplicand has many  zeroes. My  module will not  detect these
conditions.   It will  apply the  rules  in a  dumb way,  even if  the
dumbness mutates into silliness.

My module can be considered as  an alternative solution for a `bigint`
module. This  is true as long  as we do not  consider performances. An
actual  `bigint`  module  give  efficient  computation  with  extended
precision.  My  module aims  at  extended  precision computation  with
traceable steps.

Not  only the  module lacks  efficiency, but  it also  lacks ergonomy.
suppose we  want to compute  `√(b² - 4ac)`. We  would need to  write a
programme in this fashion:

```
my Arithmetic::PaperAndPencil::Number $a;
my Arithmetic::PaperAndPencil::Number $b;
my Arithmetic::PaperAndPencil::Number $c;
# initialisation of a, b and c, to be completed
...
# end of initialisation, beginning of computation
my Arithmetic::PaperAndPencil::Number $four .= new(value => '4');
my Arithmetic::PaperAndPencil::Number $result;

my Arithmetic::PaperAndPencil $sheet .= new;
$result = $sheet.squareroot($sheet.subtraction($sheet.multiplication($b, $b), $sheet.multiplication($four, $sheet.multiplication($a, $c))))
```

And  the example  above is  much  simplified. The  parameters for  the
methods are shown  as positional parameters, yet  the methods actually
require keyword parameters.

A last  point in which my  module agrees with my  training is carries.
When I  was taught arithmetics, I  learned to keep carries  in my mind
and not write them. My module will  do the same, it will not print the
carries.

What the module will do
-----------------------

When I was 10 years old, I did not know how to compute square roots, I
did not know the  1822 (or "boat") variant of the  division, I did not
know the  others variants of  multiplication and division.  The module
will provide all these.

Most human  beings can  compute in  radix 10  only. Some  have limited
skill  to  compute  in  octal   or  hexadecimal.  My  module  will  do
computations in any  radix from 2 to 36. Thus,  the mental computation
class will be able to compute Z × Z  = Y1 in radix 36 (in radix 10: 35
× 35 = 1225 = 36 × 34 + 1).

When I learned  number bases, I learned to convert  numbers from radix
10 to radix  _b_ with cascading divisions and to  convert numbers from
radix _b_ to  radix 10 by computing a polynomial  with Horner's scheme
(I did not know Horner's scheme, I even did not know what a polynomial
was, but nevertheless, I knew how to do this kind of computation). But
I did  not learn how  to convert a number  directly from radix  _b_ to
radix _b'_. Later,  I discovered the special cases  of converting from
radix 2 to radix  4, 8 or 16 or the inverse  conversions, which are in
fact very  simple. But I still  cannot convert a number  directly from
radix _b_ to radix  _b'_ in the general case. The  module will be able
to do such a conversion for any couple of bases from 2 to 36.

The numbers  processed by the  module have  no limits. Or  rather, the
limits come from the Raku interpreter  and from the host computer. So,
you can reproduce
[Frank Nelson Cole](https://en.wikipedia.org/wiki/Frank_Nelson_Cole)'s
multiplication, when he showed in 1903 the prime factors for the
[67th Mersenne number.](https://en.m.wikipedia.org/wiki/Mersenne_prime).
When  I  was  10  years  old, I  theoretically  could  compute  Cole's
multiplication, but actually I would have  made errors or I would have
given up before it was complete.

When  I   learned  multiplications   and  divisions,  I   learned  the
French-speaking formulas  which support these operations,  e.g. "En 6,
combien de fois  1, il y va 6  fois." I do not know  the equivalent in
foreign   languages.  Yet,   the  module   includes  a   multi-lingual
mechanism. So,  if I get  help from a  native English speaker,  from a
native German speaker, and so on, the module will be able to write the
formulas in English, or in German, or in some other language.

Some confusing matter
---------------------

The numbers manipulated by the module belong to two different species.
The first species contains the  numbers targetted by the computations:
multiplicands, multipliers,  partial products, and  so on, as  well as
pieces of these numbers: unit  digits, carries, etc. These numbers are
instances of the `Arithmetic::PaperAndPencil::Number` class. And there
are auxiliary numbers: counting the elements  in an array or the chars
in a  string, or  the numeric radices,  line numbers,  column numbers,
which are used to help construct  the full operations. The numbers are
plain Raku `Int` values and they  are immune from the limits of mental
computations, such as preventing the  multiplication of two numbers if
one of them is a multi-digit number.

Operations
==========

Addition
--------

No variants, no special cases. Nothing to say.

Subtraction
-----------

The subtraction is  a "reverse" addition, so there is  no variants, no
special cases  and nothing to say?  On the contrary. We  must consider
separately the  stand-alone subtraction  and the  embedded subtraction
(computing the partial remainder in  a division). Also, while there is
no  variants for  the  addition,  there is  one  for subtraction,  the
variant using the  _b_-complement, as we learn when  we study assembly
programming (2-complement or 16-complement).

### Stand-alone subtraction

A subtraction  needs a single  phase. Yet, if the  substracted numbers
are very different,  we can distinguish up to three  subphases. Let us
consider this subtraction.

```
123450000012345
-       8867700
---------------
```

The first subphase is processing each  digit from the low number. This
is what we think about when talking about a subtraction.


```
123450000012345
-       8867700
---------------
        1144645
```

There is no more digits in the low number, but there is still a carry.
The second subphase is the processing of this carry.

```
123450000012345
-       8867700
---------------
    49991144645
```

Now, there  is neither a  carry nor a digit  from the low  number. The
third  subphase is  just copying  the remaining  digits from  the high
number to the result.

```
123450000012345
-       8867700
---------------
123449991144645
```

In  some cases,  the second  subphase and  the third  subphase can  be
missing. This is the case with  subtractions embedded in a division or
a square  root extraction to  compute a partial remainder.  The second
subphase will involve  at most one digit from the  high number and the
third subphase will be totally absent.

### Embedded subtraction

Let us use the following division as an example.

```
---
9212|139
    |---
    |6
```

When  the pupil  computes  the intermediate  remainder,  he starts  by
computing  "6  time  9  is  54", then  he  compares  this  value  with
single-digit 1. The  pupil then says "from 61, it  remains 7" (or some
sentence with the same meaning, I am not a native English speaker) and
then "write 7, carry 6".

What happens? The input data to the subtraction are:

* a high number, with a single digit (1 in this example), or maybe you
would interpret it as a partially known number, "?1",

* a low number, with one or two digits (54 in this example).

The output data are:

* the  _adjusted_ high  number, with  usually two  digits (61  in this
example),

* the subtraction result, a single-digit number (7 in this example).

This process is  a mental process, without writing. So  it is coded in
the  `Arithmetic::PaperAndPencil::Number` class.  It  is  used in  the
division, but also in the  stand-alone subtraction (where we know that
the carry can never be more than `1`).

A side remark. When  I learned in my early years, I  was taught to say
(very roughly translated) "6 times 9,  54, plus 7, 61", while in other
schools other children would say "6 times 9, 54, from 61, remain 7". I
did not  understand why this  addition-like sentence in my  school was
better than the  subtraction-like sentence in other  schools and after
all these years  I still do not  understand. Yet my brain  is wired in
this way, so  this is the way the spoken  sentences are implemented in
French. In other languages, I will trust whoever helps me.

### _b_ complement subtraction

This  variant  is  used  for  the fractional  part  (or  mantissa)  of
logarithms and for subtraction in radix 2 and radix 16. Yet, it can be
used with integers in any radix and  I will give an example in decimal
with the 10-complement. Let us use the same example as above.

```
123450000012345
-       8867700
---------------
```

To compute the difference, we  must first compute the 10-complement of
the low  number (10-complement because  of radix 10).  Actually, there
are several  possible 10-complements for  the same number,  because we
did not specify the required length. If you compute logarithms using a
5-digit log  table, or if  you write  assembly programmes on  a 16-bit
computer, the  length of the  10-complement or of the  2-complement is
implied, so the question is not necessary. Here, since the high number
has 15 digits, we need the 15-long 10-complement of 8866700. There are
two ways to compute this number.

First way: we adjust the length of  the low number by adding zeroes to
the left, to reach the required length (15 in this example).

```
        8867700
000000008867700
```

We  scan the  digits right-to-left.  While these  digits are  zero, we
leave them unchanged.

```
000000008867700
             00
```

The  next  digit,  and  only  this next  digit,  is  replaced  by  its
10-complement. In the example, 7 turns to 3.

```
000000008867700
            300
```

Lastly,  all  other  digits  are replaced  with  their  9-complements,
including the  zeroes that  would still  be there.  In the  example, 7
turns to 2, 6 turns to 3, 8 turns to 1 and 0 turns to 9.

```
000000008867700
999999991132300
```

Second way to  compute the 10-complement: we adjust the  length of the
low number by adding zeroes to the left, to reach the required length.

```
        8867700
000000008867700
```

We replace all digits by their 9-complements.

```
000000008867700
999999991132299
```

We add 1.

```
000000008867700
999999991132299
              1
---------------
999999991132300
```

Once we  have the  10-complement of  the low  number, with  either the
first or second method, we add it to the high number.

```
 123450000012345
 999999991132300
----------------
1123449991144645
```

There is  always a new digit  (a sixteenth digit in  this example) and
this additional digit is always 1. We discard this digit and we obtain
the result of the subtraction, 1123449991144645.

Of  course,  when   using  binary  we  talk   about  1-complement  and
2-complement.  In hexadecimal,  we  may talk  about 15-complement  (or
F-complement) and  16-complement. But since radix  16 is, in a  way, a
"higher-level   view"  of   radix   2,  many   people  still   mention
1-complements and 2-complements.

Multiplication
--------------

### Standard

The standard multiplication is well-known:

```
   628
   234
  ----
  2512
 1884.
1256..
------
146952
```

Is  there  something  to  add?  Yes. This  standard  variant  has  two
sub-variants. The first variant is the "with short-cuts" variant.  Let
us consider the multiplication of  628 by 333. The vanilla sub-variant
executes the same computation three times:

```
3 fois 8, 24, je pose 4 et je retiens 2
3 fois 2, 6, et 2, 8, je pose 8 et je ne retiens rien
3 fois 6, 18, je pose 18

   628
   333
  ----
  1884

3 fois 8, 24, je pose 4 et je retiens 2
3 fois 2, 6, et 2, 8, je pose 8 et je ne retiens rien
3 fois 6, 18, je pose 18

   628
   333
  ----
  1884
 1884.

3 fois 8, 24, je pose 4 et je retiens 2
3 fois 2, 6, et 2, 8, je pose 8 et je ne retiens rien
3 fois 6, 18, je pose 18

   628
   333
  ----
  1884
 1884.
1884..
```

The "with shortcuts"  variant executes the computation  only once. The
second and third partial products are just copies of the first one:

```
3 fois 8, 24, je pose 4 et je retiens 2
3 fois 2, 6, et 2, 8, je pose 8 et je ne retiens rien
3 fois 6, 18, je pose 18

   628
   333
  ----
  1884

Je recopie la ligne 1884 (= "copying line 1884")

   628
   333
  ----
  1884
 1884.

Je recopie la ligne 1884 (= "copying line 1884")

   628
   333
  ----
  1884
 1884.
1884..
```

The other sub-variant is an hypothetical one. Or rather, I never heard
about  it. It  is an  extension  to multiplication  of the  "prepared"
sub-variant of  the division.  On a  first sheet  of paper,  the pupil
lists the multiples  of the multiplicand.  For  the prepared division,
the list goes up to "9 × 628", but for the prepared multiplication, we
can stop at "4 × 628", because the multiplier has no digit higher than
4. Then, the second sheet of paper has no mental multiplications, only
copies of existing lines:

```
1 times 628,  628
2 times 628, 1256
3 times 628, 1884
4 times 628, 2512
Next Page

   628
   234
  ----

Copying line 2512

   628
   234
  ----
  2512

Copying line 1884

   628
   234
  ----
  2512
 1884.

Copying line 1256

   628
   234
  ----
  2512
 1884.
1256..
```

Actually, the _prepared_ variant is less efficient than the _shortcut_
variant.  If the  multiplier is,  for example,  `747`, the  _shortcut_
variant  will  only  compute `4  ×  328`  and  `7  × 628`,  while  the
_prepared_ variant  will compute all  partial products from `2  × 628`
until `7 × 628`.

The last phase, adding the partial  products, is not shown, because it
is the same for the three sub-variants.

### "Jalousie" variant

Let us go back to multiplying 628 by 234, which gives 146 952.  In the
picture  below,  the  multiplicand  is   on  a  blue  background,  the
multiplier is on a green background and the final product is on a pink
background. These  colours play no  role in the  multiplication, their
purpose is only to streamline the explanations in this chapter.

Long before reading _Histoire d'algorithmes_ (_HAL_) and _Number Words
and Number Symbols_ (_NWNS_), I  had heard about a rectangular variant
for multiplications. It was shaped like the A1 example below.

![Various examples for the jalousie multiplication](rect-mult.png)

In  _NWNS_ page  442, the  author gives  an example  of multiplication
using indo-arabo-latin digits  (0, 1, 2, etc) following  format A2 and
the same example with  indo-arab digits (٠ for 0, ١ for 1,  ٢ for 2, ٣
for  3, etc)  following format  B3, obviously  attempting to  cram the
whole product on the bottom line.  The name of this variant comes from
Italian, _multiplicare per gelosia_, which Menninger translates as "in
the manner of a jalousie" (venitian store).

In _HAL_,  the examples  begin on  page 26,  with a  multiplication in
which  the multiplier  has only  one digit.  This multiplication  uses
pattern A1. It comes from
[_Līlāvatī_](https://sanskritlibrary.org/catalogsText/titus/class/bhasklil.html)
from  Ganesa.  _HAL_  gives  several French-speaking  names  for  this
technique:  _par  tableau_,  _par  grillage_, _par  filets_  and  _par
jalousie_ (in an array,  in the manner of a mesh  fence, in the manner
of a  fishing net and in  the manner of a jalousie). I kept  this last
one,  which exists  also  in English  and is  the  translation of  the
Italian name.

Then, in  page 28  of _HAL_,  you find  a multiplication  from
[_Miftāh al-hisāb_](https://www.britannica.com/topic/Miftah-al-hisab)
written by Al-Kāshī'. In this multiplication, the rectangle sides form
an angle of 45 degrees with the
horizontal  or with  the vertical.  Moreover, the  number are  written
right-to-left in radix 60 (seconds, then minutes, then degrees, if you
read left-to-right)  and. On page  30, you find a  multiplication with
chinese  digits  and  following  pattern  A2. It  comes  from  a  1450
manuscript, _Jiunzhang suanfa  bilei daquan_. On page 32,  there are a
A2 multiplication and  a B1