1 \section{Représentation des nombres entiers}
5 \begin{Def}[Principe de la numération de position]
6 \index{Principe de la numérotation de position}
7 Il consiste à choisir une base $b$ de numération, et $b$ symboles qui constitueront les chiffres dans la représentation d'un entier positif en base $b$.
8 Celle-ci s'écrira alors
9 $$n=n_{p}b^p+n_{p-1}b^{p-1}+\cdots+n_{1}b^1+n_{0}$$
11 Cette écriture est abrégée en ${\left(\overline{n_{p}n_{p-1}\ldots n_{0}}\right)}_{b}$.
14 En informatique, on utilise couramment les bases 2, 8 et 16.
20 L'algorithme pour obtenir la représentation en base $b$ d'un entier est :
23 \item Effectuer la division euclidienne de cet entier par $b$, division qui donne un premier quotient et un premier reste.
24 \item Le quotient est à sont tour divisé par $b$ pour donner un second quotient et un second reste, et ainsi de suite jusqu'à obtenir un quotient nul.
25 \item Les restes successifs (tous strictement inférieurs à $b$), et en commençant par le dernier, constituent la représentation en base $b$ de l'entier donné.
29 Donner la représentation de 23 en base 2.
34 \begin{Exo}[Numération, changements de base]
36 \item Chercher les entiers dont le carré a, en représentation décimale,
37 le même chiffre pour les dizaines et les unités.
38 \item On pose $a=2p-1$, $b=2p+1$, $c=2p+3$; trouver l'entier $p$ de manière que $a^2+b^2+c^2$ soit de la forme $\sur{xxxx}_{10}$.
39 \item L'entier $n$ s'écrit $\sur{341}_{10}$ et $\sur{2331}_a$. Trouver $a$.
40 \item Montrer que, dans toute base $b$ supérieure ou égale à 3, l'entier qui s'écrit $\sur{11211}_b$ n'est pas premier.
41 \item Soit $n\geqslant 7$. Donner l'écriture de $(n+1)^4$ en base $n$.
47 \begin{Exo}[Développement décimal]
48 On considère le nombre réel $x$ dont le dé\-ve\-lop\-pe\-ment décimal s'écrit $x=0,012\ 345\ 679\ 012\ 345\ 679\ \ldots\ \ldots\ \ldots$ (la séquence $012\ 345\ 679$ est reproduite indéfiniment). Ce développement décimal est périodique, de période 9.
51 vérifie une équation de la forme $10^kx=n+x$, où $k$ et $n$ sont
52 des entiers à déterminer. En résolvant cette équation,
53 montrer que $x$ est un nombre rationnel, et le mettre sous la forme
54 $x= \fr pq$ , où $p$ et $q$ sont premiers entre eux.
56 la même méthode au ``nombre" $y$ dont le développement
57 décimal est $y= 0,999\ 999\ 999\ 999\ \ldots$ (périodique de période
58 1). Quelle conclusion peut-on en tirer?
59 \item Démontrer que tout nombre réel dont le développement
60 décimal est fini ou périodique à partir d'un certain rang
61 est un nombre rationnel.
62 \item Réciproquement, on se propose de démontrer que le
63 développement décimal de tout nombre rationnel est fini ou
64 périodique à partir d'un certain rang. Pour cela, on
65 considère un rationnel $x=\fr pq$ , avec $q>0$, $p\in
66 \Z$, $p$ et $q$ premiers entre eux, et on étudiera successivement
69 \item $x$ est entier (c'est à dire $q=1$).
70 \item $x$ est rationnel non entier, et $q$ est premier avec 10 (On
71 pourra montrer que, si $q$ est premier avec 10, il existe un entier
72 $k$, non nul, tel que $10^k\equiv 1\ [q]$).
73 \item $x$ est rationnel non entier, mais $q$ n'est pas premier avec 10.
81 \section{Arithmétique en informatique}
84 La plupart des langages de programmation utilisés en informatique disposent d'un type de données pour représenter ce que les informaticiens appellent les entiers signés (les entiers relatifs) et possèdent des opérateurs pour effectuer les calculs classiques sur ces nombres.
86 \subsection{Division entière}
88 En C ou java, par exemple, le symbole $/$ représente le quotient dans la \og division entière\fg{} et le symbole $\%$ représente ce que les informaticiens appellent improprement le modulo (le reste dans leur \og division entière\fg{} ).
91 Pour des raisons pratiques de réalisation des micro-circuits des processeurs qui réalisent ces opérations, la \og division entière\fg{} ne donne pas exactement le même résultat que la division euclidienne.
95 Considérons par exemple les 4 cas possibles de division euclidienne de $a$ par $b$ lorsque $|a|=29$ et $|b|=7$ (en n'oubliant pas que le reste d'une division euclidienne ne peut être que positif)
99 \begin{tabular}{|c|c|c|c|c|c|c|}
101 $a$ & $b$ & division euclidienne & $q$ & $r$ & $a/b$ & $a\%b$ \\ \hline
102 $29$ &$7$ & $29=4\times 7+1$ & $4$ & $1$ & $4$ & $1$ \\ \hline
103 $29$ &$-7$ & $29=(-4)\times (-7)+1$ & $-4$ & $1$ & $-4$ & $1$ \\ \hline
104 $-29$ &$7$ & $-29=(-5)\times 7+6$ & $-5$ & $6$ & $-4$ & $-1$ \\ \hline
105 $-29$ &$-7$ & $-29=5\times (-7)+6$ & $5$ & $6$ & $4$ & $-1$ \\ \hline
111 Autrement dit, mathématiquement, le quotient est positif lorsque les deux nombres ont le même signe et le reste est toujours positif, et, pour que le reste soit toujours positif, le quotient peut ne pas être le quotient des valeurs absolues.
114 Informatiquement, le \og quotient\fg{} est positif lorsque les nombres ont le même signe, le \og reste\fg{} a le signe du dividende, et la valeur absolue du \og quotient\fg{} est toujours le quotient des valeurs absolues.
117 Dans les applications de calcul arithmétique, par exemple un calcul de PGCD, ce n'est pas gênant parce que les restes \og informatiques\fg{} sont congrus aux restes mathématiques modulo la valeur absolue du
118 diviseur, et qu'il ne s'agit alors que du choix d'un représentant de la classe concernée (addition et multiplication étant compatibles avec la congruence modulo $n$).
120 Mais il faut quand même savoir que l'on peut obtenir un \og reste\fg{} négatif et prendre ses dispositions le cas échéant...
123 \subsection{Arithmétique modulo $2^n$}
127 Les calculs sur les entiers, dans un ordinateur, se font dans $\Z/2^n\Z$, où $n$ est le nombre de bits utilisés dans la représentation de ces nombres.
130 Dans la plupart des microprocesseurs, les entiers sont représentés sur 64 bits, les calculs se font donc dans $\Z/2^{64}\Z$.
133 Disposer d'entiers signés ou d'entiers non signés est uniquement une question de choix du représentant dans les classes d'équivalence, mais
134 la représentation physique est la même.
137 Comme il nous est difficile de représenter ici la liste compléte de tous ces entiers, nous allons illustrer ce propos en supposant que les entiers sont représentés sur 4 bits.
138 Pour des mots de 4 bits, il y a alors 16 entiers représentables : (a.s.= arithmétique signée, a.n.s. = arithmétique non signée)
140 \begin{center}\begin{tabular}{|c|c|c|c|} \hline
141 code binaire & & a.s. & a.n.s. \\ \hline
142 0000 & interprété par & 0 & 0 \\ \hline
143 0001 & interprété par & 1 & 1 \\ \hline
144 0010 & interprété par & 2 & 2 \\ \hline
145 0011 & interprété par & 3 & 3 \\ \hline
146 0100 & interprété par & 4 & 4 \\ \hline
147 0101 & interprété par & 5 & 5 \\ \hline
148 0110 & interprété par & 6 & 6 \\ \hline
149 0111 & interprété par & 7 & 7 \\ \hline
150 1000 & interprété par & 8 & -8 \\ \hline
151 1001 & interprété par & 9 & -7 \\ \hline
152 1010 & interprété par & 10 & -6 \\ \hline
153 1011 & interprété par & 11 & -5 \\ \hline
154 1100 & interprété par & 12 & -4 \\ \hline
155 1101 & interprété par & 13 & -3 \\ \hline
156 1110 & interprété par & 14 & -2 \\ \hline
157 1111 & interprété par & 15 & -1 \\ \hline
158 \end{tabular}\end{center}\vskip 10pt
161 Pourquoi ce choix ? Pourquoi ne pas avoir, en a.s., représenté les entiers dans l'ordre croissant de 0000 (-8) à 1111 (7)?
164 \item Tout simplement pour des raisons d'efficacité : 0 doit toujours être représenté par le code \og nul\fg{} 0000.
165 \item Ensuite, il faut pouvoir comparer efficacement ces codes entre eux, ce qui explique que 0 doit être suivi de 1, arithmétique signée ou pas.
170 Ces principes ont ainsi conduit à placer les codes interprétés comme entiers négatifs après ceux qui représentent les entiers positifs.
173 Par ailleurs, on s'aperçoit que, de cette manière, les codes des entiers
174 négatifs commencent tous par 1.
175 On parle improprement de \og bit de signe\fg{}\index{bit de signe}: s'il s'agissait d'un véritable bit de signe, le code 1001 devrait être celui de -1, or c'est celui de -7.
176 Mais il n'en reste pas moins que tous les entiers négatifs commencent par 1).
179 Ainsi, il est facile de déduire la comparaison signée de la comparaison non signée : les codes qui commencent par 1 sont \og plus petits\fg{} que ceux qui commencent par 0, et, s'ils commencent par le même bit, c'est la comparaison non signée qui peut être utilisée.
185 Pour l'addition et la soustraction, les opérations et les tests de validité des résultats sont les mêmes en arithmétique signée et non signée.
186 Pour la multiplication, l'instruction n'est pas la même (le dépassement de capacité doit être ignoré en a.s. dans le dernier exemple).
190 Premiers résultats, corrects :
193 \begin{tabular}{r | r | r}
194 Opération binaire & Entiers non signés & Entiers signés \\
197 \underline{+ 1001} & \underline{+ 9} & \underline{+(-7)} \\
205 Un résultat correct en arithmétique non \break signée, et négatif en arithmétique signée, mais correct modulo 16 (-6 et 10 sont dans la même classe, mais cette classe est représentée par 10 en a.n.s. et par -6 en a.s.) :
207 \begin{tabular}{r | r | r}
208 Opération binaire & Entiers non signés & Entiers signés \\
211 \underline{+ 0110} & \underline{+ 6} & \underline{+ 6} \\
219 Un dépassement de capacité dans les deux cas, mais le résultat est correct modulo 16 : les classes de 21, de -11 et de 5 sont les mêmes :
221 \begin{tabular}{r | r | r}
222 Opération binaire & Entiers non signés & Entiers signés \\
225 \underline{+ 1001} & \underline{+ 9} & \underline{+(-7)} \\
229 Le résultat (correct modulo 16) est disponible dans tous les cas, les \og dépassement de capacité\fg{} et \og résultat négatif\fg{} sont signalés par le positionnement d'un bit dans un registre spécial.
236 Un résultat correct en a.n.s., résultat négatif en a.s., mais correct modulo 16 :
238 \begin{tabular}{r | r | r}
239 Opération binaire & Entiers non signés & Entiers signés \\
242 \underline{$\times$ 0010} & \underline{$\times$ 2} &
243 \underline{$\times$ 2} \\ 1010 & 10 & (-6) \\
250 Dépassement de capacité dans les deux cas, résultat négatif en a.s., mais résultat correct modulo 16, compte tenu du choix des représentants dans les deux arithmétiques:
252 \begin{tabular}{r | r | r}
253 Opération binaire & Entiers non signés & Entiers signés \\
256 \sou{$\times$ 0110} & \sou{$\times$ 6} & \sou{$\times$ 6} \\
257 (1)1110 & 14 & (-2) \\
266 Dépassement de capacité dans les deux cas, résultat correct en a.s., correct modulo 16 en a.n.s.
268 \begin{tabular}{r | r | r}
269 Opération binaire & Entiers non signés & Entiers signés \\
272 \sou{$\times$ 1110} & \sou{$\times$ 14} & \sou{$\times$
273 (-2)} \\ (1011)0110 & 6 & 6 \\
277 \centerline{\x{Fin du Chapitre}}
