Prüfziffer für IBAN berechnen

[BUG]

Zitat von Amateurprofi:

Ja, mit der Folge dass man etwa 10 Mal soviel Mod Operationen braucht.

Allerdings sind Sprünge (wie im if) auch nicht das Wahre, insbesondere bei Pipeline-Prozessoren. Zudem sind Divisionen heute auch nicht mehr so teuer, wie sie mal waren.
Im Zweifelsfall müsste man ausmessen, was schneller ist (eventuell abhängig von der Branch-Prediction/Speculative-Execution des Prozessors).

Bei dieser Funktion gibt es noch andere Dinge zu optimieren. Zum Beispiel ist die Speicherallokation für den temporären String nicht unbedingt billig. Auch den Rückgabewert könnte man vielleicht effizienter Zusammenbasteln.
Ansonsten kann man überlegen, nach wie vielen Stellen man jeweils frühestens einmal modulo 97 rechnen muss und dann die Schleife entsprechen aufteilen.

Und dann ist da noch die Frage, ob sich der Optimierungsaufwand überhaupt lohnt. Schließlich ist die Geschwindigkeit dieser Funktion nur bedeutsam, wenn man sie auf sehr vielen Nummern ausführen will, wobei es dann vermutlich eher an den IO-Operationen hängt.

[Amateurprofi]

Zitat von BUG:

Zitat von Amateurprofi:

Ja, mit der Folge dass man etwa 10 Mal soviel Mod Operationen braucht.

Allerdings sind Sprünge (wie im if) auch nicht das Wahre, insbesondere bei Pipeline-Prozessoren. Zudem sind Divisionen heute auch nicht mehr so teuer, wie sie mal waren.
Im Zweifelsfall müsste man ausmessen, was schneller ist (eventuell abhängig von der Branch-Prediction/Speculative-Execution des Prozessors).

Bei dieser Funktion gibt es noch andere Dinge zu optimieren. Zum Beispiel ist die Speicherallokation für den temporären String nicht unbedingt billig. Auch den Rückgabewert könnte man vielleicht effizienter Zusammenbasteln.
Ansonsten kann man überlegen, nach wie vielen Stellen man jeweils frühestens einmal modulo 97 rechnen muss und dann die Schleife entsprechen aufteilen.

Und dann ist da noch die Frage, ob sich der Optimierungsaufwand überhaupt lohnt. Schließlich ist die Geschwindigkeit dieser Funktion nur bedeutsam, wenn man sie auf sehr vielen Nummern ausführen will, wobei es dann vermutlich eher an den IO-Operationen hängt.

Willst du jetzt ernsthaft darüber diskutieren, ob der durch das IF verursachte Sprung mehr Zeit kostet als ein MOD ?

Selbstverständlich hast du Recht, dass man das noch erheblich optimieren kann.
Du sagst "müsste man ausmessen", "kann man überlegen",
Miss es doch und überleg es mal und dann schreibe die optimale Funktion.
Da wären Dir einige Leute dankbar.

Mein Ziel war nicht, eine "superperformante" Funktion zu zeigen, ich habe schlicht und einfach einen Code aus einem bestehenden Projekt kopiert. http://www.delphipraxis.net/170138-i...ml#post1228268
Dann wurde eine "Optimierung" gezeigt, die (auf meinem Rechner) etwa 65% mehr Zeit braucht.
Entsprechend habe ich reagiert.

[sx2008]

Bei der Erzeugung von IBANs ist etwas wichtiger als alles Andere: Korrektheit.
Das Ding muss richtig rechnen; das hat oberste Priorität.
Nichts ist schlimmer als wenn in einer Produktivumgebung tausende falsche IBANs verschickt werden.

Daher muss man so vorgehen:
Schritt 1:
Testdaten besorgen und eine Testumgebung für die IBAN-Funktion aufbauen.
Man sollte mindestens 5 versch. IBANs testen.
Dazu kann man ein kleines Testprogramm schreiben oder man verwendet DUnit.
Man könnte auch nur mit Assert-Anweisungen arbeiten; Hauptsache es gibt Tests.
Nicht nur die Gut-Fälle testen sondern auch gezielt ungültige Daten übergeben die von der IBAN-Funktion abgewiesen werden müssen.

