WisFaq!

Machtverheffen en worteltrekken met binaire getallen

hey!
Ik moet voor wiskunde een praktische opdracht over het binaire getallenstelsel maken. Hierin moet ik ook uitgebreid onderzoeken hoe het rekenen in dit stelsel in z'n werk gaat. Optellen, aftrekken, delen en vermenigvuldigen is al gelukt. Maar ik vraag me af hoe je in dit stelsel moet machtsverheffen en worteltrekken zonder het eerst in het decimale stelsel om te rekenen. Ik heb hier namelijk niets over kunnen en zelf lukt het me niet.
Kunnen jullie me alstublieft helpen door bijvoorbeeld een voorbeeld te geven en de rekenstappen uit te leggen?
alvast bedankt

Tanja van den Berg
10-1-2004

Antwoord

Machtsverheffen

Handig machtsverheffen kun je als volgt.
Eerst maar eens in de decimale schrijfwijze:

3⁹=
3⁸·3¹=
3⁴·3⁴·3¹=
(3²·3²)·(3²·3²)·3¹

3¹=3
3²=9
3⁴=9·9=81
3⁸=81·81=6561
Dus 3⁹=6561·3=19683

Nu binair
3⁹ decimaal komt overeen met
11¹⁰⁰¹

11¹=11
11·11=1001
1001·1001=1010001
1010001·1010001=1100110100001

De grap is nu dat de binaire schrijfwijze van 9 (1001) je precies vertelt welke getallen je nu met elkaar moet vermenigvuldigen voor het eindresultaat

Ik heb de binaire schrijfwijze even voor de verschillende stappen gezet. Allleen die tussenresultaten doen mee waar een 1 voor staat:
1| 11¹=11
0| 11·11=1001
0| 1001·1001=1010001
1| 1010001·1010001=1100110100001

We lezen dus af:
11·1100110100001=100110011100011

Worteltrekken

Ik geef je twee voorbeelden.
10011·10011=101101001
We willen nu een manier om de wortel van 101101001 te trekken.
Dat gaat als volgt:
Verdeel het getal van achter in groepjes van 2 "digits", dus
1 01 10 10 01
schrijf hieronder een 1 in het eerste groepje, verder nullen, en trek deze van elkaar af. Schrijf naast de streep een 1.
dus

1 01 10 10 01
1 00 00 00 00 =
------------- 1
   1 10 10 01 

Vul nu 1 groepje minder met nullen en schrijf hiervoor 101.
Deze aftreksom lukt niet, dus schrijf naast de aftrekstreep een 0

1 01 00 00 00
------------- 0 

Je hebt nu naast de aftrekstrepen staan 10.
Zet hierachter een 0 en een 1: 1001. Vul aan met 1 groepje minder nullen. Dus:

   1 10 10 01
  10 01 00 00
------------- 0 (want het gaat weer niet)
   1 10 10 01 

Je hebt nu naast de aftrekstrepen staan 100. Zet er 01 achter en vul aan met 1 groepje minder nullen. Dus 10001

   1 10 10 01
   1 00 01 00
------------- 1 (dit gaat wel, dus een 1 naast de aftrekstreep)
     10 01 01 

Je hebt nu naast de aftrekstrepen staan 1001. Zet hier 01 achter. Dus 100101.

     10 01 01
     10 01 01
------------- 1
            0.

Van boven naar onder staat naast de aftrekstrepen nu 10011: de wortel van 101101001.

Samengevat:

1 01 10 10 01
1 00 00 00 00
------------- 1
   1 10 10 01
1 01 00 00 00
------------- 0
   1 10 10 01
  10 01 00 00
------------- 0
   1 10 10 01
   1 00 01 00
------------- 1
     10 01 01
     10 01 01
------------- 1
            0

Nog een voorbeeld zonder commentaar:

1101·1101=10101001
10 10 10 01
 1 00 00 00
----------- 1
 1 10 10 01
 1 01 00 00
----------- 1
    1 10 01
   11 01 00
----------- 0
    1 10 01
    1 10 01
----------- 1
          0

De wortel is dus 1101

Succes!

Mocht je je afvragen hoe dit algoritme werkt:

Het is een vertaling naar binaire getallen van een algoritme dat ook bestaat voor getallen in het tientallig stelsel.

hk
10-1-2004