Horner – Konvertieren zwischen Zahlensystemen

April 8, 2013 um 7:25 pm | Veröffentlicht in Bash, Free Software/Open Source, Programmieren, Ubuntuusers | 10 Kommentare

„Mama, weißt du wie ich von einem Zahlensystem in ein anderes umrechne?“

„Nein, Schätzchen. Weiß Linux es nicht?“

„Nein, ich kann kein Programm finden, dass das kann.“

„Es gibt kein Programm um zwischen Zahlensystemen zu Konvertieren? Oh, nein …“

*Türe wird aufgestoßen, Horner-man stürmt herein*

„Fürchtet euch nicht, gesetzestreue Linuxer! Eure Klagen wurden erhöhrt!“

„Ooh, Horner-man. Unser Held!“

Autsch. Das tut weh. Ich habe es selbst geschrieben und es schmerzt trotzdem sehr. Abgegriffenes Szenario, unglaubwürdige Darsteller, ein Hauch von Sexismus. Autsch.

Kommen wir zum Thema. Seit Langem wollte ich ein Programm haben, mit dem ich einen Wert in verschiedenen Zahlensystemen darstellen kann. Dazu musste dieses Programm jedoch die Umrechnung zwischen diesen Systemen beherrschen. Mein vorrangiges Ziel war die Umrechnung vom Dezimalsystem ins Binärsystem und umgekehrt. Es gibt sicherlich Programme da draußen, die dafür geschrieben sind oder es zumindest nebenbei beherrschen. Speziell die Konvertierung zwischen Zahlensystemen zur Basis 2, 8, 10 und 16 findet sich häufig in digitalen Taschenrechnern. Speedcrunch ist ein schönes Beispiel dafür. Allerdings wollte ich nicht einfach nur ein Programm, welches mir ein Ergebnis anzeigt, sondern auch die Möglichkeit dieses Programm in einem Script zu verwenden. Es musste also konsolenbasiert arbeiten und Ein- und Ausgabe sollten über die Standardkanäle erfolgen.

Da ich kein entsprechendes Programm gefunden habe, habe ich mir vorgenommen selbst eines zu schreiben. Da ich außerdem schon länger das Horner-Schema testweise implementieren wollte,  entschied ich mich dazu, die Umrechnung damit vorzunehmen. Dazu muss erwähnt werden: ich habe dieses Programm für meine persönlichen Bedürfnisse entwickelt, weswegen es nur mit ganzen Zahlen umgehen kann. Die Berechnung mit Gleitkommazahlen ist um einiges komplizierter und es braucht ein bisschen Hirnschmalz um ein Programm zu entwickeln, das nicht sofort Probleme mit der Rechengenauigkeit bekommt. Vielleicht erweitere ich das Programm irgendwann in diese Richtung. Vorerst kann es nur Integer verwerten. Dafür kann es mit Zahlen verschiedenen Basen arbeiten. Die Untergrenze ist Basis 2 (Binär), die Obergrenze ist 36. Rein theoretisch könnte es natürlich noch mehr Basen verarbeiten, bei 36 gehen mir jedoch die sinnvollen Zahlenrepräsentationen aus (0-9, a-z).

Das Programm, oder mehr die Befehlssammlung, kann positive und negative Zahlen von 0 bis 4294967295 verwerten. Dabei ist jedoch 4294967295 das Minimum an Obergrenze. Auf einem 64-bit System ist die Obergrenze 18446744073709551615 (abhängig vom Compiler; hier: GCC). Installation und Verwendung werden noch beschrieben. Zuerst jedoch eine kleine Exkursion:

Was ist das Horner-Schema?

Das Horner-Schema wurde von William George Horner entwickelt und dient der Polynomberechnung. Da die Umrechnung in ein anderes Zahlensystem als Polynom dargestellt werden kann ist das Horner Schema (oder Horner’s Method im Englischen) eine sehr einfache und schnelle Art der Berechnung. Im Großen und Ganzen funktioniert es so:

Umwandlung in das Dezimalsystem; B ist die Basis, a ist die Ausgangszahl, a1 die erste Stelle derselben, …:
(((a1*B + a2)*B + a3)*B + a4) ...

Bsp:
Wir wollen den Binärwert (Basis = 2) 101010 in das Dezimalsystem umwandeln:
((((1*2+0)*2+1)*2+0)*2+1)*2+0 = 42

Die Umwandlung eines Dezimalwertes in ein anderes System funktioniert analog dazu. Zuerst wird per Modulo (Restwertdivision) der Restwert errechnet. Dieser stellt bereits eine Stelle des Ergebnisses dar. Da dieser Rechenvorgang genau umgekehrt zur Umwandlung ins Dezimalsystem verläuft, ist auch das Ergebnis umgekehrt:
42   % 2 = 0
42-0 / 2 = 21
21   % 2 = 1
21-1 / 2 = 10
10   % 2 = 0
10-0 / 2 = 5
 5   % 2 = 1
 5-1 / 2 = 2
 2   % 2 = 0
 2-0 / 2 = 1
 1   % 2 = 1
 1-1 / 2 = 0

Sobald die Zahl, mit der man rechnet 0 geworden ist, endet die Rechnung. Die fettgedruckten Zahlen ergeben, von unten nach oben gelesen, das Ergebnis. Die Zeichenkette ist also 101010. Das ist dieselbe Zeichenkette, die wir zuvor ins Dezimalsystem umgewandelt haben. Es funktioniert!

Die Programme

Ich habe für jeden Rechenvorgang ein C++-Programm geschrieben. 2dec wandelt eine Zahl in das Dezimalsystem um, dec2 wandelt eine Dezimalzahl in eine beliebige Basis (von 2 bis 36) um. Die beiden Programme können jedes für sich aufgerufen werden mit:
dec2 <Basis> <Wert>
2dec <Basis> <Wert>

Die <Basis> ist immer die Basis aus der, bzw. in die ich umrechnen möchte. Die jeweils andere Basis ist ja das Dezimalsystem.

Möchte ich nun den Wert 42 in das Binärsystem umrechnen, so rufe ich das Programm dec2 auf:
dec2 2 42

Möchte ich die Berechnung umdrehen, so verwende ich das Programm 2dec:
2dec 2 101010

Die beiden Programme lassen sich kombinieren, wenn ich von einer Basis in eine andere konvertieren möchte und keine von beiden die Basis 10 ist. Möchte ich wissen, welchen Binärwert der Hexadezimale Ausdruck affe hat, dann mache ich das so:
dec2 2 $(2dec 16 affe)

Ergebnis: 1010111111111110

Das Script

Diese Kombination übernimmt das Script horner. Dieses übernimmt per -i die Basis des Inputs und per -o die Basis, in die der Wert umgewandelt werden soll (Output):
horner -i 16 -o 2 affe
entspricht der obigen Kombination der beiden Programme. Das Script geht davon aus, dass die beiden Programme in einem Verzeichnis abgelegt sind, das in der $PATH-Variablen des Nutzers eingetragen ist.

Das Makefile

Am Besten ist es, wenn man den Code selbst kompiliert. Für all diejenigen, die sich dabei unwohl fühlen oder es einfach noch nicht gemacht haben: keine Sorge, das Makefile übernimmt diese Arbeit. Dazu muss das Paket automake im System installiert sein.

Installation

Zuerst benötigt man den Code, den es hier zum herunterladen gibt.

Dieses Archiv lässt sich per
tar -xvzf Horner.tar.gz
ins aktuelle Verzeichnis entpacken. Die entpackten Dateien liegen dann im selben Verzeichnis wie das Archiv.

Sobald man die Dateien entpackt hat muss man nur in einem Terminal
make
aufrufen. Dies kompiliert den Code und erzeugt die beiden Programme 2dec und dec2.

