Schnellere Mathematik durch Bit-Schieben

30.07.2017

Da ich meine Kollegen und Freunde bei jeder passenden und unpassenden Gelegenheit mit den absonderlichen Experimenten nerve, die ich in meiner Jugend mit Computern und Programmieren veranstaltet habe, nuzte ich die Gelegenheit, die sich mir durch einen dazu gefundenen Link bietet...

Inzwischen ist die Zeit heran, da ich mich wie Sid fühle: Die jungen Kollegen - und auch die Mitglieder der nachwachsenden Generation in meiner Verwandtschaft - schauen mich mit offenen Mündern an, wenn ich von Telefonen mit Schnur und der Erfindung des Internet erzähle, die ich tatsächlich noch relativ hautnah miterleben durfte.

Eine meiner liebsten Geschichten, die ich gerne abends am Kamin erzähle, wenn sich die Jungen um mich versammelt habe und ich mit einer Wolldecke über den Knien im Ohrensessel Platz genommen habe ist die folgende: "Wie wir versucht haben, den Compiler geschwindigkeitsmäßig zu übertreffen"

Wir versuchten das auf verschiedenste Weise: Einmal haben wir alle doubles in floats gewandelt, weil wir der Meinung waren, dass das wesentlich schneller gehen müsste - schließlich müssen nicht so viele Bits bewegt werden. Nachdem wir uns den vom GCC gelieferten Assemblercode angesehen haben, haben wir flugs alles wieder zurückgeändert: Der GCC hat beim Start jeder Funktion aufwändig jeden float-Parameter in einen double gewandelt, dann damit gerechnet und zum Schluss die Rückgabewerte ebenso aufwändig wieder zurückgewandelt. In durchschnittlichen Funktionen bedeutete das eine Verdopplung der Assembleranweisungen. Weil es damals auch noch auf schonenden Umgang mit der Cache-größe ankam, wollten wir gar nicht mehr wissen, wie viel langsamer unsere "tolle Idee" war...

Die zweite Idee war uns aus dem Internet zugeflogen: Im Fachgebiet Neuroinformatik, in dem ich damals arbeitete - heute das Neuroinformatics and Cognitive Robotics Lab - hatten wir viel mit Algorithmen zu tun, in denen die eine oder der andere Sigmoidfunktion oder natürliche Logarithmus auftauchten. Das Internet sagte, dass diese Funktionen ganz ohne langwierige Spezialroutinen sehr viel einfacher durch Bit-Shift-Operationen zu errechnen waren. Wir probierten das aus und sagen, dass dadurch zwar ein gewisser Fehler in die Berechnungen Einzug hielt, die Algorithmen jedoch trotz dieser Tatsache die korrekten Ergebnisse lieferten.

Bei meinem letzten Kaminabend erzählte ich diese Geschichte wieder einmal und war - so wie bei den 50 Erzählungen davor - wieder traurig, dass ich die korrekte Vorgehensweise nicht mehr kannte. Diesmal klemmte ich mich jedoch dahinter und hatte Glück: Stellvertretend für viele Quellen, die sich mit diesem Thema befassen habe ich hier drei ausgewählt:

Aktualisierung vom 30. Juli 2017

Ein weiterer Link wurde hinzugefügt

Artikel, die hierher verlinken

Mathematik mit beliebiger Präzision in Java

11.11.2018

Wann immer ich hier über Experimente mit numerischen Lösungsverfahren für Differentialgleichungssysteme berichte, habe ich im Hinterkopf, dass diese Verfahren eigentlich völlig ungeeignet dafür sind, solche Systeme zu analysieren, da heutige Digitalcomputer bereits rationale Zahlen nicht exakt darstellen können - von irrationalen ganz zu schweigen...

Alle Artikel rss Wochenübersicht Monatsübersicht Github Repositories Gitlab Repositories Mastodon Über mich home xmpp


Vor 5 Jahren hier im Blog

  • Fährnisse des Buildprozesses unter Windows

    17.07.2019

    Nachdem ich begonnen hatte, mich mit der Beschleunigung der Berechnung des Mandelbrot-Fraktals unter Zuhilfenahme der Shadereinheiten in Graphikkarten zu beschäftigen und erste Erfolge feiern konnte, wollte ich das mal auf einer richtigen Graphikkarte ausprobieren...

    Weiterlesen...

Neueste Artikel

  • Datenvalidierung UTF8 mit BiDi-Steuerzeichen (TrojanSource 2.0)

    Ich bin heute nochmal inspiriert worden, weiter über die Trojan Source Vulnerability nachzudenken. Meiner Meinung nach bestehen hier noch Probleme - speziell bei Nutzereingaben oder Daten, die über externe Schnittstellen ampfangen werden.

    Weiterlesen...
  • OpenStreetMap Navi als Docker-Container

    Ich habe die auf OpenStreetMap basierende OpenSource Navigationslösung Graphhopper in einen Docker-Container gepackt und als neuestes Mitglied in meinem Docker-Zoo willkommen geheißen.

    Weiterlesen...
  • SQL-Aggregatfunktionen in SQLite als BeanShell-Scripts

    Ich habe neulich über eine Möglichkeit berichtet, SQLite mittels der sQLshell und Beanshell-Skripten um SQL-Funktionen zu erweitern. In diesem Artikel versprach ich auch, über eine solche Möglichkeit für Aggregatfunktionen zu berichten.

    Weiterlesen...

Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.

Wer daran teilhaben und eventuell sogar davon profitieren möchte, muß damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.

Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...

PS: Meine öffentlichen GitHub-Repositories findet man hier - meine öffentlichen GitLab-Repositories finden sich dagegen hier.