AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Langzahlarithmeik

Ein Thema von eF-eS · begonnen am 2. Aug 2005 · letzter Beitrag vom 3. Aug 2005
Antwort Antwort
eF-eS
(Gast)

n/a Beiträge
 
#1

Langzahlarithmeik

  Alt 2. Aug 2005, 19:50
Hallo,

ich wollte mal fragen, ob von Euch einer schon mal den Karatsuba-Algo (Multiplikation von Langzahlen) gecodet hat und mir den Quelltext zur Einicht mailen könnte.

Vielen Dank!

lg F
  Mit Zitat antworten Zitat
Benutzerbild von nailor
nailor

Registriert seit: 12. Dez 2002
Ort: Karlsruhe
1.989 Beiträge
 
#2

Re: Langzahlarithmeik

  Alt 2. Aug 2005, 20:11
findet zwar nix in delphi, aber vllt dennoch interessant für dich (und auch allgemein sehr interessant, die seite): http://koders.com/?s=Karatsuba&_%3Ab...Ala=*&_%3Ali=*
Michael N.
http://nailor.devzero.de/code/sharpmath/testing/ --- Tests, Feedback, Anregungen, ... aller Art sehr willkommen!
::: don't try so hard - it'll happen for a reason :::
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#3

Re: Langzahlarithmeik

  Alt 2. Aug 2005, 23:04
Ja ich habe Karatsuba gecodet in ganz verschiedenen Algorithmen.
Karatsuba ist nur eine spezielle Form eines allgemeineren Verfahrens, dem "Divide & Conquer" -> Teile und Herrsche Verfahren. Karatsuba teilt dabei immer in 2 Hälten um diese dann rekursiv wiederum zu teilen bis hinunter auf einen gewählten Breakeven Point ab dem mit einem einfacheren Verfahren zb. multipliziert wird.
Höherwertige Verfahren der gleichen Methode sind zb. die Toom-Cook Abkömmlinge. Diese teilen das Problem in 3,5,7,9 Hälten auf. Mit Karatsuba muß man nicht nur Multiplizieren sondern es gibt auch Karatsuba Verfahren für die Division oder Wurzelziehen.

Ich persönlich habe in meinem DECMath folgende Karatsubalike Verfahren implementiert
- Karatsuba Multiplikation
- Karatsuba Quadrierung
- Karatsuba Quadrat-Wurzel nach P. Zimmerman
- Karatsuba Division nach Burnickel & Ziegler
- Toom-Cook-3 Multiplikation


DECMath findest du hier in der DP für Delphi 5,6,7 als binäre Distributation.

Suchst du Sourcen so wirst du für Delphi/PASCAL nur wenig fündig werden. Du solltest C/C++ lesen können dann kannst du dir ApFloat, Gimp, GMP, LiDIA usw. anschauen.

Gruß Hagen
  Mit Zitat antworten Zitat
eF-eS
(Gast)

n/a Beiträge
 
#4

Re: Langzahlarithmeik

  Alt 3. Aug 2005, 06:40
Zitat von negaH:
Suchst du Sourcen so wirst du für Delphi/PASCAL nur wenig fündig werden. Du solltest C/C++ lesen können dann kannst du dir ApFloat, Gimp, GMP, LiDIA usw. anschauen.
Yüp, Hagen, das habe ich gestern beim googlen auch gemerkt.

Alles klar, werde mich hier mal noch schlau machen.

Wie kann ich diesen Thread schließen?
  Mit Zitat antworten Zitat
Benutzerbild von TeronG
TeronG

Registriert seit: 19. Jul 2004
Ort: München
960 Beiträge
 
Delphi 2007 Professional
 
#5

Re: Langzahlarithmeik

  Alt 3. Aug 2005, 08:44
Zitat von negaH:
teilen das Problem in 3,5,7,9 Hälten
[klugscheiß] 9 Hälfen nicht eher 9 Teile
einer der wenigen Hagen-Post's die ich komplette verstehe und dann sogar nen Fehler finde!!
龍 Der Unterschied zwischen Theorie und Praxis ist in der Praxis größer als in der Theorie.
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#6

Re: Langzahlarithmeik

  Alt 3. Aug 2005, 10:57
@TeronG:

Ja, 9 Teile da haste Recht
Allerdings sind alle Karatsuba-Verfahren rekursive Verfahren. Bevor man in die Rekursion tiefer geht wird X geteilt, dann rekursiv jeder dieser Teile wiederum geteilt und nach Rückkehr aus der Rekursion werden die Teilprodukte wieder zusammengesetzt. Bei diesem Teilen + Zusammensetzen ist es aber so das die korrekte Reihenfolge des Zusammensetzens sehr wichtig ist. Und deshalb sprach ich von Hälten da zb. die Teile No. 6+7+8 stufenweise zusammengesetzt werden müssen, man hat also für diesen Zwischenschritt des Zusammensetzens immer noch Linke und Rechte Hälften.

Gruß Hagen
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 18:02 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz