\newpage
\section{De Rekenkunde van de Computer}

%-------------------------------------
%               CHRIS
%-------------------------------------

\subsectionauthor[C.S. Bras]{Optellen en Aftrekken}
Optellen wordt door de computer op dezelfde manier gedaan als dat wij dat gewend zijn te doen. Van rechts naar links wordt er per bit individueel opgeteld. Als het resultaat hieruit groter is dan 1, wordt het overschot bij de volgende significantie opgeteld. 
%\newline
\paragraph{}
\noindent
Aftrekken kan zowel door per bit het aftrekken te verrichten zoals wij dit gewend zijn in het decimale stelsel, evenals door de twee-complement variant van het getal er bij op te tellen wat in essentie dus het optellen van de negatieve tegenpool is.
\newline
\newline
Overflow bij optellen kan alleen gebeuren wanneer twee getallen dezelfde \textit{sign} hebben, wanneer dit niet het geval is zal het resultaat altijd binnen de twee begin waardes liggen en dus niet \textit{overflowen}. Bij aftrekken is dit precies andersom, overflow kan alleen voorkomen bij getallen met een ander \textit{sign}.
\newline
\newline
Om te kijken bij een \textit{signed} getal of \textit{overflow} dan toch gebeurd is, wordt er gekeken naar het \textit{sign} bit. Wanneer overflow voorkomt zal deze namelijk niet meer de waarde aannemen van het correcte \textit{sign} maar zal de waarde aannemen van het resultaat.
% \begin{figure}[h]
% \includegraphics{Tabel.png}
% \caption{Tabel met verwachte waardes om te zien wanneer overflow gebeurd is.}
% \label{fig:figure2}
% \end{figure}

\begin{table}[h]
\centering
\noindent
\newline
\begin{tabular}{|c|c|c|c|}
\hline
%\rowcolor[HTML]{BBDAFF} 
\rule{0pt}{4mm} Bewerking & Waarde A & Waarde B & Uitkomst bij overflow	 \\ \hline 
\rule{0pt}{4mm} A $+$ B     & $\geq$ 0   & $\geq$ 0   & $<$ 0            \\ \hline
\rule{0pt}{4mm} A $+$ B     & $<$ 0      & $<$ 0      & $\geq$ 0         \\ \hline
\rule{0pt}{4mm} A $-$ B     & $\geq$ 0   & $<$ 0      & $<$ 0      		 \\ \hline
\rule{0pt}{4mm} A $-$ B     & $<$ 0      & $\geq$ 0   & $\geq$ 0         \\ \hline
\end{tabular}
\caption{Tabel met verwachte waardes om overflow te constateren. \newline}
\label{tab:title}
\end{table}

Aangezien \textit{unsigned} getallen ook vaak gebruikt worden als geheugen adressen, waarbij \textit{overflow} genegeerd wordt, heeft MIPS verschillende instructies om op te tellen en af te trekken zonder rekening te houden met \textit{overflow} (ADDU, ADDIU, SUBU) evenals instructies die gebruikt worden als er wel rekening moet worden gehouden met \textit{overflow} (ADD, ADDI, SUB).

\newpage
\subsectionauthor[C.S. Bras]{Vermenigvuldigen}
Computers voeren vermenigvuldigingen door een reeks optellingen en shift operaties toe te passen op de waardes waarmee gerekend wordt. Per iteratie wordt er gekeken naar de minst significante bit van de vermenigvuldiger, als deze 1 is wordt het vermenigvuldigtal bij het product opgeteld, met 0 gebeurt er niets. Hierna wordt het vermenigvuldigtal een positie naar links \textit{geshift} terwijl de vermenigvuldiger een positie opschuift naar rechts en wordt alles nogmaals uitgevoerd, net zolang totdat elke bit van de vermenigvuldiger gedaan is.

\begin{figure}[H]
\noindent
\includegraphics[width=\textwidth]{Vermenigvuldig}
\caption{Handelingen voor vermenigvuldigen in een schema.}
\label{fig:figure1}
\end{figure}

\noindent
\newpage
Snelheid wordt behaald door stappen van dit schema parallel uit te voeren, zo worden de registers met de waardes \textit{geshift} terwijl de optelling verricht wordt voor het product.

\noindent
Een vermenigvuldiging heeft als product een getal ter grootte van de som van het aantal bits van de beginwaardes, dit betekent dus dat een 32-bit getal een product van 64-bits oplevert. In de MIPS architectuur worden hiervan de meest significante bits opgeslagen in het \textbf{HI} register en de minst significante bits in het \textbf{LO} register. Ondanks dat het product 64 bits lang is, is er maar een 32-bit ALU nodig omdat er alleen maar gerekend wordt met 32-bit getallen.

