% Copyright     Digital Equipment Corporation & INRIA     1988, 1989
%\documentstyle [fullpageusa]{article}
\documentstyle{article}
\title{BigNum\,:  Un module portable et efficace \\
pour une arithm\'etique \`a pr\'ecision arbitraire \\
\,\ \\
BigNum:  A Portable and Efficient Package \\ for
Arbitrary-Precision Arithmetic \\ \,\ \\}
\author{
Jean Claude Herv\'e \thanks{Digital Equipment Corp., Paris Research Laboratory,
        85 Av. Victor Hugo.        92500 Rueil-Malmaison, France.} \\
David Salesin $^{*}$ \\
Jean Vuillemin $^{*}$
\and
Fran\c{c}ois Morain \thanks{Institut National de Recherche
        en Informatique et Automatique, 78153, Rocquencourt, France.} \\
Bernard Paul Serpette $^{\dagger}$ \\
Paul Zimmermann $^{\dagger}$ \\
 }
\date{}
\begin{document}
\maketitle
\vspace*{48pt}
\begin{center}
Resum\'e
\end{center}
Nous sp\'ecifions un module Le-Lisp d'arithm\'etique enti\`ere \`a
pr\'ecision arbitraire, portable, mais n\'eanmoins efficace. La rapidit\'e
d'ex\'ecution de ce module est assujettie \`a la r\'e\'ecriture en langage
machine du noyau du module; nous fournissons les codes assembleurs pour
les machines VAX, Mips, 68020 et NS. Ce module est du domaine public pour
toute utilisation non commerciale.
\vspace*{48pt}
\begin{center}
Abstract
\end{center}
We specify a Le-Lisp package for arbitrary-precision integer arithmetic that
is portable, yet efficient. Making the package run fast on a given computer
involves re-writing a small kernel of our package in native assembly
language. We provide such assembly code for VAX, Mips, 68020 and NS
instruction sets. The package is publicly
available for non-commercial uses.
\clearpage
Un rapport d\'ecrivant le m\^eme module pour le langage C est disponible,
en anglais, en tant que rapport DEC. Cette implantation \'etant
particuli\`erement d\'edi\'ee au langage C, la n\^otre d\'edi\'ee \`a
Le-Lisp\footnote{Le-Lisp est une marque d\'epos\'ee de l'INRIA.}, certaines
diff\'erences de sp\'ecifications seront d\'ecrites. L'implantation C sera
appel\'ee BigNum.c.

\section{Introduction}
Le d\'eveloppement d'un module arithm\'etique \`a pr\'ecision arbitraire,
devant \^etre \`a la fois efficace et portable, soul\`eve deux probl\`emes
principaux\,:
\begin{itemize}
  \item Un module arithm\'etique, \'ecrit dans un langage de haut niveau
    (C, Le-Lisp, Modula2+, \ldots) est typiquement quatre \`a dix fois plus
    lent que le m\^eme module \'ecrit directement en langage machine.
  \item La plupart des op\'erations arithm\'etiques sont acc\'el\'er\'ees d'un
    facteur non n\'egligeable lorsque les allocations m\'emoire sont enlev\'ees
    des boucles principales, les r\'esultats interm\'ediaires et finaux
    utilisant l'espace m\'emoire r\'ef\'erenc\'e par certains des param\`etres des
    fonctions d'appel.
\end{itemize}
Pour r\'esoudre ces probl\`emes, nous avons organis\'e notre logiciel en deux
niveaux\,:
\begin{enumerate}
  \item Un niveau appel\'e \verb+Bn+, dans lequel chaque fonction traite des
    entiers non sign\'es, sans allocation, et retournant les r\'esultats en lieu
    et place des premiers arguments pass\'es \`a la fonction.
  \item Un niveau appel\'e \verb+Bz+, implant\'e au dessus de \verb+Bn+,
    sp\'ecifiant une arithm\'etique sign\'ee et o\`u, d'une mani\`ere
    traditionnelle, est faite l'allocation des r\'esultats.
\end{enumerate}
Pour des raisons d'efficacit\'e, le module \verb+Bn+ est lui-m\^eme
structur\'e en deux niveaux\,:
\begin{itemize}
  \item Le noyau \verb+KerN+, contenant les primitives dont le temps
    d'ex\'ecution est critique.
  \item Le reste de \verb+Bn+, dont le code Le-Lisp fait appel au noyau.
\end{itemize}
Le noyau \verb+KerN+ est \'ecrit en C et en Le-Lisp pour des raisons de
portabilit\'e et de documentation et peut \^etre compil\'e tel quel.
N\'eanmoins, pour obtenir une implantation vraiment efficace sur une machine
donn\'ee, \verb+KerN+ doit \^etre \'ecrit directement en langage machine.
Nous en proposons les versions pour les machines VAX, Mips, 68020, et NS.
\verb+KerN+ reste de taille raisonnable\,: 550 lignes de C,
350 lignes de Le-Lisp, 700 lignes d'assembleur 68020 et 600
lignes d'assembleur VAX.
\\
La partie de \verb+Bn+ ne faisant pas partie du noyau est \'ecrite directement
en Le-Lisp et en C. Une fonction est consid\'er\'ee comme faisant parti du noyau
s'il est possible de gagner un gain d'efficacit\'e de plus de 20\%, sur un
test standard, en r\'ecrivant cette fonction en assembleur.
La connaissance exacte des proc\'edures faisant partie de \verb+KerN+
n'a d'importance que pour les personnes devant porter le module sur une
nouvelle machine, ou ceux qui ne sont pas satisfaits de l'implantation C
ou Le-Lisp.
\\
Finalement, notons que \verb+Bn+ sert de base \`a d'autres modules
sp\'ecialis\'es tels qu'arithm\'etique rationnelle, polyn\^omiale ou modulaire.

\section{Repr\'esentation des nombres}
Les objets de base trait\'es par \verb+KerN+ sont les entiers naturels
repr\'esent\'es par leurs d\'ecompositions dans une base nomm\'ee $B$; ainsi les
nombres de \verb+KerN+ s'\'ecrivent sous la forme\,:
\[ N = \sum_{i=0}^{i<n} N_i B^i\ .\]
Nous faisons la restriction que la base $B$ est une puissance de 2. Il
existe un entier $T$ tel que\,: $B = 2^T$ ou $T = \log_2(B)$, $T$
d\'etermine le nombre de bits n\'ecessaires pour repr\'esenter un chiffre $N_i$.
La valeur de l'entier $T$ est disponible par la constante
\verb+BN_DIGIT_SIZE+.
\\[12pt]
Par la suite nous utiliserons la notion de {\em sous-nombre} d'un nombre.
Le sous-nombre, not\'e $N_{nd,nl}$, du nombre 
\[ N = \sum_{i=0}^{i<n} N_i B^i \]
est\,:
\[ N_{nd,nl} = \sum_{i=0}^{i<nl}N_{nd+i} B^i\ .\]
Ceci impose que $nd \geq 0$, $nl \geq 1$ et $nd + nl \leq n$;
$n$ est appel\'e la taille du nombre $N$ (par la suite nous noterons
$n = size(N)$). Pour le cas particulier $nl = 0$ nous convenons que tous
les sous-nombres $N_{i,0}$ sont \'equivalents \`a 0.
On remarquera que le chiffre $N_i$ est \'equivalent au sous-nombre
$N_{i,1}$.
\\
Toutes les primitives supposent, sans le tester, que, si $N_{i,j}$ est
un sous-nombre du nombre {\em N} de taille {\em n}, alors les
pr\'econditions suivantes sont v\'erifi\'ees\,: $0 \leq i < n$,
$0 \leq j \leq n$ et $0 \leq i+j \leq n$.
Aucune de ces pr\'econditions ne sont
explicitement test\'ees. L'usage de ces routines, hors de ces conditions
de validit\'e, peut conduire \`a des violations de m\'emoire.
\\
Dans l'implantation BigNum.c un sous-nombre $N_{nd,nl}$ est converti en
un autre sous-nombre \'equivalent $M_{0,nl}$ moyennant l'affectation
$M = N + nd;$ ceci impose d'une part que le langage permet l'utilisation
de pointeur \`a l'int\'erieur de tableau de chiffres\footnote{Addition d'un
pointeur sur des chiffres et d'un index comme dans l'exemple $N + nd$.}, et
d'autre part que l'organisation interne des chiffres dans un nombre soit
fix\'ee. Ces restrictions permettent de r\'eduire (g\'en\'eralement d'un tiers)
les param\`etres formels des primitives. Ainsi tous les sous-nombres sont
sp\'ecifi\'es par deux variables ($N$ et $nl$) au lieu de trois ($N$, $nd$ et
$nl$).

\section{Op\'eration en place\,:\,Bn}
Dans cette section nous d\'ecrirons les fonctions traitant des entiers non
sign\'es. Dans les exemples les entiers sont imprim\'es en hexad\'ecimal,
les poids forts \`a gauche, chaque chiffre \'etant encadr\'e par le caract\`ere
\verb+|+. Nous utiliserons une implantation o\`u \verb+BN_DIGIT_SIZE+ vaut
32.

\subsection{Addition}
({\bf BnAddCarry} {\em N nd nl r})
\\[12pt]
La fonction {\bf BnAddCarry} propage en place la retenue {\em r}, valant 0
ou 1,  sur le sous-nombre $N_{nd,nl}$ et retourne la retenue sortante. Plus
formellement la fonction {\bf BnAddCarry} effectue l'op\'eration suivante\,:
\[ N_{nd,nl} + r = (\sum_{i=0}^{i<nl}N_{nd+i} B^i) + r = (\sum_{i=0}^{i<nl}N'_{nd+i} B^i) + r' B^{nl}\ .\]
La fonction {\bf BnAddCarry} remplace tous les chiffres $N_{nd+i}$ par leurs
\'equivalents $N'_{nd+i}$ et retourne comme r\'esultat la retenue $r'$ valant
0 ou 1. Cette retenue vaut 1 si et seulement si le sous-nombre $N_{nd,nl}$
est \'egal \`a $B^{nl} - 1$ et si la retenue entrante $r$ vaut 1. La longueur
$nl$ peut-\^etre \'egale \`a z\'ero, dans ce cas la retenue sortante prend la
m\^eme valeur que la retenue entrante.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (BnComplement n 0 4) n)
= |FFFFFFFF|FFFFFFFF|FFFFFFFF|FFFFFFFF|
? (cons (BnAddCarry n 1 3 0) n)
= (0 . |FFFFFFFF|FFFFFFFF|FFFFFFFF|FFFFFFFF|)
? (cons (BnAddCarry n 2 2 1) n)
= (1 . |00000000|00000000|FFFFFFFF|FFFFFFFF|)
? (cons (BnAddCarry n 0 3 1) n)
= (0 . |00000000|00000001|00000000|00000000|)
? (cons (BnAddCarry n 0 3 1) n)
= (0 . |00000000|00000001|00000000|00000001|)
? (cons (BnAddCarry n 0 3 1) n)
= (0 . |00000000|00000001|00000000|00000002|)
\end{verbatim}
\vspace*{24pt}
({\bf BnAdd} {\em N nd nl M md ml r})
\\[12pt]
La fonction {\bf BnAdd} effectue l'addition des deux sous-nombres
$N_{nd,nl}$ et $M_{md,ml}$ et de la retenue {\em r}, place le
r\'esultat dans le sous-nombre $N_{nd,ml}$, propage la retenue de cette
addition sur le sous-nombre $N_{nd+ml,nl-ml}$ et retourne la retenue
sortante. Plus formellement la fonction {\bf BnAdd} effectue l'op\'eration
suivante\,:
\[ N_{nd,nl} + M_{md,ml} + r = (\sum_{i=0}^{i<nl}N_{nd+i} B^i) + (\sum_{i=0}^{i<ml}M_{md+i} B^i) + r = (\sum_{i=0}^{i<nl}N'_{nd+i} B^i) + r' B^{nl}\ .\]
La fonction {\bf BnAdd} remplace tous les chiffres $N_{nd+i}$ par leurs
\'equivalents $N'_{nd+i}$ et retourne comme r\'esultat la retenue $r'$ valant 0
ou 1. Ceci impose donc que $0 \leq r \leq 1$ et $nl \geq ml$. Les deux nombres
$N$ et $M$ peuvent \^etre identiques \footnote{Au sens de la fonction {\bf eq}
de Le-Lisp\,: (eq $N$ $M$).} \`a la condition que $nd \leq md$. De m\^eme la
longueur $ml$ peut-\^etre \'egale \`a z\'ero, dans ce cas la forme
({\bf BnAdd} {\em N nd nl M md 0 r}) est \'equivalente \`a\,:
({\bf BnAddCarry} {\em N nd nl r}).
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (BnComplement n 0 3) n)
= |00000000|FFFFFFFF|FFFFFFFF|FFFFFFFF|
? (cons (BnAdd n 0 1 n 1 1 1) n)
= (1 . |00000000|FFFFFFFF|FFFFFFFF|FFFFFFFF|)
? (cons (BnAdd n 0 2 n 2 1 0) n)
= (1 . |00000000|FFFFFFFF|00000000|FFFFFFFE|)
? (cons (BnAdd n 2 1 n 3 1 1) n)
= (1 . |00000000|00000000|00000000|FFFFFFFE|)
? (cons (BnAdd n 0 2 n 0 1 0) n)
= (0 . |00000000|00000000|00000001|FFFFFFFC|)
\end{verbatim}
\vspace*{15pt}

\subsection{Soustraction}
({\bf BnComplement} {\em N nd nl})
\\[12pt]
La fonction {\bf BnComplement} remplace tous les chiffres du sous-nombre
$N_{nd,nl}$ par leur compl\'ement \`a la base, ce qui correspond \`a
l'inversion logique de tous les bits. Plus formellement la fonction
{\bf BnComplement} effectue l'op\'eration suivante\,:
\[ \overline{N_{nd,nl}} = \overline{\sum_{i=0}^{i<nl}N_{nd+i} B^i} = \sum_{i=0}^{i<nl}\overline{N_{nd+i}} B^i = \sum_{i=0}^{i<nl}(B - N_{nd+i} - 1) B^i\ .\]
La fonction {\bf BnComplement} ne retourne aucun r\'esultat significatif. Aucun
effet de bord n'est effectu\'e lorsque la longueur $nl$ vaut 0.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (progn (BnComplement n 1 2) n)
= |00000003|FFFFFFFD|FFFFFFFE|00000000|
\end{verbatim}
\vspace*{12pt}
({\bf BnSubtractBorrow} {\em N nd nl r})
\\[12pt]
La fonction {\bf BnSubtractBorrow} propage en place l'emprunt {\em r}, de
valeur 0 ou 1, sur le sous-nombre $N_{nd,nl}$ et retourne l'emprunt
sortant. Plus formellement la fonction {\bf BnSubtractBorrow} effectue
l'op\'eration suivante\,:
\[ N_{nd,nl} + B^{nl} + r - 1 = (\sum_{i=0}^{i<nl}N_{nd+i} B^i) + B^{nl} + r - 1 = (\sum_{i=0}^{i<nl}N'_{nd+i} B^i) + r' B^{nl}\ .\]
La fonction {\bf BnSubtractBorrow} remplace tous les chiffres $N_{nd+i}$ par
leurs \'equivalents $N'_{nd+i}$ et retourne comme r\'esultat l'emprunt sortant
$r'$ valant 0 ou 1. Cet emprunt vaut 0 si et seulement si le sous-nombre
$N_{nd,nl}$ et l'emprunt entrant sont \'egaux \`a 0. La longueur $nl$
peut-\^etre \'egale \`a z\'ero, dans ce cas l'emprunt sortant prend la m\^eme
valeur que l'emprunt entrant.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) n)
= |00000000|00000000|00000000|00000000|
? (cons (BnSubtractBorrow n 1 3 1) n)
= (1 . |00000000|00000000|00000000|00000000|)
? (cons (BnSubtractBorrow n 2 2 0) n)
= (0 . |FFFFFFFF|FFFFFFFF|00000000|00000000|)
? (cons (BnSubtractBorrow n 0 3 0) n)
= (1 . |FFFFFFFF|FFFFFFFE|FFFFFFFF|FFFFFFFF|)
? (cons (BnSubtractBorrow n 0 3 0) n)
= (1 . |FFFFFFFF|FFFFFFFE|FFFFFFFF|FFFFFFFE|)
? (cons (BnSubtractBorrow n 0 3 0) n)
= (1 . |FFFFFFFF|FFFFFFFE|FFFFFFFF|FFFFFFFD|)
\end{verbatim}
\vspace*{24pt}
({\bf BnSubtract} {\em N nd nl M md ml r})
\\[12pt]
La fonction {\bf BnSubtract} effectue la soustraction des deux
sous-nombres $N_{nd,nl}$ et $M_{md,ml}$ et de l'emprunt {\em r}, 
place le r\'esultat dans le sous-nombre $N_{nd,ml}$, propage l'emprunt 
de cette soustraction sur le sous-nombre $N_{nd+ml,nl-ml}$ et retourne
l'emprunt sortant.  Plus formellement la fonction {\bf BnSubtract}
effectue l'op\'eration suivante\,:
\[ N_{nd,nl} - M_{md,ml} + B^{nl} + r - 1 = (\sum_{i=0}^{i<nl}N_{nd+i} B^i) - (\sum_{i=0}^{i<ml}M_{md+i} B^i) + B^{nl} + r - 1 = (\sum_{i=0}^{i<nl}N'_{nd+i} B^i) + r' B^{nl}\ .\]
La fonction {\bf BnSubtract} remplace tous les chiffres $N_{nd+i}$ par leurs
\'equivalents $N'_{nd+i}$ et retourne comme r\'esultat l'emprunt sortant $r'$
valant 0 ou 1. Ceci impose donc que $0 \leq r \leq 1$ et $nl \geq ml$.
Les deux nombres $N$ et $M$ peuvent \^etre identiques \`a la condition que
$nd \leq md$. De m\^eme la longueur $ml$ peut-\^etre \'egale \`a z\'ero, dans ce
cas la forme ({\bf BnSubtract} {\em N nd nl M md 0 r}) est \'equivalente \`a\,:
({\bf BnSubtractBorrow} {\em N nd nl r}).
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (BnComplement n 3 1) n)
= |FFFFFFFF|00000000|00000000|00000000|
? (cons (BnSubtract n 0 1 n 1 1 0) n)
= (0 . |FFFFFFFF|00000000|00000000|FFFFFFFF|)
? (cons (BnSubtract n 0 2 n 2 1 0) n)
= (1 . |FFFFFFFF|00000000|00000000|FFFFFFFE|)
? (cons (BnSubtract n 2 1 n 3 1 1) n)
= (0 . |FFFFFFFF|00000001|00000000|FFFFFFFE|)
? (cons (BnSubtract n 0 3 n 0 1 0) n)
= (1 . |FFFFFFFF|00000000|FFFFFFFF|FFFFFFFF|)
\end{verbatim}
\vspace*{15pt}

\subsection{Multiplication}
({\bf BnMultiplyDigit} {\em P pd pl N nd nl M md})
\\[12pt]
La fonction {\bf BnMultiplyDigit} effectue la multiplication du sous-nombre
$N_{nd,nl}$ par le chiffre $M_{md}$ avec accumulation dans le
sous-nombre $P_{pd,pl}$, et retourne la retenue produite. Plus
formellement la fonction {\bf BnMultiplyDigit} effectue l'op\'eration
suivante\,:
\[ P_{pd,pl} + M_{md}\times N_{nd,nl} = (\sum_{i=0}^{i<pl}P_{pd+i} B^i) + M_{md}(\sum_{i=0}^{i<nl}N_{nd+i} B^i) = (\sum_{i=0}^{i<pl}P'_{pd+i} B^i) + r' B^{pl}\ .\]
La fonction {\bf BnMultiplyDigit} remplace tous les chiffres $P_{pd+i}$ par
leurs \'equivalents $P'_{pd+i}$ et retourne comme r\'esultat la retenue sortante
$r'$ valant 0 ou 1. Ceci impose donc que $pl>nl$. La longueur $nl$ peut-\^etre
\'egale \`a z\'ero, dans ce cas la retenue sortante vaut z\'ero et aucun effet
de bord n'est effectu\'e. Les deux nombres $P$ et $N$ peuvent \^etre identiques
\`a la condition que $pd \leq nd$. Enfin le chiffre $M_{md}$ peut-\^etre
n'importe lequel des chiffres de $P$ ou de $N$. Les cas $M_{md} = 0$ et
$M_{md} = 1$ sont explicitement test\'es pour acc\'el\'erer les temps de calcul.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 6)) (BnComplement n 0 4) n)
= |00000000|00000000|FFFFFFFF|FFFFFFFF|FFFFFFFF|FFFFFFFF|
? (cons (BnMultiplyDigit n 3 3 n 0 2 n 0) n)
= (0 . |FFFFFFFF|00000000|00000000|FFFFFFFF|FFFFFFFF|FFFFFFFF|)
? (cons (BnMultiplyDigit n 3 3 n 0 2 n 0) n)
= (1 . |FFFFFFFD|FFFFFFFF|00000001|FFFFFFFF|FFFFFFFF|FFFFFFFF|)
? (cons (BnMultiplyDigit n 3 3 n 0 2 n 0) n)
= (1 . |FFFFFFFC|FFFFFFFE|00000002|FFFFFFFF|FFFFFFFF|FFFFFFFF|)
? (cons (BnMultiplyDigit n 0 3 n 0 2 n 3) n)
= (1 . |FFFFFFFC|FFFFFFFE|00000002|00000001|FFFFFFFF|FFFFFFFD|)
? (cons (BnMultiplyDigit n 0 2 n 0 1 n 3) n)
= (1 . |FFFFFFFC|FFFFFFFE|00000002|00000001|00000001|FFFFFFF7|)
? (cons (BnMultiplyDigit n 0 2 n 0 1 n 3) n)
= (0 . |FFFFFFFC|FFFFFFFE|00000002|00000001|00000003|FFFFFFE5|)
\end{verbatim}
\vspace*{24pt}
({\bf BnMultiply} {\em P pd pl N nd nl M md ml})
\\[12pt]
La fonction {\bf BnMultiply} effectue la multiplication des deux
sous-nombres $N_{nd,nl}$ et $M_{md,ml}$ avec accumulation dans le
sous-nombre $P_{pd,pl}$, et retourne la retenue produite. Plus
formellement la fonction {\bf BnMultiply} effectue l'op\'eration
suivante\,:
\[ P_{pd,pl} + N_{nd,nl}\times M_{md,ml} = (\sum_{i=0}^{i<pl}P_{pd+i} B^i) + (\sum_{i=0}^{i<nl}N_{nd+i} B^i)(\sum_{i=0}^{i<ml}M_{md+i} B^i) = (\sum_{i=0}^{i<pl}P'_{pd+i} B^i) + r' B^{pl}\ .\]
La fonction {\bf BnMultiply} remplace tous les chiffres $P_{pd+i}$ par
leurs \'equivalents $P'_{pd+i}$ et retourne comme r\'esultat la retenue sortante
$r'$ valant 0 ou 1. Ceci impose donc que $pl\geq nl + ml$. La longueur $nl$
peut-\^etre \'egale \`a z\'ero, dans ce cas la retenue sortante vaut z\'ero et
aucun effet de bord n'est effectu\'e. La boucle de calcul \'etant effectu\'e
sur $ml$, la fonction est plus performante lorsque $nl \geq ml$.
Il n'est pas possible d'effectuer des chevauchements entre les sous-nombres
$P_{pd,pl}$ et $N_{nd,nl}$ ou $M_{md,ml}$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n  (BnCreate 'n 8)) (for (i 0 1 7) (BnSetDigit n i i)) n)
= |00000007|00000006|00000005|00000004|00000003|00000002|00000001|00000000|
? (cons (BnMultiply n 4 4 n 0 2 n 2 2) n)
= (0 . |00000007|00000009|00000007|00000004|00000003|00000002|00000001|00000000|)
? (progn (BnComplement n 0 4) n)
= |00000007|00000009|00000007|00000004|FFFFFFFC|FFFFFFFD|FFFFFFFE|FFFFFFFF|
? (cons (BnMultiply n 4 4 n 0 2 n 2 2) n)
= (1 . |00000003|00000008|0000000D|00000007|FFFFFFFC|FFFFFFFD|FFFFFFFE|FFFFFFFF|)
\end{verbatim}
\vspace*{24pt}
({\bf BnShiftLeft} {\em N nd nl M md s})
\\[12pt]
La fonction {\bf BnShiftLeft} d\'ecale vers la gauche tous les chiffres du
sous-nombre $N_{nd,nl}$, les $s$ bits laiss\'es vacants d'un
chiffre sont remplac\'es par les $s$ bits sortants du chiffre pr\'ec\'edent,
les $s$ bits laiss\'es vacants du premier chiffre sont remplac\'es par des
z\'eros, et les $s$ bits sortants du dernier chiffre sont plac\'es,
cadr\'es sur les poids faibles, dans le chiffre $M_{md}$. La fonction
{\bf BnShiftLeft} effectue donc une multiplication par $2^s$ sur le
sous-nombre $N_{nd,nl}$. Plus formellement la fonction {\bf BnShiftLeft}
effectue l'op\'eration suivante\,:
\[ 2^sN_{nd,nl} = 2^s(\sum_{i=0}^{i<nl}N_{nd+i} B^i) = (\sum_{i=0}^{i<nl}N'_{nd+i} B^i) + M'_{md}B^{nl}\ .\]
La fonction {\bf BnShiftLeft} remplace tous les chiffres $N_{nd+i}$ par leurs
\'equivalents $N'_{nd+i}$ et le chiffre $M_{md}$ par $M'_{md}$. Ceci impose
donc que $0 \leq s < $ \verb+BN_DIGIT_SIZE+. Le cas particulier $s = 0$ est
explicitement test\'e pour acc\'el\'erer le temps de calcul.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (progn (BnShiftLeft n 1 3 n 0 8) n)
= |00000300|00000200|00000100|00000000|
? (progn (BnShiftLeft n 1 3 n 0 16) n)
= |03000000|02000000|01000000|00000000|
? (progn (BnShiftLeft n 1 3 n 0 16) n)
= |00000200|00000100|00000000|00000300|
\end{verbatim}
\vspace*{15pt}

\subsection{Division}
({\bf BnDivideDigit} {\em Q qd R rd N nd nl M md})
\\[12pt]
La fonction {\bf BnDivideDigit} effectue la division du sous-nombre
$N_{nd,nl}$ par le chiffre $M_{md}$, place le quotient dans le sous-nombre
$Q_{qd,nl-1}$ et le reste dans le chiffre $R_{rd}$. Plus formellement
l'\'equation suivante est satisfaite\,:
\[ \sum_{i=0}^{i<nl}N_{nd+i} B^i = (\sum_{i=0}^{i<nl-1}Q_{qd+i} B^i)\times M_{md} + R_{rd}\ {\rm avec}\ 0 \leq R_{rd} < M_{md}\ .\]
La fonction {\bf BnDivideDigit} impose donc
que $nl > 1$, $N_{nd+nl-1} < M_{md}$ et que $size(Q) \geq qd+nl-1$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (progn (BnDivideDigit n 0 n 2 n 0 3 n 3) n)
= |00000003|00000000|AAAAAAAB|00000000|
? (progn (BnDivideDigit n 0 n 2 n 0 3 n 3) n)
= |00000003|00000000|38E38E39|00000000|
? (progn (BnDivideDigit n 0 n 2 n 0 3 n 3) n)
= |00000003|00000002|12F684BD|AAAAAAAA|
? (progn (BnDivideDigit n 0 n 2 n 1 2 n 0) n)
= |00000003|12F684BF|12F684BD|00000003|
\end{verbatim}
\vspace*{24pt}
({\bf BnDivide} {\em N nd nl M md ml})
\\[12pt]
La fonction {\bf BnDivide} effectue la division du sous-nombre
$N_{nd,nl}$ par le sous-nombre $M_{md,ml}$, place le quotient dans le
sous-nombre $N_{nd+ml,nl-ml}$ et le reste dans le sous-nombre
$N_{nd,ml}$. Plus formellement l'\'equation suivante est satisfaite\,:
\[ \sum_{i=0}^{i<nl}N_{nd+i} B^i = (\sum_{i=0}^{i<nl-ml}N'_{nd+ml+i} B^i)\times (\sum_{i=0}^{i<ml}M_{md+i} B^i) + (\sum_{i=0}^{i<ml}N'_{nd+i} B^i) \]
\[ {\rm avec}\ 0 \leq  \sum_{i=0}^{i<ml}N'_{nd+i} B^i < \sum_{i=0}^{i<ml}M_{md+i} B^i\ .\]
La fonction {\bf BnDivide} remplace tous les chiffres $N_{nd+i}$ par leurs
\'equivalents $N'_{nd+i}$. Ceci impose donc que $nl > ml$ et que
$N_{nd+nl-1} < M_{md+ml-1}$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 5)) (for (i 0 1 4) (BnSetDigit n i i)) n)
= |00000004|00000003|00000002|00000001|00000000|
? (progn (BnDivide n 0 3 n 3 2) n)
= |00000004|00000003|7FFFFFFF|00000003|80000003|
? (progn (BnDivide n 0 2 n 4 1) n)
= |00000004|00000003|7FFFFFFF|E0000000|00000003|
? (progn (BnDivide n 2 3 n 0 2) n)
= |00000004|80000003|7FFFFFF3|E0000000|00000003|
\end{verbatim}
\vspace*{24pt}
({\bf BnShiftRight} {\em N nd nl M md s})
\\[12pt]
La fonction {\bf BnShiftRight} d\'ecale vers la droite tous les chiffres du
sous-nombre $N_{nd,nl}$, les $s$ bits laiss\'es vacants d'un
chiffre sont remplac\'es par les $s$ bits sortants du chiffre suivant,
les $s$ bits laiss\'es vacants du dernier chiffre sont remplac\'es par des
z\'eros, et les $s$ bits sortants du premier chiffre sont plac\'es,
cadr\'es sur les poids forts, dans le chiffre $M_{md}$. La fonction
{\bf BnShiftRight} effectue donc une division par $2^s$ sur le sous-nombre
$N_{nd,nl}$. Plus formellement l'\'equation suivante est satisfaite\,:
\[ \sum_{i=0}^{i<nl}N_{nd+i} B^i = 2^s(M'_{md}B^{-1} + \sum_{i=0}^{i<nl}N'_{nd+i} B^i)\ .\]
La fonction {\bf BnShiftRight} remplace tous les chiffres $N_{nd+i}$ par leurs
\'equivalents $N'_{nd+i}$ et le chiffre $M_{md}$ par $M'_{md}$. Ceci impose
donc que $0 \leq s < $ \verb+BN_DIGIT_SIZE+. Le cas particulier $s = 0$ est
explicitement test\'e pour acc\'el\'erer le temps de calcul.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (progn (BnShiftRight n 1 3 n 0 8) n)
= |00000000|03000000|02000000|01000000|
? (progn (BnShiftRight n 1 3 n 0 16) n)
= |00000000|00000300|00000200|00000000|
? (progn (BnShiftRight n 1 3 n 0 16) n)
= |00000000|00000000|03000000|02000000|
\end{verbatim}
\vspace*{24pt}
Les deux proc\'edures suivantes sont utilis\'ees dans le processus de
normalisation de la division longue.
\\[24pt]
({\bf BnNumLeadingZeroBitsInDigit} {\em N nd})
\\[12pt]
La fonction {\bf BnNumLeadingZeroBitsInDigit} calcule le nombre de bits nuls
dans les poids forts du chiffre $N_{nd}$. Plus formellement la fonction
{\bf BnNumLeadingZeroBitsInDigit} calcule l'entier $k$ tel que l'\'equation
suivante soit satisfaite\,:
\[ \frac{B}{2} < (N_{nd} + 1) 2^k \leq B\ .\]
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (BnNumLeadingZeroBitsInDigit n 0)
= 32
? (BnNumLeadingZeroBitsInDigit n 1)
= 31
? (BnNumLeadingZeroBitsInDigit n 3)
= 30
? (progn (BnComplement n 2 1) n)
= |00000003|FFFFFFFD|00000001|00000000|
? (BnNumLeadingZeroBitsInDigit n 2)
= 0
\end{verbatim}
\vspace*{24pt}
({\bf BnIsDigitNormalized} {\em N nd})
\\[12pt]
La fonction {\bf BnIsDigitNormalized} retourne 0 si le chiffre $N_{nd}$
v\'erifie\,:
\[ 0 \leq N_{nd} < \frac{B}{2}\ .\]
La fonction {\bf BnIsDigitNormalized} teste le bit de poids fort du chiffre
$N_{nd}$ et retourne 0 si ce bit a pour valeur 0; dans le cas contraire
la fonction retourne un entier diff\'erent de 0, la valeur exacte de cet
entier peut d\'ependre des machines.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (BnIsDigitNormalized n 0)
= 0
? (BnIsDigitNormalized n 1)
= 0
? (progn (BnComplement n 0 2) n)
= |00000003|00000002|FFFFFFFE|FFFFFFFF|
? (BnIsDigitNormalized n 0)
= 255
? (BnIsDigitNormalized n 1)
= 255
\end{verbatim}
\vspace*{15pt}

\subsection{Comparaisons}
({\bf BnIsDigitZero} {\em N nd})
\\[12pt]
La fonction {\bf BnIsDigitZero} retourne 0 si le chiffre $N_{nd}$ est
non nul.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (BnIsDigitZero n 0)
= 255
? (BnIsDigitZero n 1)
= 0
\end{verbatim}
\vspace*{24pt}
({\bf BnIsZero} {\em N nd nl})
\\[12pt]
La fonction {\bf BnIsZero} retourne 0 si le sous-nombre $N_{nd,nl}$ est
non nul.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (BnIsZero n 0 1)
= 255
? (BnIsZero n 0 2)
= 0
? (BnIsZero n 1 1)
= 0
\end{verbatim}
\vspace*{24pt}
({\bf BnCompareDigits} {\em N nd M md})
\\[12pt]
La fonction {\bf BnCompareDigits} retourne -1 si le chiffre $N_{nd}$ est
strictement plus petit que le chiffre $M_{md}$, 0 si le chiffre
$N_{nd}$ est \'egal au chiffre $M_{md}$ et 1 si le chiffre $N_{nd}$
est strictement sup\'erieur au chiffre $M_{md}$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (BnCompareDigits n 0 n 0)
= 0
? (BnCompareDigits n 0 n 1)
= -1
? (BnCompareDigits n 1 n 0)
= 1
? (progn (BnComplement n 0 2) n)
= |00000003|00000002|FFFFFFFE|FFFFFFFF|
? (BnCompareDigits n 0 n 0)
= 0
? (BnCompareDigits n 0 n 1)
= 1
? (BnCompareDigits n 1 n 0)
= -1
\end{verbatim}
\vspace*{24pt}
({\bf BnCompare} {\em N nd nl M md ml})
\\[12pt]
La fonction {\bf BnCompare} retourne -1 si le sous-nombre $N_{nd,nl}$ est
strictement plus petit que le sous-nombre $M_{md,ml}$, retourne 0 si le
sous-nombre $N_{nd,nl}$ est \'egal au sous-nombre $M_{md,ml}$ et
retourne 1 si le sous-nombre $N_{nd,nl}$ est strictement sup\'erieur
au sous-nombre $M_{md,ml}$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 5)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000000|00000003|00000002|00000001|00000000|
? (BnCompare n 2 3 n 2 2)
= 0
? (BnCompare n 2 3 n 0 2)
= 1
? (BnCompare n 3 2 n 0 2)
= -1
? (progn (BnComplement n 0 2) n)
= |00000000|00000003|00000002|FFFFFFFE|FFFFFFFF|
? (BnCompare n 0 2 n 0 2)
= 0
? (BnCompare n 0 1 n 1 1)
= 1
? (BnCompare n 1 1 n 0 1)
= -1
? (BnCompare n 2 3 n 0 2)
= -1
? (BnCompare n 3 2 n 0 2)
= -1
\end{verbatim}
\vspace*{24pt}
({\bf BnIsDigitOdd} {\em N nd})
\\[12pt]
La fonction {\bf BnIsDigitOdd} retourne la valeur 0 si le chiffre $N_{nd}$
est pair. Cette fonction test le bit de poids faible du chiffre $N_{nd}$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (BnIsDigitOdd n 0)
= 0
? (BnIsDigitOdd n 1)
= 255
? (progn (BnComplement n 0 2) n)
= |00000003|00000002|FFFFFFFE|FFFFFFFF|
? (BnIsDigitOdd n 0)
= 255
? (BnIsDigitOdd n 1)
= 0
\end{verbatim}
\vspace*{24pt}
({\bf BnNumDigits} {\em N nd nl})
\\[12pt]
La fonction {\bf BnNumDigits} retourne le nombre de chiffres significatifs du
sous-nombre $N_{nd,nl}$. Cette fonction retourne la valeur 1 pour le
cas particulier o\`u le sous-nombre $N_{nd,nl}$ vaut 0.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (setq n (BnCreate 'n 4))
= |00000000|00000000|00000000|00000000|
? (BnNumDigits n 0 4)
= 1
? (progn (BnSetDigit n 1 3) n)
= |00000000|00000000|00000003|00000000|
? (BnNumDigits n 0 3)
= 2
? (progn (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (BnNumDigits n 0 4)
= 4
? (BnNumDigits n 2 0)
= 1
\end{verbatim}
\vspace*{15pt}

\subsection{Fonctions logiques}
({\bf BnAndDigits} {\em N nd N md})
\\[12pt]
La fonction {\bf BnAndDigits} effectue le {\bf et logique} entre les chiffres
$N_{nd}$ et $M_{md}$, le chiffre r\'esultant est mis \`a la place du chiffre
$N_{nd}$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (progn (BnAndDigits n 3 n 1) n)
= |00000001|00000002|00000001|00000000|
? (progn (BnAndDigits n 0 n 2) n)
= |00000001|00000002|00000001|00000000|
\end{verbatim}
\vspace*{24pt}
({\bf BnOrDigits} {\em N nd M md})
\\[12pt]
La fonction {\bf BnOrDigits} effectue le {\bf ou logique} entre les chiffres
$N_{nd}$ et $M_{md}$, le chiffre r\'esultant est mis \`a la place du chiffre
$N_{nd}$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (progn (BnOrDigits n 3 n 1) n)
= |00000003|00000002|00000001|00000000|
? (progn (BnOrDigits n 0 n 2) n)
= |00000003|00000002|00000001|00000002|
\end{verbatim}
\vspace*{24pt}
({\bf BnXorDigits} {\em N nd M md})
\\[12pt]
La fonction {\bf BnXorDigits} effectue le {\bf ou exclusif logique} entre
les chiffres $N_{nd}$ et $M_{md}$, le chiffre r\'esultant est mis
\`a la place du chiffre $N_{nd}$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (progn (BnXorDigits n 3 n 1) n)
= |00000002|00000002|00000001|00000000|
? (progn (BnXorDigits n 0 n 2) n)
= |00000002|00000002|00000001|00000002|
\end{verbatim}
\vspace*{15pt}

\subsection{Affectations}
Les fonctions suivantes permettent de manipuler directement la repr\'esentation
interne des nombres.
\\[24pt]
({\bf BnSetToZero} {\em N nd nl})
\\[12pt]
La fonction {\bf BnSetToZero} remet \`a z\'ero le sous-nombre $N_{nd,nl}$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 7)) (for (i 0 1 6) (BnSetDigit n i i)) n)
= |00000006|00000005|00000004|00000003|00000002|00000001|00000000|
? (progn (BnSetToZero n 2 4) n)
= |00000006|00000000|00000000|00000000|00000000|00000001|00000000|
? (progn (BnSetToZero n 1 0) n)
= |00000006|00000000|00000000|00000000|00000000|00000001|00000000|
\end{verbatim}
\vspace*{24pt}
({\bf BnSetDigit} {\em N nd digit})
\\[12pt]
La fonction {\bf BnSetDigit} permet d'affecter le chiffre $N_{nd}$
\`a la valeur enti\`ere {\em digit}.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (setq n (BnCreate 'n 4))
= |00000000|00000000|00000000|00000000|
? (progn (BnSetDigit n 3 12) n)
= |0000000C|00000000|00000000|00000000|
? (progn (BnSetDigit n 0 255) n)
= |0000000C|00000000|00000000|000000FF|
\end{verbatim}
\vspace*{24pt}
({\bf BnAssign} {\em M md N nd nl})
\\[12pt]
La fonction {\bf BnAssign} transfert le sous-nombre $N_{nd,nl}$ dans le
sous-nombre $M_{md,nl}$ avec perte de l'ancien sous-nombre
$M_{md,nl}$. Le chevauchement des zones de transfert est valide.
Pour que le sous-nombre $M_{md,nl}$ soit valide, la condition suivante
doit \^etre v\'erifi\'ee\,:
\[ md + nl \leq size(M)\ .\]
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 7)) (for (i 0 1 6) (BnSetDigit n i i)) n)
= |00000006|00000005|00000004|00000003|00000002|00000001|00000000|
? (progn (setq m  (BnCreate 'n 9))
?        (for (i 0 1 8) (BnSetDigit m i (+ 10 i)))
?        m)
= |00000012|00000011|00000010|0000000F|0000000E|0000000D|0000000C|0000000B|0000000A|
? (progn (BnAssign m 1 n 2 4) m)
= |00000012|00000011|00000010|0000000F|00000005|00000004|00000003|00000002|0000000A|
? (progn (BnAssign m 0 m 1 3) m)
= |00000012|00000011|00000010|0000000F|00000005|00000004|00000004|00000003|00000002|
? (progn (BnAssign m 3 m 0 6) m)
= |0000000F|00000005|00000004|00000004|00000003|00000002|00000004|00000003|00000002|
? (progn (BnAssign m 3 m 0 0) m)
= |0000000F|00000005|00000004|00000004|00000003|00000002|00000004|00000003|00000002|
\end{verbatim}
\vspace*{15pt}

\subsection{Conversion en fix Le-Lisp}
En Le-Lisp, il n'est pas forcement possible de d\'efinir, comme un simple
entier, l'intervalle repr\'esentant les chiffres (i.e. les entiers compris
entre 0 et $B$). Le pr\'edicat suivant sp\'ecifie quels sont les chiffres
pouvant \^etre repr\'esent\'es par entier Le-Lisp. La taille, en nombre de bits,
des chiffres au del\`a de laquelle une conversion vers un entier Le-Lisp est
possible est d\'efinie par la constante\,: \verb+BN_WORD_SIZE+. Cette
constante vaut 15 pour la plupart des machines. L'implantation BigNum.c
suppose implicitement que les constantes \verb+BN_WORD_SIZE+ et
\verb+BN_DIGIT_SIZE+ ont la m\^eme valeur. Cette restriction permet de passer
directement les chiffres en param\`etres des primitives (au lieu d'utiliser
deux variables $N$ et $nd$ pour le chiffre $N_{nd}$).
\\[24pt]
({\bf BnDoesDigitFitInWord} {\em N nd})
\\[12pt]
La fonction {\bf BnDoesDigitFitInWord} retourne 0 si le chiffre $N_{nd}$
ne peut pas \^etre converti dans un entier Le-Lisp.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (BnDoesDigitFitInWord n 2)
= 1
? (progn (BnComplement n 0 3) n)
= |00000003|FFFFFFFD|FFFFFFFE|FFFFFFFF|
? (BnDoesDigitFitInWord n 2)
= 0
\end{verbatim}
\vspace*{24pt}
({\bf BnGetDigit} {\em n nd})
\\[12pt]
La fonction {\bf BnGetDigit} retourne le chiffre $N_{nd}$. Il n'est pas
v\'erifi\'e que ce dernier puisse \^etre repr\'esent\'e par un entier Le-Lisp (se
r\'ef\'erer \`a la fonction {\bf BnDoesDigitFitInWord}).
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (setq n (BnCreate 'n 4)) (for (i 0 1 3) (BnSetDigit n i i)) n)
= |00000003|00000002|00000001|00000000|
? (BnGetDigit n 2)
= 2
? (progn (BnComplement n 1 2) n)
= |00000003|FFFFFFFD|FFFFFFFE|00000000|
? (BnGetDigit n 2)
= -3.595385e+N8
\end{verbatim}
\vspace*{15pt}

\subsection{Cr\'eation et gestion}
Les fonctions d'ordre plus g\'en\'eral, du module \verb+Bn+ sont\,:
\\[24pt]
({\bf BnAlloc} {\em size})
\\[12pt]
La fonction {\bf BnAlloc} alloue la place pour un nombre pouvant contenir
au plus {\em size} chiffres. On impose que {\em size} soit un nombre
{\em strictement positif}.
Les valeurs des chiffres du nombre rendu en r\'esultat par la fonction
{\bf BnAlloc} sont impr\'evisibles.
\\[24pt]
({\bf BnCreate} {\em type size})
\\[12pt]
La fonction {\bf BnCreate} alloue la place pour un nombre pouvant contenir
au plus {\em size} chiffres, initialise le type de ce nombre \`a
{\em type} et initialise tous les chiffres du nombre \`a 0. On impose que
{\em size} soit un nombre {\em strictement positif}.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BnCreate 'n 4)
= |00000000|00000000|00000000|00000000|
\end{verbatim}
\vspace*{24pt}
({\bf BnSetType} {\em N type})
\\[12pt]
La fonction {\bf BnSetType} permet de modifier le champ {\em type} du nombre
$N$. La sp\'ecification de \verb+KerN+ n'utilise pas pour ses besoins
propres le type d'un nombre, mais ce champ donne la possibilit\'e de
d\'efinir, dans des librairies de plus haut niveau, des fonctions
g\'en\'eriques, c'est \`a dire des fonctions ayant des comportements
diff\'erents selon le type de ses arguments. Par exemple le champ {\em type}
peut contenir le signe d'un nombre.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (BnSetType (BnAlloc 8) 'bar) 'ok)
= ok
\end{verbatim}
\vspace*{24pt}
({\bf BnGetType} {\em N})
\\[12pt]
La fonction {\bf BnGetType} retourne le type associ\'e au nombre $N$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (progn (BnSetType (setq n (BnAlloc 8)) 'foo) (BnGetType n))
= foo
? (progn (BnSetType n 'bar) (BnGetType n))
= bar
\end{verbatim}
\vspace*{24pt}
({\bf BnGetSize} {\em N})
\\[12pt]
La fonction {\bf BnGetSize} retourne le nombre de chiffres disponibles dans
le nombre $N$. Il n'est pas possible de changer dynamiquement la
taille d'un nombre; ainsi, pour un m\^eme nombre, {\bf BnGetSize} retourne
toujours la m\^eme valeur.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BnGetSize (BnAlloc 8))
= 8
\end{verbatim}
\vspace*{24pt}

\section{Allocation des r\'esultats\,:\,Bz}
Le niveau \verb+Bz+ est conceptuellement plus simple que celui de \verb+Bn+.
Un nombre $z \in Z$ est repr\'esent\'e par un BigNum dont le champ type
contient le signe de l'entier.
Les fonctions de \verb+Bz+ sont sans effet de bord, et allouent l'espace
m\'emoire pour leurs r\'esultats. Toutes les fonctions de ce niveau sont
directement interfac\'ees avec l'arithm\'etique g\'en\'erique de Le-Lisp.

\subsection{Fonctions arithm\'etiques}
({\bf BzAbs} {\em Z})
\\[12pt]
La fonction {\bf BzAbs} retourne la valeur absolue du nombre $Z$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BzAbs 1234567890123)
= 1234567890123
? (BzAbs -1234567890123)
= 1234567890123
? (BzAbs #{0})
= 0
\end{verbatim}
\vspace*{24pt}
({\bf BzSign} {\em Z})
\\[12pt]
La fonction {\bf BzSign} retourne -1 si le nombre $Z$ est strictement
n\'egatif, 0 si ce nombre est nul et 1 si ce nombre est strictement positif.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BzSign 1234567890123)
= 1
? (BzSign -1234567890123)
= -1
? (BzSign #{0})
= 0
\end{verbatim}
\vspace*{24pt}
({\bf BzNegate} {\em Z})
\\[12pt]
La fonction {\bf BzNegate} retourne l'oppos\'e du nombre $Z$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BzNegate 1234567890123)
= -1234567890123
? (BzNegate -1234567890123)
= 1234567890123
? (BzNegate #{0})
= 0
\end{verbatim}
\vspace*{24pt}
({\bf BzCompare} {\em Y Z})
\\[12pt]
La fonction BzCompare retourne -1 si le nombre $Y$ est strictement
plus petit que le nombre $Z$, 0 si ces deux nombres sont \'egaux et
1 si le nombre $Y$ et strictement plus grand que le nombre
$Z$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BzCompare 1234567890123 1234567890123)
= 0
? (BzCompare 1234567890123 123456789)
= 1
? (BzCompare 1234567890123 -1234567890123)
= 1
? (BzCompare -1234567890123 -123456789)
= -1
\end{verbatim}
\vspace*{24pt}
({\bf BzAdd} {\em Y Z})
\\[12pt]
La fonction {\bf BzAdd} retourne un nombre repr\'esentant la somme des nombres
$Y$ et $Z$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BzAdd 1234567890123 123456789)
= 1234691346912
? (BzAdd 1234567890123 -1234567890123)
= 0
? (BzAdd -1234567890123 -123456789)
= -1234691346912
\end{verbatim}
\vspace*{24pt}
({\bf BzSubtract} {\em Y Z})
\\[12pt]
La fonction {\bf BzSubtract} retourne un nombre repr\'esentant la diff\'erence
des nombres $Y$ et $Z$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BzSubtract 1234567890123 123456789)
= 1234444433334
? (BzSubtract 1234567890123 -1234567890123)
= 2469135780246
? (BzSubtract -1234567890123 -123456789)
= -1234444433334
\end{verbatim}
\vspace*{24pt}
({\bf BzMultiply} {\em Y Z})
\\[12pt]
La fonction {\bf BzMultiply} retourne un nombre repr\'esentant le produit
des nombres $Y$ et $Z$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BzMultiply 1234567890123 123456789)
= 152415787517090395047
? (BzMultiply 1234567890123 -1234567890123)
= -1524157875322755800955129
? (BzMultiply -1234567890123 -123456789)
= 152415787517090395047
\end{verbatim}
\vspace*{24pt}
({\bf BzDivide} {\em Y Z})
\\[12pt]
La fonction {\bf BzDivide} effectue la division du nombre $Y$ par le
nombre $Z$ et en retourne le quotient.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BzDivide 1234567890123 123456789)
= 10000
? (BzDivide 1234567890123 -1234567890123)
= -1
? (BzDivide -1234567890123 -123456789)
= 10001
\end{verbatim}
\vspace*{24pt}
({\bf BzMod} {\em Y Z})
\\[12pt]
La fonction {\bf BzMod} effectue la division du nombre $Y$ par le
nombre $Z$ et en retourne le reste.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BzMod 1234567890123 123456789)
= 123
? (BzMod 1234567890123 -1234567890123)
= 0
? (BzMod -1234567890123 -123456789)
= 123456666
\end{verbatim}
\vspace*{15pt}

\subsection{Cr\'eation}
({\bf BzCreate} {\em size})
\\[12pt]
La fonction {\bf BzCreate} alloue la place pour un nombre pouvant contenir
au plus {\em size} chiffres et initialise tous les chiffres du nombre \`a 0.
On impose que {\em size} soit un nombre {\em strictement positif}.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BzCreate 4)
= 0
\end{verbatim}
\vspace*{24pt}
({\bf BzCopy} {\em Z})
\\[12pt]
La fonction {\bf BzCopy} retourne une copie du nombre $Z$.
\\[18pt]
{\bf Exemple\,:}
\begin{verbatim}
? (BzCopy 1234567890123)
= 1234567890123
? (BzCopy -1234567890123)
= -1234567890123
? (BzCopy #{0})
= 0
\end{verbatim}
\vspace*{15pt}

\subsection{Lecture et \'ecriture}
Les nombres de BigNum peuvent \^etre lus et \'ecrits comme les petits entiers
Le-Lisp. N\'eanmoins certaines restrictions du syst\`eme d'entr\'ee-sortie
de Le-Lisp nous ont contraint \`a introduire la notation $\#\{Digit*\}$.
Les restrictions sont les suivantes\,:
\begin{enumerate}
  \item
    Les nombres de BigNum ne peuvent pas \^etre lus de mani\`ere standard
    lorsque la base des nombres en entr\'ee est diff\'erente de dix.
  \item
    L'impression d'un nombre comportant trop\footnote{Le {\em trop} est
    d\'ependant de la valeur de la marge droite et de la taille maximum d'un
    symbole} de chiffres peut faire appara\^{\i}tre des caract\`eres parasites
    de fin de ligne. De plus, du fait de la pr\'esence de ces caract\`eres
    parasites, la relecture d'un nombre, \`a partir de sa repr\'esentation
    externe, peut provoquer des erreurs.
\end{enumerate}
La notation $\#\{Digit*\}$ permet\,:
\begin{enumerate}
  \item
    De lire un nombre dans la base en entr\'ee courante.
  \item
    D'ignorer les caract\`eres ne faisant pas parti des chiffres admissibles
    par la base en entr\'ee courante. Ceci permet, entre autre, de scinder
    les grands nombres en plusieurs lignes.
  \item
    D'imprimer, lorsque la variable Le-Lisp \verb+#:system:print-for-read+
    est positionn\'ee, des nombres qui seront ult\'erieurement relisible.
\end{enumerate}
Voici une petite session mettant en jeu les diff\'erents points \'enonc\'es
ci-dessus\,:
\\[18pt]
\begin{verbatim}
? 29348092384092384506795626345             ; lecture en standard.
= 29348092384092384506795626345
? (ibase 16)                                ; on change de base.
= 16
? add                                       ; Pour les petits ca passe.
= 2781
? decede                                    ; Pour les gros ca casse.
= -12578
? #{decede}                                 ; En fait il faut lire.
= 14601950
? (ibase a)                                 ; Repasse en base 10.
= 10
? (defun foo ()
?    ; Ecrit et relit le meme nombre.
?    (with ((outchan (openo "/tmp/foo")))
?       (print (** (** (** (** 2 3) 4 ) 5) 6))
?       (close (outchan)) )
?    (with ((inchan (openi "/tmp/foo")))
?       (untilexit eof (print (read)) (print "another")) ))
= foo
? (foo)
234854258277383322788948059678933702737568254890831987070729097153220902511460
another
8443463698998384768703031934976
another
= 8
? (setq #:system:print-for-read t)
= t
? (foo)
#{2348542582773833227889480596789337027375682548908319870707290971532209025114
608443463698998384768703031934976}
"another"
= 8
? #{123 456 ;on met des espaces tous les 3 caracteres
? 789
? }
= #{1234563789}
? (obase (ibase 16))
= 16
? #{123 456 ;on met des espaces tous les 3 caracteres
? 789
? }
= #{123456EDEEACEE3CAACEE789}
\end{verbatim}

\newpage

\section{Remerciements}
Patrice Bertin, Hans Boehm, Jerome Chailloux, Michel Gangnet and Mark Shand
ont contribu\'e \`a la
r\'ealisation de ce module. Qu'ils en soient remerci\'es ici.

\section{Bibliography}

\begin{description}

\item [{[Chailloux 87]}]
J\'er\^ome Chailloux, Matthieu Devin, Francis Dupont, Jean-Marie Hullot, Bernard Serpette, Jean Vuillemin.
{\em Le-Lisp version 15.2, le Manuel de r\'ef\'erence.}
Documentation INRIA, Mai 1987.

\item [{[Knuth]}]
D. E. Knuth,
{\em The Art of Computer Programming, vol. 2, Seminumerical Algorithms.}
Addison Wesley, 1981.

\end{description}

\section{Distribution du module}
Ce document, et les sources du module BigNum porte la mention
"Copyright Digital Equipment Corporation \& INRIA 1988, 1989".
Cette documentation et les sources du module BigNum peuvent \^etre
obtenus, en contactant par courrier \'electronique ou postal,:
\begin{verbatim}
    Digital P.R.L.,
    Attn Librarian,
    85, Avenue Victor Hugo,
    92563 Rueil Malmaison Cedex. France.          (adresse postale)

    librarian@decprl.dec.com                      (adresse electronique)
\end{verbatim}
  ou,:
\begin{verbatim}
    I.N.R.I.A.,
    A l'attention de B. Serpette,
    Domaine de Voluceau,
    78150, Rocquencourt, France.                 (adresse postale)

    serpette@inria.inria.fr                      (adresse electronique)
\end{verbatim}
La documentation et les sources du module BigNum peuvent \^etre
librement reproduites et distribu\'ees moyennant les conditions
suivantes\,:
\begin{itemize}
  \item Digital PRL ou l'INRIA doivent \^etre avertis de la copie.

  \item La mention du {\em copyright} ne doit en aucun cas \^etre enlev\'ee
    de la documentation et des sources.

  \item Tout travail incorporant le module BigNum devra mentionner
    explicitement l'utilisation de ce module et son origine en incluant cette
    phrase\,: {\em Ce travail utilise le module BigNum d\'evelopp\'e
    conjointement par l'INRIA et Digital PRL.}

  \item Toutes les modifications effectu\'ees sur le module BigNum devront
    \^etre explicitement notifi\'ees par la nature de la modification, son
    auteur et son adresse. Ces notifications ne pourront \^etre enlev\'ees
    des distributions futures.

  \item Tout travail utilisant intensivement le module BigNum peut \^etre
    librement distribu\'e sous les m\^emes conditions de distribution que le
    module BigNum.
\end{itemize}
L'INRIA et Digital Equipment Corporation n'offrent aucune garantie, implicite
ou explicite, sur cette documentation et sur le logiciel qu'elle d\'ecrit, en
ce qui concerne la diffusabilit\'e ou l'ad\'equation \`a une utilisation
particuli\`ere. l'INRIA et Digital Equipment Corporation ainsi que les
distributeurs \`a venir ne seront en aucun cas responsables des dommages
produits.

\tableofcontents

\end{document}
