Autor Beitrag
Fiete
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 601
Erhaltene Danke: 339

W7
Delphi 6 pro
BeitragVerfasst: Sa 29.09.07 16:49 
Die Unit LangZahlRechnen wurde entwickelt, um mit beliebig langen Ganzzahlen arbeiten zu können.
Zur Geschwindigkeitserhöhung habe ich eine Blocklänge von 9 und den Typ Extended gewählt.
Die Prozedurköpfe stehen unten, Beispiele im Anhang:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
unit LangZahlRechnen;

interface
 uses StdCtrls, SysUtils;

 const T=1000000000;BL=9;
 type TFeld=Array of Extended;

 procedure LangInt(var A:TFeld;B:LongWord);
 // IntegerVariable B umwandeln in ein Array vom Typ TFeld
 function LangKleiner(A,B:TFeld):Boolean; // A<B ?
 function LangGleich(A,B:TFeld):Boolean;  // A=B ?
 procedure LangRead(Zahl:String;var Z:TFeld); // Zahl eingeben
 procedure LangAdd(var S:TFeld;A,B:TFeld);  // A+B
 procedure LangSub(var D:TFeld;A,B:TFeld);  // A-B
 procedure LangMul(var E:TFeld;A,B:TFeld);  // A*B
 procedure LangDivision(var E,R:TFeld;A,B:TFeld); // A / B
 procedure LangIntToStr(Zahl:TFeld;var Erg:String); // Liste --> String wandeln
 procedure LangAusgabeList(LBox:TListBox;S:TFeld); // Ergebnis in Listbox ausgeben
 procedure LangAusgabeMemo(LMemo:TMemo;S:TFeld); // Ergebnis in Memo ausgeben
 procedure LangWurzel(var XA:TFeld;A:TFeld); // W=sqrt(A)
 procedure LangPower(var P:TFeld;Basis,Exponent:LongWord); // P=Basis^Exponent
 procedure LangFakultaet(var Fakultaet:TFeld;N:LongWord); // n!

 implementation


Gruß, Fiete

Moderiert von user profile iconGausi: Delphi-Tags hinzugefügt
Einloggen, um Attachments anzusehen!
_________________
Fietes Gesetz: use your brain (THINK)
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: So 30.09.07 00:18 
Der Typ Extended ist gerade im Bereich Integer-Arithmethik auf Grund seiner Eigenschaften als "Glitkomma-Zahl" nicht die beste Wahl für das Rechnen ohne Rundungsfehler. Auch kann man problemlos ähnliche Geschwindigkeiten mit geeigneten Algorithmen auf DWORD-Basis (Also zur Basis 2^32) erreichen.

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Fiete Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 601
Erhaltene Danke: 339

W7
Delphi 6 pro
BeitragVerfasst: Mo 01.10.07 12:25 
Der Typ DWORD-Basis (Also zur Basis 2^32) reicht bei weitem nicht aus.
Die Zeile

H:=A[J]*B[I]+E[I+J-1]+UE;

ergibt eine 18-stellige Zahl, bei der noch keine Rundungsfehler entstehen!

Gruß Fiete

_________________
Fietes Gesetz: use your brain (THINK)
Allesquarks
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 510

Win XP Prof
Delphi 7 E
BeitragVerfasst: Fr 05.10.07 22:15 
Ich würde user profile iconBenBe da recht geben, dass dwords besser geeignet sind. Ich habe mich damals auch für die dwords entschieden. Dies hatte mehrere Gründe. Ohne jetzt deine Leistung schmählern zu wollen aber vielleicht interessierts dich ja:

1. Bei extended verschenkst du Speicherplatz, da bei jedem extended in deinem Feld ein Vorzeichen und noch einen Exponenten mitspeicherst. Das ist gleichzeitig ein Geschwindigkeitsverlust denn du brauchst für jeden extended drei Speicherzugriffe (10 byte) obwohl du darin nur 64 bit signifikante Stellen hast also eigentlich 2 Speicherzugriffe nur bräuchtest. Also da Addition von dwords 1 Takt braucht, dürftest du so ungefähr durch diese Designentscheidung fast 30% Performance einbüßen. Desweiteren kann es sein, dass der Coprozessor hierfür auch länger braucht, als die integerpipeline. Da der ja intern noch die Exponenten "normalisieren" muss und ja nicht ahnen kannst, dass du die Fließkommaeinheit für Ganzzahlen benutzt/missbrauchst.

2. Überläufe sind in der Integerpipeline einfach per Flag abrufbar und können dann über den assemblerbefehl adc mit überlauf direkt weiterverarbeitet werden, das spart das if in der innersten Schleife und damit auch erheblich Zeit da dann ja häufig gesprungen wird. Ich gebe zu dass ist dann x86 speziefisch aber das schränkt für die meisten den Einsatzbereich nicht ein. Selbst wenn man adc nicht verwenden mag dann dürfte das setzen der Flags aus der fpu ebenfalls nochmal länger dauern als diese dierekt abzufragen in der integerpipeline.

Das zum Grundsätzlichen. Allerdings sind in deiner Unit noch zusätzliche unnötige Beschränkungen.

Einerseits könnte man indem man das extendedfeld als packed deklariert wenigstens alle zwei extended einen Speicherzugriff sparen weil der dritte dann wenigstens schon im Cache ist.

In der Addition und, wahrscheinlich auch woanders, erzeugst du einen Überlauf bei T, das du meiner meinung nach willkürlich auf 100... setzt. Der Computer rechnet binär und ein extended kann ganze Zahlen bis 2^64 oder (2^64)-1 ohne Rundung darstellen, weiß jetzt gerade nicht genau. Jedenfalls beschränkst du durch das Heruntersetzen dieses Limits den Wertebereich eines einzelnen extendeds und musst infolgedessen im gleichen Verhältnis längere Arrays of extended verwenden um gleich große Zahlen zu erreichen. Hier gilt dann wieder das gleiche Argument wie oben, dass mehr Speicherzugriffe auch gleichzeitig (bei Addition vermute ich fast linearen Zusammenhang) mehr Geschwindigkeit kostet.
Fiete Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 601
Erhaltene Danke: 339

W7
Delphi 6 pro
BeitragVerfasst: So 07.10.07 12:46 
Danke für die Anstöße!

Das Ganze müßt ihr historisch sehen. Die Unit ist im DOS-Zeitalter auf einem 8086 entstanden als es nur 16-Bit-Rechner gab und der Coprozessor wirklich hardwaremäßig drinsteckte.

Mein Ziel war es mit einer Operation möglichst viele Ziffern zu berechnen, daher die Blocklänge 9 und T=1000000000.
Mit dem Datentyp Int64 wäre heute alles erledigt. Extended durch Int64 ersetzen und div bzw. mod einbauen.

Die ganze Unit könnte natürlich noch in Assembler geschrieben werden. Da wäre Extended wieder von Interesse, da der Compiler nur die beiden oberen Register benutzt und nicht alle 8.

Gruß, Fiete

_________________
Fietes Gesetz: use your brain (THINK)