From 66d54be6a4d62a1c43a34a44b521cb8499425326 Mon Sep 17 00:00:00 2001 From: Lucian Mogosanu Date: Mon, 26 Feb 2018 20:35:10 +0200 Subject: [PATCH] posts, 06c: Small but necessary clarifications --- posts/y04/06c-ffa-egypt-proof.markdown | 21 +++++++++++---------- 1 file changed, 11 insertions(+), 10 deletions(-) diff --git a/posts/y04/06c-ffa-egypt-proof.markdown b/posts/y04/06c-ffa-egypt-proof.markdown index ae7e31a..1ab4ab7 100644 --- a/posts/y04/06c-ffa-egypt-proof.markdown +++ b/posts/y04/06c-ffa-egypt-proof.markdown @@ -290,8 +290,8 @@ K(1) * B^0 + K(2) * B^1 + K(3) * B^2 + ... where `0 <= K(I) < B`, i.e. `K(I)` is a "modulo-B digit". Our particular `K(I)` is `Ybit(I)` and it denotes the elements of the bit-vector -`Y`. From this follows that the sum-of-products factor in the definition -of `XY(N)` is in fact `Y`, and thus `XY(N)` becomes: +`Y`. From this follows that the sum-of-products factor in the relation +of `XY(N)` above is in fact `Y`, and thus `XY(N)` becomes: ~~~~ XY(N) = X * Y @@ -301,15 +301,16 @@ This then settles it. A number of refinement steps have brought us from repeated `FZ_Add` operations to the mathematical `*`; the reverse (un-)refinement is also possible[^4], which serves to prove that the algorithm implemented by `FZ_Mul_Egyptian` and the algebraic `*` are -equivalent. The reader is, of course, encouraged to challenge this. +equivalent. The reader is, of course, encouraged to challenge this +statement. More importantly, these refinement steps serve to show us what egyptian multiplication *is*: given a base `B` and two numbers `X` and `Y`, egyptian multiplication finds the answer to `X * Y` by adding `X` and -multiplying it (the same `X`) by `B` a number of times equal to the +multiplying it (the same `X`) by `B` a number of times depending on the number of digits (in base-`B` representation) of `Y`. Programmers can -then implement the same algorithm on ternary or quaternary computers, -etc.[^5] +then implement a variation of this algorithm on ternary or quaternary +computers, etc.[^5] We move on to the trickier part of our article: egyptian division. @@ -425,7 +426,7 @@ mathematical form that allows us to reason about it. At least two aspects are not exactly easy to spot: `R` and `Q` suffer two updates each, and the `R` in `R < Divisor` (on which the conditional updates to `Q` and `R` depend) is not the same `R` as in the previous iteration of -the loop. We'll try to untangle this first, by defining a +the loop. We'll try to untangle this first, by taking a *conditional*-`R` (`CR`) which maps to the first update to `R`: ~~~~ @@ -467,7 +468,7 @@ mathematical, so it might be completely non-obvious where the relations come from. The reader is recommended to go through the mental gymnastics necessary to obtain them by using pen and paper. At the end it should be clear that `Q(N)` is the resulting quotient, while `R(N)` is the -resulting remainder, and furthermore that the equation: +resulting remainder, and furthermore we wish to show that the equation: ~~~~ Dividend = Divisor * Q(N) + R(N) @@ -597,8 +598,8 @@ The reader is again recommended to follow the reasoning using pen and paper. The (by now very) keen reader will notice that the first bracket in the -definition of `R(N)` represents the very definition of `Dividend`; the -second definition doesn't seem to be anything in particular, so we'll +relation above represents the exact base-2 decomposition of `Dividend`; +the second term doesn't seem to denote anything in particular, so we'll give the (not-so-inspired) name `DR`, leading to: ~~~~ -- 1.7.10.4