Ergebnissgrößer Binärmultiplikation

17.06.2007, 20:19

OttO84

Ergebnissgrößer Binärmultiplikation

Hallo, das Ergebniss der Multiplikation von Binärzahlen ist ja

m*n = z

die Größe von Z ist

mindestens m+n-1 bis m+n Bit groß.

Wie kann man dies Sinnvoll zeigen? Ich schreibe derzeit nämlich an einem Beleg wo ich nebenbei das kurz Zeigen wollte. Bis jetzt beschränkte sich das nur an einer Beispielrechnung mit 2 Zahlen.

Aber ich finde das nicht so anspruchsvoll Big Laugh

So das ich doch gerne diese Behauptung irgendwie aufzeigen wollte das ein gewisser anspruch wieder gespiegelt wird.

Vielen Dank für die Tips schonmal im Vorraus

17.06.2007, 21:17

Auf diesen Beitrag antworten »

Zitat:

Original von OttO84
das Ergebniss der Multiplikation von Binärzahlen ist ja

m*n = z

die Größe von Z ist

mindestens m+n-1 bis m+n Bit groß.

Vor allem solltest du es erstmal richtig aufschreiben - so wie hier formuliert ist es nämlich falsch. Was du meinst, ist vermutlich

Zitat:

Wir betrachten positive Binärzahlen $\begin{eqnarray*} x,y \end{eqnarray*}$ ohne führende Nullen. Hat $\begin{eqnarray*} x \end{eqnarray*}$ genau $\begin{eqnarray*} m \end{eqnarray*}$ Binärstellen, und $\begin{eqnarray*} y \end{eqnarray*}$ entsprechend genau $\begin{eqnarray*} n \end{eqnarray*}$ Binärstellen, dann hat ihr Produkt $\begin{eqnarray*} z=x\cdot y \end{eqnarray*}$ entweder $\begin{eqnarray*} m+n-1 \end{eqnarray*}$ oder $\begin{eqnarray*} m+n \end{eqnarray*}$ Binärstellen.

Also nicht die Zahl $\begin{eqnarray*} x \end{eqnarray*}$ mit ihrer Binärstellenzahl $\begin{eqnarray*} m \end{eqnarray*}$ einfach so durcheinanderwursteln, wie du es oben getan hast.

Zum Nachweis: Genaugenommen musst du dir nur klar werden, dass $\begin{eqnarray*} m \end{eqnarray*}$ Binärstellen für $\begin{eqnarray*} x \end{eqnarray*}$ genau dann auftreten, wenn $\begin{eqnarray*} 2^{m-1}\leq x < 2^m \end{eqnarray*}$ gilt.

18.06.2007, 11:31

OttO84

Auf diesen Beitrag antworten »

Zitat:

Zum Nachweis: Genaugenommen musst du dir nur klar werden, dass $\begin{eqnarray*} m \end{eqnarray*}$ Binärstellen für $\begin{eqnarray*} x \end{eqnarray*}$ genau dann auftreten, wenn $\begin{eqnarray*} 2^{m-1}\leq x < 2^m \end{eqnarray*}$ gilt.

Danke erstmal für die Tips, habe sehr geholfen smile

Aber sollte es nicht heißen

$\begin{eqnarray*} 2^{m-1}<x \le 2^{m} \end{eqnarray*}$

denn wenn ich

$\begin{eqnarray*} 2^{m-1}*2^{n-1} = 2^{m+n-2} \end{eqnarray*}$

Daraus ergeben sich ja die Schranken, so das es heißen würde

$\begin{eqnarray*} 2^{m+n-2}<x*y\le 2^{m+n} \end{eqnarray*}$

Oder habe ich einen Denkfehler?

18.06.2007, 11:58

Auf diesen Beitrag antworten »

Zitat:

Original von OttO84
Aber sollte es nicht heißen

$\begin{eqnarray*} 2^{m-1}<x \le 2^{m} \end{eqnarray*}$

Nein - ich meine es genauso, wie ich es gesagt habe. Zähl mal richtig durch: $\begin{eqnarray*} 2^m \end{eqnarray*}$ in Binärdarstellung umfasst eine führende Eins und dann genau $\begin{eqnarray*} m \end{eqnarray*}$ Nullen, also insgesamt bereits $\begin{eqnarray*} (m+1) \end{eqnarray*}$ Binärstellen.

18.06.2007, 12:51

OttO84

Auf diesen Beitrag antworten »

Ahja

gut da wäre das auch geklärt. Besten Dank Freude

19.06.2007, 09:50

Otto84

Auf diesen Beitrag antworten »

Ich nochmal verwirrt

Wie verhält sich das, bei Fixpunktzahlen? Da sagt man ja das bei dem Produkt die Anzahl der Stellen nach Komma gleich der Summe der Nachkommastellen der Faktoren sind. Das kann ja dann so nich gezeigt werden.