Schritt 2:
Umsetzen der IBAN Berechnung in Code.
Dabei sollte man gleich alle Länder vorsehen.
Ausserdem gehört dazu auch eine Prüfung der Eingabeparameter (Buchstaben in Konto-Nr, ...).

Schritt 3:
Optional prüfen, ob man den Code noch optimieren kann.
Wichtig ist, dass man mit dem Optimieren aufhört bevor der Code schlecht lesbar wird.
Einfacher Code ist meist auch schneller (bzw. ausreichend schneller) Code.
Nach jedem Optimierungsschritt muss auf Korrektheit getestet werden.

[Furtbichler]

Zitat von sx2008:

Korrektheit...das hat oberste Priorität.

Richtig. Nagel auf den Kopf und den Punkt getroffen.
Klitzekleines aber:

Zitat:

Man sollte mindestens 5 versch. IBANs testen.

Wenn, dann richtig: Stichwort: Codeabdeckung. Die Tests müssen in diesem Falle wirklich alle Fälle abdecken, d.h. (ich hab nu nich in den Code geschaut) es müssen Äquivalenzklassen gebildet werden, das sind die Mengen von Eingaben, die den jeweils gleichen Codepfad durchlaufen. Und aus jeder der Äquivalenzklassen reicht es, 1-3 Kandidaten zu nehmen.

Gibt es Übergänge zwischen den Äquivalenzklassen (z.B. <0, =0, >0), nimmt man sich jeweils Kandidaten 'am Rand', also die, die gerade noch in eine Klasse passen.

Bei gutem Code benötigt man dann keine gezielten 'Angriffe' mit ungültigen Daten, denn diese sind in einer oder mehrerer Äquivalenzklassen enthalten. Trotzdem...

Zitat von sx2008:

Nicht nur die Gut-Fälle testen sondern auch gezielt ungültige Daten übergeben die von der IBAN-Funktion abgewiesen werden müsssen...Nach jedem Optimierungsschritt muss auf Korrektheit getestet werden.

Ja, ja, ja. Abnick, full ACK, und was man sonst noch so alles sagt.

Das sollte man eigentlich für jede Klasse machen, aber wer hat schon die Zeit dafür (ja: man muss sie sich nehmen).

[Amateurprofi]

@sx2008:
Alles was du schriebst ist absolut korrekt.
In meinem Projekt IBANs http://www.delphipraxis.net/170138-ibans.html habe das zum Teil realisiert.

Die Prüfung von IBANs ist für alle Länder, soweit mir die Daten zugänglich waren, möglich, allerdings betrifft das nur die "Syntax" der IBANs.

