nicht angemeldet
effektiver künstlicher Zahlenüberlauf oder Modulo selber gemacht
Gunnar BittersmannHallo,
da ich hier schon in einigen Antworten ein tiefgreifendes Verständnis für Zahlen und Gesetzmäßigkeiten beobachten konnte, setlle ich mal ein Problem zur Lösung.
Ich brauche eine Funktion, die mir einen Zahlenüberlauf realisiert bzw. aus einer Zahl die Zahl macht die entstanden wäre, wenn es einen Überlauf gegeben hätte. Der Wertebereich sollte z.B. von 0 bis 359 gehen (ganze Zahlen), obwohl es ein vorzeichenbehafteter 32bit-integer ist (ein 32bit-Überlauf muß nicht berücksichtigt sein, so groß werden die "Eingangszahlen" nicht).
Das ganze würde natürlich mit Modulo gehen aber der steht nicht zur Verfügung. Ich habe zwar schon mal einen Modulo selber programmiert aber der war relativ ineffizient (ich muß um jeden Prozessortakt ringen). Ich hoffe nun, es gibt eine effizientere Lösung, vielleicht eine auf Bit-Ebene, die ich nicht sehe.
An schnellen Befehlen, die in Frage kommen, stehen zur Verfügung:
- die vier Grundrechenarten
- bitweise and or xor not
- shift links und rechts
- Inkrementieren und Dekrementieren (hat aber keinen Rückgabewert, sondert ändert die Variable am Speicherort)
- Betragsbildung
- if ... else ... endif
Der Syntax, den ich verwende, soll weitestgehend BASIC entsprechen (was ich kaum kenne), ist aber was Spezielles mit vielen hardwarespezifischen Befehlen.
Die Suchmaschinen haben mir nicht viel geholfen, da "Modulo" häufig erwähnt wird, wenn es verwendet wird und google das gar mit dem Wort Mod assoziiert, was Unmengen Suchergebnisse zu Modifikationen liefert.
-
Hello out there!
Schleifen hast du auch zur Verfügung?
WHILE x >= m DO x = x - m
kommt ohne Division aus. (x ist deine Eingabe; m dein Modul, in deinem Bsp. 360)
Der Syntax,
_die_ Syntax [Wikipedia, Wiktionary]
See ya up the road,
Gunnar--
„Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ (Kirsten Evers)-
Schleifen hast du auch zur Verfügung?
WHILE x >= m DO x = x - m
Ja, do while und for. Deren Zeitverhalten habe ich aber noch nie untersucht und die Hardware ist gerade in Gebrauch so das ich das jetzt nicht testen kann.
Deine Lösung funktioniert aber nicht für negative x. Mit einer Fallunterscheidung dürfte es schon zu langsam sein, muß ich aber testen.
PS: x ist vermutlich immer kleiner als das Vierfache von m aber eine Lösung die davon unabhängig ist, wäre natürlich besser.
-
Hello out there!
WHILE x >= m DO x = x - m
Deine Lösung funktioniert aber nicht für negative x.Dann musst du natürlich addieren:
WHILE x < 0 DO x = x + m
PS: x ist vermutlich immer kleiner als das Vierfache von m
Dann soll das schnell genug sein.
aber eine Lösung die davon unabhängig ist, wäre natürlich besser.
Dann kommst du wohl nicht um eine Division herum. Ob diese samt Auswertung des Ergebnisses schneller ist als ein paar wenige Additionen/Subtraktionen, hängt wohl von der Hardware ab.
See ya up the road,
Gunnar--
„Und [dieses Forum] soll […] auch ein Fachforum bleiben und kein Psychologieforum werden.“ (Kirsten Evers)
-
-
-
Yerf!
Das ganze würde natürlich mit Modulo gehen aber der steht nicht zur Verfügung.
Wir suchen also ein z = x mod y
An schnellen Befehlen, die in Frage kommen, stehen zur Verfügung:
- die vier Grundrechenarten
Integer?
z = x - ((x / y) * y)
bei Float wirds komplizierter...
- Betragsbildung
Damit könnte man evtl. Probleme mit negativem x umgehen.
x mod y = abs(x) mod y // oder lieg ich da grad falsch?
Gruß,
Harlequin
-
Hello,
Das ganze würde natürlich mit Modulo gehen aber der steht nicht zur Verfügung.
Wir suchen also ein z = x mod y
An schnellen Befehlen, die in Frage kommen, stehen zur Verfügung:
- die vier Grundrechenarten
Integer?
z = x - ((x / y) * y)
Man weiß ja nicht, wei es umgesetzt wir und auf welchem Prozessor.
Aber ich gehe mal davon aus, dass es kein Mathematischer Coprozessor ist, sondern irgendeine eine Single-Chip-Gurke.Da wären DIV und MUL auf jeden Fall sehr teure Statements.
Als Beispiel beim Beim 8086
DIV 3+9+16+4+4+4+17 = 57 (zuzügl. 2*EA) genau nachvollziehbar
MUL 77+133+83+139 = 432 (zuzügl. 2*EA) Maximalwert
SUB 90+162+168 = 420 (zuzügl. 2*EA)Das muss man sich also sehr genau überlegen, ob man nicht lieber eine Abbildung von "repnz" oder so ähnlich benutzt. Das ist bei den hardwarenahen Hochsprachen i.d.R. in For-Schleifen umgesetzt.
Wenn es sich um sogenannte "dedizierte For-Schleifen" handelt, in denen man den Schleifenzähler wärend der Abarbeitung nicht mehr verändrn darf, sind die extrem schnell.Das kann man aber eben nicht beantworten, ohne den Assempler-Code Deiner Hochsprache zu haben und ohne den Prozessortyp genauer zu kennen.
Wenn es um das Ausknautschen von Taktzyklen geht, wird ja wohl Portierbarkeit eher keine Rolle spielen
Harzliche Grüße vom Berg
http://bergpost.annerschbarrich.deTom
--
Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
Nur selber lernen macht schlau
Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)
-
Hello,
*ups*, wie konnte denn das passieren?
SUB 3+9+16+4+4+4+17 = 57 (zuzügl. 2*EA) genau nachvollziehbar
MUL 77+133+83+139 = 432 (zuzügl. 2*EA) Maximalwert
DIV 90+162+168 = 420 (zuzügl. 2*EA)
so herum latürnich (sic!)
Harzliche Grüße vom Berg
http://bergpost.annerschbarrich.deTom
--
Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
Nur selber lernen macht schlau
Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)
-
Yerf!
Man weiß ja nicht, wei es umgesetzt wir und auf welchem Prozessor.
Deshalb wollte ich eine weitere Lösung zud er von Gunnar posten. Vergleichen, was nun schneller ist, kann nur der OP.
Gruß,
Harlequin
-
Sorry, das wollte ich eigentlich gleich dazuschreiben.
= (Zuweisung) 2 Takte
+, -, * je 2 Takte
/ 5 Takte
inc, dec je 3 Takte (inklusive Zuweisung)
absi (Betragsbildung) 3 Takte
and, or, xor je 2 Zakte
not 1 Takt
shift weiß ich gerade nicht
if ... else ... endif mit einer Bedingung 6+3 Takte wenn wahr, 4 Takte wenn falschDer Prozessor ist ein DPS mit 40 Mhz.
-
Yerf!
= (Zuweisung) 2 Takte
+, -, * je 2 Takte
/ 5 TakteWobei es schon komisch ist, dass der Prozessor * und / so gut kann aber dann kein Modulo...
Gruß,
Harlequin
-
Hello,
= (Zuweisung) 2 Takte
+, -, * je 2 Takte
/ 5 TakteWobei es schon komisch ist, dass der Prozessor * und / so gut kann aber dann kein Modulo...
only RISC brings fun
oder wie hieß der Spruch mit dem Germanismus drin?
Harzliche Grüße vom Berg
http://bergpost.annerschbarrich.deTom
--
Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
Nur selber lernen macht schlau
Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)
-
Yerf!
only RISC brings fun
oder wie hieß der Spruch mit dem Germanismus drin?
No RISC no fun
Aber Modulo gehört bei Integer doch eigentlich zu den Grundrechenarten (gerade auch weil das Nachbilden über die anderen Operationen so aufwendig ist).
Gruß,
Harlequin
-
Aber Modulo gehört bei Integer doch eigentlich zu den Grundrechenarten (gerade auch weil das Nachbilden über die anderen Operationen so aufwendig ist).
Ich werde mal bei den Entwicklern anfragen. Bei einer anderen Gelegenheit haben die mir auch eine undokumentierte Funktion verraten, die unsagbar nützlich war für meine Zwecke.
-
-
-
-
-
Integer?
z = x - ((x / y) * y)
Ja, ganze Zahlen.
Beispiel:
-10, -370, -730 ist gleichbedeutend und soll 350 ergeben
370, 730, 1090 ist gleichbedeutend und soll 10 ergebenz = x - ((x / y) * y) ergibt
-10 (mit absi ist da nichts zu machen)
10Ich komme jetzt auf folgendes, ich glaube meine alte Lösung war noch etwas schlechter:
z = (x + 1440) - (((x + 1440) / y) * y) ergibt
350
10
Das sind 15 Takte ohne Klammern. Bei Klammern verhält sich der Compiler relativ undurchschaubar, das muß ich testen. Vermutlich sind es in Summe 18 Takte.Da ich die Funktion je Prozeßaufruf relativ häufig ausführen muß, sind 18 Takte für einen Überlauf der sonst nebenbei Auftritt recht viel. Leider funktioniert das nur bei 2^x.
Daher hatte ich auf eine schnelle Lösung auf Bit-Ebene gehofft.
-
Yerf!
Beispiel:
-10, -370, -730 ist gleichbedeutend und soll 350 ergeben
370, 730, 1090 ist gleichbedeutend und soll 10 ergebenDas ist aber kein normales Modulo...
Ich komme jetzt auf folgendes, ich glaube meine alte Lösung war noch etwas schlechter:
z = (x + 1440) - (((x + 1440) / y) * y) ergibt...etwas anderes
Das sind 15 Takte ohne Klammern. Bei Klammern verhält sich der Compiler relativ undurchschaubar, das muß ich testen. Vermutlich sind es in Summe 18 Takte.
Bei der Geschwindigkeit für Multiplikation/Division dürfte das aber der schneller Weg sein, eine Schleife ist da sicherlich langsamer.
Daher hatte ich auf eine schnelle Lösung auf Bit-Ebene gehofft.
Auf Bit-Ebene kann man leider nur mit 2er-Potenzen hantieren...
Gruß,
Harlequin
-
Hello,
Auf Bit-Ebene kann man leider nur mit 2er-Potenzen hantieren...
Da gibt's auch Tricks für MUL 3 oder DIV 3 usw. Für 5 gab es auch was...
Aber das ist lange her. Da müsste ich jetzt selber in die alten Bücher schauen. Aus dem Kopf weiß ich das nicht mehr.
Harzliche Grüße vom Berg
http://bergpost.annerschbarrich.deTom
--
Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
Nur selber lernen macht schlau
Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)
-
Das ist aber kein normales Modulo...
Das ist ein Überlauf, das Modulo habe ich doch nur gesucht, um einen Überlauf zu machen.
Also ich habe getestet:
die do ... until Schleife wird mind. einmal durchlaufen, was bei Werten im Wertebereich "ungünstig" ist. Im worst-case Fall ist sie zu langsam (8 bis 28 Takte im Beispiel) und würde mit einer Fallunterscheidung noch um bis 9 Takte langsamer werden.Meine neue Lösung braucht nur 15 Takte. Der Compiler scheint verbessert worden zu sein, seit ich mich beschwert habe, daß selbst doppelte Klammern um einen Ausdruck nicht optimiert werden. Auf Assembler-Niveau könnte man noch 2 Takte rausholen, weil eine Subtraktion doppelt ist. Das zu erkennen ist aber vom Compiler zu viel erwartet.
15 Takte gilt es zu schlagen. Ich danke aber schon mal, daß ich aufgrund der Vorschläge erneut nachdenken mußte und dabei auf eine bessere Lösung gekommen bin. Im Moment bekomme ich die x mal 15 Takte auch noch unter aber Alles ist noch nicht umgesetzt.
-
Hallo,
Ist das noch aktuell?
15 Takte gilt es zu schlagen.
Nur 15 Takte für dein Modulo? Das ist schwer zu toppen, wenn man nicht hardwarenah programmieren kann, wie z.B. so:
MOV AX, Wert
XOR DX, DX
MOV BX, Modul
DIV BXDas Ergebnis der Divison befindet sich jetzt in AX, wobei der gesuchte Rest der Division in DX steht.
Im Moment bekomme ich die x mal 15 Takte auch noch unter
Wieso x mal 15 Takte? Verstehe nicht ganz, aber egal...
Eine Lösung auf Bit-Ebene ist auch möglich, aber halt kaum unter 15 Takten. Man müsste zuerst wissen, wieviel Takte ein SHR 8 braucht.
Also ist es noch aktuell? Dann würde ich noch ein bischen drüber meditieren, solche Kopfnüsse interessieren mich :-)
Gruß, Don P
-
Hello,
15 Takte gilt es zu schlagen.
Nur 15 Takte für dein Modulo? Das ist schwer zu toppen, wenn man nicht hardwarenah programmieren kann, wie z.B. so:
MOV AX, Wert
XOR DX, DX
MOV BX, Modul
DIV BXDas Ergebnis der Divison befindet sich jetzt in AX, wobei der gesuchte Rest der Division in DX steht.
Und wieviele Takte benötigt welche Operation?
Insbesondre DIV dürfte doch auch heute noch mehr als 150 Takte benötigen?Harzliche Grüße vom Berg
http://bergpost.annerschbarrich.deTom
--
Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
Nur selber lernen macht schlau
Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)
-
Und wieviele Takte benötigt welche Operation?
Insbesondre DIV dürfte doch auch heute noch mehr als 150 Takte benötigen?Die Division benötig auf diesem Prozessor, so wie sie vom Compiler umgesetzt wird, 5 Takte.
-
Hello,
Und wieviele Takte benötigt welche Operation?
Insbesondre DIV dürfte doch auch heute noch mehr als 150 Takte benötigen?Die Division benötig auf diesem Prozessor, so wie sie vom Compiler umgesetzt wird, 5 Takte.
Wie geht das?
Wie zählt das?Man muss doch mindestens zwei Register mit Werten laden und dann den Befehl auch noch übermitteln, das Ergebnis abholen usw...
Harzliche Grüße vom Berg
http://bergpost.annerschbarrich.deTom
--
Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
Nur selber lernen macht schlau
Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)
-
Die Division benötig auf diesem Prozessor, so wie sie vom Compiler umgesetzt wird, 5 Takte.
Wie geht das?
Öhm, vielleicht findest Du die Antwort hier:
http://www.analog.com/UploadedFiles/Data_Sheets/ADSP-21060_21060L.pdf
So einer ist es, komisch nur, daß dort von 6 Takten die Rede ist.Wie zählt das?
Man muss doch mindestens zwei Register mit Werten laden und dann den Befehl auch noch übermitteln, das Ergebnis abholen usw...
Wie das zählt? Nur die Division kostet 5 Takte, egal ob mit Konstanten oder Variablen (allerdings nur mit Variablen aus dem internen RAM), Für die Zuweisung des Ergebnisses auf eine Variable werden noch mal zwei Takte fällig.
-
Hello,
http://www.analog.com/UploadedFiles/Data_Sheets/ADSP-21060_21060L.pdf
So einer ist es, komisch nur, daß dort von 6 Takten die Rede ist.Geniales Teil.
Harzliche Grüße vom Berg
http://bergpost.annerschbarrich.deTom
--
Fortschritt entsteht nur durch die Auseinandersetzung der Kreativen
Nur selber lernen macht schlau
Ein Jammer ist auch, dass die Dummen so selbstsicher und die Klugen voller Zweifel sind. Das sollte uns häufiger zweifeln lassen :-)
-
-
-
-
-
Hallo,
Ist das noch aktuell?
Ja. Der Support hat zwar schon versprochen, nach eine Lösung zu suchen, hat aber noch nicht wieder geantwortet.
Wieso x mal 15 Takte?
Weil ich die Funktion mehrfach in einem Prozeßaufruf verwenden muß.
Eine Lösung auf Bit-Ebene ist auch möglich, aber halt kaum unter 15 Takten. Man müsste zuerst wissen, wieviel Takte ein SHR 8 braucht.
Jedes shift egal um wieviel Stellen braucht zwei Takte. Damit habe ich auch schon versucht was hinzubekommen, bin aber mit dem Wertebereich zu keinem Ergebnis gekommen.
Dann würde ich noch ein bischen drüber meditieren, solche Kopfnüsse interessieren mich :-)
Gruß, Don P
Auf solche Leute hatte ich gehofft. :-)
-
Hallo,
Dann würde ich noch ein bischen drüber meditieren, solche Kopfnüsse interessieren mich :-)
Auf solche Leute hatte ich gehofft. :-)
Muss leider passen. Es geht zwar auf Bit-Ebene, ist aber sehr umständlich und dauert viel zu lange mit den vielen and, xor, shift usw., die dazu nötig sind.
Aber: Dein DSP kann doch Modulo, anscheinend gibt es eine C-Funktion namens fmod, die das erledigt. Vielleicht benutzt du einfach die falsche Programmiersprache?
Gruß, Don P
-
Muss leider passen. Es geht zwar auf Bit-Ebene, ist aber sehr umständlich und dauert viel zu lange mit den vielen and, xor, shift usw., die dazu nötig sind.
Schade, bei einem Wertebereich von 2^n wäre es natürlich einfach gewesen. Danke für deine Mühe.
Aber: Dein DSP kann doch Modulo, anscheinend gibt es eine C-Funktion namens fmod, die das erledigt. Vielleicht benutzt du einfach die falsche Programmiersprache?
Ich bin leider an die eine Programmiersprache gebunden. Ich wüßte nicht, wie ich sonst die ganze IO-Hardware ansprechen soll, die mit dem DSP verbaut ist.
Es sei denn, man kann das dekompilieren, die entsprechenden Teile ersetzen und wieder kompilieren. Es gibt ein Modul um binär-files direkt zu laden, nicht nur den kompilierten Code aus dem Editor.
Wenn noch was rauskommt, werde ich berichten.
-
-
-
-
-
-