Skip to main content


Zutaten: Zucker, Kakaomasse (50%), Milchzucker, Weizenmehl, Vollmilchpulver, Magermilchpulver, Butterreinfett, Sahnepulver, Butter (1,4%)
Kann Spuren von Analysis und Geometrie enthalten.

Beitrag_30_titel_positionssystem

Positionssysteme mit negativer Basis

Rike und Max sind nun wieder zu Hause. Sie treffen sich in Rikes Loft. Rike hat sich für die Bewohner ihrer virtuellen (hyperbolischen) Welt besondere Zahlensysteme ausgedacht. Da sieht man einer Zahl nicht mehr so einfach ihren Wert an. Außerdem hat jede Stadt in Hyperland ihre eigene Währung. So braucht zum Umrechnen einen kleinen Rechner oder ein Smartphone. Max soll das jetzt mal austesten.

Max Hi, Rike, wenn ich das austesten soll, muss ich das erstmal verstehen.

Binärsystem

Rike Okay. Erinnerst Du Dich an das Binärsystem?

Max Okay, kenne ich.

Rike Da haben wir die Basis 2

q\;=\;2

und jede Zahl n kannst Du als Summe

n\;=\;\sum_{i=0}^N\;a_i\;2^i

schreiben. Die a_i sind dann die Ziffern aus dem Alphabet

\mathcal{A}\;=\;\{\;0,\;1\;\}

und man kann n dann mit der Basis 2 darstellen, indem man nur die Ziffern a_i schreibt, mit der größten beginnend:

[a_N\;a_{N-1}\;a_{N-2}\;\dots\;a_1\;a_0]_2

Max Okay, Rike, das hatte ich vor laaaanger Zeit, mach doch mal ein einfaches Beispiel!

Rike Lass uns 256 nehmen, das ist eine Zweierpotenz,…

Max …, stimmt,

256\;=\;2^8

Rike Richtig, das schreibst Du also als Summe:

256\;=\;1 \cdot 2^8\;+\;0\;\cdot\;2^7\;+\;0\;\cdot\;2^6\;+\;0\;\cdot\;2^5\;+\;0\;\cdot\;2^4\;+\;0\;\cdot\;2^3\;+\;0\;\cdot\;2^2\;+\;0\;\cdot\;2^1\;+\;0\;\cdot\;2^0

=\;[100\; 000\; 000]_2

Max Okay, ich erinnere mich.

Algorithmus

Rike Ich habe noch ein anderes Verfahren gefunden, um diese a_i auszurechen. Das geht so: Du teilst 256 durch die Basis 2 und ermittelst den Rest:

256\;=\;2\;\cdot\;128\;+\;0\;\equiv\;0\;\mathrm{mod}\;2

Max Okay.

Rike Dieser Rest 0 ist die letzte Ziffer der Binärdarstellung, also

a_0\;=\;0

Max Okay.

Rike Jetzt nimmst Du den Rest und ziehst ihn von der Ausgangszahl n ab, teilst das durch die Basis 2 und erhälst n_1:

n_1\;:=\;\frac{256\;-\;0}{2}\;=\;\frac{256}{2}\;=\;128

Für n_1 berechnest Du wieder den Rest bei der Division durch 2:

Max Das ist 0.

Rike Stimmt, das wird dann a_1:

a_1\;:\equiv\; n_1\;=\;128\;\equiv\;0 \;\mathrm{mod}\; 2

Max Gut.

Rike Das machst Du so weiter, bis der Quotient n_N gleich dem Rest a_N ist:

n_2\;=\;\frac{128\;-\;0}{2}\;=\;\frac{128}{2}\;=\;64

a_2\;\equiv\;0\;\mathrm{mod}\;2

n_3\;=\;\frac{64\;-\;0}{2}\;=\;\frac{64}{2}\;=\;32

a_3\;\equiv\;0\;\mathrm{mod}\;2

n_4\;=\;\frac{32\;-\;0}{2}\;=\;\frac{32}{2}\;=\;16

a_4\;\equiv\;0\;\mathrm{mod}\;2

n_5\;=\;\frac{16\;-\;0}{2}\;=\;\frac{16}{2}\;=\;8

a_5\;\equiv\;0\;\mathrm{mod}\;2

n_6\;=\;\frac{8\;-\;0}{2}\;=\;\frac{8}{2}\;=\;4

a_6\;\equiv\;0\;\mathrm{mod}\;2

n_7\;=\;\frac{4\;-\;0}{2}\;=\;\frac{4}{2}\;=\;2

a_7\;\equiv\;0\;\mathrm{mod}\;2

n_8\;=\;\frac{2\;-\;0}{2}\;=\;\frac{2}{2}\;=\;1

a_8\;\equiv\;1\;=\;n_8\;\mathrm{mod}\;2

Max Na, gut. Ist vielleicht ein Verfahren, was Du gut programmieren kannst, aber die Binärdarstellung ist nicht neu.

Rike Das stimmt, das gibt‘s schon sehr lange. In meinem Spiel aber soll das so eine Art Parallelwelt sein. Die Leute in den verschiedenen Städten sind sehr eigenwillig und jede Stadt hat ihre eigene Währung. Das muss natürlich was ganz anderes sein als wir das kennen. In der Mitte von Hyperland ist es am einfachsten; die Leute sind ärmer dran. Am Hyperlandrand haben die Leute viel mehr Geld und rechnen in anderen Größenordnungen.

 

