Ist die Multiplikation und Division mit Schichtoperatoren in C tatsächlich schneller?

288

Multiplikation und Division können beispielsweise mit Bitoperatoren erreicht werden

i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)

und so weiter.

Ist es tatsächlich schneller, say (i<<3)+(i<<1)zu verwenden, um mit 10 zu multiplizieren, als i*10direkt zu verwenden? Gibt es irgendeine Art von Eingabe, die auf diese Weise nicht multipliziert oder geteilt werden kann?

eku
quelle
8
Tatsächlich ist eine billige Division durch eine andere Konstante als eine Zweierpotenz möglich, aber ein kniffliger Teilstrahl, dem Sie in Ihrer Frage mit "/ Division ... / dividiert" nicht gerecht werden. Siehe zum Beispiel hackersdelight.org/divcMore.pdf (oder holen Sie sich das Buch "Hacker's Freude", wenn Sie können).
Pascal Cuoq
46
Es klingt nach etwas, das leicht getestet werden kann.
Juanchopanza
25
Wie immer - es kommt darauf an. Es war einmal ein Assembler auf einem Intel 8088 (IBM PC / XT), bei dem eine Multiplikation eine Unmenge von Uhren erforderte. Verschiebungen und Hinzufügungen wurden viel schneller ausgeführt, daher schien es eine gute Idee zu sein. Während des Multiplizierens war die Buseinheit jedoch frei, die Befehlswarteschlange zu füllen, und der nächste Befehl konnte dann sofort beginnen. Nach einer Reihe von Verschiebungen und Hinzufügungen wäre die Befehlswarteschlange leer und die CPU müsste warten, bis der nächste Befehl aus dem Speicher abgerufen wird (jeweils ein Byte!). Messen, messen, messen!
Bo Persson
19
Beachten Sie außerdem, dass die Rechtsverschiebung nur für vorzeichenlose Ganzzahlen genau definiert ist . Wenn Sie eine vorzeichenbehaftete Ganzzahl haben, ist nicht definiert, ob 0 oder das höchste Bit von links aufgefüllt werden. (Und vergessen Sie nicht die Zeit, die jemand anderes (sogar Sie selbst) benötigt, um den Code ein Jahr später zu lesen!)
Kerrek SB
29
Tatsächlich implementiert ein guter optimierender Compiler Multiplikation und Division mit Verschiebungen, wenn diese schneller sind.
Peter G.

Antworten:

487

Kurze Antwort: Nicht wahrscheinlich.

Lange Antwort: Ihr Compiler verfügt über einen Optimierer, der weiß, wie man so schnell multipliziert, wie es Ihre Zielprozessorarchitektur kann. Am besten teilen Sie dem Compiler Ihre Absicht klar mit (dh i * 2 statt i << 1) und lassen Sie ihn entscheiden, wie die schnellste Assembly- / Maschinencodesequenz lautet. Es ist sogar möglich, dass der Prozessor selbst den Multiplikationsbefehl als eine Folge von Verschiebungen und Additionen im Mikrocode implementiert hat.

Fazit: Verbringen Sie nicht viel Zeit damit, sich darüber Gedanken zu machen. Wenn Sie verschieben möchten, verschieben Sie. Wenn Sie multiplizieren möchten, multiplizieren Sie. Tun Sie, was semantisch am klarsten ist - Ihre Mitarbeiter werden es Ihnen später danken. Oder verfluchen Sie Sie später, wenn Sie etwas anderes tun.

Drew Hall
quelle
31
Ja, wie gesagt, die möglichen Gewinne für fast jede Anwendung werden die eingeführte Dunkelheit völlig überwiegen. Sorgen Sie sich nicht vorzeitig um diese Art der Optimierung. Erstellen Sie, was sematisch klar ist, identifizieren Sie Engpässe und optimieren Sie von dort aus ...
Dave
4
Wenn Sie die Lesbarkeit und Wartbarkeit optimieren, haben Sie wahrscheinlich mehr Zeit, um die Dinge zu optimieren, die laut Profiler Hot-Code-Pfade sind.
Doug65536
5
Diese Kommentare lassen es so klingen, als würden Sie die potenzielle Leistung aufgeben, wenn Sie dem Compiler mitteilen, wie er seine Arbeit erledigen soll. Dies ist nicht der Fall. Mit x86 erhalten Sie tatsächlich besseren Code als mit der Shift-Version . Als jemand, der sich viel mit der Compiler-Ausgabe beschäftigt (siehe viele meiner Antworten zu ASM / Optimierung), bin ich nicht überrascht. Es gibt Zeiten, in denen es hilfreich sein kann, den Compiler auf eine Art und Weise in die Hand zu nehmen , aber dies ist keine davon. gcc ist gut in ganzzahliger Mathematik, weil es wichtig ist. gcc -O3return i*10
Peter Cordes
Habe gerade eine Arduino-Skizze heruntergeladen, die hat millis() >> 2; Wäre es zu viel verlangt worden, nur zu teilen?
Paul Wieland
1
Ich habe i / 32vs i >> 5und i / 4vs i >> 2auf gcc für cortex-a9 (das keine Hardware-Abteilung hat) mit Optimierung -O3 getestet und die resultierende Baugruppe war genau die gleiche. Ich mochte es nicht, zuerst Divisionen zu verwenden, aber es beschreibt meine Absicht und die Ausgabe ist dieselbe.
Robsn
91

Nur ein konkreter Punkt: Vor vielen Jahren habe ich zwei Versionen meines Hashing-Algorithmus verglichen:

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = 127 * h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

und

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = (h << 7) - h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

Auf jeder Maschine, auf der ich das Benchmarking durchgeführt habe, war die erste mindestens so schnell wie die zweite. Etwas überraschend war es manchmal schneller (zB bei einem Sun Sparc). Wenn die Hardware keine schnelle Multiplikation unterstützte (und die meisten damals nicht), konvertierte der Compiler die Multiplikation in die entsprechenden Kombinationen von Shifts und Add / Sub. Und weil es das endgültige Ziel kannte, konnte es dies manchmal in weniger Anweisungen tun, als wenn Sie die Schichten und die Add / Subs explizit geschrieben haben.

