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 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

Bernhard Helmes schrieb:

> 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

Bernhard Helmes (rom*devalco.de) schrieb:
> 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

Markus Wichmann schrieb:
> Bernhard Helmes (rom*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
> in höchstem Maße macht. ...

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

Detlef Müller wrote:

> 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]

Hallo Christopher,

> 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

Bernhard Helmes schrieb:

> 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.rosenthal*web.de

"Bernhard Helmes" <rom*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

Einen erfreulichen guten Abend,

>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

Gruß von den Primzahlen
Bernhard

Jutta Gut (gut.jutta.gerhard*chello.at) schrieb:
>
> "Bernhard Helmes" <rom*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.
>

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
>

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