libzahl

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

commit d998ab149b65c2a8e85e30d9405ae19d4e2ec54a
parent 12c7344ec6770c692094456bc81e7ed4322552aa
Author: Mattias Andrée <maandree@kth.se>
Date:   Mon, 16 May 2016 18:01:44 +0200

Misc work on the manual

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

Diffstat:
Mdoc/bit-operations.tex | 71++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
Mdoc/not-implemented.tex | 81+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 149 insertions(+), 3 deletions(-)

diff --git a/doc/bit-operations.tex b/doc/bit-operations.tex @@ -1,7 +1,10 @@ \chapter{Bit operations} \label{chap:Bit operations} -TODO +libzahl provides a number of functions that operate on +bits. These can sometimes be used instead of arithmetic +functions for increased performance. You should read +the sections in order. \vspace{1cm} \minitoc @@ -11,7 +14,48 @@ TODO \section{Boundary} \label{sec:Boundary} -TODO % zbits zlsb +To retrieve the index of the lowest set bit, use + +\begin{alltt} + size_t zlsb(z_t a); +\end{alltt} + +\noindent +It will return a zero-based index, that is, if the +least significant bit is indeed set, it will return 0. + +If {\tt a} is a power of 2, it will return the power +of which 2 is raised, effectively calculating the +binary logarithm of {\tt a}. Note, this is only if +{\tt a} is a power of two. More generally, it returns +the number of trailing binary zeroes, if equivalently +the number of times {\tt a} can evenly be divided by +2. However, in the special case where $a = 0$, +{\tt SIZE\_MAX} is returned. + +A similar function is + +\begin{alltt} + size_t zbit(z_t a); +\end{alltt} + +\noindent +It returns the minimal number of bits require to +represent an integer. That is, $\lceil \log_2 a \rceil - 1$, +or equivalently, the number of times {\tt a} can be +divided by 2 before it gets the value 0. However, in +the special case where $a = 0$, 1 is returned. 0 is +never returned. If you want the value 0 to be returned +if $a = 0$, write + +\begin{alltt} + zzero(a) ? 0 : zbits(a) +\end{alltt} + +The definition ``it returns the minimal number +of bits required to represent an integer,'' +holds true if $a = 0$, the other divisions +do not hold true if $a = 0$. \newpage @@ -161,7 +205,28 @@ divide-and-conquer algorithms. \section{Bit manipulation} \label{sec:Bit manipulation} -TODO % zbset + +The function + +\begin{alltt} + zbset(z_t r, z_t a, size_t bit, int mode); +\end{alltt} + +\noindent +is used to manipulate single bits in {\tt a}. It will +copy {\tt a} into {\tt r} and then, in {\tt r}, either +set, clear, or flip, the bit with the index {\tt bit} +— the least significant bit has the index 0. The +action depend on the value of {\tt mode}: + +\begin{itemize} +\item +$mode > 0$ ($+1$): set +\item +$mode = 0$ ($0$): clear +\item +$mode < 0$ ($-1$): flip +\end{itemize} \newpage diff --git a/doc/not-implemented.tex b/doc/not-implemented.tex @@ -399,7 +399,10 @@ using the following algorithm: \} zfree(k), zfree(a); \} +\end{alltt} +\newpage +\begin{alltt} void fib(z_t f, z_t n) \{ @@ -591,6 +594,11 @@ be improve by comparing character by character manually with using {\tt zxor}. +\newpage +\section{Miscellaneous} +\label{sec:Miscellaneous} + + \subsection{Character retrieval} \label{sec:Character retrieval} @@ -601,3 +609,76 @@ getu(z_t a) return zzero(a) ? 0 : a->chars[0]; \} \end{alltt} + +\subsection{Fit test} +\label{sec:Fit test} + +Some libraries have functions for testing +whether a big integer is small enough to +fit into an intrinsic type. Since libzahl +does not provide conversion to intrinsic +types this is irrelevant. But additionally, +it can be implemented with a single +one-line macro that does not have any +side-effects. + +\begin{alltt} + #define fits_in(a, type) (zbits(a) <= 8 * sizeof(type)) + \textcolor{c}{/* \textrm{Just be sure the type is integral.} */} +\end{alltt} + + +\subsection{Reference duplication} +\label{sec:Reference duplication} + +This could be useful for creating duplicates +with modified sign. But only if neither +{\tt r} or {\tt a} will be modified whilst +both are in use. Because it is unsafe, +fairly simple to create an implementation +with acceptable performance — {\tt *r = *a}, +— and probably seldom useful, this has not +be implemented. + +\begin{alltt} + int + refdup(z_t r, z_t a) + \{ + \textcolor{c}{/* \textrm{Almost fully optimised, but perfectly portable} *r = *a; */} + r->sign = a->sign; + r->used = a->used; + r->alloced = a->alloced; + r->chars = a->chars; + \} +\end{alltt} + + +\subsection{Variadic initialisation} +\label{sec:Variadic initialisation} + +Must bignum libraries have variadic functions +for initialisation and uninitialisation. This +is not available in libzahl, because it is +not useful enough and has performance overhead. +And what's next, support {\tt va\_list}, +variadic addition, variadic multiplication, +power towers, set manipulation? Anyone can +implement variadic wrapper for {\tt zinit} and +{\tt zfree} if they really need it. But if +you want to avoid the overhead, you can use +something like this: + +\begin{alltt} + /* \textrm{Call like this:} MANY(zinit, (a), (b), (c)) */ + #define MANY(f, ...) (_MANY1(f, __VA_ARGS__,,,,,,,,,)) + + #define _MANY1(f, a, ...) (void)f a, _MANY2(f, __VA_ARGS__) + #define _MANY2(f, a, ...) (void)f a, _MANY3(f, __VA_ARGS__) + #define _MANY3(f, a, ...) (void)f a, _MANY4(f, __VA_ARGS__) + #define _MANY4(f, a, ...) (void)f a, _MANY5(f, __VA_ARGS__) + #define _MANY5(f, a, ...) (void)f a, _MANY6(f, __VA_ARGS__) + #define _MANY6(f, a, ...) (void)f a, _MANY7(f, __VA_ARGS__) + #define _MANY7(f, a, ...) (void)f a, _MANY8(f, __VA_ARGS__) + #define _MANY8(f, a, ...) (void)f a, _MANY9(f, __VA_ARGS__) + #define _MANY9(f, a, ...) (void)f a +\end{alltt}