[linux-l] n*(n+1)/2 - war: SQL

[Frank Reker]

Am Fri 27. Oct 2006 00:42 +0000 schrieb Volker Grabsch:

>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.
>
>Es ging auch nur um den einen Grenzfall, wo die Multiplikation versagt,
>aber die Addition nicht.


sehr einfach:

n*(n+1)/2 == 2 * (n/2 * n/2) + n/2
bei geradem n funktioniert dass auch sofort mit integer-division bzw.
right-shift.
fuer ungerades n:
n*(n+1)/2 == 2 * [(n-1)/2 * (n-1)/2] + (n-1)/2 + n
da fuer ungerades n bei integer-division bzw. right-shift
n/2 == (n-1)/2,
ist zwischen 1. und 2. formel der einzigste unterschied das +n
das kann man aber durch (n&1)*n ersetzen was bei geradem n zu 0 fuehrt,
und die dann immer ausfuehren. eine fallunterscheidung ist dann nicht
mehr noetig - die komplette formel lautet also:
2 * (n/2 * n/2) + n/2 + (n&1)*n
fuer den computer:
n2=n&1;
n2*=n;
n>>=1;
m=n*n;
m<<=1;
m+=n+n2;

da in dieser formel kein zwischenergebnis groesser wird als das
ergebnis, kommt es auch nicht zu einem unnoetigen overflow.
allerdings ehoeht sich so der aufwand auf 2 multiplikationen,
2 shifts, 2 additionen und ein and. bei computern die das
unterstuetzen koennte man (in asm) die eine multiplikationen
auch durch ein conditional move ersetzen.

da stellt sich dann die frage ob das wirklich performanter ist
als:
if (n&1) {
  n2=n+1;
  n2>>=1;
  m=n*n2;
} else {
  n2=n>>1;
  n+=1;
  m=n*n2;
}
hier hat man naemlich nur ein shift, ein increment, eine multiplikation
sowie ein and und ein cond. jump, und ein unnoetiger overflow tritt
auch nicht auf.
und ob ein cond. jump wirklich ineffizienter als eine mult. eine add
und ein shift ist, wage ich zu bezweifeln. ausserdem bei computern die
cond. moves unterstuetzen, laesst sich der cond. jump auch durch
2 cond. moves ersetzen.
z.b. 21164er asm (alpha) (code1):
OR        R1,R1,R2    ; R2=R1
ADDQ      R1,#1,R3    ; R3=R1+1
CMOVLBC   R1,R3,R2    ; wenn R1 gerade: R2=R3
CMOVLBS   R1,R3,R1    ; wenn R1 ungerade: R1=R3
SLR       R1,#1,R1    ; R1>>=1
MULQ      R1,R2,R1    ; R1*=R2
obiges code-fragment geht davon aus, dass n vorher in register R1
steht, der urspruengliche inhalt von R1, R2, R3 nachher nicht mehr 
benoetigt wird, und das ergebnis nachher in R1 steht.

sieht doch recht effizient aus, oder?


der erste algor. hingegen saehe so aus (code2):
OR        R31,R31,R3  ; R3=0
CMOVLBS   R1,R1,R3    ; wenn R1 ungerade R3=R1
SLR       R1,#1,R1    ; R1>>=1
MULQ      R1,R1,R2    ; R2=R1*R1
SLL       R2,#1,R2    ; R2<<=1
ADDQ      R1,R3,R3    ; R3+=R1
ADDQ      R2,R3,R1    ; R1=R2+R3

und ohne cond. move (code3):
AND       R1,#1,R3    ; R3=R1&1
MULQ      R1,R3,R3    ; R3*=R1
SLR       R1,#1,R1    ; R1>>=1
MULQ      R1,R1,R2    ; R2=R1*R1
SLL       R2,#1,R2    ; R2<<=1
ADDQ      R1,R3,R3    ; R3+=R1
ADDQ      R2,R3,R1    ; R1=R2+R3

jeweils mit den selben vorraussetzungen.

der unterschied zwischen code2 und code3 ist, eine mult. (code3) vs.
ein cond. move (code2). der cond. move ist aber effizienter.
code2 hat gegenuebe code1 einen cond. move weniger, dafuer
ein add und ein shift mehr. ein cond. move auf einem 21164er ist
effezienter als ein add + ein shift. von daher ist code1 der
effizienteste. zumindest auf nem 21164er.

interessant waere noch zu vgl. wie gcc die beiden algorithmen
uebersetzen wuerde?


-- 
Don't worry be happy ...
Ciao Frank
-------------- nächster Teil --------------
Ein Dateianhang mit Binärdaten wurde abgetrennt...
Dateiname   : nicht verfügbar
Dateityp    : application/pgp-signature
Dateigröße  : 189 bytes
Beschreibung: nicht verfügbar
URL         : <https://mlists.in-berlin.de/pipermail/linux-l-mlists.in-berlin.de/attachments/20061027/bc5175b1/attachment.sig>