Beachten Sie, dass dies vor etwa 15 Jahren war. Hoffentlich sind die Compiler seitdem nur besser geworden, sodass Sie sich darauf verlassen können, dass der Compiler das Richtige tut, wahrscheinlich besser als Sie. (Der Grund, warum der Code so C'ish aussieht, ist, dass er vor über 15 Jahren war. Ich würde ihn heute offensichtlich verwenden std::stringund iterieren.)

James Kanze
quelle
5
Sie könnten an dem folgenden Blog-Beitrag interessiert sein, in dem der Autor feststellt, dass moderne Optimierungs-Compiler gängige Muster rückentwickeln, die Programmierer möglicherweise verwenden, um sie effizienter in ihre mathematischen Formen zu integrieren, um wirklich die effizienteste Anweisungssequenz für sie zu generieren . shape-of-code.coding-guidelines.com/2009/06/30/…
Pascal Cuoq
@PascalCuoq Nichts wirklich Neues. Ich habe vor fast 20 Jahren so ziemlich dasselbe für Sun CC entdeckt.
James Kanze
67

Lassen Sie mich neben all den anderen guten Antworten hier auf einen weiteren Grund hinweisen, warum Sie Shift nicht verwenden sollten, wenn Sie Teilen oder Multiplizieren meinen. Ich habe noch nie jemanden gesehen, der einen Fehler eingeführt hat, indem er die relative Priorität von Multiplikation und Addition vergessen hat. Ich habe Fehler gesehen, die eingeführt wurden, als Wartungsprogrammierer vergaßen, dass das "Multiplizieren" über eine Schicht logischerweise eine Multiplikation ist, aber nicht syntaktisch dieselbe Priorität wie die Multiplikation hat. x * 2 + zund x << 1 + zsind sehr unterschiedlich!

Wenn Sie an Zahlen arbeiten, verwenden Sie arithmetische Operatoren wie + - * / %. Wenn Sie an Bit-Arrays arbeiten, verwenden Sie Bit-Twiddling-Operatoren wie & ^ | >>. Mischen Sie sie nicht; Ein Ausdruck, der sowohl ein bisschen Twiddling als auch Arithmetik hat, ist ein Fehler, der darauf wartet, passiert zu werden.

Eric Lippert
quelle
5
Mit einfachen Klammern vermeidbar?
Joel B
21
@ Joel: Sicher. Wenn Sie sich daran erinnern, dass Sie sie brauchen. Mein Punkt ist, dass es leicht zu vergessen ist, dass Sie es tun. Menschen, die die mentale Angewohnheit haben, "x << 1" zu lesen, als wäre es "x * 2", haben die mentale Angewohnheit zu denken, dass << die gleiche Priorität wie die Multiplikation hat, was es nicht ist.
Eric Lippert
1
Nun, ich finde den Ausdruck "(hi << 8) + lo" aufschlussreicher als "hi * 256 + lo". Wahrscheinlich ist es Geschmackssache, aber manchmal ist es klarer, Bit-Twiddling zu schreiben. In den meisten Fällen stimme ich Ihrem Standpunkt jedoch voll und ganz zu.
Ivan Danilov
32
@Ivan: Und "(hi << 8) | lo" ist noch deutlicher. Das Setzen der niedrigen Bits eines Bit-Arrays ist keine Addition von ganzen Zahlen . Es setzt Bits , also schreiben Sie den Code, der Bits setzt.
Eric Lippert
1
Beeindruckend. Ich habe es vorher nicht so gesehen. Vielen Dank.
Ivan Danilov
50

Dies hängt vom Prozessor und vom Compiler ab. Einige Compiler optimieren den Code bereits auf diese Weise, andere nicht. Sie müssen also jedes Mal überprüfen, wenn Ihr Code auf diese Weise optimiert werden muss.

Wenn Sie nicht dringend optimieren müssen, würde ich meinen Quellcode nicht verschlüsseln, nur um eine Montageanweisung oder einen Prozessorzyklus zu speichern.

Jens
quelle
3
Nur um eine grobe Schätzung hinzuzufügen: Bei einem typischen 16-Bit-Prozessor (80C166) erfolgt das Hinzufügen von zwei Ints zu 1-2 Zyklen, eine Multiplikation zu 10 Zyklen und eine Division zu 20 Zyklen. Plus einige Bewegungsoperationen, wenn Sie i * 10 in mehrere Operationen optimieren (jede Bewegung einen weiteren +1 Zyklus). Die gängigsten Compiler (Keil / Tasking) optimieren nur für Multiplikationen / Divisionen mit einer Potenz von 2.
Jens
55
Im Allgemeinen optimiert der Compiler den Code besser als Sie.
user703016
Ich bin damit einverstanden, dass beim Multiplizieren von "Mengen" der Multiplikationsoperator im Allgemeinen besser ist, aber beim Teilen von vorzeichenbehafteten Werten durch Potenzen von 2 ist der >>Operator schneller als /und wenn die vorzeichenbehafteten Werte negativ sein können, ist er oft auch semantisch überlegen. Wenn man den Wert braucht, der x>>4produzieren würde, ist das viel klarer als x < 0 ? -((-1-x)/16)-1 : x/16;, und ich kann mir nicht vorstellen, wie ein Compiler diesen letzteren Ausdruck zu etwas Schönem optimieren könnte.
Supercat
38

Ist es tatsächlich schneller, say (i << 3) + (i << 1) zu verwenden, um mit 10 zu multiplizieren, als i * 10 direkt zu verwenden?

Möglicherweise befindet es sich auf Ihrem Computer oder nicht. Wenn Sie sich darum kümmern, messen Sie Ihren tatsächlichen Verbrauch.

Eine Fallstudie - von 486 bis Core i7

Benchmarking ist sehr schwierig sinnvoll durchzuführen, aber wir können uns einige Fakten ansehen. Unter http://www.penguin.cz/~literakl/intel/s.html#SAL und http://www.penguin.cz/~literakl/intel/i.html#IMUL erhalten wir eine Vorstellung von x86-Taktzyklen benötigt für arithmetische Verschiebung und Multiplikation. Nehmen wir an, wir halten uns an "486" (das neueste aufgelistete), 32-Bit-Register und sofort, IMUL benötigt 13-42 Zyklen und IDIV 44. Jeder SAL benötigt 2 und addiert 1, so dass selbst wenn einige von ihnen zusammen oberflächlich aussehen, dies aussieht wie ein Gewinner.

In diesen Tagen mit dem Kern i7:

(von http://software.intel.com/en-us/forums/showthread.php?t=61481 )

Die Latenz beträgt 1 Zyklus für eine Ganzzahladdition und 3 Zyklen für eine Ganzzahlmultiplikation . Die Latenzen und den Durchsatz finden Sie in Anhang C des "Referenzhandbuchs zur Optimierung von Intel® 64- und IA-32-Architekturen" unter http://www.intel.com/products/processor/manuals/ .

(von einem Intel Klappentext)

Mit SSE kann der Core i7 simultane Additions- und Multiplikationsbefehle ausgeben, was zu einer Spitzenrate von 8 Gleitkommaoperationen (FLOP) pro Taktzyklus führt

Das gibt Ihnen eine Vorstellung davon, wie weit die Dinge gekommen sind. Die Optimierungs-Trivia - wie Bit Shifting versus *-, die bis in die 90er Jahre ernst genommen wurden, sind jetzt einfach veraltet. Die Bitverschiebung ist immer noch schneller, aber für Nicht-Zweierpotenzen (Mul / Div) ist es wieder langsamer, wenn Sie alle Verschiebungen durchführen und die Ergebnisse hinzufügen. Dann bedeuten mehr Anweisungen mehr Cache-Fehler, mehr potenzielle Probleme beim Pipelining, mehr Verwendung temporärer Register kann mehr Speichern und Wiederherstellen von Registerinhalten aus dem Stapel bedeuten ... es wird schnell zu kompliziert, alle Auswirkungen endgültig zu quantifizieren, aber sie sind überwiegend negativ.

Funktionalität im Quellcode vs. Implementierung

Im Allgemeinen ist Ihre Frage mit C und C ++ gekennzeichnet. Als Sprachen der 3. Generation wurden sie speziell entwickelt, um die Details des zugrunde liegenden CPU-Befehlssatzes auszublenden. Um ihre Sprachstandards zu erfüllen, müssen sie Multiplikations- und Verschiebungsvorgänge (und viele andere) unterstützen, auch wenn die zugrunde liegende Hardware dies nicht tut . In solchen Fällen müssen sie das erforderliche Ergebnis unter Verwendung vieler anderer Anweisungen synthetisieren. Ebenso müssen sie Softwareunterstützung für Gleitkommaoperationen bereitstellen, wenn der CPU diese fehlt und keine FPU vorhanden ist. Moderne CPUs unterstützen *und<<Das mag absurd theoretisch und historisch erscheinen, aber die Bedeutung ist, dass die Freiheit, die Implementierung zu wählen, in beide Richtungen geht: Selbst wenn die CPU über eine Anweisung verfügt, die die im Quellcode im allgemeinen Fall angeforderte Operation implementiert, steht es dem Compiler frei Wählen Sie etwas anderes, das es bevorzugt, da es für den speziellen Fall, mit dem der Compiler konfrontiert ist, besser ist .

Beispiele (mit einer hypothetischen Assemblersprache)

source           literal approach         optimised approach
#define N 0
int x;           .word x                xor registerA, registerA
x *= N;          move x -> registerA
                 move x -> registerB
                 A = B * immediate(0)
                 store registerA -> x
  ...............do something more with x...............

Anweisungen wie exklusiv oder ( xor) haben keine Beziehung zum Quellcode, aber wenn Sie irgendetwas mit sich selbst verknüpfen, werden alle Bits gelöscht, sodass etwas auf 0 gesetzt werden kann. Quellcode, der Speicheradressen impliziert, erfordert möglicherweise keine Verwendung.

Diese Art von Hacks wurde verwendet, solange es Computer gibt. In den frühen Tagen von 3GLs musste die Compiler-Ausgabe den vorhandenen Hardcore-Hand-optimierenden Assembler-Entwickler erfüllen, um die Entwickler-Aufnahme zu sichern. Community, dass der produzierte Code nicht langsamer, ausführlicher oder auf andere Weise schlechter war. Compiler haben schnell viele großartige Optimierungen vorgenommen - sie wurden zu einem besseren zentralen Speicher als jeder einzelne Assembler-Programmierer, obwohl es immer die Möglichkeit gibt, dass sie eine bestimmte Optimierung verpassen, die in einem bestimmten Fall entscheidend ist - Menschen können es manchmal Nut it out und tappen nach etwas Besserem, während Compiler einfach tun, was ihnen gesagt wurde, bis jemand diese Erfahrung in sie zurückspeist.

Selbst wenn das Verschieben und Hinzufügen auf einer bestimmten Hardware noch schneller ist, hat der Compiler-Writer wahrscheinlich genau dann geklappt, wenn es sowohl sicher als auch vorteilhaft ist.

Wartbarkeit

Wenn sich Ihre Hardware ändert, können Sie sie neu kompilieren. Sie wird sich die Ziel-CPU ansehen und eine weitere beste Wahl treffen, während Sie Ihre "Optimierungen" wahrscheinlich nie wieder besuchen oder auflisten möchten, welche Kompilierungsumgebungen Multiplikation verwenden und welche sich verschieben sollten. Denken Sie an all die bitverschobenen "Optimierungen" ohne Potenz von zwei, die vor mehr als 10 Jahren geschrieben wurden und jetzt den Code verlangsamen, in dem sie sich befinden, da er auf modernen Prozessoren ausgeführt wird ...!

Glücklicherweise können gute Compiler wie GCC in der Regel eine Reihe von Bitverschiebungen und Arithmetik durch eine direkte Multiplikation ersetzen, wenn eine Optimierung aktiviert ist (dh ...main(...) { return (argc << 4) + (argc << 2) + argc; }-> imull $21, 8(%ebp), %eax), sodass eine Neukompilierung auch ohne Korrektur des Codes hilfreich sein kann. Dies ist jedoch nicht garantiert.

Seltsamer Bitshifting-Code, der Multiplikation oder Division implementiert, ist weit weniger aussagekräftig für das, was Sie konzeptionell erreichen wollten. Andere Entwickler werden davon verwirrt sein, und ein verwirrter Programmierer führt eher Fehler ein oder entfernt etwas Wesentliches, um die scheinbare Vernunft wiederherzustellen. Wenn Sie nur nicht offensichtliche Dinge tun, wenn sie wirklich greifbar sind, und sie dann gut dokumentieren (aber keine anderen Dinge dokumentieren, die sowieso intuitiv sind), sind alle glücklicher.

Allgemeine Lösungen versus Teillösungen

Wenn Sie etwas mehr Wissen, wie , dass Ihr intWille wirklich nur Werte werden zu speichern x, yund zdann können Sie in der Lage sein , einige Anweisungen zu arbeiten , dass die Arbeit für diese Werte und erhalten Sie Ihr Ergebnis schneller , als wenn der Compiler nicht haben diese Einsicht und braucht eine Implementierung, die für alle intWerte funktioniert . Betrachten Sie zum Beispiel Ihre Frage:

Multiplikation und Division können mit Bitoperatoren erreicht werden ...

Sie veranschaulichen die Multiplikation, aber wie steht es mit der Division?

int x;
x >> 1;   // divide by 2?

Nach dem C ++ Standard 5.8:

-3- Der Wert von E1 >> E2 ist E1 rechtsverschobene E2-Bitpositionen. Wenn E1 einen vorzeichenlosen Typ hat oder wenn E1 einen vorzeichenbehafteten Typ und einen nicht negativen Wert hat, ist der Wert des Ergebnisses der integrale Bestandteil des Quotienten von E1 geteilt durch die auf die Potenz E2 erhobene Größe 2. Wenn E1 einen vorzeichenbehafteten Typ und einen negativen Wert hat, ist der resultierende Wert implementierungsdefiniert.

Ihre Bitverschiebung hat also ein implementierungsdefiniertes Ergebnis, wenn sie xnegativ ist: Auf verschiedenen Computern funktioniert sie möglicherweise nicht auf die gleiche Weise. Funktioniert aber /weitaus vorhersehbarer. (Es ist möglicherweise auch nicht perfekt konsistent, da verschiedene Maschinen unterschiedliche Darstellungen negativer Zahlen und damit unterschiedliche Bereiche haben können, selbst wenn die gleiche Anzahl von Bits die Darstellung ausmacht.)

Sie können sagen "Es ist mir egal ... das intspeichert das Alter des Mitarbeiters, es kann niemals negativ sein". Wenn Sie diese Art von besonderen Einsichten haben, dann ja - Ihre >>sichere Optimierung wird möglicherweise vom Compiler übergeben, es sei denn, Sie tun dies ausdrücklich in Ihrem Code. Aber es ist riskant und selten nützlich, da Sie diese Art von Einsicht oft nicht haben und andere Programmierer, die an demselben Code arbeiten, nicht wissen, dass Sie das Haus auf ungewöhnliche Erwartungen an die Daten gesetzt haben, die Sie haben. Ich kümmere mich um ... was als absolut sichere Änderung an ihnen erscheint, könnte aufgrund Ihrer "Optimierung" nach hinten losgehen.

Gibt es irgendeine Art von Eingabe, die auf diese Weise nicht multipliziert oder geteilt werden kann?

Ja ... wie oben erwähnt, haben negative Zahlen ein implementierungsdefiniertes Verhalten, wenn sie durch Bitverschiebung "geteilt" werden.

Tony Delroy
quelle
2
Sehr schöne Antwort. Der Vergleich von Core i7 und 486 ist aufschlussreich!
Drew Hall
Auf allen gängigen Architekturen intVal>>1wird dieselbe Semantik verwendet, die sich von denen intVal/2auf eine Weise unterscheidet, die manchmal nützlich ist. Wenn man den Wert, den gewöhnliche Architekturen liefern würden intVal >> 1, auf tragbare Weise berechnen muss, müsste der Ausdruck etwas komplizierter und schwerer zu lesen sein und würde wahrscheinlich einen wesentlich schlechteren Code erzeugen als den, für den er erzeugt wurde intVal >> 1.
Supercat
35

Ich habe gerade versucht, auf meinem Computer Folgendes zu kompilieren:

int a = ...;
int b = a * 10;

Beim Zerlegen wird Folgendes ausgegeben:

MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX
LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift !
SHL EAX, 1 ; Multiply by 2 using shift

Diese Version ist schneller als Ihr handoptimierter Code mit reinem Verschieben und Hinzufügen.

Sie wissen wirklich nie, was der Compiler einfallen wird, daher ist es besser, einfach eine normale Multiplikation zu schreiben und ihn so optimieren zu lassen, wie er möchte, außer in sehr präzisen Fällen, in denen Sie wissen, dass der Compiler nicht optimieren kann.

user703016
quelle
1
Sie hätten eine große Gegenstimme dafür bekommen, wenn Sie den Teil über den Vektor übersprungen hätten. Wenn der Compiler die Multiplikation korrigieren kann, kann er auch sehen, dass sich der Vektor nicht ändert.
Bo Persson
Wie kann ein Compiler wissen, dass sich eine Vektorgröße nicht ändert, ohne wirklich gefährliche Annahmen zu treffen? Oder haben Sie noch nie von Parallelität gehört ...
Charles Goodwin
1
Ok, Sie durchlaufen also einen globalen Vektor ohne Sperren? Und ich durchlaufe einen lokalen Vektor, dessen Adresse nicht übernommen wurde, und rufe nur const-Member-Funktionen auf. Zumindest mein Compiler erkennt, dass sich die Vektorgröße nicht ändert. (und bald wird uns wahrscheinlich jemand zum Chatten markieren :-).
Bo Persson
1
@BoPersson Nach all dieser Zeit entfernte ich schließlich meine Aussage, dass der Compiler nicht in der Lage sei, zu optimieren vector<T>::size(). Mein Compiler war ziemlich alt! :)
user703016
21

Das Schalten ist im Allgemeinen viel schneller als das Multiplizieren auf Anweisungsebene, aber Sie verschwenden möglicherweise Ihre Zeit mit vorzeitigen Optimierungen. Der Compiler kann diese Optimierungen durchaus zur Kompilierungszeit durchführen. Wenn Sie dies selbst tun, wird die Lesbarkeit beeinträchtigt und die Leistung wird möglicherweise nicht beeinträchtigt. Es lohnt sich wahrscheinlich nur, solche Dinge zu tun, wenn Sie ein Profil erstellt haben und festgestellt haben, dass dies ein Engpass ist.

Tatsächlich kann der Teilungstrick, der als "magische Teilung" bekannt ist, enorme Gewinne bringen. Wieder sollten Sie zuerst ein Profil erstellen, um zu sehen, ob es benötigt wird. Wenn Sie es jedoch verwenden, gibt es nützliche Programme, mit denen Sie herausfinden können, welche Anweisungen für dieselbe Teilungssemantik erforderlich sind. Hier ist ein Beispiel: http://www.masm32.com/board/index.php?topic=12421.0

Ein Beispiel, das ich aus dem OP-Thread auf MASM32 entfernt habe:

include ConstDiv.inc
...
mov eax,9999999
; divide eax by 100000
cdiv 100000
; edx = quotient

Würde erzeugen:

mov eax,9999999
mov edx,0A7C5AC47h
add eax,1
.if !CARRY?
    mul edx
.endif
shr edx,16
Mike Kwan
quelle
7
@ Aus irgendeinem Grund hat mich dein Kommentar zum Lachen gebracht und meinen Kaffee verschüttet. Vielen Dank.
Asawyer
30
Es gibt keine zufälligen Forenthreads darüber, wie man Mathe mag. Jeder, der Mathe mag, weiß, wie schwierig es ist, einen echten "zufälligen" Forenthread zu generieren.
Joel B
1
Es lohnt sich wahrscheinlich nur, solche Dinge zu tun, wenn Sie ein Profil erstellt und festgestellt haben, dass dies ein Engpass ist, und die Alternativen und das Profil erneut implementiert haben und mindestens den 10-fachen Leistungsvorteil erzielen .
Lie Ryan
12

Shift- und Integer-Multiplikationsbefehle weisen auf den meisten modernen CPUs eine ähnliche Leistung auf - Integer-Multiplikationsbefehle waren in den 1980er Jahren relativ langsam, aber im Allgemeinen trifft dies nicht mehr zu. Ganzzahlige Multiplikationsbefehle können eine höhere Latenz aufweisen , sodass es immer noch Fälle geben kann, in denen eine Verschiebung vorzuziehen ist. Das Gleiche gilt für Fälle, in denen Sie mehr Ausführungseinheiten beschäftigen können (obwohl dies in beide Richtungen möglich ist).

Die Ganzzahldivision ist jedoch immer noch relativ langsam, daher ist die Verwendung einer Verschiebung anstelle der Division durch eine Zweierpotenz immer noch ein Gewinn, und die meisten Compiler werden dies als Optimierung implementieren. Beachten Sie jedoch, dass die Dividende entweder ohne Vorzeichen oder als positiv bekannt sein muss, damit diese Optimierung gültig ist. Bei einer negativen Dividende sind Verschiebung und Division nicht gleichwertig!

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 5; i >= -5; --i)
    {
        printf("%d / 2 = %d, %d >> 1 = %d\n", i, i / 2, i, i >> 1);
    }
    return 0;
}