II_30_hyperbel_arnold_03-03

Max Hmm.

Negative Basis

Rike Die erste Idee ist, das jetzt die Basis q negativ ist.

Du kannst nämlich jede Zahl auch als Summe der folgenden Art schreiben:

n\;=\;\sum_{i=0}^N\;a_i\;q^i

und

q\;<\;0.

Dann sind die Ziffern a_i aus dem Alphabet:

\mathcal{A}\;:=\;\{\;0,\;1,\;\dots\;,\;|q|\;-\;1\;\}

Max Kann ich mir schwer vorstellen.

Beispiel mit q=-2

Rike Der Stadt in der Hyperlandmitte habe ich die Basis

q\;=\;-2

gegeben. Lass uns dasselbe Beispiel noch mal mit n\;=\;256 zur Basis -2 rechnen.

Max Gut.

Rike Das geht so:

256\;=\;2\;\cdot\;128\;+\;0\;\equiv\;0\;\mathrm{mod}\;2

also

a_0\;:=\;0.

Dann

n_1\;:=\;\frac{256\;-\;0}{-2}\;=\;\frac{256}{-2}\;=\;-128

a_1\;:\equiv\; n_1\;=\;-128\;\equiv\;0 \;\mathrm{mod}\; 2

usw.

n_2\;=\;\frac{-128\;-\;0}{-2}\;=\;\frac{-128}{-2}\;=\;64

a_2\;\equiv\;0 \;\mathrm{mod}\; 2

n_3\;=\;\frac{64\;-\;0}{-2}\;=\;\frac{64}{-2}\;=\;-32

a_3\;\equiv\;0 \;\mathrm{mod}\; 2

Max Okay, ist nicht

256\;=\;2^8\;=\;(-2)^8\;=\;1\;\cdot\;(-2)^8 ?

Rike Ja, richtig.

Max Also kriegst Du

256\;=\;[100\; 000\; 000]_{-2}

Rike Stimmt.

Max Wozu brauchst Du denn dieses negative Binärsystem?

Negative Zahlen

Rike Damit kann ich auch negative ganze Zahlen "negativ binär" ohne Minuszeichen ausdrücken.

Max Was? Wie geht das? Mach doch mal ein Beispiel! Nimm doch mal

n\;=\;-1.

Rike Okay! a_0 ermitteln wir wieder als Rest bei der Division von n durch 2:

a_0\;=\;-1\;\equiv\;1 \;\mathrm{mod}\; 2

n_1\;=\;\frac{n\;-\;a_0}{-2}\;=\;\frac{-1-1}{-2}\;=\;\frac{-2}{-2}\;=\;1

a_1\;=\;n_1\;\equiv\;1 \;\mathrm{mod}\; 2

Fertig!

n\;=\;[11]_{-2}

Max Hey! Da sieht man nicht so leicht, ob man Schulden hat!

Rike Doch, das lernen die Hyperlandkinder in der 1. Klasse!

***

Übungsaufgaben

  1. Schreibe den Formalismus zur Berechnung der a_i für q\;\lt\;0 auf!
  2. Berechne für n\; \in\; \{\;1,\; -1,\; 100,\; -100,\; 1\;000\;000,\; -1\;000\;000\;\} die Darstellung zur Basis q\;=\;-2 und q\;=\;-16.
  3. Wie erkennt man, ob eine Zahl negativ ist?

Lösungen

  1. n\;\equiv\; a_0\; \mathrm{mod}\; |q|

    n_1\;=\;\frac{n\;-\;a_0}{q}

    a_1\;\equiv\;n_1\;\mathrm{mod}\;|q|

    \dots

    n_{i+1}\;=\;\frac{n_i\;-\;a_i}{q}

    a_{i+1}\;\equiv\;n_i\;\mathrm{mod}\;|q|

    bis

    n_i\;=\;a_i, \; N\;:=\;i

  2. 1\;=\;[1]_{-2}

    -1\;=\;[11]_{-2}

    100\;=\;[110\; 100\;100]_{-2}

    -100\;=\;[11\;1 01\;100]_{-2}

    1\;000\;000\;=\;[100\;110\;100\;011\;001\; 000\; 000]_{-2}

    -1\;000\;000\;=\;[1\;100\;011\;100\;001\;011\; 000\; 000]_{-2}

    Für q\;=\;-16 haben wir das Alphabet

    \mathcal{A}\;:=\;\{\;0,\;1,\;\dots\;,\;9,\;10,\;11,\;12,\;13,\;14,\;15\;\},

    was wir wie üblicherweise mit

    \mathcal{A}\;:=\;\{\;0,\;1,\;\dots\;,\;9,\;a,\;b,\;c,\;d,\;e,\;f\;\},

    identifizieren.

    1\;=\;[1]_{-16}

    -1\;=\;[1f]_{-16}

    100\;=\;[1a4]_{-16}

    -100\;=\;[7c]_{-16}

    1\;000\;000\;=\;[1\;f0c\;3c0]_{-16}

    -1\;000\;000\;=\;=[115\;e40]_{-16}

  3. N ist ungerade.