Autor Beitrag
MrSaint
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1033
Erhaltene Danke: 1

WinXP Pro SP2
Delphi 6 Prof.
BeitragVerfasst: So 08.08.04 12:25 
Hi!

Ich schreibe mir grade eine Langzahlarithmetik (also eine Klasse, die mit theoretisch unendlich langen Zahlen rechnen kann). Funktioniert alles soweit, nur leider dauert das dividieren im moment eindeutig viel zu lang. ich mach es im moment so, dass ich die Zahl nehme und davon den Divident in einer Schleife abziehe, bis ich bei null bin (oder es eben nicht mehr teilabr ist) und zähle dabi hoch, wie oft ih abgezogen habe. Sollte dazusagn, dass das eine ganzzahlige Division sein soll, also praktisch ein Äquivlent zu div. So ungefähr mach ich das im moment, hlt nur mit meinen methoden meiner Klasse.. also so könnte man das ausdrücken, wenn man mit normalen integers arbeiten würde:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
while (iZuDividieren > iDivident) do
begin
  dec(iZuDividieren, iDivident);
  inc(iLoesung);
end;
dec(iLoesung);


Ja, also diese Methode is zu langsam. Hat jemand villeicht ne idee wie ich das beschleunigen könnte bzw. gibt es irgendnen algo, der das schneller erledigt? Mir fällt grad nix ein :/




MrSaint


Moderiert von user profile iconTino: Topic aus Sonstiges verschoben am Di 07.09.2004 um 10:45

_________________
"people knew how to write small, efficient programs [...], a skill that has subsequently been lost"
Andrew S. Tanenbaum - Modern Operating Systems
catweasel
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 487
Erhaltene Danke: 1

Win 7 64bit
Delphi 7 Second Sedition V7.2
BeitragVerfasst: So 08.08.04 12:35 
Kann man das nicht so machen wie beim "Teilen mit Rattenschwanz" wie wir alle es mal in der 2. Klasse gelernt haben...

Also: letzte Stelle Divident guggen ob divisor reinpasst, wenn nich zwei letzten Dividentenstellen und dann eben abziehen, ein bischen was "im Sinn" behalten und die nächte Ziffer "runterholen" .....

Dann sind die ersten Stellen sogar schon verfügbar bevor die Division komplett is ;-)

Catweasel

_________________
Pommes werden schneller fertig wenn man sie vor dem Frittieren einige Minuten in siedendes Fett legt.
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: Mo 09.08.04 21:13 
Geht vom Schema her relativ einfach:

Anlegen eines Puffers (genauso groß, wie der Divisor, d.h. dass, durch dass du teilst).
Puffer = 0 (wird der Rest)
Ergebnis = 0
Schleife: (So oft, wie die Zahl Bits hat)
Puffer Multiplizieren mit 2
Ergebnis Multiplizieren mit 2
Zahl multiplizieren mit 2
Übertragsbit zu Puffer addieren
If Puffer > Divisor Then Ergebnis + 1
Wiederholen

Teilt (wenn effektiv implementiert) auf nem 1,4 GHz AMD ne 64 KB Zahl in < 1 sec

Hab Quelltext dafür da, u.a. auch die ganzen anderen Rechenarten.

_________________
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.
MrSaint Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1033
Erhaltene Danke: 1

WinXP Pro SP2
Delphi 6 Prof.
BeitragVerfasst: Di 10.08.04 06:36 
Guten morgen!

Danke erst mal euch beiden!
Hmm, BenBE, kannst mir erklären, warum das so funktionieren soll? ich mein, implementiert bekomm ich das, aber ich will ja auch verstehen warum :)



MfG
MrSaint

_________________
"people knew how to write small, efficient programs [...], a skill that has subsequently been lost"
Andrew S. Tanenbaum - Modern Operating Systems
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: Di 10.08.04 20:29 
Hängt mit dem Puffer zusammen. Stell dir die Zahl als Binärzahl vor. Durch die Multiplikation mit zwei erhälst du immer die vorderste Ziffer als LSb des Restes. Alles andere läuft dann ab, wie bei der Div mit Rattenschwanz.

_________________
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.
MrSaint Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1033
Erhaltene Danke: 1

WinXP Pro SP2
Delphi 6 Prof.
BeitragVerfasst: Di 31.08.04 19:21 
Hi!

