Beweis eines Multiplikationsalgorithmus |
| 06.04.2012, 02:14 | Der Mathematik | Auf diesen Beitrag antworten » | ||
| Beweis eines Multiplikationsalgorithmus Es geht um Folgendes:  http://i.imgur.com/pScD8.pngWie man sieht, berechnet dieser Algorithmus die Multiplikation zweier natürlicher Zahlen a und b indem er, in diesem Fall, das a ständig halbiert und abrundet, falls nötig, und das b genauso oft verdoppelt. Nachher werden die Zeilen, welche eine gerade Zahl in der a-Spalte enthalten, "gestrichen", sodass man schliesslich durch die Aufsummierung der verbliebenen b-Spalteneinträge das Produkt von a und b erhält. Wie beweist man nun, dass dieser Algorithmus gültig ist für beliebige natürliche Zahlen a & b? Ich bin eigentlich Informatiker im Grundstudium und habe leider meistens nur die Implementation solcher mathematischer Gedankenkonstrukte geübt. Für das Beweisen solcher Algorithmen fehlen mir, glaube ich, immer noch die rigorosen Beweistechniken eines echten Mathematikers. Eine Idee habe ich aber schon, ich weiss halt nur nicht wie ich sie in einen formellen, mathematisch hieb- und stichfesten, Beweis verwandle. Wenn man die Zahl a umrechnet in das Binärsystem, in dem obigen Fall wäre es: [44] Zehnersystem = [101100] Binärsystem und man die Binärzahl nun vertikal als eine zusätzliche Spalte hinstellt (0 ganz oben, 1 ganz unten), kann man die Einsen auffassen als die Zeilen, welche nicht gelöscht werden, und die Nullen als die Zeilen, die gelöscht werden. Was rechts passiert, ist eigentlich simpel: Wobei n = [ Anzahl der Stellen in der Binärdarstellung von a - 1 ] ist. Nun müsste man "einfach" die ungewünschten Indizes aus der Summe extrahieren. Laufvariable k...........................Binärstelle von a.......................b im Algorithmus 0 --.........................................0...(0. Stelle)...........................50 1 --.........................................0...(1. Stelle).........................100 2............................................1...(2.Stelle)...........................200 3............................................1...........................................400 4 --.........................................0..(n-1. Stelle).......................800 n= 5........................................1..(n. Stelle).........................1600 In diesem Fall wären es 0, 1 und 4. Im formellen Beweis müsste man es irgendwie einrichten, dass die Laufvariable abhängt von der jeweilgen Binärstelle der Zahl a. Falls die Binärstelle "x" eine 0 enthält so wird die Laufvariable "x" entfernt und falls sie eine 1 enthält, so wird die Laufvariable genützt in der Summenformel. Kann mir nun jemand sagen, ob diese Idee überhaupt etwas taugt, und wie ich den mathematischen Beweis ansetzen soll? Danke schon mal im Voraus! |
||||
| 06.04.2012, 04:54 | SusiQuad | Auf diesen Beitrag antworten » | ||
| RE: Beweis eines Multiplikationsalgorithmus [attach]23850[/attach]
Es gibt SHIFT und ROTATE -Befehle für Prozessoren (siehe 6.4), die das CARRY füttern, sodass eine Steuerung (ohne Laufvariable) mit einer Nullabfrage auskommt. Erster Hit bei Google mit "Shift register i386", wobei ich mich an frühere Zeiten (Z80) erinnert fühlte. - Insofern braucht es noch eine formale math.-(binaer-)Betrachtung. HTH |
||||
| 06.04.2012, 08:40 | Mystic | Auf diesen Beitrag antworten » | ||
| RE: Beweis eines Multiplikationsalgorithmus Das ist ein uralter Hut, und ich meine das jetzt gar nicht böse, aber es ist wirklich so... Hier die ersten Sätze aus der Wikipedia: Die Russische Bauernmultiplikation (auch Ägyptisches Multiplizieren, Abessinische Bauernregel oder Verdopplungs-Halbierungs-Methode genannt) ist ein einfaches Verfahren zur Multiplikation zweier natürlicher Zahlen. Schon im Altertum bekannt, war das Verfahren in Deutschland bis ins Mittelalter und in Russland bis weit in die Neuzeit üblich, woher auch der Name rührt. Es ist gesichert, dass die Ägypter bereits eine analoge Methode zur Multiplikation verwendeten. Der Algorithmus ist auf dem Papyrus Rhind beschrieben. |
||||
| 06.04.2012, 11:46 | Der Mathematik | Auf diesen Beitrag antworten » | ||
RE: Beweis eines Multiplikationsalgorithmus
Danke vielmals für den Namen dieser Methode! Ich will aber dennoch wissen, woher man die Zuversicht nehmen kann, dass man immer genau das Produkt zweier natürlicher Zahlen a & b durch diesen Algorithmus errechnet. Ich meine, es könnte ja sein, dass es für die Zahlen a = 2405957 und b = 9847756 nicht geht.... Gewissheit schafft da wohl nur ein mathematischer Beweis, oder sehe ich das falsch? Und da ich ja nicht wirklich mit mathematischen Beweismethoden vertraut bin, frage ich mich, wie man solche, und insbesondere diesen, Algorithmen beweist? |
||||
| 06.04.2012, 15:48 | Mystic | Auf diesen Beitrag antworten » | ||
| RE: Beweis eines Multiplikationsalgorithmus Naja, schauen wir uns das Beispiel 44*50 einfacher mal genauer dafür an... Wenn man die Binärdarstellung von 44 hier verwendet, also und diese in 44*50 einsetzt so erhält man d.h., man muss von der rechten Spalte mit den "Verdoppelungen" gewisse Werte aufaddieren... Welche genau, darüber geben die Zahlen in der linken Spalte Auskunft... Ich denke das reicht mal für einen ersten Hinweis... |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
Doppelpost!