Ausgabe:

5 / 2 = 2, 5 >> 1 = 2
4 / 2 = 2, 4 >> 1 = 2
3 / 2 = 1, 3 >> 1 = 1
2 / 2 = 1, 2 >> 1 = 1
1 / 2 = 0, 1 >> 1 = 0
0 / 2 = 0, 0 >> 1 = 0
-1 / 2 = 0, -1 >> 1 = -1
-2 / 2 = -1, -2 >> 1 = -1
-3 / 2 = -1, -3 >> 1 = -2
-4 / 2 = -2, -4 >> 1 = -2
-5 / 2 = -2, -5 >> 1 = -3

Wenn Sie dem Compiler helfen möchten, stellen Sie sicher, dass die Variable oder der Ausdruck in der Dividende explizit ohne Vorzeichen ist.

Paul R.
quelle
4
Ganzzahlige Multiplikationen werden beispielsweise auf der PPU von PlayStation 3 mikrocodiert und blockieren die gesamte Pipeline. Es wird empfohlen, auf einigen Plattformen noch ganzzahlige Multiplikationen zu vermeiden :)
Maister
2
Viele vorzeichenlose Divisionen werden - vorausgesetzt der Compiler weiß wie - mit vorzeichenlosen Multiplikationen implementiert. Ein oder zwei Multiplikationen mit jeweils wenigen Taktzyklen können die gleiche Arbeit leisten wie eine Division mit jeweils 40 Zyklen.
Olof Forshell
1
@Olof: wahr, aber natürlich nur für die Division durch eine Kompilierungszeitkonstante gültig
Paul R
4