Mittels
make install
kann man die Programme dann automatisch installieren. Dabei werden sie im Verzeichnis /bin im Home-Verzeichnis des Nutzers abgelegt. Dieses Verzeichnis sollte immer im $PATH liegen und der Nutzer hat dort immer Schreibrechte. Möchtest du die Installation anpassen (sprich: die Dateien woanders unterbringen), dann musst du nur die Dateien 2dec, dec2 und horner im gewünschten Verzeichnis ablegen.

Abschlussbemerkung

Die Programme, das Script und das Makefile stehen unter der GPLv3. Sie sind in keinster Art und Weise getestet und implementieren so gut wie keine Fehlerbehandlung. Über Bugmeldungen freue ich mich, kann aber nicht versprechen, dass ich sie schnell behebe. Wie erwähnt: die Programme sind aus Neugier entstanden und erfüllen meine Anforderungen. Deswegen habe ich vorerst auch nicht vor, sie auf GitHub oder sonstwo hochzuladen. Wenn du das gerne tun möchtest, tu dir keinen Zwang an. Informiere mich in diesem Fall aber bitte darüber.

Über den Inhalt der Programme und des Scripts verliere ich hier keine großen Worte. Wenn du Interesse hast zu erfahren was hier genau passiert, dann schreib mir das in den Kommentaren. Ich antworte dir dann entweder dort oder schreibe einen neuen Artikel zum Thema.

=-=-=-=-=
Powered by Blogilo

10 Kommentare »

RSS feed for comments on this post. TrackBack URI

  1. Arghh, bleib mir weg damit! In der letzten Digitaltechnik-Klausur durfte ich schon genügend Horner-Schema anwenden😛 (ich studiere derzeit Angewandte Informatik)😉

    Nein, Quatsch beiseite: Schöner und ausführlicher Artikel, echt verständlich erklärt🙂

    • Bei mir ist es schon eine Zeit lang her, dass ich das Horner-Schema zuletzt in einer Lehrveranstaltung gesehen habe, da es ja eher zu den Grundlagen gehört. Seit damals bin ich fasziniert von der Einfachheit der Methode. Fast so elegant wie die Gauss’sche Summenformel.

  2. Danke für den interessanten Artikel! Werde gleich mal dein Programm testen🙂

  3. Hi, meine Lösung für die Konsole:
    echo „ibase=X ; obase=Y; ZAHL“ | bc

    Die Basen X,Y können von 2 bis 16 variieren.

    • Danke für den Hinweis.

  4. Ich enttäusche dich nur ungern, aber der Taschenrechner (im Programmiermodus) macht das ganz gut zwischen Binär, Oktal, Dezimal und Hexadezimal…

    • Das stimmt, deswegen habe ich auch SpeedCrunch aufgelistet. Mein Script ist aber nicht auf diese vier Basen limitiert, sondern kann zwischen allen Basen zwischen 2 bis 36 konvertieren.

  5. Falls du es noch für Gleitkommazahlen weiterentwickeln willst, ich hab geschaut, ob das CAS maxima dein Problem nicht lösen kann. Nicht direkt, das wird wohl normalerweise per ibase, obase gelöst. Aber ich bin auf ein script gestoßen, das genau das macht: http://www.ma.utexas.edu/pipermail/maxima/2008/014099.html

  6. Nachtrag: Für schnelle Antworten einzelner Abfragen eignet sich wie so oft wolframalpha: http://www.wolframalpha.com/input/?i=1g65a_25

  7. Tolles Skript – das Horner Schema kannte ich bisher nur für den Bereich der Polynomdivision, aber die Konvertierung anderer Zahlensysteme ist natürlich mittels Horner-Schema sehr gut gelöst.
    Bei mir verrichtet es seit heute auch wunderbar seinen Dienst🙂


Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

Erstelle eine kostenlose Website oder Blog – auf WordPress.com.
Entries und Kommentare feeds.

%d Bloggern gefällt das: