### ----------------------------------------------------
### -- Arithmetic::PaperAndPencil
### -- Licenses: Artistic-2.0
### -- Authors: Jean Forget
### -- File: doc/Description-en.md
### ----------------------------------------------------
### -- Chunk 4 of 4
 / / |4      |/ / / |4
             --------       --------
    7
```

The corresponding action contains:

* `level = 5`

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

At first, my intention was to create five different instances
of object `A::PP::Action`:

1. read digit 6 of the multiplicand (`level = 6`),

2. read digit 2 of the multiplier (`level = 6`),

3. say message "6 fois 2, 12" (`level = 6`),

4. write digit 1 of the partial product (`level = 6`),

5. write digit 2 of the partial product (`level = 5`),

Each object instance would contain  a single line coordinate, a single
column  coordinate and,  except  for the  spoken  message instance,  a
single  value. The  instances  would have  different  labels, such  as
`WRI00` (which actually exists) for  write-instances and a new `REA00`
for read-instances.

Eventually, I put everything into the  same object instance and I feel
it is  better. There  is still  a case where  there are  two instances
instead of one.  When I conclude a  computation with "Je pose  2 et je
retiens 1", there is a first  instance with the computation message "6
fois 2,  12" and  the reading  of digits, and  a second  instance with
message "Je pose..." and the writing of the new digits.

### Databases

Instead of using  RAM objects and classes, I considered  for some time
using SQL  tables. But this  would have added pointless  problems with
infrastructure and logistics.

### Output formats

I considered  other output formats,  in addition to HTML:  plain text,
L<sup>A</sup>T<sub>E</sub>X + Metapost, curses , Gimp, or even a video
format  (why  not).  I  may  code  the  L<sup>A</sup>T<sub>E</sub>X  +
Metapost output format, but the others are not in the to-do list.

### Zigzag addition

The standard addition involves right-aligned numbers, that is, number
aligned according to the unit digits. Example:

```
   2512
   1844
   1256
   ----
   5612
```

Yet, for the needs of multiplications, I had the intention of creating
a "zigzag" variant, without aligning the number. Examples:

```
    2512       2512          2512
   1844      1844           1884
    1256       1256        1256
   -----     ------        ------
   22208     188168        146952
