Formel für allgemeine Anzahl der Multiplikations-Operationen,

Question 1

Aufgabe:

Formel für allgemeine Anzahl der Multiplikations-Operationen in Abhängikeit von n, um Koeffizienten der Summenformel eines Polynoms, das in Produktform gegeben ist, zu erhalten.

Problem/Ansatz:

geg: f(x) = $ \prod_{i=1}^{n}{(a_i + x)} $

ges: Formel für allgemeine Anzahl der Multiplikations-Operationen in Abhängikeit von n, um Koeffizienten $b_i$ zu erhalten, sodass f(x) = $ \sum\limits_{n=0}^{n}{b_i*x^i} $ .

Beispiel:

geg: f(x) = (a+x)(b+x)

Lösung: Anzahl: 1, da Koeffizienten $b_1= a+b, b_2=a*b, b_3 = 1$ und nur für $b_1$ eine Multiplikation benötigt wird.

Question 2

Auch ohne die Frage zu verstehen, erkennt man, dass f(x) = $ \sum\limits_{n=0}^{n}{b_i*x^i} $ nicht simmen kann. Wahrscheinlich sollte es f(x) = $ \sum\limits_{i=0}^{n}{b_i*x^i} $ heißen.

Question 3

@Roland Es geht um die Komplexitätsanalyse. Darum möchte ich die Anzahl der relevanten Operationen (Multiplikationen) bestimmen.

Question 4

Hallo,

Willkommen in der Mathelounge!

geg: f(x) = $ \prod_{i=1}^{n}{(a_i + x)} $
ges: Formel für allgemeine Anzahl der Multiplikations-Operationen in Abhängikeit von n, um Koeffizienten $b_i$ zu erhalten, sodass f(x) = $ \sum\limits_{n=0}^{n}{b_i*x^i} $ .

Das sind die Dreieckszahlen.

Ist $M(n)$ die Anzahl der notwendige Multiplikationen um von $ \prod_{i=1}^{n}{(a_i + x)} $ nach $ \sum\limits_{n=0}^{n}{b_i\cdot x^i}$ zu kommen, so ist$$M(n) = \frac{n}{2}(n-1)$$Zeigen lässt sich das über Induktion.

Offensichtlich ist $$M(1)=0, \quad M(2)= 1$$und mit jedem weiteren $n$ kommen $n-1$ Multiplikationen dazu.

Gruß Werner

Question 5

Vielen Dank für deine Antwort.

Ich frage mich, ob das wirklich so stimmt.

Für $ M(3) $ mit $ f(x) = (a+x)(b+x)(c+x)$ ergeben sich doch für die Summenform folgende Koeffizienten:

$b_0 = a+b+c$ -> $0$ Multikplikationen

$b_1 = ab+ac+bc$ -> $3$ Multikplikationen

$b_2 = abc$ -> $2$ Multikplikationen

$b_3 = 1$ -> $0$ Multikplikationen

Insgesamt also $5$ Multiplikationen, wobei man insgesamt $4$ verschiedene hat, weil an $ab $ das $c$ direkt dran multpliziert werden kann.

Aber laut deiner Formel müssten es ja

$M(3) = \frac{3}{2}(3-1)=3$ Multiplikationen sein..

Question 6

Du sparst eine Multiplikation, wenn du nicht a*b +a*c, sondern a*(b+c) rechnest.

Question 7

Du sparst eine Multiplikation, wenn du nicht a*b +a*c, sondern a*(b+c) rechnest.

Oder auch $ac+bc=c(a+b)$. Und wenn Du jetzt noch die weglässt, die Du doppelt gezählt hast (die $ab$), bleiben nur noch 3 übrig:$$\begin{aligned} f(x) &= (a+x)(b+x)(c+x)\\ &= ({\color{red}ab} + (a+b)x + x^2)(c+x) &&|\, 1\,\text{Multipl.} \\ &= ({\color{red}abc}+ ({\color{red}(a+b)c} + ab)x + (a+b+c)x^2 + x^3 &&|\, 2\,\text{Multipl.} \end{aligned}$$

Werner-Salomon · Answer 1 · 2023-04-17T19:34:15+0000

Hallo,

Willkommen in der Mathelounge!

geg: f(x) = $ \prod_{i=1}^{n}{(a_i + x)} $
ges: Formel für allgemeine Anzahl der Multiplikations-Operationen in Abhängikeit von n, um Koeffizienten $b_i$ zu erhalten, sodass f(x) = $ \sum\limits_{n=0}^{n}{b_i*x^i} $ .

Das sind die Dreieckszahlen.

Ist $M(n)$ die Anzahl der notwendige Multiplikationen um von $ \prod_{i=1}^{n}{(a_i + x)} $ nach $ \sum\limits_{n=0}^{n}{b_i\cdot x^i}$ zu kommen, so ist$$M(n) = \frac{n}{2}(n-1)$$Zeigen lässt sich das über Induktion.

Offensichtlich ist $$M(1)=0, \quad M(2)= 1$$und mit jedem weiteren $n$ kommen $n-1$ Multiplikationen dazu.

Gruß Werner

Vielen Dank für deine Antwort.

Ich frage mich, ob das wirklich so stimmt.
Für $ M(3) $ mit $ f(x) = (a+x)(b+x)(c+x)$ ergeben sich doch für die Summenform folgende Koeffizienten:
$b_0 = a+b+c$ -> $0$ Multikplikationen
$b_1 = ab+ac+bc$ -> $3$ Multikplikationen
$b_2 = abc$ -> $2$ Multikplikationen
$b_3 = 1$ -> $0$ Multikplikationen
Insgesamt also $5$ Multiplikationen, wobei man insgesamt $4$ verschiedene hat, weil an $ab $ das $c$ direkt dran multpliziert werden kann.
Aber laut deiner Formel müssten es ja
$M(3) = \frac{3}{2}(3-1)=3$ Multiplikationen sein.. — nobaski, 19 Apr 2023
Du sparst eine Multiplikation, wenn du nicht a*b +a*c, sondern a*(b+c) rechnest. — Gast hj2166, 19 Apr 2023
Du sparst eine Multiplikation, wenn du nicht a*b +a*c, sondern a*(b+c) rechnest.
Oder auch $ac+bc=c(a+b)$. Und wenn Du jetzt noch die weglässt, die Du doppelt gezählt hast (die $ab$), bleiben nur noch 3 übrig:$$\begin{aligned} f(x) &= (a+x)(b+x)(c+x)\\ &= ({\color{red}ab} + (a+b)x + x^2)(c+x) &&|\, 1\,\text{Multipl.} \\ &= ({\color{red}abc}+ ({\color{red}(a+b)c} + ab)x + (a+b+c)x^2 + x^3 &&|\, 2\,\text{Multipl.} \end{aligned}$$ — Werner-Salomon, 19 Apr 2023

Formel für allgemeine Anzahl der Multiplikations-Operationen,

1 Antwort

Ähnliche Fragen

Eingabetools:

Beliebte Fragen:

Heiße Lounge-Fragen: