Dezimal in Binär (rational)

17/03/2009 - 13:34 von Markus Wichmann | Report spam
Hi all,

ich fragte mich, wie man eine beliebige rationale Zahl in ihre binàre
Darstellung umwandeln kann.

OK, für binàre Zahlen interessiert ja nur eine gewisse Anzahl Stellen,
aber welche? Nehmen wir mal folgende Aufgabenstellung: Schreiben Sie
ohne zu cheaten (Wikipedia ist erlaubt, Java-Applets nicht!) die binàre
Representation von 1,19 in IEEE 754 double precission auf.

Die Aufgabe kann man natürlich in einen einfachen und einen schweren
Teil spalten:

1. Konversion der Vorkommastellen:
Da ist nicht viel zu machen: 1 bleibt 1.

2. Konversion der Nachkommastellen:
Da nahm ich mir erstmal einen Sysiphos-Algorithmus vor

x - Eingabe

char buf[52] = 52 * "0";

for i = 1 to infty
if (x - 2^(-i) > 0)
buf[i - 1] = "1";
x -= 2^(-i);
fi
if (x = 0) break;
done

Nur geht dieser Algorithmus bis unendlich und das ist dann doch ein
bisschen doll...

Was wàre denn ein gutes Minimum? Ich meine, wir kennen den Exponenten
der Fließkommazahl (der ist 1, da es genau eine binàre Vorkommastelle
gibt), und wir kennen die Breite der Mantisse (52 Bit). Das letzte Bit
der Mantisse hat also die Wertigkeit -52 (Exponent minus Mantissenbreite
minus 1, weil die erste Ziffer der Mantisse immer 1 ist und deshalb
weggelassen wird).

Aber so ist der Algorithmus immer noch Sysiphos-Arbeit. Gibt es einen
besseren (Mit dem Taschenrechner, weil ich 32768^-1 nicht aus dem Kopf
berechnen kann, kam ich bislang auf eine Binàrzahl 1,001100001010001...)?

Tschö,
Markus

GUI - ein Hintergrundbild und zwölf XTerms

vim -c "exec \"norm iwHFG#NABGURE#IVZ#UNPXRE\"|%s/#/ /g|norm g??g~~"
 

Lesen sie die antworten

#1 Helmut Richter
17/03/2009 - 14:31 | Warnen spam
On Tue, 17 Mar 2009, Markus Wichmann wrote:

aber welche? Nehmen wir mal folgende Aufgabenstellung: Schreiben Sie
ohne zu cheaten (Wikipedia ist erlaubt, Java-Applets nicht!) die binàre
Representation von 1,19 in IEEE 754 double precission auf.



119/100 = 1 + 1/4 * 19/25

2^20 - 1 = 1048575 = 25 · 41943

19/25 = 19 · 41943 / (2^20 - 1) = 796917 / (2^20 - 1)

Das wàre also der unendliche Binàrbruch, dessen 20 Ziffen die
Binàrdarstellung von 796917 haben, also

0.(11000010100011110101)...

Damit ist 1,19 binàr

1.00(11000010100011110101)...

auf beliebig viele Stellen.

Die einzige Kunst ist die Periodenlànge 20 für den Nenner 25 oben zu
erraten. Das geht so: Für Primzahlen n ist sie ein Teiler d von n-1; da
gibts nicht viele zum Ausprobieren. Für Primzahlpotenzen n^r ist sie d·n^k
für k<r, meist k=r-1. Für Zahlen mit mehreren Primfaktoren ist sie das kgV
der Periodenlàngen der enthaltenen Primzahlpotenzen.

Helmut Richter

Ähnliche fragen