mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP Schnelle Modulo-Operation mit variablen Parametern


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Rechenfreak (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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?

von Joe F. (easylife)


Bewertung
0 lesenswert
nicht lesenswert
Wie groß kann denn x und n maximal werden (x%n)?

von Theor (Gast)


Bewertung
0 lesenswert
nicht lesenswert

von A. S. (achs)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Rechenfreak (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Theor schrieb:
> könnte Dir evtl. weiterhelfen.
Ja Danke, ist halt auch wieder eine Schleife.

von sid (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von A. S. (achs)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Nick M. (muellernick)


Bewertung
0 lesenswert
nicht lesenswert
Rechenfreak schrieb:
> Geht es
> auch anders?

Klar, ein paar Tabellen und genügend RAM ...

von Yalu X. (yalu) (Moderator)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Christoph db1uq K. (christoph_kessler)


Bewertung
0 lesenswert
nicht lesenswert
Wenn der Prozessor multiplizieren kann, ist vielleicht eine 
Multiplikation mit dem Kehrwert möglich?

von Egon D. (egon_d)


Bewertung
0 lesenswert
nicht lesenswert
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.

: Bearbeitet durch User
von Yalu X. (yalu) (Moderator)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Egon D. (egon_d)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Yalu X. (yalu) (Moderator)


Bewertung
0 lesenswert
nicht lesenswert
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.

von A. S. (achs)


Bewertung
0 lesenswert
nicht lesenswert
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

von Jürgen S. (engineer) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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
von A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.