\require{AMSmath}

Omrekenen naar een n-tallig talstelsel: algoritme

Ik maak een PO over talstelsels. Hiervoor wil ik onder andere een programmaatje schrijven om een getal voor te stellen in een ander talstelsel. Ik vraag me af of dit altijd mogelijk is? Bestaat er een algemene formule?

Bij voorbaat dank...

Arwin
Leerling bovenbouw havo-vwo - dinsdag 6 januari 2004

Antwoord

Hoi,

Er zijn verschillende soorten talstelsels. Je kan er meer over vinden door op deze site eens te zoeken op Talstelsel bijvoorbeeld. Eén bijzonder type is het positietalstelsel. Hierbij stellen we een getal voor door een geordende serie van symbolen (cijfers). De symbolen kunnen zich herhalen, maar de positie van het symbool bepaalt het gewicht. Voorbeelden hiervan zijn het klassiek tientallig talstelsel, het binaire en het hexadecimale. Verder spreken we af om ons te beperken tot gehele getallen.

In een n-tallig positietalstelsel hebben we n verschillende cijfers: {c₀, c₁, … c_n-1}. Voor n=10 hebben we de cijfers {0,1,2,3,4,5,6,7,8,9} en voor n=16 hebben we de cijfers {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. Elk cijfer heeft een waarde. Voor het tientallig is dat de klassieke waarde van het cijfer. Voor het hexadecimale is dat ook zo met de uitbreiding dat A=10, B=11, C=12, D=13, E=14 en F=15.

We schreven eerder al dat we een geheel getal in het n-tallig positietalstelsel voorstellen door een opeenvolging van cijfers uit dat talstelsel. Elk cijfer in de voorstelling heeft dan een rangnummer en een gewicht. We schrijven het cijfer met het grootste gewicht vooraan, dat met het kleinste achteraan. We tellen de cijfers van achter naar voor, beginnend met positie 0.
Een getal N kan dus in het n-tallig talstelsel voorgesteld worden als k cijfers: N=[a_k-1, ..., a₁, a₀]_n waarbij elke a_i een n-tallig cijfer is.

De gewichten die we aan de opeenvolgende posities toekennen zijn typisch opeenvolgende machten van een getal dat we de basis B van het talstelsel noemen. Meestal kiezen we B=n het aantal cijfers en geven we aan alle cijfers opeenvoldende waarden 0,1,..,n-1. Dit heeft het voordeel dat we elk geheel getal kunnen voorstellen en dat deze voorstelling uniek is. We bewijzen deze eigenschappen hier niet, maar ze zijn wel belangrijk om in te zien dat het programma dat we proberen te schrijven correct is. (Als je zin hebt, moet je deze regels maar eens proberen te doorbreken…)

Met onze definities van cijfers, basis en posities kunnen we een betrekking afleiden tussen een getal en zijn voorstelling in een positietalstelsel: als we een geheel getal N in het n-tallig talstelsel kunnen voorstellen als [a_k-1, ... a₁, a₀]_n , dan moet: N=a_k-1.B^k-1+ ... +a₁.B+a₀ of kort: N=sum(a_i.Bⁱ:i=0..k-1).
We kunnen dit ook schrijven als: N=(..((0.B+a_k-1).B+ ... +a₂).B+a₁).B+a₀ (1).

Als we nu achterenvolgens definiëren:
N_k=0
N_k-1= N_k.B+a_k-1
...
N_i= N_i+1.B+a_i
...
N₁= N₂.B+a₁
N₀= N₁.B+a₀
Dan kan je een paar interessante dingetjes afleiden. Je ziet zo dat N=N₀.
De rest r bij deling van a door b noteren we als: r=a (mod b) (lees: a ‘modulo’ b). Omdat alle a_i cijfers zijn in een n-tallig talstelsel, waar cijfers een waarde 0,1,…n-1=B-1 hebben, liggen alle a_i tussen 0 en B-1. Daarom is: a_i= N_i (mod B) en N_i+1= (N_i-a_i)/B. Dit is de essentie van het algoritme om naar het n-tallig talstelsel om te rekenen. Als N_iB, dan is a_i= N_i en N_i+1=0 en kunnen we stoppen.

Je kan N als volgt naar het n-tallig talstelsel omrekenen:
i=0
N_i=N
doe
...a_i= N_i (mod B)
...N_i+1= (N_i-a_i)/B
...i=i+1
totdat (N_i=0)
k=i-1

Omdat we eigenlijk niet zo geïnteresseerd zijn in die rij N_i kan je vereenvoudigen:

i=0
m=N
doe
...a_i= m (mod B)
...m= (m-a_i)/B
...i=i+1
totdat (m=0)
k=i-1

Ga jij na waarom dit precies werkt voor alle beginwaarden van N?
Je merkt terecht op dat we N eigenlijk al moeten kunnen voorstellen in de computer om dit algoritme te kunnen uitvoeren. Intern zal dit binair zijn, praktisch in je programmeeromgeving decimaal. Om dan van een 7-tallig naar een 32-tallig om te rekenen ga je dus best via 10-tallig om.
Met behulp van (1) kan je een algortime maken om de cijferreeks van het n-tallig naar het decimaal om te rekenen.

Groetjes en succes ermee ,
Johan

andros
dinsdag 6 januari 2004

Omrekenen van getallenstelsels

©2001-2024 WisFaq