From c3ab337dd90f303227a55f4ec935d4cbbc8518c6 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Thu, 2 Jun 2016 13:28:15 +0200 Subject: Manual: extended gcd calculates two values for free, which most implementations ignore MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- doc/not-implemented.tex | 11 +++++++++++ 1 file changed, 11 insertions(+) diff --git a/doc/not-implemented.tex b/doc/not-implemented.tex index aea63fc..3e33c6f 100644 --- a/doc/not-implemented.tex +++ b/doc/not-implemented.tex @@ -65,6 +65,17 @@ extgcd(z_t bézout_coeff_1, z_t bézout_coeff_2, z_t gcd \} \end{alltt} +Perhaps you are asking yourself ``wait a minute, +doesn't the extended Euclidean algorithm only +have three outputs if you include the greatest +common divisor, what is this shenanigans?'' +No\footnote{Well, technically yes, but it calculates +two values for free in the same ways as division +calculates the remainder for free.}, it has five +outputs, most implementations just ignore two of +them. If this confuses you, or you want to know +more about this, I refer you to Wikipeida. + \newpage \section{Least common multiple} -- cgit v1.2.3-70-g09d2