Dies hängt vollständig vom Zielgerät, der Sprache, dem Zweck usw. ab.

Pixelknirschen in einem Grafikkartentreiber? Sehr wahrscheinlich, ja!

.NET-Geschäftsanwendung für Ihre Abteilung? Absolut kein Grund, sich überhaupt damit zu beschäftigen.

Für ein Hochleistungsspiel für ein mobiles Gerät lohnt es sich möglicherweise, einen Blick darauf zu werfen, jedoch erst, nachdem einfachere Optimierungen durchgeführt wurden.

Brady Moritz
quelle
2

Tun Sie dies nur, wenn Sie dies unbedingt müssen und Ihre Code-Absicht eher eine Verschiebung als eine Multiplikation / Division erfordert.

An einem typischen Tag - Sie könnten möglicherweise einige Maschinenzyklen einsparen (oder verlieren, da der Compiler besser weiß, was zu optimieren ist), aber die Kosten lohnen sich nicht - verbringen Sie Zeit mit kleinen Details und nicht mit tatsächlichen Aufgaben. Die Pflege des Codes wird schwieriger und schwieriger Ihre Mitarbeiter werden Sie verfluchen.

Möglicherweise müssen Sie dies für Berechnungen mit hoher Last tun, bei denen jeder gespeicherte Zyklus Minuten Laufzeit bedeutet. Sie sollten jedoch jeweils einen Ort optimieren und jedes Mal Leistungstests durchführen, um festzustellen, ob Sie es wirklich schneller gemacht oder die Compilerlogik gebrochen haben.

Kromster
quelle
1

Soweit ich weiß, kann die Multiplikation bei einigen Maschinen bis zu 16 bis 32 Maschinenzyklen erfordern. So Ja , je nach Maschinentyp sind bitshift Betreiber schneller als Multiplikation / Division.

Bestimmte Maschinen haben jedoch einen Mathematikprozessor, der spezielle Anweisungen zur Multiplikation / Division enthält.

iammilind
quelle
7
Die Leute, die Compiler für diese Maschinen schreiben, haben wahrscheinlich auch die Hackers Delight gelesen und entsprechend optimiert.
Bo Persson
1

Ich stimme der markierten Antwort von Drew Hall zu. Die Antwort könnte jedoch einige zusätzliche Hinweise enthalten.

Für die überwiegende Mehrheit der Softwareentwickler sind Prozessor und Compiler für die Frage nicht mehr relevant. Die meisten von uns sind weit jenseits von 8088 und MS-DOS. Es ist vielleicht nur für diejenigen relevant, die sich noch für eingebettete Prozessoren entwickeln ...

Bei meiner Softwarefirma sollte Mathematik (add / sub / mul / div) für die gesamte Mathematik verwendet werden. Während der Konvertierung zwischen Datentypen sollte Shift verwendet werden, z. ushort zu Byte als n >> 8 und nicht n / 256.

deegee
quelle
Ich stimme dir auch zu. Ich folge unbewusst der gleichen Richtlinie, obwohl ich noch nie eine formale Anforderung dazu hatte.
Drew Hall
0

Bei vorzeichenbehafteten Ganzzahlen und Rechtsverschiebung gegenüber Division kann dies einen Unterschied machen. Bei negativen Zahlen rundet die Verschiebung in Richtung negativer Unendlichkeit, während die Division in Richtung Null rundet. Natürlich ändert der Compiler die Division in etwas Billigeres, aber normalerweise ändert er sie in etwas, das das gleiche Rundungsverhalten wie die Division aufweist, da er entweder nicht beweisen kann, dass die Variable nicht negativ ist, oder einfach nicht Pflege. Wenn Sie also nachweisen können, dass eine Zahl nicht negativ ist, oder wenn es Ihnen egal ist, in welche Richtung sie gerundet wird, können Sie diese Optimierung auf eine Weise durchführen, die mit größerer Wahrscheinlichkeit einen Unterschied macht.

Harold
quelle
oder wirf die Nummer aufunsigned
Lie Ryan
4
Sind Sie sicher, dass das Schaltverhalten standardisiert ist? Ich hatte den Eindruck, dass die Rechtsverschiebung bei negativen Ints implementierungsdefiniert ist.
Kerrek SB
1
Während Sie vielleicht erwähnen sollten, dass Code, der sich auf ein bestimmtes Verhalten für rechtsverschiebende negative Zahlen stützt, diese Anforderung dokumentieren sollte, ist der Vorteil der Rechtsverschiebung in Fällen enorm, in denen er natürlich den richtigen Wert liefert und der Divisionsoperator Code zum Verschwenden generiert Zeitberechnung eines unerwünschten Werts, dessen Benutzercode dann zusätzliche Zeit für die Anpassung verschwenden müsste, um das zu erhalten, was die Verschiebung überhaupt gegeben hätte. Wenn ich meine Druthers hätte, hätten Compiler die Möglichkeit, bei Versuchen, eine signierte Teilung durchzuführen, zu
kreischen
1
... Code, der weiß, dass die Operanden positiv sind, könnte die Optimierung verbessern, wenn er vor der Division in vorzeichenlose Zeichen umgewandelt wird (möglicherweise später in vorzeichenbehaftete), und Code, der weiß, dass Operanden möglicherweise negativ sind, sollte diesen Fall im Allgemeinen sowieso explizit behandeln (in diesem Fall) man kann genauso gut davon ausgehen, dass sie positiv sind).
Supercat
0

Python-Test, der dieselbe Multiplikation 100 Millionen Mal mit denselben Zufallszahlen durchführt.

>>> from timeit import timeit
>>> setup_str = 'import scipy; from scipy import random; scipy.random.seed(0)'
>>> N = 10*1000*1000
>>> timeit('x=random.randint(65536);', setup=setup_str, number=N)
1.894096851348877 # Time from generating the random #s and no opperati

>>> timeit('x=random.randint(65536); x*2', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); x << 1', setup=setup_str, number=N)
2.2616429328918457

>>> timeit('x=random.randint(65536); x*10', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); (x << 3) + (x<<1)', setup=setup_str, number=N)
2.9485139846801758

>>> timeit('x=random.randint(65536); x // 2', setup=setup_str, number=N)
2.490908145904541
>>> timeit('x=random.randint(65536); x / 2', setup=setup_str, number=N)
2.4757170677185059
>>> timeit('x=random.randint(65536); x >> 1', setup=setup_str, number=N)
2.2316000461578369

Wenn Sie also in Python eine Verschiebung anstelle einer Multiplikation / Division mit einer Zweierpotenz durchführen, ergibt sich eine leichte Verbesserung (~ 10% für die Division; ~ 1% für die Multiplikation). Wenn es sich nicht um eine Zweierpotenz handelt, ist mit einer erheblichen Verlangsamung zu rechnen.

Auch diese #s ändern sich abhängig von Ihrem Prozessor, Ihrem Compiler (oder Interpreter - der Einfachheit halber in Python).

