Quadrieren mit Binomi
Bernhard Helmes
ich habe einen kurzen Algorithmus zum Quadrieren von Zahlen skizziert.
http://beablue.selfip.net/devalco/quadrat.htm
Der Algorithmus verwendet die 1. und 2. binomischen Formeln und läuft
rekursiv,
ich meine, der Algorithmus müßte ein bißchen schneller als die
Schulmultiplikation laufen.
Vielleicht kann man den Algorithmus in der Schule für eine praktische
Anwendung der Binomischen Formeln verwenden, vielleicht ist es aber
auch nur eine mathematische Spielerei :-)
Falls jemand eine Verbesserung im Algorithmus findet,
würde ich mich über eine kurze Antwort freuen.
Freundliche Grüße von den Primzahlen
Bernhard
Rainer Rosenthal
> ich meine, der Algorithmus mￜￜte ein biￜchen schneller als die
> Schulmultiplikation laufen.
Was spricht dagegen, dass Du das mit Laufzeiten untermauerst?
Also: Programme A=alt und B=neu schreiben, Testdatensatz rein
und Zeiten dokumentieren. Anschlieï¿œend hier stolz verkï¿œnden,
wieviel Ersparnis es gebracht hat.
Gruￜ,
RR
Markus Wichmann
> Einen erfreulichen guten Tag,
>
> ich habe einen kurzen Algorithmus zum Quadrieren von Zahlen skizziert.
> http://beablue.selfip.net/devalco/quadrat.htm
>
> Der Algorithmus verwendet die 1. und 2. binomischen Formeln und läuft
> rekursiv,
> ich meine, der Algorithmus müßte ein bißchen schneller als die
> Schulmultiplikation laufen.
>
Vielleicht. Aber jeder Mikroprozessor, den ich kenne, hat
einenMultiplikationsbefehl, der aus deinem Algorithmus Umstandskrämerei
in höchstem Maße macht. Und jeder Mensch, den ich kenne, rechnet das
anders. Möglichkeit 1: "Schulmultiplikation"
81^2 = 81*81 = 81*8*10 + 81*1 = (8*8*10 + 8*1)*10 + 81
Subproblem: 81*8 = 8*8*10 + 8*1 = 160 + 8 = 648
=> 81^2 = 6480 + 81 = 6561
Auf mathematisch: Sei x die natürliche Zahl, deren Quadrat zu berechnen
ist. Sei (a_i) eine Zahlenfolge mit
x = sum_{i=0}^{n} (a_i * 10^i)
Dann ist
x^2 = x * x = (sum_{i=0}^{n} (a_i * 10^i))^2
öhm... aber auf die allgemeine Formel komm ich gerade nicht...
Möglichkeit 2: Binomische Formeln
Die kann man tatsächlich anwenden, aber wohl eher in Dezimalzerlegung
als irgendwas anderes:
55^2 = (50+5)^2 = 50^2 + 2 * 5 * 50 + 5^2
= 2500 + 500 + 25
= 3025
Für Zahlen größer 100 kann man entweder den Multinomialsatz anwenden
(wenn ihn jemand versteht) oder einfach das Problem delegieren:
123^2 = (100 + 23)^2 = 100^2 + 2 * 100 * 23 + 23^2
23^2 = (20 + 3)^2 = 400 + 120 + 9 = 529
123^2 = 10.000 + 4.600 + 529 = 15.129
Das ist ein (in Zahlen: 1) Rekursionsschritt. Dagegen dein Algorithmus:
123 mod 2 = 1
123 mod 4 = 3 -> 123^2 = 124^2 - 2*124 + 1
= 15376 - 248 + 1
= 15129
124 mod 2 = 0 -> 124^2 = 4 * 62^2 = 4*3844 = 15376
62 mod 2 = 0 -> 62^2 = 4 * 31^2 = 4*961 = 3844
31 mod 2 = 1
31 mod 4 = 3 -> 31^2 = 32^2 - 2*32 + 1
= 1024 - 64 + 1 = 961
32 mod 2 = 0 -> 32^2 = 4 * 16^2 = 4*256 = 1024
16 mod 2 = 0 -> 16^2 = 4 * 8^2 = 4*64 = 256
8 mod 2 = 0 -> 8^2 = 4 * 4^2 = 4*16 = 64
4 mod 2 = 0 -> 4^2 = 4 * 2^2 = 4*4 = 16
2 mod 2 = 0 -> 2^2 = 4 * 1^2 = 4
1^2 = 1
Und hier bin ich alle Zeilen runter- und wieder hochgegangen.
> Vielleicht kann man den Algorithmus in der Schule für eine praktische
> Anwendung der Binomischen Formeln verwenden, vielleicht ist es aber
> auch nur eine mathematische Spielerei :-)
>
> Falls jemand eine Verbesserung im Algorithmus findet,
> würde ich mich über eine kurze Antwort freuen.
>
Wofür soll der Algorithmus sein? Kopfrechnen? Da bleibe ich lieber bei
der Dezimalzerlegung. Maschinenrechnen? Dafür ist er schon zu
kompliziert.
> Freundliche Grüße von den Primzahlen
> Bernhard
HTH,
Markus
--
Nur weil ein Genie nix reißt, muß ja nun nicht gleich jeder Idiot
pausieren... Bully hats ja auch geschafft.
-- gUnter nanonüm in de.alt.anime
Detlef Müller
> Bernhard Helmes (r...@devalco.de) schrieb:
>> Einen erfreulichen guten Tag,
>>
>> ich habe einen kurzen Algorithmus zum Quadrieren von Zahlen skizziert.
>
> Vielleicht. Aber jeder Mikroprozessor, den ich kenne, hat
> einenMultiplikationsbefehl, der aus deinem Algorithmus Umstandskrämerei
Um Solche grundlegenden Algorithmen zu motivieren stelle man sich vor,
es geht darum Große Zahlen zu berechnen, sprich solche mit vielen
hundert Dezimalstellen, die womöglich teilweise auf eine Festplatte
ausgelagert sind.
Dann lohnt es sich auf einmal wieder, sich Gedanken über so etwas zu
machen.
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Christopher Creutzig
> Um Solche grundlegenden Algorithmen zu motivieren stelle man sich vor,
> es geht darum Gro�e Zahlen zu berechnen, sprich solche mit vielen
> hundert Dezimalstellen, die wom�glich teilweise auf eine Festplatte
> ausgelagert sind.
> Dann lohnt es sich auf einmal wieder, sich Gedanken �ber so etwas zu
> machen.
Schon, aber dann sollte sich vorher dringend anschauen, was in dem
Bereich bislang �blicherweise verwendet wird. FFT- und Toom-(Cook-)
Multiplikation sind durchaus ein spannendes Thema. Insbesondere bei
Zahlen, die nicht mehr in den Hauptspeicher passen, w�rde ich zun�chst
einmal letztgenannte Klasse anschauen. (Karatsuba ist ein Spezialfall
der Toom-Verfahren.)
Klar, das ist alles nicht auf das Quadrieren optimiert, aber kann man
wirklich erwarten, durch den Spezialfall viel zu gewinnen?
Letzten Endes sind einfache Verfahren, die etwas schneller als
Schulmultiplikation laufen, doch eher eine nette Spielerei als irgendwie
f�r den praktischen Einsatz gut.
Bernhard, was ich nicht verstanden habe: �m�sste ein bisschen schneller
laufen�? Wie weit kommst Du mit der Analyse, wie schnell Dein
Algorithmus und wie schnell der klassische Algorithmus sind?
--
F�r zuverl�ssige Statistiken sind bislang noch
nicht ausreichend viele Universen beobachtet worden.
[Hans Crauel zur Zuverl�ssigkeit von Klimamodellen]
Bernhard Helmes
> Bernhard, was ich nicht verstanden habe: „müsste ein bisschen schneller
> laufen“? Wie weit kommst Du mit der Analyse, wie schnell Dein
> Algorithmus und wie schnell der klassische Algorithmus sind?
Also nehmen wir mal an, man würde die Multiplikation / Quadrierung als
Schulmultiplikation binär durchführen:
a*a =(Anzahl von gesetzten Bits von a)^2 Additionen
Bei meiner Quadrierung wird bei jedem Schritt das a um mindestens 2
Bits verkürzt, also bekäme ich eine Dreiecksmatrix heraus, die ich
zeilenweise addieren müßte : (Anzahl der gesetzten Bits von a)^2 / 2
Bei der Subtraktion um 1 gewinne ich nichts,
Bei der Addition um 1 ersetze ich eine Addition anstelle der
aufeinanderfolgenden 1
11 -> 1 Addition
111 -> 1 Addition
1111 -> 1 Addition
Ich meine, ich käme ungefähr auf einen Faktor 3 heraus, wenn man nur
die Additionen betrachtet,
Wenn ich morgen Zeit habe, werde ich mal ein paar Zufallszahlen
quadrieren und für die einzelnen Additionen nachrechnen.
Ich behaupte nicht, daß dieser Algorithmus bahnbrechend ist, fand ihn
jedoch für das Forum erwähnenswert,
weil man durch die Verwendung von Binomi einen Vorteil hat.
Gruß von den Primzahlen
Bernhard
Rainer Rosenthal
> Ich behaupte nicht, daￜ dieser Algorithmus bahnbrechend ist, fand ihn
> jedoch fï¿œr das Forum erwï¿œhnenswert,
> weil man durch die Verwendung von Binomi einen Vorteil hat.
Sowohl Christopher als auch ich haben Dich nun schon gefragt, wie
groￜ dieser Vorteil ist, d.h. was Du gemessen hast. Es wￜre nett,
wenn Du dazu was sagen kï¿œnntest.
Mit Gruￜ zurￜck an die Primzahlen und die Kubikwurzeln,
Rainer Rosenthal
r.ros...@web.de
Jutta Gut
"Bernhard Helmes" <r...@devalco.de> schrieb
> Ich meine, ich k�me ungef�hr auf einen Faktor 3 heraus, wenn man nur
> die Additionen betrachtet,
Daf�r hast du in jedem Schritt eine Abfrage, ob a gerade, =1 oder =3 mod 4
ist. Das kostet doch sicher auch Rechenzeit.
Gr��e
Jutta
Bernhard Helmes
>Sowohl Christopher als auch ich haben Dich nun schon gefragt, wie
>groß dieser Vorteil ist, d.h. was Du gemessen hast. Es wäre nett,
>wenn Du dazu was sagen könntest.
annähernd einen Faktor 3, wobei ich bei der "Schulmultiplikation" mich
auf die binäre Multiplikation beziehe.
Sourcecode in Mupad
bits:=proc (a)
begin
bits:=0;
aa:=a;
while aa>0 do
if aa mod 2 = 1 then
aa:=(aa-1)/2;
bits:=bits+1;
else
aa:=aa/2;
end_if;
end_while;
return (bits);
end_proc;
laenge:=proc (a)
begin
b:=1;
l:=1;
while b<a do
b:=b*2;
l:=l+1;
end_while;
return (l);
end_proc;
quadrierung:=proc (a)
begin
if a>1 then
if a mod 2 = 0 then
a:=a/2;
q:=4*quadrierung (a);
else
if a mod 4 = 1 then
a:=a-1;
addition:=addition+laenge (2*a+1);
q:=quadrierung (a)+2*a+1;
else
a:=a+1;
addition:=addition+laenge (2*a+1);
q:=quadrierung (a)-2*a+1;
end_if;
end_if;
else
return (1);
end_if;
end_proc;
multiplikation_alt:=0;
multiplikation_neu:=0;
for i from 1 to 1000 do
a:=random ()*random ()*random ();
addition:=0;
quadrierung (a);
multiplikation_alt:=multiplikation_alt+laenge (a)*bits (a);
multiplikation_neu:=multiplikation_neu+addition;
end_for;
print ( multiplikation_neu, multiplikation_alt);
2254976, 6187750
Markus Wichmann
>
> "Bernhard Helmes" <r...@devalco.de> schrieb
>
>> Ich meine, ich käme ungefähr auf einen Faktor 3 heraus, wenn man nur
>> die Additionen betrachtet,
>
> Dafür hast du in jedem Schritt eine Abfrage, ob a gerade, =1 oder =3 mod 4
>
Wenn man einen cleveren Compiler hat, nicht, denn der Rest bei der
Division durch 2 ist genau das letzte Bit der Zahl, der Rest bei
Division durch 4 die letzten zwei Bits. Ein Compiler kann also einfache
Bittestoperationen verwenden. Sicher, es kostet Rechenzeit, aber
verglichen mit etwas so komplexem wie der Addition ist das nix.
> Grüße
> Jutta
Christopher Creutzig
> Division durch 4 die letzten zwei Bits. Ein Compiler kann also einfache
> Bittestoperationen verwenden. Sicher, es kostet Rechenzeit, aber
> verglichen mit etwas so komplexem wie der Addition ist das nix.
Seit etwa 1990 kannst Du f�r eine Addition (bei Zahlen in der Wortgr��e
des Prozessors) effektiv einen Taktzyklus rechnen. Die drei Vergleiche
sind da teurer - einmal ganz zu schweigen von dem, was kleine Codebl�cke
viel langsamer macht als alles andere, was man einbauen kann: Viele
Verzweigungen.
Faktor 3 ist sicherlich ein nettes, theoretisch interessantes Kleinod.
Wobei der Code einige Additionen nicht z�hlt, etwa zur Berechnung von
a-1 oder 2*a+1. (Bernhard, nebenbei, ein kleiner Vorschlag: laenge := n
-> ceil(log(2, n)): d�rfte schneller sein, und lokale Variablen sind
schneller als die globalen Variablen wie b, l, q, bits, aa, die Du
verwendest.)
--
F�r 10 EUR im Jahr erfahre ich hier sogar was meine Meinung ist.
Andere Leute m�ssen daf�r heiraten.
[Lars Friedrich �ber UseNet]
RMG
Bernhard Helmes <r...@devalco.de> wrote:
Wie ich das sehen, hast du vergessen die Division durch 2 mitzuzählen, die gibts nicht umsonst.
--
RMG