Es geht um eine Zahl, die mich mit besonderem Stolz und großer Freude erfüllt: soeben sind es 40.000 lineare Optimierungsprobleme geworden, die mein Simplex-Rechner seit dem 1. Januar 2010 für seine Besucher gelöst hat – online, kostenlos, ohne Anmeldung und mit Anzeige aller Zwischenschritte. Das waren im Mittel 47 gelöste Probleme (Modelle) pro Tag, wobei diese Zahl eine gewisse Varianz mit sich bringt: von einem einzelnen Modell am 26. August 2010 bis zu 1.778 Modellen (!) am 21. Juni 2011 erstreckt sich die Spannweite.
Natürlich war für mich zu erwarten, dass zu den klassischen Zeiten der Klausurvorbereitungen, also gegen Ende der Vorlesungszeiten an den Hochschulen, die Last steigt. Aber bislang kommt der Server auch damit klar, und ich freue mich, dass meine Implementierung des primalen und dualen Simplex-Algorithmus so gut angenommen wird. Geht es in diesem Tempo weiter, dann wird noch vor Jahresende die Marke von 50.000 gelösten Problemen erreicht. Das würde mich freuen – für ein Skript, das in seinem Kern inzwischen 11 Jahre alt ist, wäre es eine beachtliche Karriere.
It’s commonplace to assume that one can’t code an instruction to be performed faster than the processor can do it if it has such an instruction in hardware. However, this assumption is wrong here and there, and particularly incredible evidence for that fact is the fast inverse square root. When I heard about it for the first time, I was amazed by the stunning approach. Here’s how it goes: let x be a 32-bit unsigned floating point number (in other words, a standard unsigned float). The next step is to treat the bits of x as a 32-bit integer value, divide it by 2 (=shift one bit to the right) and subtract it from the “magic” hex number 0x5f3759df. The float representation of the result yields the first approximation of 1/sqrt(x).
Wikipedia has all the details. Kudos to whoever invented this… my hat’s off to you!
Since I wrote my PhD thesis about how to use idle desktop PCs and video game consoles for massive-scale distributed computing (the so-called “Desktop Grid” approach), I am interested in the potential of this concept. A remarkable article from Science magazine by Martin Hilbert et al., published this year, came to my attention recently (Science 332, 60 (2011)). It points out that in 1986, the planet’s total installed computational capacities provided 3×10^8 million instructions per second (MIPS), while in 2007, this number has increased to 6.4×10^12 MIPS. In other words, the computational potential has grown by a factor of approximately 21,300 compared to the level of 1986. For an annualized rate, assuming equal growth every year, this means that the world’s computing capacity grew by 60.7 per cent every year from 1986 to 2007.
While this is impressive enough on its own, there’s more to come. Less than 0.5 per cent of 2007′s global computing potential came from supercomputers – the vast majority being provided by desktop computers, video game consoles (a staggering 25 per cent) and mobile devices (6 per cent). Fantastic news for Desktop Grids! Like the dinosaurs, supercomputers will eventually become extinct.
The article I have referred to in this blog post is freely available for personal reading, courtesy of Science magazine and Martin Hilbert.
(As an aside, Moore’s Law predicts that every 18 months, the number of transistors placed on newly designed ICs can be doubled, meaning that there’s growth by 58.7 per cent every year. However, we can’t expect the number of computers to remain constant over time, nor can we expect every computer to be replaced by latest technology once available, so Moore’s Law is really research-related and not to be confused with this result.)
Jeder, der schon einmal eine Mathe-Vorlesung besucht hat, kennt sie: die “Wählt man”-Beweise. Wählt man dieses und jenes, legt sich der zu beweisende Sachverhalt elegant vor einem dar, ohne dass man einen größeren Aufwand des Beweisens dafür betreiben müsste. Das Unangenehme ist nur: auf das, was dafür eingangs zu wählen ist, muss man erst einmal kommen. Daher finde ich diese Form des Beweisens für diejenigen, die den Beweis nachvollziehen, öfters ziemlich frustrierend: ich bevorzuge eine konstruktive(re) Vorgehensweise, die auch dann funktioniert, wenn man gerade nicht intuitiv oder anderweitig weiß, was man nun zu wählen hat.
Für einen bestimmten Fall aus der Statistik, den Vorfaktor 1/(n-1) beim Schätzer der Varianz einer Zufallsvariable aus einer Stichprobe, ist mir der beschriebene Umstand in Lehn/Wegmann: Einführung in die Mathematische Statistik begegnet. Während der Arbeit an meiner Dissertation im Sommer 2009 hatte ich selbst recht viel mit Statistik zu tun und wollte nicht einfach nur hinnehmen, dass da 1/(n-1) steht bzw. den etwa zweizeiligen “Wählt man”-Ausführungen der Herren Lehn und Wegmann folgen, sondern gern genau wissen, warum das so ist. Das Ergebnis ist ein konstruktiver Schritt-für-Schritt-Beweis, den ich seinerzeit mit LaTeX niedergeschrieben und vor kurzem beim Aufräumen meines Laptops wiedergefunden habe. Für alle, die so etwas in welchem Zusammenhang auch immer gebrauchen können – hier ist er: Warum hat der Schätzer für die Varianz 1/(n-1) und nicht 1/n als Vorfaktor
Nebenbei eine triviale und natürlich auch wenig überraschende Schlußfolgerung: die Varianz ist für einelementige Stichproben nicht definiert. Aber wer würde sie da schon brauchen…
Finally, it’s here – my home page made it to version 2.0, and now it’s a blog. While still under construction, I consider this place a vault holding information worth sharing, in particular my own work and references to other interesting sites.
Uncategorized | admin | 
03.05.2012 00:36 | 
Comments (0) 
Subscribe