Verdere snelheidswinst kan behaald worden door meerdere optel units te gebruiken om zo in plaats nog meer handelingen parallel te kunnen verrichten.

\begin{figure}[H]
\noindent
\includegraphics[width=\textwidth]{Parallel}
\caption{Meerdere optel units als grote vertakking om snelheid van een vermenigvuldiging te verhogen.}
\label{fig:figure2}
\end{figure}

\subsubsection{Negatief Vermenigvuldigen}
Om negatieve getallen te vermenigvuldigen worden eerst de waardes omgezet naar de positieve tegenhangers, daarna worden de benodigde handelingen om te vermenigvuldigen slechts 31 keer gedaan en tijdens de shifts worden de signs behouden, zo blijft de sign-bit buiten de berekening. Aan de hand van de initiële waardes van de sign-bits wordt bepaald welke waarde de sign-bit moet hebben van de uitkomst. 

\subsectionauthor[C.S. Bras]{Delen}
Delen bestaat evenals vermenigvuldigen voor een computer uit een langere reeks aan simpelere handelingen. In plaats van optellen, maakt de computer gebruik van aftrekken. Dit wordt gedaan door telkens te kijken naar welke significantie de deler geshift kan worden terwijl deze nog past in het deeltal, dit wordt er dan vanaf getrokken en in het resultaat wordt de bit waarvan de significantie overeen komt met het aantal shifts naar links op 1 gezet. Dit herhaalt zichzelf totdat de deler niet meer past in het getal dat is overgebleven van het deeltal en er dus een rest over blijft. Dit is dus eigenlijk een staartdeling.

\begin{figure}[H]
\noindent
\includegraphics[width=\textwidth/2]{Delen}
\caption{Een uitwerking van een staartdeling.}
\label{fig:figure3}
\end{figure}

De hardware die dit moet uitvoeren, moet over een aantal functies beschikken. De deler begint in de meest significante positie en wordt elke iteratie een positie naar rechts geshift terwijl het quotiënt begint in de minst significante positie en wordt telkens naar links geshift. Tijdens elke iteratie wordt gekeken of de resulterende waarde na het aftrekken kleiner is dan 0 door naar de sign bit te kijken, als dit het geval is betekent dit dat de deler in deze significante positie niet past en dus moet deze er weer bij opgeteld worden om terug te komen bij het getal waarmee deze iteratie begon. Dit staat allemaal beschreven in het figuur hieronder.

\begin{figure}[H]
\noindent
\includegraphics[width=(\textwidth/4) * 3]{Deel_Algoritme}
\caption{Een schema van het algoritme dat gebruikt wordt om te delen}
\label{fig:figure4}
\end{figure}

Net als vermenigvuldigen geeft delen ook een 64-bit resultaat wanneer er gedeeld wordt met twee 32-bit getallen, echter is het ditmaal verdeeld onder het quotiënt en de rest die overblijft na het delen. Net zoals bij het vermenigvuldigen is er ook geen 64-bit ALU maar een 32-bit variant omdat de shifts tijdens het aftrekken al worden uitgevoerd en er dus geen 64 bits aan ruimte nodig is bij het aftrekken.

\subsubsection{Negatief Delen}
Negatieve getallen kunnen gedeeld worden door de signs van het deeltal en de deler te onthouden en vervolgens de positieve varianten van deze waardes tegen elkaar te delen zoals hiervoor beschreven is. Dit brengt echter een paar dingen met zich mee waar op gelet moet worden, het meest belangrijk zijnde het juiste sign plaatsen bij het restgetal zodat de formule \textit{Deeltal $=$ Deler $\cdot$ Quotiënt $+$ Rest} geldig blijft maar er niet voor zorgt dat de absolute waarde van het quotiënt verandert doordat de sign van de deler of het deeltal verandert.

\subsubsection{Snelheidsverbeteringen}
In tegenstelling tot vermenigvuldigen kunnen er niet een hele hoop optel units achter elkaar gezet worden die meerdere deelstappen tegelijk uitvoeren omdat de sign bit van het resultaat bekend moet zijn om de volgende stap te bepalen. Een manier om toch een hogere snelheid te behalen is door te werken met voorspellende hardware die door middel van een look-up tabel probeert te voorspellen wat de waarde gaat zijn, dit heet de \textit{SRT divison technique}. De snelheidswinst die dit oplevert wordt vooral bepaald door de kwaliteit van de tabel waarin gezocht wordt.

\subsubsection{Delen in MIPS}
In MIPS kun je de instructies DIV en DIVU gebruiken om respectievelijk een signed en een unsigned integer te delen. Het resultaat wordt net zoals bij een vermenigvuldiging opgeslagen in het HI en LO register en dus zullen deze opgehaald moeten worden met de MFHI en MFLO instructies.

\subsectionauthor[R. van den Berge]{Floating Point}

Programmeertalen ondersteunen kommagetallen, welke reële getallen worden genoemd in de wiskunde. Een paar voorbeelden van reële getallen zijn $\pi$, $e$, $0.000000001$ $1.0 \cdot 10^{-9}$ en $3,155,760,000$ ofwel $3.15576 \cdot 10^{-9}$.  Het laatste getal is groter dan dat een integer kan bevatten. Het getal is geschreven in de \textbf{wetenschappelijke notatie}, wat inhoudt dat er één getal voor de komma staat en er een maal $10$x wordt toegepast afhankelijk van het aantal cijfers voor of achter de komma van het originele getal. Een getal dat voor de komma geen $0$ heeft staan, heet een \textbf{normalized} (gestandaardiseerd) getal. Dus $1.0 \cdot 10^{x}$ is een gestandaardiseerd getal, maar $10.0 \cdot 10^{x}$ en $0.1 \cdot 10^{x}$ bijvoorbeeld niet.

Net als decimale getallen kun je ook binaire getallen in de wetenschappelijke notatie schrijven. Om een binair getal in zijn gestandaardiseerde vorm te houden, moet je als basisgetal een getal nemen om bits te kunnen verschuiven, 2 dus. Je neemt dus $2$ als basisgetal in plaats van $10$.  Je krijgt dus $1.xxxxxxx \cdot 2^{yyyy}$. De gestandaardiseerde vorm en wetenschappelijke notatie gecombineerd bieden drie voordelen: Het maakt het data uitwisselen makkelijker met floating point getallen, het versimpelt de wiskundige algoritmes die van tevoren al weten dat ze te maken krijgen met deze notatie en het verhoogd de nauwkeurigheid waarmee de getallen kunnen worden opgeslagen.

Omdat je maar een beperkt aantal bits tot je beschikking hebt moet je een compromis maken tussen de grootte van de exponent en de getallen achter de komma. Ook moet worden aangegeven of het getal positief of negatief is. 

\begin{figure}[H]
\includegraphics[width=\textwidth]{3_5-1}
\caption{De floating point representatie.}
\label{fig:figure5}
\end{figure}

Van links naar rechts gelezen wordt de eerste bit dus gebruikt om aan te geven of het getal positief of negatief is. De volgende acht om de exponent aan te geven, de exponent wordt berekend door de getallen van de acht bits bij elkaar op te tellen $-127$ (min $0 - 127$ en max $256 - 127$ dus). Dan worden de laatste $23$  bits gebruikt om het getal achter de komma uit te rekenen. De vorm is dus 
$(-1)^{s} \cdot fraction \cdot 2^{exponent}$.

Op het moment dat er een te groot positief exponent wordt ingevoerd om met deze methode weer te geven vindt er een \textbf{overflow} plaats. Dit betekent dus dat het exponent te groot is om het getal met het aantal bits weer te geven. Een \textbf{underflow} is hetzelfde als een overflow maar dan bij te grote negatieve exponenten. Om de kans op overflow en underflow te verkleinen heb je ook een \textbf{double precision}. Het eerder besproken model heet de \textbf{single precision}. Bij de double precision wordt de exponent verhoogd naar $11$ bits en de fraction wordt eerst verkleind naar $(20)$ bits en daar worden vervolgens $32$ bits aan toegevoegd, een totaal van $52$ bits dus voor de fraction en $64$ bits voor het gehele getal.

Deze notatie gaat volgens de IEEE $(754)$ floating-point standard uitgevonden in $1980$ en sindsdien zit het in elke computer. De term significante cijfers (significand) wordt gebruikt om de fraction van $23$ of $52$ bits plus de s van $1$ bit aan te duiden, dus $23 + 1$ en $52 + 1$ significante cijfers zijn er beschikbaar bij floating point representation. IEEE $(754$) heeft ook een notatie voor een getal als $0/0$, NaN (not a number). De bedenkers van IEEE $754$ wilden dat het lezen van het getal voor bijvoorbeeld simpele vergelijkingen zoals kleiner of groter dan $0$ de bit voor een positief of negatief getal aan het begin hebben. Hierdoor hoeft bij zo'n vergelijking maar $1$ bit gelezen te worden. 

\newpage
\begin{figure}[H]
\noindent\includegraphics[width=\textwidth]{3-5_2}
\caption{Hier een voorbeeld van het omzetten van een decimaal getal naar de IEEE $754$ representatie.}
\label{fig:figure6}
\end{figure}



\subsubsection{Floating-Point additie}

Om de problemen te beschrijven met het optellen van getallen in wetenschappelijke notatie met floating-point additie is hier eerst een voorbeeld met normale getallen. Het gaat hier om $9.999 \cdot 10^{1} + 1.610 \cdot 10^{-1}$. Het uiteindelijke getal heeft maar $4$ significante cijfers en $2$ getallen voor het exponent.\\
\begin{enumerate}
\item De exponenten moeten gelijk woeden. $10^{-1}$ wordt $10^{1}$. Het getal wordt dus $0.01610 \cdot 10^{1}$.