19.06.2007, 12:12

Auf diesen Beitrag antworten »

Das ist ja doch auch ein anderes Problem! Zwar verwandt, aber eben doch anders.

Da musst du klar sagen: Was bedeutet bei dir genau $\begin{eqnarray*} n \end{eqnarray*}$ Nachkommastellen für eine Binärzahl $\begin{eqnarray*} x \end{eqnarray*}$ ? Vermutlich, dass an Position $\begin{eqnarray*} n \end{eqnarray*}$ der Nachkommastellen eine Eins, und danach nur noch Nullen kommen... In dem Sinne ist dann $\begin{eqnarray*} 2^n\cdot x \end{eqnarray*}$ eine ganze, ungerade Zahl...

20.06.2007, 10:50

Ott084

Auf diesen Beitrag antworten »

Also mit n Nachkommastellen meine ich beispielsweise

$\begin{eqnarray*} xx.xx \end{eqnarray*}$

zwei Nachkommastellen.

wenn ich zum Beispiel
4545 mit 5454 multipliziere dann erhalte ich

24788430
2478,8430 die Anzahl der Stellen hat sich für den Nachkommabereich verdoppelt. Ich bin mir nicht sicher wie man hier zeigen kann für dualzahlen das die Stellen sich verdoppeln. Weil letztendlich existiert ja das Komma so nur rein hypothetisch.

20.06.2007, 16:38

Auf diesen Beitrag antworten »

Zitat:

Original von Ott084
zwei Nachkommastellen.

wenn ich zum Beispiel
4545 mit 5454 multipliziere dann erhalte ich

24788430
2478,8430 die Anzahl der Stellen hat sich für den Nachkommabereich verdoppelt.

Du meinst also eigentlich

$\begin{eqnarray*} 45.45 \cdot 54.54 = 2478.8430 \end{eqnarray*}$

und folgerst: Die Anzahl der Nachkommastellen hat sich verdoppelt, von 2 auf 4 ?

Sehe ich anders: Nullen am Ende kann man ja auch weglassen, und das Ergebnis $\begin{eqnarray*} 2478.843 \end{eqnarray*}$ hat nur drei statt vier Nachkommastellen - was nun? Augenzwinkern

Das meine ich mit Definition der Anzahl Nachkommastellen! Allerdings kann das, was du mit deinem "Gegenbeispiel" (zu deiner eigenen Regel) im Dezimalsystem so eindrucksvoll gezeigt hast, im Binärsystem nicht passieren...

21.06.2007, 08:28

OttO84

Auf diesen Beitrag antworten »

Ja die Null kann man weg lassen wenn es sich wirklich um Kommazahlen handelt.

Festkommazahlen bassieren aber auf reiner Integerberechnung und somit wäre die Null ja wieder gerechtfertigt im Ergebniss.

Vorallem weil bei der Festlegung der Darstellung wieiviele Nachkommastellen eigentlich benötigt werden normalerweise genau gesagt wird wo Dezimalpunkt sein soll, aber der Exisitiert nur rein Hypothetisch.

21.06.2007, 15:08

Auf diesen Beitrag antworten »

Danke für die Erklärung, aber ich weiß durchaus, was Festkommazahlen sind. Augenzwinkern

Was ich allerdings nicht weiß ist, was du für Festkommazahlen hier

Zitat:

Original von Otto84
Da sagt man ja das bei dem Produkt die Anzahl der Stellen nach Komma gleich der Summe der Nachkommastellen der Faktoren sind.

noch beweisen willst - allenfalls, dass die Summenanzahl an Nachkommastellen ausreichend ist zur Erfassung des Multiplikationsergebnisses. Das ist was anderes als zu sagen, dass Produkt genau so viele Nachkommastellen wie die Summe der Nachkommastellen der Faktoren (siehe meinen letzten Beitrag)!

26.06.2007, 10:22

Otto84

Auf diesen Beitrag antworten »

Also hier ist nochmal ein Zitat aus meinem Buch was ich vor mir liegen habe,

Zitat:

Die Multiplikation zweier Zahlen mit n und k Stellen nach dem Komma ergiebt ein Produkt mit n+k Stellen

Und genau das möchte ich ja Zeigen, das Beispiel von oben kann ja so nicht verwendet werden, da ja ein Unterschied in den Stellen entstehen kann. Mein Ziel ist praktisch das ich als Ergebnis.

$\begin{eqnarray*} 2^{n+k-1}\le Stellen<2^{n+k} \end{eqnarray*}$

erhalte.

Nur habe ich keinen richtigen Ansatz ich hatte es erst so gedacht.

$\begin{eqnarray*} a2^{n}*b2^{k} = ab2^{n+k} \end{eqnarray*}$

aber so richtig glücklich bin ich damit nicht unglücklich

Neue Frage »

Antworten »

Ergebnissgrößer Binärmultiplikation

Verwandte Themen