DAIDEN.IN Book Archive > German 4 > New PDF release: Algebraische Algorithmen

New PDF release: Algebraische Algorithmen

By Prof. Dr. Attila Pethö (auth.), Prof. Dr. Michael Pohst (eds.)

ISBN-10: 3322802809

ISBN-13: 9783322802804

ISBN-10: 3528065982

ISBN-13: 9783528065980

Dr. Attial Pethö ist Dozent für Mathematik an der Kossuth Lajos Universität in Debrecen, Ungarn.

Show description

Read Online or Download Algebraische Algorithmen PDF

Similar german_4 books

Transport- und Lagerlogistik: Planung, Aufbau und Steuerung by Heinrich Martin (auth.) PDF

BuchhandelstextDer Schwerpunkt des Buches liegt auf der planerischen shipping- und Lagertechnik mit notwendiger Vordimensionierung. Die bearbeiteten Themen der shipping- und Lagerbereiche sind nach funktionellem Aufbau, Vor- und Nachteilen, Einsatzgebieten und planerisch interessierenden Fakten dargestellt.

Technische Informatik 2: Grundlagen der Computertechnik by PD Dr.-Ing. Wolfram Schiffmann, Dipl.-Phys. Robert Schmitz PDF

Die beiden B? nde Technische Informatik bieten einen verst? ndlichen Einstieg in dieses wichtige Teilgebiet der Informatik. Leser mit unterschiedlichen Vorkenntnissen gewinnen schrittweise einen ? berblick ? ber die ben? tigten elektrotechnischen und elektronischen Grundlagen. Auf dieser foundation werden die Komponenten und Strukturen von heutigen Computersystemen eingef?

Additional info for Algebraische Algorithmen

Example text

Die Zeitkomplexitat eines solchen Algorithmus ist durch die Anzahl und die GroBe der Teilprobleme und zu einem geringeren AusmaB vom Arbeitsaufwand fiir die Zerlegung des Problems bestimmt. Wir werden solche Algorithmen noch oft sehen. Einen Bericht iiber eine Implementierung des Karatsuba-Algorithmus und seine Anwendung bei der Suche nach Primzahlzwillingen findet man in [57]. Wir mochten hier dar auf hinweisen, daB der Karatsuba-Algorithmus nicht die schnellste Moglichkeit ist, groBe Zahlen zu multiplizieren.

Es sei Rein Ring, in dem die Grundoperationen algorithmisch sind, a E R und n E N. Der folgende Algorithmus berechnet offensichtlich das Element an. 3 (Potenzierung) a E R,n E N, n in der dyadischen Listendarstellung (no, .. , n,) gegeben, Output: an. Input: 1. If n = ( ) then output 1 return. 2. (3 +- a, m +- inv(n), m +- red(m), 3. while m <> ( ) do { (3 +- (32, if first(m)= 1 then (3 +- (3a, m +- red(m), } 4· output (3, return. Die n-te Potenz eines Elementes konnen wir also mit hochstens 2Iog(n) Multiplikationen berechnen, wenn die Zwischenresultate nicht schnell wachsen.

5) verknupft sind. Wenn Ui und UiH schon vorhanden sind, dann muB man Ui durch Ui+l dividieren. 6 proportional zu l(UiH)I(qi+I). Es gilt offensichtlich l(Ui+I) ~ l(UI). Damit erhalten wir die folgende obere Abschatzung. 3 Ring der ganzen Zahlen 30 tiGCDE(m, n, k) < < t l(Ui)l(qi) :::; l(UI) 4l(U,)! 6) mit g = 2 benutzt haben. Ur-I E S gi·lt qr = - un d U 1• Ui-I = qiUi + Ui+l > (qi + 1)Ui+l, :n Ui-I d as h ewt qi + 1 < --. + 1) < Ur-I II r-I qr i=1 r-I Ur Ui-I _ i=1 Ui+1 - nr-I i-O nr Ur Ui _ UOUI 2 i=2 Ui Ur ( :::; Uo ) Ur 2 , woraus wir unmittelbar erhalten.

Download PDF sample

Algebraische Algorithmen by Prof. Dr. Attila Pethö (auth.), Prof. Dr. Michael Pohst (eds.)


by Daniel
4.1

Rated 4.56 of 5 – based on 43 votes