Haftungsausschluss: Hausaufgabenfrage. Ich suche nach einem Hinweis ...
Professor F. Lake sagt seiner Klasse, dass es asymptotisch schneller ist, eine n-Bit-Ganzzahl zu quadrieren als zwei n-Bit-Ganzzahlen zu multiplizieren. Sollten sie ihm glauben?
Ich glaube, dass die Multiplikation von zwei n-Bit-Ints über shift / add eine O (n) -Operation ist, aber ich kann nicht sehen, warum das Quadrieren eines n-Bit-int anders wäre. Fehle ich etwas?
Da Sie nur einen Hinweis wollten, kommt die Antwort aus dieser Gleichung: (a + b)^2 = a^2 + b^2 + 2*a*b
Um das Puzzle nicht zu verderben, habe ich die komplette Lösung separat gepostet:)
Stellen Sie sich vor, dass Quadrieren tatsächlich asymptotisch schneller ist. Dann, wenn Sie ein * b haben, könnten Sie berechnen:
%Vor%Die Lösung dieses Gleichungssystems ergibt dann:
%Vor%Aber dann haben wir
%Vor%oder ohne Zwischenvariablen:
%Vor%Sie können also jede Multiplikation durch zwei Quadrierungsoperationen ersetzen (und einige Additionen und Division durch 4, was nur eine Bitverschiebung ist, und diese können alle für asymptotische Komplexität ignoriert werden). Die Komplexität der Multiplikation ist also höchstens doppelt so komplex wie die Quadrierung. Natürlich ist "zweimal" ein konstanter Faktor, was bedeutet, dass beide die gleiche asymptotische Komplexität haben.
Hier ist ein Hinweis .
Und hier ist meine Lösung in GEHEIMCODE: Fdhnevat zrnaf lbh bayl unir gb qb bar vavgvny SG, abg gjb, fb vg'f snfgre.
Mein Gedanke ist, dass zur Multiplikation zweier n-Bit-Ganzzahlen Ihr Algorithmus zwei beliebige n-Bit-Ganzzahlen berücksichtigen muss. Das ist (2^n)^2 mögliche Eingaben.
Ein Quadrierungsalgorithmus muss nur 2^n mögliche Eingaben verarbeiten, obwohl er als ein Multiplikationsalgorithmus mit zwei gleichwertigen Eingaben modelliert werden kann.
Ich schätze, es gäbe eine Möglichkeit, den generischen Multiplikationsalgorithmus zu optimieren, wenn Sie wissen, dass beide Eingaben gleich sind, aber ich müsste darüber nachdenken. Das ist die Linie, die ich untersuchen würde, jedenfalls ...
Umgeschrieben: Dies ist die einzige Verbesserung, die ich beim Quadrieren einer n-Bit-Zahl über die Multiplikation von zwei n-Bit-Zahlen sehen kann. Es ist möglicherweise nicht asymptotisch besser in der O (n ^ 2) vs. O (n) Art von Art und Weise, die häufig in der Informatik verwendet wird. Wenn wir es jedoch asymptotisch wörtlich nehmen, was die Komplexität bedeutet, die angegangen wird (einschließlich der multiplikativen Konstanten), dann wird dies zu dieser Definition passen. Wie auch immer, es ist alles, was ich sehen kann, also nimm es oder lass es.
Nehmen wir an, wir haben zwei N-Bit-Zahlen, x und y . Wir können sie zusammen multiplizieren ( x*y ) mit der Shift-and-Add-Methode mit A * N ^ 2 + O (N) -Operationen, wobei A eine Konstante ist. Der zweite Term, der O (N) -Begriff, kann für genügend N vernachlässigt werden, so dass die Anzahl der Operationen im Wesentlichen A * N ^ 2 ist.
Jetzt berechnen wir x^2 . Wenn wir a so definieren, dass nur die oberen N / 2 Bits von x und b nur die unteren N / 2 Bits von x enthalten, dann
Beachten Sie jedoch, dass wir eine N-Bit-Zahl mit A * N ^ 2-Operationen multiplizieren können. Um a * a zu multiplizieren, müssen wir nur A * (N / 2) ^ 2 = A * N / 4 Operationen ausführen. Das gleiche gilt für b * b und a * b. Wenn wir die O (N) -Operationen ignorieren, wird x^2 = (a + b)^2 in
Operationen, die natürlich besser sind als der Standard A * N ^ 2, um zwei beliebige N-Bit-Zahlen mit A * N ^ 2/4 zu multiplizieren. Wir können dies weiter verbessern, indem wir die gleiche Operation mit a^2 und b^2 wiederholen. Irgendwann wird es nicht vorteilhaft sein, dies weiter zu machen. Das ist keine enorme Verbesserung, aber es ist alles, was ich finden kann. Sie können selbst entscheiden, ob das zählt oder nicht.
Tags und Links algorithm