Optimieren Sie nicht wie bei allen anderen vorzeitig. Schreiben Sie gut lesbaren Code, Profil, wenn er nicht schnell genug ist, und versuchen Sie dann, die langsamen Teile zu optimieren. Denken Sie daran, Ihr Compiler kann viel besser optimieren als Sie.

Dr. Jimbob
quelle
0

Es gibt Optimierungen, die der Compiler nicht durchführen kann, da sie nur für einen reduzierten Satz von Eingaben funktionieren.

Unten finden Sie C ++ - Beispielcode, der eine schnellere Division durchführen kann, indem eine 64-Bit-Multiplikation mit dem Kehrwert durchgeführt wird. Sowohl Zähler als auch Nenner müssen unter einem bestimmten Schwellenwert liegen. Beachten Sie, dass es kompiliert werden muss, um 64-Bit-Befehle zu verwenden, um tatsächlich schneller als die normale Division zu sein.

#include <stdio.h>
#include <chrono>

static const unsigned s_bc = 32;
static const unsigned long long s_p = 1ULL << s_bc;
static const unsigned long long s_hp = s_p / 2;

static unsigned long long s_f;
static unsigned long long s_fr;

static void fastDivInitialize(const unsigned d)
{
    s_f = s_p / d;
    s_fr = s_f * (s_p - (s_f * d));
}

static unsigned fastDiv(const unsigned n)
{
    return (s_f * n + ((s_fr * n + s_hp) >> s_bc)) >> s_bc;
}

static bool fastDivCheck(const unsigned n, const unsigned d)
{
    // 32 to 64 cycles latency on modern cpus
    const unsigned expected = n / d;

    // At least 10 cycles latency on modern cpus
    const unsigned result = fastDiv(n);

    if (result != expected)
    {
        printf("Failed for: %u/%u != %u\n", n, d, expected);
        return false;
    }

    return true;
}

int main()
{
    unsigned result = 0;

    // Make sure to verify it works for your expected set of inputs
    const unsigned MAX_N = 65535;
    const unsigned MAX_D = 40000;

    const double ONE_SECOND_COUNT = 1000000000.0;

    auto t0 = std::chrono::steady_clock::now();
    unsigned count = 0;
    printf("Verifying...\n");
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            count += !fastDivCheck(n, d);
        }
    }
    auto t1 = std::chrono::steady_clock::now();
    printf("Errors: %u / %u (%.4fs)\n", count, MAX_D * (MAX_N + 1), (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += fastDiv(n);
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Fast division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    count = 0;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += n / d;
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Normal division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    getchar();
    return result;
}
user2044859
quelle
0

Ich denke, in dem einen Fall, dass Sie mit einer Zweierpotenz multiplizieren oder dividieren möchten, können Sie mit der Verwendung von Bitshift-Operatoren nichts falsch machen, selbst wenn der Compiler sie in einen MUL / DIV konvertiert, da einige Prozessoren Mikrocode (wirklich a Makro) sie sowieso, so dass Sie in diesen Fällen eine Verbesserung erzielen, insbesondere wenn die Verschiebung mehr als 1 beträgt. Oder expliziter, wenn die CPU keine Bitshift-Operatoren hat, wird es sowieso ein MUL / DIV sein, aber wenn die CPU hat Bitshift-Operatoren vermeiden Sie einen Mikrocode-Zweig und dies sind ein paar Anweisungen weniger.

Ich schreibe gerade Code, der viele Verdopplungs- / Halbierungsoperationen erfordert, da er an einem dichten Binärbaum arbeitet, und es gibt eine weitere Operation, von der ich vermute, dass sie optimaler ist als eine Addition - eine Linke (Zweierpotenz multiplizieren) ) mit einem Zusatz verschieben. Dies kann durch eine Linksverschiebung und ein x oder ersetzt werden, wenn die Verschiebung breiter als die Anzahl der Bits ist, die Sie hinzufügen möchten. Ein einfaches Beispiel ist (i << 1) ^ 1, wodurch eins zu einem doppelten Wert hinzugefügt wird. Dies gilt natürlich nicht für eine Rechtsverschiebung (Zweierpotenz), da nur eine Linksverschiebung (Little Endian) die Lücke mit Nullen füllt.

In meinem Code werden diese Multiplikationen / Division durch zwei und Potenzen von zwei Operationen sehr intensiv verwendet, und da die Formeln bereits ziemlich kurz sind, kann jeder Befehl, der eliminiert werden kann, einen erheblichen Gewinn bedeuten. Wenn der Prozessor diese Bitshift-Operatoren nicht unterstützt, wird kein Gewinn erzielt, aber es wird auch kein Verlust auftreten.

Außerdem stellen sie in den Algorithmen, die ich schreibe, die Bewegungen visuell dar, so dass sie in diesem Sinne tatsächlich klarer sind. Die linke Seite eines Binärbaums ist größer und die rechte ist kleiner. Außerdem haben in meinem Code ungerade und gerade Zahlen eine besondere Bedeutung, und alle linken Kinder im Baum sind ungerade und alle rechten Kinder und die Wurzel sind gerade. In einigen Fällen, auf die ich noch nicht gestoßen bin, aber vielleicht habe ich nicht einmal daran gedacht, ist x & 1 möglicherweise eine optimalere Operation als x% 2. x & 1 für eine gerade Zahl ergibt Null, für eine ungerade Zahl jedoch 1.

Wenn ich für x & 3 Null bekomme, weiß ich, dass 4 ein Faktor unserer Zahl ist und dasselbe für x% 7 für 8 und so weiter. Ich weiß, dass diese Fälle wahrscheinlich nur einen begrenzten Nutzen haben, aber es ist schön zu wissen, dass Sie eine Moduloperation vermeiden und stattdessen eine bitweise Logikoperation verwenden können, da bitweise Operationen fast immer die schnellsten sind und für den Compiler am wenigsten wahrscheinlich mehrdeutig sind.