Bei der Erstellung von IBANs (ich habe mich da auf "deutsche" beschränkt, bin ich noch etwas weiter gegangen.
Ich prüfe da nicht nur, ob die BLZ aus 8 und die Kontonummer aus 10 Dezimalziffern besteht, sondern auch,
- ob die BLZ tatsächlich existiert (BLZ-Datei der Deutschen Bundesbank)
- ob die Kontonummer von der der BLZ zugeordneten Prüfmethode als gültig anerkannt wird.
Letzteres ist aber auch nur eingeschränkt aussagefähig, weil die Prüfmethoden nur prüfen, ob die Kontonummer eine Kontonummer der jeweiligen Bank sein könnte, jedoch nicht, ob die Kontonummer wirklich existiert.
Wirklich "lecker" ist die Prüfmethode Nr. 09 - die gibt immer "OK" zurück.

Wie ich schon schrieb, ist die in #5 vorgestellte Funktion meinem IBANs-Projekt entnommen.
Da dort die Korrektheit der BLZ und Kontonummer schon an anderer Stelle erfolgt, habe ich in der Funktion zur Erstellung der IBAN diese Prüfung nicht vorgenommen.

Du schriebst "Wichtig ist, dass man mit dem Optimieren aufhört bevor der Code schlecht lesbar wird."
Ich denke "lesbar" ist eine recht subjektive Angelegenheit.
Als Assembler-Freak ist für mich z.B. ASM-Code lesbar wie ein Buch, andere sehen das, subjektiv zu Recht, ganz anders.
Nun ja, zum Abschluss:
Ich habe mir den Spaß gemacht, die in #5 stehende CreateGermanIBan noch einmal zu optimieren.

Ergebnis für 10M Durchläufe:
Original : 1965 MS, ASM-Version 390 MS, also 5 Mal so schnell.

Delphi-Quellcode:

FUNCTION ACreateGermanIban(const BankCode,Account:String):String;
asm
               test     eax,eax
               je       @Fail
               cmp      [eax-4],8
               jne      @Fail
               test     edx,edx
               je       @Fail
               cmp      [edx-4],10
               jne      @Fail
               push     ebx
               push     edi
               push     esi
               mov      ebx,eax              // @BankCode
               mov      edi,edx              // @Account
               mov      esi,ecx              // @Result
               // SetLength(Result,22)
               mov      eax,ecx
               mov      edx,22
               call     System.@UStrSetLength
               // Result[1..4]:='DE00'
               mov      esi,[esi]
               mov      [esi],$450044        // 'DE'
               mov      [esi+4],$300030      // '00'
               // Result[5..12]:=BankCode
               movdqu   xmm0,[ebx]
               movdqu   [esi+8],xmm0
               // Result[13..22]:=Account
               movdqu   xmm0,[edi]
               movdqu   [esi+8+16],xmm0
               mov      eax,[edi+16]
               mov      [esi+8+16+16],eax
               // Prüfziffer errechene
               mov      ebx,97               // Divisor
               xor      eax,eax
               // ... 9 Zeichen ab BankCode[1]
               lea      edi,[esi+8+18]       // Hinter Result[13]
               mov      edx,-9               // 9 Zeichen auswerten
               call     @GetMod
               // ... 8 Zeichen ab Account[2]
               add      edi,16               // Hinter Result[21]
               mov      edx,-8               // 8 Zeichen auswerten
               call     @GetMod
               // ... Account[10]
               movzx    ecx,word[edi]
               sub      cx,'0'
               lea      eax,[eax*4+eax]
               lea      eax,[eax*2+ecx]
               // ... 'DE00'
               mov      ecx,1000000
               mul      ecx
               add      eax,131400           // 'DE00'
               div      ebx
               // CheckSum:=98-Checksum
               mov      eax,98
               sub      eax,edx
               // Result[3..4]=CheckSum
               xor      edx,edx
               mov      bl,10
               div      bl
               or       [esi+4],al
               or       [esi+6],ah
               pop      esi
               pop      edi
               pop      ebx
               ret
@GetMod:       movzx    ecx,word[edi+edx*2]
               sub      cx,'0'
               lea      eax,[eax*4+eax]
               lea      eax,[eax*2+ecx]
@NoDiv:        add      edx,1
               jl       @GetMod
               div      ebx
               mov      eax,edx
               ret
@Fail:         mov      eax,ecx              // @Result
               call     System.@WStrClr
end;

[Mikkey]

Um auf Deine ursprüngliche Frage zurückzukommen:

Wenn Du eine Zahl (dargestellt als einzelne Ziffern) hast, die in dem Programmiersystem nicht verwendet werden kann, kannst Du sie teilen. Aus Deiner 24-stelligen Zahl machst Du z.B. zwei 12-stellige:

n * 10^12 + m

Du bildest dann den n mod 97. Das Ergebnis multiplizierst Du mit 10^12 und addierst es zu m.

Das Ergebnis modulo 97 ergibt Dein gewünschtes Ergebnis.

Hast Du nur eine 32-Bit-Arithmetik zur Verfügung, kannst Du natürlich auch in drei 8-stellige Zahlen teilen.

[jfheins]

Es reicht übrigens auch, wenn du es mit 10^12 mod 97 (also 50) multiplizierst.
Für eine Beispielrechnung verweise ich hier mal frech auf meinen eigenen Post in der EE: http://www.entwickler-ecke.de/viewto...=679625#679625