[linux-l] SQL

[Volker Grabsch]

On Thu, Oct 26, 2006 at 10:13:24AM +0200, Steffen Dettmer wrote:
> > (bevor die Gauß-Kenner jetzt kommen: Jaja, man addiert auch nicht alle
> > Zahlen zusammen, sondern kommt mit einer Inkrementierung, einer
> > Multiplikation und einer Halbierung aus. Aber habt ihr euch schonmal
> > gefragt, wie man letzteres tut, ohne dabei den Zahlenbereich dabei
> > zu sprengen?
> 
> Halbierung ohne dabei den Zahlenbereich zu sprengen? Einmal binär
> nach rechts schieben...
[...]
> Ja, daher sollte man auch erst halbieren, aber da muss man wohl ne
> ungerade/gerade Fallunterscheidung machen (was binär bei unsigned ints
> wieder einfach ist).

100 Punkte für den Kandidaten. Ich hatte gehofft, auch ohne
Fallunterscheidung könnte man auskommen, wie in einer "geschlossenen
Formel" eben, also im Maschinencode ohne Jump/Call auskommen. Da
ist mir aber noch nichts eingefallen.

> Multiplikation geht natürlich so nicht, aber selbst echtes Adieren ist
> nicht sicher. Das oben (1mio) passt ja auch nicht in 32 Bit.

Es ging auch nur um den einen Grenzfall, wo die Multiplikation versagt,
aber die Addition nicht.

> > Dann wäre die Multiplikation ne Katastrophe, aber die Addierschleife
> > würde korrekt arbeiten.)
> 
> So, jetzt mal noch was: gibt es deinen extrem konstruierten Grenzfall
> überhaupt? Also eine Reihe derartiger Zahlen, deren Summe 4.294.967.296
> ist? Wie ist die grösste (zum Nachrechnen für mich :))
> 
> Halte ich für ziemlich unwahrscheinlich, dass es die gibt :-)

Wenn man Wahrscheinlichkeitsrechnung und Zahlentheorie mixt, muss man
sehr vorsichtig sein ...

Also, nehmen wir die größe 16-Bit-Zahl, also die Wurzel von unserer
Grenze:
    n = 65536

Dann ist n-1 auf jeden Fall zu klein:

    (n-1)*n < n^2 = 4294...

Und n liegt auf jeden Fall drüber:

    n*(n+1) > n^2 = 4294...

Das heißt, unser konstruierter Grenzfall liegt *immer* bei der Wurzel.
Die Wurzel ist zu groß, die Wurzel-1 ist zu klein.

Jetzt ist also nur noch die Frage, ob die Wurzel, also n, nun als
Gegenbeispiel taugt oder nicht. Aber da unser n > 1 ist, folgt:

    n*(n+1)/2 < n*(n+n)/2 = n^2 = 4294...

Oder mit unseren konkreten Zahlen zum Nachrechnen:

    1+2+...+65536 = 2147516416, also noch 32 Bit

Die Multiplikation in der Gauß-Formeln hingegen liefert den
Zwischenwert:

    65536*65537 = 4295032832, also sprengt die 32 Bit

Wie oben gezeigt funktioniert diese Konstruktion ganz allgemein.
Für eine 2k-Bit-Architektur liefert n = 2^k das Gegenbeispiel.

(Um n > 1 zu erfüllen, muss k > 0 gelten, aber wir betrachten
hier eh keine 0-Bit-Architekturen :-))

Zugegeben, die ungeraden k habe ich jetzt nicht untersucht.
Aber schon die geraden k beweisen, dass die "Chance" bei
mind. 50% liegt.

Für ungerade k will ich mir jetzt keinen Beweis aus den Fingern
saugen, das Runden wird ekelhaft. Aber im konkreten Fall einer
31-Bit-Architektur funktioniert n = 46341:

    46341*46342   > 2^31
    46341*46342/2 < 2^31

Das heißt, auch für vorzeichenbehaftete 32-Bit-Integers funktioniert
die Konstruktion.

Ein C-Programm, das diese Schwäche tatsächlich aufdeckt, wäre nicht
schlecht ... hat einer Lust?


Viele Grüße,

    Volker

-- 
Volker Grabsch
---<<(())>>---
Administrator
NotJustHosting GbR