| Autor |
Beitrag |
MrSaint
      
Beiträge: 1033
Erhaltene Danke: 1
WinXP Pro SP2
Delphi 6 Prof.
|
Verfasst: 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:
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 Tino: 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
      
Beiträge: 487
Erhaltene Danke: 1
Win 7 64bit
Delphi 7 Second Sedition V7.2
|
Verfasst: 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
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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 
      
Beiträge: 1033
Erhaltene Danke: 1
WinXP Pro SP2
Delphi 6 Prof.
|
Verfasst: 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
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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 
      
Beiträge: 1033
Erhaltene Danke: 1
WinXP Pro SP2
Delphi 6 Prof.
|
Verfasst: 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  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  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
      
Beiträge: 1112
|
Verfasst: 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 
      
Beiträge: 1033
Erhaltene Danke: 1
WinXP Pro SP2
Delphi 6 Prof.
|
Verfasst: 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
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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 
      
Beiträge: 1033
Erhaltene Danke: 1
WinXP Pro SP2
Delphi 6 Prof.
|
Verfasst: 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
|
|
|