Ich suche nach einer einfachen und schnellen Schnelle Modulo-Operation mit einem jeweils variablen Parameter, den ich vorgebe. Modulo8 und 16 sind bei Integer trivial, aber ich brauche auch die (n-1) , also 7,15,23,47,63. Integerdivision soll vermieden werden. Momentan wird gezählt. Geht es auch anders?
Wie groß kann denn x und n maximal werden (x%n)?
Das hier: https://graphics.stanford.edu/~seander/bithacks.html#ModulusDivisionEasy könnte Dir evtl. weiterhelfen.
Lass es doch per switch Mal den Compiler machen. Den größten Gewinn erzielst Du vermutlich, wenn Du es auf unsigned beschränken oder umbauen kannst.
Hä? ohne grundrechenarten (keine Addition/Substraktion in schleife) keine multiplikation oder division.. wie wollste dann? und komm mir nicht mit shifts (division /multiplikation mit 2) das hat Du damit ja auch ausgeschlossen Glaskugel ist schlecht in Code zu realisieren, da fehlt das pseudowissenschaftliche Element.
Rechenfreak schrieb: > Theor schrieb: >> könnte Dir evtl. weiterhelfen. > Ja Danke, ist halt auch wieder eine Schleife. na, dann musst Du die Frage beantworten Joe F. schrieb: > Wie groß kann denn x und n maximal werden (x%n)? Die innere Schleife oben läuft bei 7000%7 keine 10 Mal durch. Das ist 100 Mal schneller als ein "normaler" Schleifenansatz.
Welche Implementationen von n % k überhaupt einen Vorteil gegenüber der Division bringen, hängt von mehreren Faktoren ab: - Welcher Bereich von n soll abgedeckt werden? - Wie lange dauert eine Division? - Wie lange dauert eine Multiplikation? - Wie lange dauert ein Left-/Right-Shift um b Bits? - Wie lange dauern Sprünge? Die letzten vier Fragen können zusammengefasst werden zu: - Auf welchem Prozessor soll das Ganze laufen? Gerade für k=23 und k=47 wird es nicht ganz leicht sein, schneller als die Division zu werden.
Wenn der Prozessor multiplizieren kann, ist vielleicht eine Multiplikation mit dem Kehrwert möglich?
Yalu X. schrieb: > Gerade für k=23 und k=47 wird es nicht ganz leicht > sein, schneller als die Division zu werden. Wieso eigentlich? Korrigiere mich, wenn ich falsch liege, aber das Bestimmen der Restklasse ist doch distributiv, d.h. es gilt: (a+b) mod x = (a mod x) + (b mod x) (Gegebenenfalls kann rechts ein Repräsentant herauskommen, der größer als x ist, aber das ist durch erneute Berechnung des Restes leicht zu beheben.) Da die Argumente ja in einem binären Stellenwert- system vorliege, in dem beim Vorliegen einer Eins die entsprechenden Zweierpotenzen addiert werden, müsste es genügen, zur Berechnung der Restklasse die RESTE der Zweierpotenzen zu addieren, die eine Eins im Argument haben. Für frei wählbare, aber zur Laufzeit feste Werte von x lassen sich die den einzelnen Bitstellen entsprechenden Reste vorausberechnen.
Egon D. schrieb: > Da die Argumente ja in einem binären Stellenwert- > system vorliege, in dem beim Vorliegen einer Eins > die entsprechenden Zweierpotenzen addiert werden, > müsste es genügen, zur Berechnung der Restklasse > die RESTE der Zweierpotenzen zu addieren, die eine > Eins im Argument haben. So ähnlich funktioniert ja auch die Division im Dualsystem. Wird nur der Rest und nicht der Quotient benötigt, kann der Divisionsalgorithmus noch etwas vereinfacht werden. Dennoch wird es schwer sein, mit einer mikroprogrammierten Division, wie sie bspw. die x86-Prozessoren haben, zu konkurrieren. Deswegen habe ich oben auch nach dem verwendeten Prozessor gefragt.
Yalu X. schrieb: > Dennoch wird es schwer sein, mit einer > mikroprogrammierten Division, wie sie bspw. die > x86-Prozessoren haben, zu konkurrieren. Wir gehen von verschiedenen Voraussetzungen aus. Ich hatte unter "die Division" natürlich eine schriftliche Division per Software verstanden -- wenn der Prozessor einen Divisionsbefehl hat, dann wird der ausdrückliche Wunsch des TO, OHNE Integer-Divisionen auszukommen, nämlich witzlos.
Egon D. schrieb: > wenn der Prozessor einen Divisionsbefehl hat, dann wird der > ausdrückliche Wunsch des TO, OHNE Integer-Divisionen auszukommen, > nämlich witzlos. Nicht unbedingt, denn auch der Divisionsbefehl der x86-Prozessoren ist im Vergleich zur Multiplikation immer noch extrem langsam, weswegen man ihn gerne vermeidet. Aber auch gegenüber einer Softwaredivision wird es dein Verfahren nicht generell schneller sein. In den folgenden Fällen wirst du vermutlich gewinnen: - Auf einem 8-Bit-Prozessor in einer Hochsprache, wenn der Dividend länger als 8 Bit ist und die Laufzeitbibliothek keine passenden Divisionsroutinen mit ungleicher Operandenlänge (also bspw. 16/8 oder 32/8) verfügt und stattdessen auf eine 16/16- bzw. 32/32-Division zurückgegriffen werden muss. - Wenn der Dividend nur einen Teil des möglichen Wertebereichs nutzt (bspw. nur 9 von 16 Bit), so dass bei deinem Verfahren einige Schleifdurchläufe eingespart werden können. In allen anderen Fällen wird dein Verfahren wohl gleich schlecht oder schlechter als die klassische Divisionsroutine abschneiden. Du kannst es ja mal testweise ausprobieren, am besten auf einem einfachen Prozessor wie dem AVR, wo man noch leicht die Taktzyklen zählen kann.
Yalu X. schrieb: > Gerade für k=23 und k=47 wird es nicht ganz leicht sein, schneller als > die Division zu werden. wobei ich mich auch frage, was gemeint war, da Rechenfreak schrieb: > Modulo8 und 16 > sind bei Integer trivial, aber ich brauche auch die (n-1) , also > 7,15,23,47,63. irgendwie überhaupt nicht in einen sinnvollen Zusammenhang gebracht werden kann. Die Schleife in Theors Ling geht so nur bei 2^n-1
Bei der Resourcenverteilung heutiger Microcontroller ist es in der Regel am Besten, eine inverse Division per Multiplikation durchzuführen und binär zu arbeiten. Also entweder händisch durch Abzug des ganzzahligen Teilers M = Y - INT (Y/N) mit 1/N als lookup mit geeigneter Skalierung oder man skaliert erst und macht das Modulo binär durch Weglassen der hohen Bits und anschließender Rückskalierung. So mache ich das auch im FPGA. Das letztere funktioniert besonders effektiv, wenn die Anzahl der möglichen M-Operatoren limitiert ist.
Rechenfreak schrieb: > [Modulo-Operation] 7,15,23,47,63. > > Integerdivision soll vermieden werden. Momentan wird gezählt. Geht es > auch anders? n Modulo N wenn n >= 0 zur Basis B = N+1 dargestellt ist: n = (sum a_k · B^k) mod N n = sum ((a_k mod N)·(N+1 mod N)^k) = sum (a_k mod N) d.h. n = Quersumme (n) mod N Beispiel: 111 mod 7 = (1 + 5 + 7) mod 7 = 6 mod 7 denn 111 = Binär 1101111 = Oktal 157. 111 mod 63 = (1 + 47) mod 63 = 48 mod 63 denn 111 = [1][47] zur Basis 64. 111 mod 3 = (1 + 2 + 3 + 3) mod 3 = 0 denn 111 = 1233 zur Basis 4. 123456 mod 99 = (12 + 34 + 56) mod 99 = 102 mod 99 = 3 mod 99. Das funktioniert natärlich auch mod 23 und mod 47, allerdings ist es eher unüblich, dass Zahlen zur Bases 24 oder 48 (oder einem Vielfachen davon) dargestellt sind.
:
Bearbeitet durch User
Yalu X. schrieb: > So ähnlich funktioniert ja auch die Division im Dualsystem. > mikroprogrammierten Division, wie sie bspw. die x86-Prozessoren haben, > zu konkurrieren. Nur begann man bei besseren Prozessoren schon vor Äonen damit, auf etwas andere Art in Radix 4 zu dividieren (=> Pentium Divisionsfehler). https://de.wikipedia.org/wiki/SRT-Division Oder auch gänzlich anders: https://de.wikipedia.org/wiki/Goldschmidt-Division "Dabei wird die Division auf eine Multiplikation zurückgeführt, womit bereits evtl. vorhandene Multiplizierer mitverwendet werden können."
:
Bearbeitet durch User
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.