Sorry erst mal, dass ich mich so lang nemme gemeldet hatte, aber ich hatte für dieses Projekt zu wenig zeit, da ich gearbeitt hab und auch noch versch. andere Sachen dazwichen kamen (z.B. abrauchen der HDD und komplette Umstellung auf WinXP).
BenBE, ich muss leider sagen, dass ich das immer noch net verstanden hab :( Also dividieren mit Rattenschwanz sagt mir erst mal überhaupt nix :oops: und dann versteh ich auch den Satz net:
Zitat:
Durch die Multiplikation mit zwei erhälst du immer die vorderste Ziffer als LSb des Restes

Wenn mn eine Binärzahl mit 2 multipliziert verschiebt man, bildlich gesprochen, die Ziffern all eine Stelle nach links und hängt hinten ne null an. Okay, aber was hat das mit dem Rest zu tun? und was LSb heißen soll, weiß ich au net wirklich :oops: Also tut mir leid, wenn ich mich hier "a bissal deppad" anstell, aber ich verstehs einfach net :( Kannst mir das mal bitte etwas ausführlicher erklären ? Wär super :)




MrSaint

_________________
"people knew how to write small, efficient programs [...], a skill that has subsequently been lost"
Andrew S. Tanenbaum - Modern Operating Systems


Zuletzt bearbeitet von MrSaint am Di 31.08.04 19:36, insgesamt 1-mal bearbeitet
.Chef
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1112



BeitragVerfasst: Di 31.08.04 19:26 
Vielleicht hilfts ja weiter:

Ich hab mal ein Tutorial über 16-Bit-Division auf 8-Bit Controllern geschrieben, also quasi das selbe Problem etwas kleiner. Lies es einfach mal durch: Link
Das Prinzip ist das vom BenBE angesprochene.

Gruß,
Jörg

_________________
Die Antworten auf die 5 häufigsten Fragen:
1. Copy(), Pos(), Length() --- 2. DoubleBuffered:=True; --- 3. Application.ProcessMessages bzw. TThread --- 4. ShellExecute() --- 5. Keine Vergleiche von Real-Typen mit "="!
MrSaint Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1033
Erhaltene Danke: 1

WinXP Pro SP2
Delphi 6 Prof.
BeitragVerfasst: Di 31.08.04 20:32 
dangge... jetzt weiß ich zumindest was ihr mit "Division mit Rattenschwanz" gemeint habt ;)
ich werd das mal versuchen in meine Klasse zu implementieren, bin mir da aber net wirklih sicher, ob ich damit erfolg haben werde... so ganz sicher fühl ich mich no net dabei ;) aber mal sehn, wenns net geht, mld ich mich einfach nommal ;)



THX

MrSaint

_________________
"people knew how to write small, efficient programs [...], a skill that has subsequently been lost"
Andrew S. Tanenbaum - Modern Operating Systems
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: Di 31.08.04 20:32 
LSb = Least Significant Bit
LSB = Least Significant Byte

Mit der Multiplikation mit 2 scheibst du einfach nur eine Ziffer aus dem Puffer links und fügst diese zum bisherigen Rest hinzu. Dadurch erreichst du den gleichen Effekt wie beim Herunterziehen der nächsten Ziffer bei der Rattenschwanzdivision.

_________________
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.
MrSaint Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1033
Erhaltene Danke: 1

WinXP Pro SP2
Delphi 6 Prof.
BeitragVerfasst: Mi 01.09.04 13:53 
So, hab das nun alles kapiert und das so implementiert, wie BenBE vorher vorgeschlagen hatte.

BenBE hat folgendes geschrieben:
Schleife: (So oft, wie die Zahl Bits hat)
Puffer Multiplizieren mit 2
Ergebnis Multiplizieren mit 2
Zahl multiplizieren mit 2
Übertragsbit zu Puffer addieren
If Puffer > Divisor Then Ergebnis + 1
Wiederholen


Ich hab es nur nicht mit dem Zahl *2 gemacht, sondern ich les mir die Bits einfach von vorne bis hinten aus :) Funktioniert super :)
Ein ganz großes DANKE!



MrSaint

_________________
"people knew how to write small, efficient programs [...], a skill that has subsequently been lost"
Andrew S. Tanenbaum - Modern Operating Systems