n über k - berechnen!?

[Amateurprofi]

Zitat von Wolfgang Mix:

Und wie würdest Du das heute machen?

Ich hab das mal komplett in ASM hingestolpert.
Wesentliche Änderungen:
1) wenn N-K < K ist wird NK(N,K) als NK(N,N-K) ausgeführt.
2) die Routine die versucht Faktoren durch Kürzen zu eleminieren, arbeitet vollständig in der FPU

Besonders bei großen N und großen K ergeben sich durch (1) erhebliche Verbesserungen gegenüber der ursprünglichen Version.

Code:

NK(50,10)       1000000 x ausgeführt = 390 ms (ursprünglich 1200 ms)
NK(25000,24999)       1 x ausgeführt =   0 ms (ursprünglich 1800 ms)

Bei Fehlern wird als Ergebnis NaN zurückgegeben.
Andere Fehler wie Überschreitung des Rechenbereiches oder Out of Memory werden nicht abgefangen.

Delphi-Quellcode:

FUNCTION NK(n,k:integer):extended;
asm
               test     eax,eax
               js       @ReturnNan           // n<0, Fehler
               test     edx,edx
               js       @ReturnNan           // k<0, Fehler
               je       @Return1             // k=0, Result=1
               mov      ecx,eax
               sub      ecx,edx              // d:=n-k
               js       @Return0             // k>n, Result=0
               je       @Return1             // k=n, Result=1
               cmp      ecx,edx              // if d<k then k:=d
               jae      @1
               mov      edx,ecx
@1:            cmp      edx,1
               jne      @2                   // k<>1
@ReturnN:      push     eax
               fild     dword [esp]
               pop      eax
               jmp      @End
@ReturnNan:    lea      eax,@Nan.Pointer[eax]
               fld      tbyte [eax]
               jmp      @End
@NaN:          dw       0,0,0,$C000,$FFFF
@Return0:      fldz
               jmp      @End
@Return1:      fld1
               jmp      @End
               //---------------------------------------------------------------
@2:            push     ebx                  // EBX retten
               // Platz für k Integers auf Stack reservieren
               lea      ecx,[edx*4]
               sub      esp,ecx
               // n, n-1, n-2, ... n-k+1 auf Stack legen
               sub      ecx,4
@Loop1:        mov      [esp+ecx],eax
               sub      eax,1
               sub      ecx,4
               jnc      @Loop1
               //---------------------------------------------------------------
               // alle k gegen n aus liste kürzen, ggfs. in st aufmultiplizieren
               //---------------------------------------------------------------
               push     edx                  // k
               fld1
               fld1
               fild     dword [esp]          // st0=k, st1=Const 1, st2=Produkt(k)
               lea      eax,[edx-1]
@Loop2:        mov      ecx,edx              // Index Listenende
@Loop3:        // prüfen, ob ein Wert aus der Liste durch k teilbar ist
               fild     dword [esp+ecx*4]    // st0=n
               fdiv     st,st(1)             // st0=n/k
               fld      st                   // dto
               frndint                       // st0=Int(n/k)
               fcomip   st,st(1)
               je       @Divisible           // n durch k teilbar
               ffree    st(0)
               fincstp
               sub      ecx,1
               jne      @Loop3
               fmul     st(2),st             // k zu st(1) multiplizieren
@NextK:        fsub     st,st(1)             // k:=k-1
               sub      eax,1
               jne      @Loop2               // weiter bis k=1
               jmp      @Finish
@Divisible:    // Ist teilbar. wenn quotient=1 dann n aus Liste entfernen,
               // sonst Quotient in Liste
               fcomi    st,st(2)
               je       @Quotient1           // Quotient ist 1
               fistp    dword [esp+ecx*4]    // Quotient in Liste
               jmp      @NextK
@Quotient1:    // Qoutient=1, n aus Liste entfernen
               ffree    st(0)
               fincstp
               mov      ebx,[esp+edx*4]
               mov      [esp+ecx*4],ebx
               sub      edx,1
               jmp      @NextK
@Finish:       // Alle n aus Liste aufmultiplizieren
               fcomp                        // k vom FPU-Stack nehmen
@Loop4:        fimul    dword [esp+edx*4]
               sub      edx,1
               jne      @Loop4
               // Und durch Produkt(k) dividieren
               fdivrp
               // Liste vom Stack nehmen
               pop      edx
               lea      esp,[esp+edx*4]
               pop      ebx
@End:
end;