Schnelle Modulo-Operation mit variablen Parametern

Wie groß kann denn x und n maximal werden (x%n)?

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?

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.

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.

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.

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."