Ich erfinde so ziemlich das Feld der dichten Binärbäume, daher erwarte ich, dass die Leute den Wert dieses Kommentars möglicherweise nicht verstehen, da die Leute sehr selten nur Faktorisierungen nur mit Zweierpotenzen durchführen oder nur Zweierpotenzen multiplizieren / teilen wollen.

Louki Sumirniy
quelle
0

Ob es tatsächlich schneller ist, hängt von der tatsächlich verwendeten Hardware und dem tatsächlich verwendeten Compiler ab .

Albert van der Horst
quelle
0

Wenn Sie die Ausgabe für die Syntax x + x, x * 2 und x << 1 auf einem gcc-Compiler vergleichen, erhalten Sie in der x86-Assembly dasselbe Ergebnis: https://godbolt.org/z/JLpp0j

        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        add     eax, eax
        pop     rbp
        ret

Sie können gcc also als klug genug betrachten, um seine beste Lösung unabhängig von Ihrer Eingabe zu ermitteln.

Buridan
quelle
0

Ich wollte auch sehen, ob ich das Haus schlagen könnte. Dies ist allgemeiner bitweise für eine beliebige Zahl durch eine beliebige Zahlenmultiplikation. Die von mir erstellten Makros sind etwa 25% mehr bis doppelt so langsam wie die normale * Multiplikation. Wie von anderen gesagt, wenn es nahe an einem Vielfachen von 2 liegt oder aus wenigen Vielfachen von 2 besteht, könnten Sie gewinnen. wie X * 23 aus (X << 4) + (X << 2) + (X << 1) + X wird langsamer als X * 65 aus (X << 6) + X.

#include <stdio.h>
#include <time.h>

#define MULTIPLYINTBYMINUS(X,Y) (-((X >> 30) & 1)&(Y<<30))+(-((X >> 29) & 1)&(Y<<29))+(-((X >> 28) & 1)&(Y<<28))+(-((X >> 27) & 1)&(Y<<27))+(-((X >> 26) & 1)&(Y<<26))+(-((X >> 25) & 1)&(Y<<25))+(-((X >> 24) & 1)&(Y<<24))+(-((X >> 23) & 1)&(Y<<23))+(-((X >> 22) & 1)&(Y<<22))+(-((X >> 21) & 1)&(Y<<21))+(-((X >> 20) & 1)&(Y<<20))+(-((X >> 19) & 1)&(Y<<19))+(-((X >> 18) & 1)&(Y<<18))+(-((X >> 17) & 1)&(Y<<17))+(-((X >> 16) & 1)&(Y<<16))+(-((X >> 15) & 1)&(Y<<15))+(-((X >> 14) & 1)&(Y<<14))+(-((X >> 13) & 1)&(Y<<13))+(-((X >> 12) & 1)&(Y<<12))+(-((X >> 11) & 1)&(Y<<11))+(-((X >> 10) & 1)&(Y<<10))+(-((X >> 9) & 1)&(Y<<9))+(-((X >> 8) & 1)&(Y<<8))+(-((X >> 7) & 1)&(Y<<7))+(-((X >> 6) & 1)&(Y<<6))+(-((X >> 5) & 1)&(Y<<5))+(-((X >> 4) & 1)&(Y<<4))+(-((X >> 3) & 1)&(Y<<3))+(-((X >> 2) & 1)&(Y<<2))+(-((X >> 1) & 1)&(Y<<1))+(-((X >> 0) & 1)&(Y<<0))
#define MULTIPLYINTBYSHIFT(X,Y) (((((X >> 30) & 1)<<31)>>31)&(Y<<30))+(((((X >> 29) & 1)<<31)>>31)&(Y<<29))+(((((X >> 28) & 1)<<31)>>31)&(Y<<28))+(((((X >> 27) & 1)<<31)>>31)&(Y<<27))+(((((X >> 26) & 1)<<31)>>31)&(Y<<26))+(((((X >> 25) & 1)<<31)>>31)&(Y<<25))+(((((X >> 24) & 1)<<31)>>31)&(Y<<24))+(((((X >> 23) & 1)<<31)>>31)&(Y<<23))+(((((X >> 22) & 1)<<31)>>31)&(Y<<22))+(((((X >> 21) & 1)<<31)>>31)&(Y<<21))+(((((X >> 20) & 1)<<31)>>31)&(Y<<20))+(((((X >> 19) & 1)<<31)>>31)&(Y<<19))+(((((X >> 18) & 1)<<31)>>31)&(Y<<18))+(((((X >> 17) & 1)<<31)>>31)&(Y<<17))+(((((X >> 16) & 1)<<31)>>31)&(Y<<16))+(((((X >> 15) & 1)<<31)>>31)&(Y<<15))+(((((X >> 14) & 1)<<31)>>31)&(Y<<14))+(((((X >> 13) & 1)<<31)>>31)&(Y<<13))+(((((X >> 12) & 1)<<31)>>31)&(Y<<12))+(((((X >> 11) & 1)<<31)>>31)&(Y<<11))+(((((X >> 10) & 1)<<31)>>31)&(Y<<10))+(((((X >> 9) & 1)<<31)>>31)&(Y<<9))+(((((X >> 8) & 1)<<31)>>31)&(Y<<8))+(((((X >> 7) & 1)<<31)>>31)&(Y<<7))+(((((X >> 6) & 1)<<31)>>31)&(Y<<6))+(((((X >> 5) & 1)<<31)>>31)&(Y<<5))+(((((X >> 4) & 1)<<31)>>31)&(Y<<4))+(((((X >> 3) & 1)<<31)>>31)&(Y<<3))+(((((X >> 2) & 1)<<31)>>31)&(Y<<2))+(((((X >> 1) & 1)<<31)>>31)&(Y<<1))+(((((X >> 0) & 1)<<31)>>31)&(Y<<0))
int main()
{
    int randomnumber=23;
    int randomnumber2=23;
    int checknum=23;
    clock_t start, diff;
    srand(time(0));
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYMINUS(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    int msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYMINUS Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYSHIFT(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYSHIFT Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum= randomnumber*randomnumber2;
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("normal * Time %d milliseconds", msec);
    return 0;
}
AlexanderLife
quelle