\item Nu ga je de getallen bij elkaar optellen; $0.016 + 9.999 = 10.015$. De som is dus $10.015 \cdot 10^{1}$. 

\newpage

\item Dit getal moet opnieuw in wetenschappelijke notatie gezet worden. Het wordt dus $1.0015 \cdot 10^{2}$. Wanneer er zo'n geval is van verschuiven en exponenten vergroten moet er altijd worden gecheckt op een underflow of overflow. 

\item Omdat er maar 4 significante cijfers mogen zijn, moet het worden afgerond. $1.0015 \cdot 10^{2}$ wordt $1.002 \cdot 10^{2}$.
\end{enumerate}

\begin{figure}[H]
\begin{center}
\includegraphics[height=13cm,keepaspectratio]{3_5-4}
\end{center}
\caption{Het schema van floating-point additie.}
\label{fig:figure7}
\end{figure}

\subsubsection{Floating-Point vermenigvuldiging}

Bij getallen vermenigvuldigen met getallen in de wetenschappelijke notatie gaat het iets anders dan bij optellen. Hier het voorbeeld bij $1.110 \cdot 1010 \cdot 9.200 \cdot 10^{-5}$. Hier ook weer $4$ cijfers voor de significand en $2$ voor de exponent.

Stap 1: Je kan bij vermenigvuldigen de exponenten bij elkaar optellen. In dit geval $10 + -5 = 5$. Als je dit doet met een binair exponent dan moet je dus twee binaire exponenten bij elkaar optellen. In dit geval dus $10 + 127 + -5 + 127 = 259$. Dit is te groot om in $8$ bits op te slaan. Vandaar dat hier van tevoren al $-127$ wordt gedaan. De uiteindelijke exponent is dus $259 – 127 = 132$. 

Stap 2: Dan ga je de significante cijfers vermenigvuldigen, $9.200 \cdot 1.110 = 10.212$. Som is dus $10.212 \cdot 10^{5}$.

Stap 3: Dan gaan we het cijfer standaardiseren: $1.0212 \cdot 10^{6}$.

Stap 4: we mogen maar $4$ significante cijfers hebben dus het wordt $1.021 \cdot 10^{6}$.

Stap 5: Afhankelijk of de bit die aangeeft of de getallen positief of negatief zijn van de getallen gelijk aan elkaar is, is het product positief. Als deze verschilt is het getal negatief.

\subsectionauthor[R. van den Berge]{Fallacies and Pitfalls}

Een fallacy in de computerwereld is: Net zoals je een getal n bits naar links opschuift en het getal met 2n wordt vermenigvuldigd, wordt het getal met n bits opschuiving naar rechts gedeeld door $2$n. Dit is inderdaad het geval bij unsigned integers, maar niet bij signed integers. $-5 / 4$ moet met een integer $-1$ opleveren. $-5$ in binair is $1111$ $1111$ $1111$ $1111$ $1111$ $1111$ $1111$ $1011$. Als je dit $2$ naar rechts opschuift dan krijg je $0011$ $1111$ $1111$ $1111$ $1111$ $1111$ $1111$ $1110$. Dit zou dus $-1$ moeten opleveren, maar in werkelijkheid is dit $1,073,741,822$. 
Floating point getallen zijn slechts benaderingen van echte getallen en omdat computers slechts een gelimiteerde nauwkeurigheid hebben werkt de bovenstaande formule niet. 

Een andere fallacy is dat parallelle operaties die voor integers werken ook voor floating-point datatypen werken. Hierom moeten programmeurs die parallelle code schrijven met floating-point instructies bewijzen dat deze operaties correcte en betrouwbare resultate weergeven. 

Een pitfall is dat ADDIU instructies (add immediate unsigned) zijn $16$-bit getal uitbreidt. Een ADDIU instructie wordt gebruikt om waarden toe te voegen aan signed integers als overflow niet uitmaakt. MIPS heeft geen subtract immediate instructie dus de MIPS architecten hebben dus besloten om het immediate veld te sign-extenden. 

In $1994$ maakte Intel fouten met hun Pentium. Ze gebruikten een algoritme dat bij delingen de volgende $2$ bits raadden aan de hand van de belangrijkste bits van de divisor en de dividend. Deze gerade waarden komen uit een tabel die $-2$, $-1$, $0$, $+1$ of $+2$ bevat. Door fouten in dit algoritme waren de eerste $11$ bits altijd juist, maar er zaten regelmatig fouten in bits $12$ tot en met $52$. Dit kostte intel uiteindelijk $500$ miljoen dollar. 




