libzahl

big integer library
git clone git://git.suckless.org/libzahl
Log | Files | Refs | README | LICENSE

commit 781e9d05388539d989e3578ebc7f8a7cd038aeb0
parent 183bfa766f29b3eb46b01c7b6e82d71d822b02d5
Author: Mattias Andrée <maandree@kth.se>
Date:   Tue, 29 Nov 2016 23:55:29 +0100

Fix errors in the manual (most of them found by Ivan Zuboff)

Signed-off-by: Mattias Andrée <maandree@kth.se>

Diffstat:
doc/arithmetic.tex | 42+++++++++++++++++++++---------------------
doc/bit-operations.tex | 2+-
doc/get-started.tex | 2+-
doc/libzahl.tex | 2+-
doc/libzahls-design.tex | 8++++----
doc/miscellaneous.tex | 30+++++++++++++++---------------
doc/not-implemented.tex | 9++++++---
doc/what-is-libzahl.tex | 25+++++++++++++++++++------
8 files changed, 68 insertions(+), 52 deletions(-)

diff --git a/doc/arithmetic.tex b/doc/arithmetic.tex @@ -69,7 +69,7 @@ instruction specifically for performing addition with ripple-carry over multiple words, adds twos numbers plus the carry from the last addition. libzahl uses assembly to -implement this efficiently. If however, an +implement this efficiently. If, however, an assembly implementation is not available for the on which machine it is running, libzahl implements ripple-carry less efficiently @@ -80,8 +80,8 @@ the compiler is known to support this extension, it is implemented using inefficient pure C code. This last resort manually predicts whether an addition will overflow; -this could be made more efficent, but never -using the highest bit, in each character, +this could be made more efficient, by never +using the highest bit in each character, except to detect overflow. This optimisation is however not implemented because it is not deemed important enough and would @@ -100,9 +100,9 @@ in-place operation: \noindent Use this whenever possible, it will improve your performance, as it will involve less -CPU instructions for each character-addition +CPU instructions for each character addition and it may be possible to eliminate some -character-additions. +character additions. \newpage @@ -138,7 +138,7 @@ These function \emph{do not} allow {\tt NULL} for the output parameters: {\tt quotient} and {\tt remainder}. The quotient and remainder are calculated simultaneously and indivisibly, hence -{\tt zdivmod} is provided to calculated both, if +{\tt zdivmod} is provided to calculated both; if you are only interested in the quotient or only interested in the remainder, use {\tt zdiv} or {\tt zmod}, respectively. @@ -146,14 +146,14 @@ interested in the remainder, use {\tt zdiv} or These functions calculate a truncated quotient. That is, the result is rounded towards zero. This means for example that if the quotient is in -$(-1,~1)$, {\tt quotient} gets 0. That that, this +$(-1,~1)$, {\tt quotient} gets 0. That is, this % TODO try to clarify would not be the case for one of the sides of zero. For example, if the quotient would have been floored, negative quotients would have been rounded away from zero. libzahl only provides truncated -division, +division. -The remain is defined such that $n = qd + r$ after +The remainder is defined such that $n = qd + r$ after calling {\tt zdivmod(q, r, n, d)}. There is no difference in the remainer between {\tt zdivmod} and {\tt zmod}. The sign of {\tt d} has no affect @@ -188,7 +188,7 @@ lend you a hand. % Floored division \begin{alltt} - void \textcolor{c}{/* \textrm{All arguments most be unique.} */} + void \textcolor{c}{/* \textrm{All arguments must be unique.} */} divmod_floor(z_t q, z_t r, z_t n, z_t d) \{ zdivmod(q, r, n, d); @@ -199,7 +199,7 @@ lend you a hand. % Ceiled division \begin{alltt} - void \textcolor{c}{/* \textrm{All arguments most be unique.} */} + void \textcolor{c}{/* \textrm{All arguments must be unique.} */} divmod_ceiling(z_t q, z_t r, z_t n, z_t d) \{ zdivmod(q, r, n, d); @@ -214,7 +214,7 @@ lend you a hand. % commercial rounding \begin{alltt} /* \textrm{This is how we normally round numbers.} */ - void \textcolor{c}{/* \textrm{All arguments most be unique.} */} + void \textcolor{c}{/* \textrm{All arguments must be unique.} */} divmod_half_from_zero(z_t q, z_t r, z_t n, z_t d) \{ zdivmod(q, r, n, d); @@ -237,7 +237,7 @@ not award you a face-slap. % Had positive punishment % This rounding method is also called: % round half away from infinity \begin{alltt} - void \textcolor{c}{/* \textrm{All arguments most be unique.} */} + void \textcolor{c}{/* \textrm{All arguments must be unique.} */} divmod_half_to_zero(z_t q, z_t r, z_t n, z_t d) \{ zdivmod(q, r, n, d); @@ -254,7 +254,7 @@ not award you a face-slap. % Had positive punishment % This rounding method is also called: % round half towards positive infinity \begin{alltt} - void \textcolor{c}{/* \textrm{All arguments most be unique.} */} + void \textcolor{c}{/* \textrm{All arguments must be unique.} */} divmod_half_up(z_t q, z_t r, z_t n, z_t d) \{ int cmp; @@ -272,7 +272,7 @@ not award you a face-slap. % Had positive punishment % This rounding method is also called: % round half towards negative infinity \begin{alltt} - void \textcolor{c}{/* \textrm{All arguments most be unique.} */} + void \textcolor{c}{/* \textrm{All arguments must be unique.} */} divmod_half_down(z_t q, z_t r, z_t n, z_t d) \{ int cmp; @@ -297,7 +297,7 @@ not award you a face-slap. % Had positive punishment % bankers' rounding % It is the default rounding method used in IEEE 754. \begin{alltt} - void \textcolor{c}{/* \textrm{All arguments most be unique.} */} + void \textcolor{c}{/* \textrm{All arguments must be unique.} */} divmod_half_to_even(z_t q, z_t r, z_t n, z_t d) \{ int cmp; @@ -316,7 +316,7 @@ not award you a face-slap. % Had positive punishment % Division with round half to odd \newpage \begin{alltt} - void \textcolor{c}{/* \textrm{All arguments most be unique.} */} + void \textcolor{c}{/* \textrm{All arguments must be unique.} */} divmod_half_to_odd(z_t q, z_t r, z_t n, z_t d) \{ int cmp; @@ -342,7 +342,7 @@ not award you a face-slap. % Had positive punishment Currently, libzahl uses an almost trivial division algorithm. It operates on positive numbers. It begins -by left-shifting the divisor as must as possible with +by left-shifting the divisor as much as possible with letting it exceed the dividend. Then, it subtracts the shifted divisor from the dividend and add 1, left-shifted as much as the divisor, to the quotient. @@ -350,7 +350,7 @@ The quotient begins at 0. It then right-shifts the shifted divisor as little as possible until it no longer exceeds the diminished dividend and marks the shift in the quotient. This process is -repeated on till the unshifted divisor is greater +repeated until the unshifted divisor is greater than the diminished dividend. The final diminished dividend is the remainder. @@ -376,7 +376,7 @@ exponentiation are \noindent They are identical, except {\tt zpowu} expects -and intrinsic type as the exponent. Both functions +an intrinsic type as the exponent. Both functions calculate \vspace{1em} @@ -410,7 +410,7 @@ exponentiation by squaring. {\tt zmodpow} and {\tt zmodpowu} are optimised, they modulate results for multiplication and squaring at every multiplication and squaring, rather than -modulating every at the end. Exponentiation +modulating the result at the end. Exponentiation by modulation is a very simple algorithm which can be expressed as a simple formula diff --git a/doc/bit-operations.tex b/doc/bit-operations.tex @@ -160,7 +160,7 @@ calculate division by a power of two and modulus a power of two efficiently using bit-shift and bit-truncation operations. libzahl also has a bit-split operation that can be used -to efficently calculate both division and +to efficiently calculate both division and modulus a power of two efficiently in the same operation, or equivalently, storing low bits in one integer and high bits in another integer. diff --git a/doc/get-started.tex b/doc/get-started.tex @@ -58,7 +58,7 @@ are done using it, for example before the program exits. \}} \end{alltt} -{\tt zunsetup} all memory that has been reclaimed to +{\tt zunsetup} frees all memory that has been reclaimed to the memory pool, and all memory allocated by {\tt zsetup}. Note that this does not free integers that are still in use. It is possible to simply call {\tt zunsetup} diff --git a/doc/libzahl.tex b/doc/libzahl.tex @@ -78,7 +78,7 @@ copyright notice and this permission notice appear in all copies.} % It should look just like a sentience except it may not end with a % period unless that is part of an ellipsis or an abbreviation. % I would also like to use straight apostrophes, like in French, (and -% reserve the curved ones for quotes,) but that is just too painful in +% reserve the curved ones for quotes), but that is just too painful in % LaTeX, so I will only be do so for French words. Most style guides % for English will be followed. They will only be broken if they are % stupid or inferior. For example, I will never write ‘CPU's’ for diff --git a/doc/libzahls-design.tex b/doc/libzahls-design.tex @@ -155,7 +155,7 @@ allows you do so if you so choose. The {\tt .sign} member, is either $-1$, 0, or 1, when the integer is negative, zero, or positive, -respectively. Whenever, {\tt .sign} is 0, the value +respectively. Whenever {\tt .sign} is 0, the value of {\tt .used} and {\tt .chars} are undefined. {\tt .used} holds to the number of elements used in @@ -192,7 +192,7 @@ they are not considered input integers. The order of the input parameters are that of the order you would write them using mathematical notation, this also holds true if you include the output parameter -(as long as there is exactly one output,) for example +(as long as there is exactly one output), for example \vspace{1em} $a \gets b^c \mod d$ @@ -256,7 +256,7 @@ This assumption is not made for non-commutative functions. When writting your own functions, be aware, -input-parameters are generally not declared {\tt const} +input parameters are generally not declared {\tt const} in libzahl. Currently, some functions actually make modifications (that do not affect the value) to -input-parameters. +input parameters. diff --git a/doc/miscellaneous.tex b/doc/miscellaneous.tex @@ -65,7 +65,7 @@ a proper UCS minus sign is not supported. Using what we have learned so far, and {\tt zstr} which we will learn about in \secref{sec:String output}, we can construct a simple program that calculates the -sum of a set of number. +sum of a set of numbers. \begin{alltt} \textcolor{c}{#include <stdio.h> @@ -153,10 +153,10 @@ there are cases where it is needed. In some case \noindent however its implementation is optimised to be around three times as fast. It just swaps the members -of the parameters, and thereby the values, There +of the parameters, and thereby the values. There is no rewriting of {\tt .chars} involved; thus it runs in constant time. It also does not -require that any argument has be initialised. +require that any argument has been initialised. After the call, {\tt a} will be initialised if and only if {\tt b} was initialised, and vice versa. @@ -301,11 +301,11 @@ The return for {\tt zcmpmag} value is defined \vspace{1em} \noindent -It is discouraged, stylistically, to compare -against, $-1$ and $+1$, rather, you should -always compare against $0$. Think of it as -returning $a - b$, or $\lvert a \rvert - \lvert b \rvert$ -in the case of {\tt zcmpmag}. +It is discouraged, stylistically, to compare against +$-1$ and $+1$, rather, you should always compare +against $0$. Think of it as returning $a - b$, or +$\lvert a \rvert - \lvert b \rvert$ in the case of +{\tt zcmpmag}. \newpage @@ -320,7 +320,7 @@ run the same version of libzahl, and run on compatible microarchitectures, that is, the processors must have endianness, and the intrinsic integer types in C must have the same widths on all processors. When this is not -the case, string conversion (see \secref{sec:Assignment} +the case, string conversion can be used (see \secref{sec:Assignment} and \secref{sec:String output}), but when it is the case {\tt zsave} and {\tt zload} can be used. {\tt zsave} and {\tt zload} are declared as @@ -331,11 +331,11 @@ and \secref{sec:String output}), but when it is the case \end{alltt} \noindent -{\tt zsave} stores a version- and microarchitecture-depend +{\tt zsave} stores a version- and microarchitecture-dependent binary representation of {\tt a} in {\tt buf}, and returns the number of bytes written to {\tt buf}. If {\tt buf} is -{\tt NULL}, the numbers that will be written is returned. -{\tt zload} unmarshals an integers from {\tt buf}, created -with {\tt zsave}, into {\tt a}, and returns the number of -read bytes. {\tt zload} and will return the value returned -by {\tt zsave}. +{\tt NULL}, the numbers bytes that would have be written is +returned. {\tt zload} unmarshals an integers from {\tt buf}, +created with {\tt zsave}, into {\tt a}, and returns the number +of read bytes. {\tt zload} returns the value returned by +{\tt zsave}. diff --git a/doc/not-implemented.tex b/doc/not-implemented.tex @@ -84,9 +84,12 @@ more about this, I refer you to Wikipeida. \( \displaystyle{ \mbox{lcm}(a, b) = \frac{\lvert a \cdot b \rvert}{\mbox{gcd}(a, b)} }\) +\vspace{1em} -Be aware, {\tt zgcd} can return zero. - +$\mbox{lcm}(a, b)$ is undefined when $a$ or +$b$ is zero, because division by zero is +undefined. Note however that $\mbox{gcd}(a, b)$ +is only zero when both $a$ and $b$ is zero. \newpage \section{Modular multiplicative inverse} @@ -309,7 +312,7 @@ TODO % Square: Cipolla's algorithm, Pocklington's algorithm, Tonelli–Shanks al }\) \vspace{1em} -This can be implemented much more efficently +This can be implemented much more efficiently than using the naïve method, and is a very important function for many combinatorial applications, therefore it may be implemented diff --git a/doc/what-is-libzahl.tex b/doc/what-is-libzahl.tex @@ -57,8 +57,8 @@ it can still be improved. Furthermore, GNU MP cannot be used for robust applications. \item -LibTomMath is very slow, infact performance is not its -priority, rather its simplicit is the priority. Despite +LibTomMath is very slow, in fact performance is not its +priority, rather its simplicity is the priority. Despite this, it is not really that simple. \item @@ -73,8 +73,8 @@ philosophy.\footnote{\href{http://suckless.org/philosophy} {http://suckless.org/philosophy}} libzahl is simple, very fast, simple to use, and can be used in robust applications. Currently however, it does not support -multithreading, but it has better support multiprocessing -and distributed computing than its competitor. +multithreading, but it has better support for multiprocessing +and distributed computing than its competitors. Lesser ``competitors'' (less known) to libzahl include Hebimath and bsdnt. @@ -142,10 +142,10 @@ caught using {\tt setjmp}. This ensure that it can be used in robust applications, catching errors does not become a mess, and it minimises the overhead of catching errors. Errors are only checked when they can -occur, not also after each function-return. +occur, not also after each function return. Additionally, libzahl tries to keep the functions' -names simple and natural rather than techniqual or +names simple and natural rather than technical or mathematical. The names resemble those of the standard integer operators. For example, the left-shift, right-shift and truncation bit-operations in libzahl are called @@ -214,6 +214,19 @@ strictly necessary for it to be an CPU-intrinsic, but that would be favourable for performance.) \end{itemize} +Because of the prevalence of theses properties +in contemporary machines, and the utilisation of +these properties in software, especially software +for POSIX and popular platforms with similar +properties, any new general-purpose machine most +have these properties lest, it but useless with +today's software. Therefore, libzahl can make +the assumption that the machine has these +properties. If the machine does not have these +properties, the compiler must compensate for +these machines deficiencies, making it generally +slower. + These limitations may be removed later. And there is some code that does not make these assumptions but acknowledge that it may be a case. On the other