```

The zigzag addition would have been a private method, outside of the
public API.

Actually, I found another way to deal with these additions, by storing
individual  digits in  an  array-of-lists variable,  each digit  being
stored without referring to its  parent number. The additional benefit
is that this  system is compatible with the diagonal  additions of the
`jalousie-A` and `jalousie-B` multiplication  variants, while the zigzag
addition is not.

### CSV modules and HTML modules

I know that parsing HTML with regexes  is a big no-no. Yet, the `html`
method in  the `Arithmetic::PaperAndPencil` module writes a pseudo-HTML string, and then
processes it  with regexes to  create a HTML  string. The key  here is
that  the  first generated  string  is  _pseudo_-HTML, with  no  fancy
features  such as  HTML attributes,  HTML comments  and the  like. The
pseudo-HTML is very simple and so it can be parsed with regexes.

Likewise, I have not found CSV-parsing modules,  so I had to do my own
parsing  with regexes.  On  the  other hand,  I  do  not need  advance
features of CSV  parsing, such as embedded  quoted strings, semi-colon
escaping and the like. So for this  part, as for HTML processing, I am
happy with just using simple regexes.

Various Topics
==============

Converting a Number to Radix _b_
--------------------------------

You know the first digits of π and  e in radix 10. What about radix 12
and radix 16? Module  `Arithmetic::PaperAndPencil` can help you answer
these questions, but with a few counter-intuitive steps to bypass some
obstacles.

Let  us use  the example  of π  in  radix 16.  The first  part of  the
discussion does  not apply  to radix  12, but only  to radix  16 (plus
radix 8 and radix 2). As many other programming languages, Raku allows
some kind of conversion with:

```
$out = sprintf("%x", $in);
```

There is a condition, `$in` must be an integer value, which is not the
case of π (or e). We bypass this condition by using a scaling factor:

```
sub conv16-pi(Int $scale) {
  sprintf("%x",  π × 16 ** $scale);
}
```

The user must still insert a  dot character into the string just after
digit "3" to represent the decimal  point. When dealing with radix 16,
this function is correct for any scale from 1 to 13. But with a higher
parameter value, all digits starting with  the 14th are zero, which is
wrong (the 13th digit is zero, also, but in its case this is correct).
This  problem is  caused by  the fact  that in  Raku, constant  `π` is
specified with 15 decimal digits  after the fractional point, which is
the equivalent of 13 hexadecimal digits after the fractional point.

Remark: as you most certainly know, you have the following approximate
equation: "2^10 ≈ 10^3". With this, you can easily find "16^5 ≈ 10^6".
So  a  fractional part  with  12  decimal  digits  will convert  to  a
fractional part  with 10 correct  hexadecimal digits and  a fractional
part with 18 decimal digits will  convert to a fractional part with 15
correct hexadecimal digits.

This solution,  without `Arithmetic::PaperAndPencil`, is  wrong beyond
the 13th  fractional digit. In  addition, it  is limited to  radix 16,
radix 8 and radix  2 and it cannot be used  with other numerical bases
such as 12.

Module  `Arithmetic::PaperAndPencil` allows  us to  move beyond  these
limitations. We need two scaling factors and three variables:

* `$factor16` equal to 16^_n1_,
* `$factor10` equal to 10^_n2_,
* `$pi-x10` equal to π × $factor10,
* `$pi-x16` equal to π × $factor16,
* `$pi-x10-x16` equal to π × $factor10 × $factor16.

The function you will use is:

```
sub conv-pi(Int $scale) {
  # https://en.wikipedia.org/wiki/Pi#Approximate_value_and_digits
  # https://oeis.org/A000796
  my Str $pi-alpha = '314159265358979323846264338327950288419716939937510';

  my Int $scale10 = ($scale × 6 / 5).ceiling;
  my Arithmetic::PaperAndPencil::Number $factor16 .= new(:radix(16), :value('1' ~ '0' x $scale));
  my Arithmetic::PaperAndPencil::Number $factor10 .= new(:radix(10), :value('1' ~ '0' x $scale10));
  $factor16 = $operation.conversion(number => $factor16, radix => 10);
  $factor10 = $operation.conversion(number => $factor10, radix => 16);

  my Arithmetic::PaperAndPencil::Number $pi-x10 .= new(:radix(10), :value($pi-alpha.substr(0, 1 + $scale10)));
  my Arithmetic::PaperAndPencil::Number $pi-x10-x16 = $operation.multiplication(multiplicand => $pi-x10, multiplier => $factor16);
  $pi-x10-x16 = $operation.conversion(number => $pi-x10-x16, radix => 16);
  my Arithmetic::PaperAndPencil::Number $pi-x16 = $operation.division(dividend => $pi-x10-x16, divisor => $factor10);
  return $pi-x16.value;
}
```

You can  easily adapt this function  to another radix such  as 12. You
still  have  to pay  attention  to  fraction  "6/5" which  allows  the
function to compute the radix-10 scaling factor.

Yet, even if Raku cannot do infinite precision with `Num`'s, it can do
this with integers. The core  `Int`'s are actually `Bigint`'s in every
aspect but  the name.  The conversion  function can  be a  bit simpler
with:

```
sub conv-pi(Int $scale) {
  # https://en.wikipedia.org/wiki/Pi#Approximate_value_and_digits
  # https://oeis.org/A000796
  my Str $pi-alpha = '314159265358979323846264338327950288419716939937510';

  my Int $scale10 = ($scale × 6 / 5).ceiling;
  my Arithmetic::PaperAndPencil::Number $factor16 .= new(:radix(10), :value((16 ** $scale).Str));
  my Arithmetic::PaperAndPencil::Number $factor10 .= new(:radix(10), :value('1' ~ '0' x $scale10));
  $factor10   = $operation.conversion(number => $factor10  , radix => 16);

  my Arithmetic::PaperAndPencil::Number $pi-x10   .= new(:radix(10), :value($pi-alpha.substr(0, 1 + $scale10)));
  my Arithmetic::PaperAndPencil::Number $pi-x10-x16 = $operation.multiplication(multiplicand => $pi-x10, multiplier => $factor16);
  $pi-x10-x16 = $operation.conversion(number => $pi-x10-x16, radix => 16);
  my Arithmetic::PaperAndPencil::Number $pi-x16 = $operation.division(dividend => $pi-x10-x16, divisor => $factor10);
  return $pi-x16.value;
}
```

and we spare a few CPU cycles.

This  programme  is  available  in the  `examples`  directory  of  the
distribution.

In the case of  the golden ratio φ, conversions from  radix 10 are not
necessary. You can just  apply the formula "(1 + √5)  / 2" and compute
its value  directly in the  destination radix. Remember that  you must
use the proper scaling factors.

```
sub phi(Int $radix, Int $scale) {
  my $zero = '0' x $scale;
  my Arithmetic::PaperAndPencil $op .= new;
  my Arithmetic::PaperAndPencil::Number $five .= new(:radix($radix), :value('5' ~ $zero ~ $zero));
  my Arithmetic::PaperAndPencil::Number $one  .= new(:radix($radix), :value('1' ~ $zero));
  my Arithmetic::PaperAndPencil::Number $two  .= new(:radix($radix), :value<2>);
  my Arithmetic::PaperAndPencil::Number $x = $op.square-root($five);
  $x = $op.addition($one, $x);
  $x = $op.division(dividend => $x, divisor => $two);
  return $x.value;
}
```

Beware, this function  is correct for radix 6 or  more. Finding why it
is wrong for  a lower radix is  left as an exercise to  the reader. Or
you can cheat and read the `examples` directory.

Of  course, there  are also  formulas  to compute  π or  e, but  these
formulas are infinite series, with  a convergence speed which can vary
between reasonably fast and agonizingly slow. For example,

```
atan(x) = x - x^3/3 + x^5/5 - x^7/7 + ...
π = 4 × atan(1)
π = 16 × atan(1/5) - 4 × atan(1/237)
```

Since each multiplication and each division is an iterative processus,
including  these  inside an  outer  loop  for computing  atan(x)  with
`Arithmetic::PaperAndPencil` is a  bad idea. Try another  method to do
computations with extended precision.

Square Root and Newton's Method
-------------------------------

To compute a  square root, I use the "gallows"  method, which has many
common points with the "gallows"  method for the division. Some people
might say "Why  use this time-consuming method,  while Newton's method
converges  fast? See  the programme  below, which  computes √2  with 8
fractional digits in just 4 iterations (plus a 5th iteration to ensure
the first  fractional digits do not  vary; actually, we find  that the
value has 11 correct fractional digits)."

```
sub test-num {
  my Num $x  = 2.Num;
  my Num $r1;
  my Num $ε  = 1e-8;
  my Num $r2 = 1.Num;
  my Int $n;
  my Int $n-max = 1000;

  for 1 .. $n-max -> $n {
    $r1 = $r2;
    $r2 = ½ × ($r1 + $x / $r1);
    say $n, ' ', $r2.Num;
    if ($r1 - $r2).abs < $ε {
      last;
    }
  }
}
```

Newton's method  is very fast  indeed, provided you use  an electronic
device to  compute the  divisions. Maybe you  should do  the following
test.  Switch  off  all  electronic devices  in  the  room:  computer,
smartphone, smartwatch, Amazon Alexa and  so on, including the vintage
pocket calculator that  your grandfather bought in the  1970's. Grab a
pencil and  a paper sheet, possibly  an eraser, and compute  √2 with 8
fractional digits, using  Newton's method. I did  this experiment, see
below (the horizontal lines are a  scanning glitch because of folds in
the paper sheet).

![Computing √2 with Newton's method](test-Newton.webp)

Transcription

```
16h21   ½( 1    +  2/1)  =   3/2             17      17
        ½( 3/2  +  4/3)  =  17/12          × 17    × 12
        ½(17/12 + 24/17) = 577/408         ----    ----
                                            119      34
                                            17      17
                                           ----    ----
                                            289     204
                                          + 288     408
                                           ----
                                            577
16h23

  577,00000000|408
  169 0       |---
  058 0       |1,41421568
   17 20
    0 880
      0640
       2320
        2800
         3520
          254
16h26
 ----------
 2,0000000000000000|1,41421568
 0 585784320       |----------
   0200980480      |1,41421144
    0595589120     |1,41421568
     0299028480    |       ---
      0161854440   |       712
       0204328720  |1,41421356
        0629071520
         0633852480
          068166208
16h35
```

A few  explanations. Do not  bother about the vertical  lines starting
from a  zero and  ending at another  zero. I drew  them to  ensure the
digits are properly aligned.

The experiment  is more or  less biased  in favor of  Newton's method.
First, the value of √2 is well known,  so I knew where I was going to.
Then, instead of doing all computations in all iterations with 9-digit
numbers  (that is,  1  digit for  the integer  part  and 8  fractional
digits), I computed the first  three values as fractions.  Only during
the third  iteration did I convert  the fraction into a  number with 8
fractional digits. So  I had to compute only one  11-by-3 division and
one  17-by-9  division (plus  two  2-by-2  multiplications) on  paper,
instead of three 17-by-9 divisions.  Then since the numbers 1,41421144
and 1,41421568  share many digits,  I added  the last three  digits of
each and I divided the result by 2, instead of adding the full numbers
and  dividing  the  full  result  by 2.  During  the  computations  on
fractions, I  did most computations  in my mind without  writing them,
such as multiplication 12 × 24.  I only wrote the multiplications 17 ×
17 and 12 × 17, the addition 289 + 288 and the doubling of 204 to 408.

Even with  all these biases  favouring Newton's  method, it tool  me a
quarter of an  hour to compute the  square root, 9 minutes  of which I
spent computing a 17-by-9 division.

Then I switched  on my computer and I wrote  a programme with Newton's
method  and `Arithmetic::PaperAndPencil`.  Of course,  to get  similar
results, I  had to compute the  square root of 2×10^16,  using a first
value equal to 10^8. The previous chapter will explain why. There is a
difference between  my script and  my paper experiment, because  I did
not compute  fractions (3/2, 17/12,  577/288), but 9-digits  values as
soon as the first iteration: 1.50000000, 1.41666666, etc. Also, I used
division type `"cheating"`. This can be  explained by the fact that in
my paper  experiment, when  computing the  initial candidate  digit, I
used a 2-digit partial divisor while  the module always uses a 1-digit
partial  divisor.  For example,  when  computing  58578432 divided  by
141xxx, I  would not  say "En 5  combien de  fois 1, il  y va  5 fois"
(approximate translation "How many 1 in 5, I get 5 times") but "En 58,
combien de  fois 14,  il y va  4 fois" ("How  many 14  in 58, I  get 4
times").  When I  was  10 years  old,  I  did not  know  by heart  the
multiples of 14, now I know them partially.

The  programme  is  available  in  the  `examples`  directory  of  the
distribution.

I did some simple statistics on the CSV file. So I found that Newton's
method  required  90  1-by-1  (or 2-by-1)  divisions  and  371  1-by-1
multiplications.  There were  also 31  `"DIV03"` actions  ("Je triche,
j'essaie  directement _n_"  or "I  cheat, I  directly use  _n_"). When
looking only  at the  last division,  200...00 by  141..68, I  found 9
1-by-1 divisions, 81 1-by-1 multiplications and 8 `"DIV03"` actions.

I also  executed a counter-experiment,  computing √2 with  the gallows
method, first  without any electronic  device, second with  my module.
Here is the papersheet.

![Computing √2 with the gallows method](test-gallows.webp)

and  its electronic  equivalent (I  omit most  horizontal lines,  they
waste space for no good reason).

<pre>
09h38
20000000000000000|1,41421356    09h46
100              |----------
 0400            |24
  11900          | 4
   060400        |281
    0383600      |  1
     10075900    |2824
        <strike>62204</strike>    |   4
      159063100  |28282
       1764177500|    2
        067121264|282841
                 |     1
                 |2828423
                 |      3
                 |28284265
                 |       5
                 |282842706
                 |        6
</pre>

As you  may notice, when  computing the sixth fractional  digit, there
was a mistake. The digit was  computed with 1007590 divided by 282842,
so the first candidate digit would have been computed with 100 divided
by 28.  I wrongly  used 4, while  I should have  known better.  Then I
successfuly used  3. This explains  the "4" overwritten with  "3" (not
appearing in the transcription)  and the crossed-out partial remainder
62204 (which appears in the transcription).

Computing the square root with the gallows method took as much time as
the  17-by-9 division  when  using Newton's  method  (remember that  I
recorded the  times with  a 1-minute  scale). If  we extract  the same
statistics on the  CSV file as above, we find  that the gallows method
required   8  1-by-1   divisions  (`"DIV01"`   actions),  107   1-by-1
multiplications (`"MUL01"`  actions) and 10 `"DIV02"`  actions ("C'est
trop fort,  j'essaie _n_"  or "This  is too much,  I try  _n_"). These
values are  a bit higher  than for the  17-by-9 division which,  may I
remind you, used the type `"cheating"`.

If Newton's method  in electronic version is a  method which converges
very  fast, its  paper-and-pencil  version is  still  slower than  the
paper-and-pencil version of  the gallows method. And  with respect to
the electronic version, even if it  converges fast, it is still slower
than the direct method, a simple `$y = $x.sqrt;` instruction.

Bibliography
============

_Zahlwort  und   Ziffer:  Eine  Kulturgeschichte  der   Zahlen_,  Karl
Menninger, published  by Vanderhoeck & Ruprecht  Publishing Company, I
do not know the ISBN.

_Number Words and Number Symbols, A Cultural History of Numbers_, Karl
Menninger, published by Dover, ISBN 0-486-27096-3, english translation
of the previous entry.

_Histoire d'Algorithmes,  du caillou à  la puce_, Jean-Luc  Chabert et
al, published by Belin, ISBN 2-7011-1346-6

See also a programme for HP48 and similar:
[div\_pro](https://www.hpcalc.org/details/5303).

License
=======

Text  published  under the  CC-BY-ND  license:  Creative Commons  with
attribution and with no modification.


