|
|
Forum: Mikrocontroller und Digitale Elektronik AVR/ Teilbarkeit durch 100 und 400Ahoi, kurze Frage: Wie stelle ich möglichst effizient fest, ob eine Zahl durch 100 bzw. durch 400 restlos teilbar ist? Zielplattform: AVR, Assembler Effizient heißt, dass ich keinen Algo suche, wie sowas hier:
So Algos benutze ich nämlich zur Zeit, und die sind irgendwie zu Lahm geworden. Vielen Dank für Antworten und viele Grüße, Haku hüstel... also eine Zahl ist dann durch 100 Teilbar ganzzahlig wenn ihre lezten beiden Ziffern eine 0 sind :P Bei 400 findet man sicher auch irgensowas. Warum ist dein obiger Algorithmus zu langsam? Wie risig ist den die Zahl´und wie oft musst du das machen das das zu langsam wird o.O Und die zu vergleichende Zahl ist ein Word ? Da es hoechstens 655 Zahlen gibt, die durch hundert teilbar sind waere allenfalls ein Binaerer Vergleich mit einer Tabelle moeglich, das waeren dann 10 Vergleiche. Ja. die Tabelle ist etwas gross. >hüstel... also eine Zahl ist dann durch 100 Teilbar ganzzahlig wenn ihre
lezten beiden Ziffern eine 0 sind :P
hüstel... wer rechnet denn schon mit BCD ?
Zerleg deine Divisoren in ihre Primfaktoren: 400 = 2*2*2*2*5*5 Die prüfst du jetzt der reihe nach, die zweier natürlich zuerst, die gehen am schnellsten (teste bit0 == 0, shift) (zusammengefasst:
) den Rest wie gehabt in der schleife, nur halt check auf "teilbar durch 25". Na. wenn man durch 5, oder 25 teilt, kann man gleich durch hundert teilen... Sicher, aber wenn seine Eingagnswerte halbwegs gleichverteilt sind, kann er mit dem ersten Check auf "Teilbar durch 16" schon eine Menge ausschliessen, und spart sich die Schleife danach komplett. Ja WENN er mal sagt wie groß z.B. sein Zahlenbereich ist ;) Aber... er schweigt ja :) Dreckig, sollte aber seinen Zweck erfüllen:
Bin jetzt von 16-Bits unsigned ausgegangen. Man kann das natürlich auch in einer Schleife lösen, aber wenn's um Performance geht... In Assembler lässt sich das sogar relativ elegant coden. Hoffe, das bringt dir was. >Sicher, aber wenn seine Eingagnswerte halbwegs gleichverteilt sind, kann >er mit dem ersten Check auf "Teilbar durch 16" schon eine Menge >ausschliessen, und spart sich die Schleife danach komplett. Würde ich auch auch jeden Fall davorsetzen. Je nach Wertebereich kann er danach sogar mit 8-Bits weiterrechnen. HannsW wrote: > Wie wärs denn mit Modulo 100 resp. modulo 100? > > Hanns Witzbold... was meinste, was ich grad versuche? Ne, ernsthaft. Die Idee von Kai Giebeler sieht verlockend aus, werd ich denn mal fix ausprobieren. Läubi Mail@laeubi.de: Groß heißt, ein Wort, die Annahme war schon richtig (tschuldigung, und ich hab schon gehofft, mal nix vergessen zu haben). Wie viele Takte ich dafür nun zur Verfügung hab, kann ich nicht direkt sagen, weil der Rest des Programms noch nicht existiert...muss denn so gestrickt werden, dass es nachher schnell genug ist. Deshalb kann ich (bis jetzt) nur sagen, "so schnell wie möglich", sorry. Aber schon vielen Dank für die Ideen! Willst Du ausrechnen, ob ein Datum ein Schaltjahr ist? Wenn es sich um ein aktuelles Datum handelt, dann würde auch der Test auf durch 4 reichen, Es sei denn, Du schätzt die Haltbarkeit Deines Programms auf > 2100 ein. Sven Pauli wrote: > kurze Frage: Wie stelle ich möglichst effizient fest, ob eine Zahl durch > 100 bzw. durch 400 restlos teilbar ist? ... > So Algos benutze ich nämlich zur Zeit, und die sind irgendwie zu Lahm > geworden. Klingt nach Schaltjahrberechnung. Das ist natürlich absolut zeitkritisch, man hat ja nur 100 Jahre Zeit dafür :-) Sowas würde ich nicht mehr in Assembler machen, allein schon wegen der Übersichtlichkeit und Portierbarkeit. Ich habs in C gemacht: Beitrag "Berechnung Datum + Uhrzeit + Sommerzeit" Die Routine wird jede Sekunde aufgerufen, ist also in keinster Weise zeitkritisch. Die CPU-Last dürfte schätzungsweise <0,01% sein. Man sollte immer erstmal abschätzen, wie oft etwas ausgeführt werden muß, ehe man anfängt zu optimieren. Sonst ist die viele Arbeit umsonst und hat keinen Effekt. Peter Wolfgang Mües wrote: > Willst Du ausrechnen, ob ein Datum ein Schaltjahr ist? Ja. > Wenn es sich um ein aktuelles Datum handelt, dann würde auch der Test > auf durch 4 reichen, Es sei denn, Du schätzt die Haltbarkeit Deines > Programms auf > 2100 ein. Nö. Deine Annahme is richtig bis 2100, logisch. Aber es kommen auch Jahreszahlen (Datummere...) aus der Vergangenheit vor.. Peter Dannegger wrote: > Klingt nach Schaltjahrberechnung. Jop. > Das ist natürlich absolut zeitkritisch, man hat ja nur 100 Jahre Zeit > dafür :-) Jo, vorallendingen wenn man ein paar Zehntausend Datensätze nacheinander durchackern will. > Sowas würde ich nicht mehr in Assembler machen, allein schon wegen der > Übersichtlichkeit und Portierbarkeit. Aber C aufm AVR ist meiner Ansicht nach Murks... ich hab kein Problem mit 2000 Zeilen Assembler^^ Hab ich auch schon unter Beweis gestellt (Anhang). > Ich habs in C gemacht: Hihi, genau... ((a % 100) == 0). Hab ich sogar auch schon gemacht, um dann im Assembler-Listing festzustellen, dass es nen Sprung in eine div-Unterroutine gibt... leider. > Man sollte immer erstmal abschätzen, wie oft etwas ausgeführt werden > muß, ehe man anfängt zu optimieren. Sonst ist die viele Arbeit umsonst > und hat keinen Effekt. S.o. Danke euch allen! >Jo, vorallendingen wenn man ein paar Zehntausend Datensätze nacheinander >durchackern will. Ich glaube, dass keiner hier bei einem AVR von solchen Zahlen ausgegangen ist. Den AVR dieser Datenmenge zu füttern dauert wahrscheinlich immer noch deutlich länger als die Berechnung. >dann im Assembler-Listing festzustellen, dass es nen Sprung in eine >div-Unterroutine gibt... leider. na ja... was hast du erwartet :) Der Algorithmus, den ich da geschrieben habe ist auch nichts anderes als eine normale binäre Division mit festem Divisor. Naja das Stimmt so nicht. die Daten eines 32kSRAm bei 115kbaud hat man in < 5 Sek auf dem AVR/PC das wäre 16k Worte :) 115 kBaud? Bei 16 MHz führt der den Algorithmus locker einmal pro empfangenem Bit aus. In 5 s könnte der 800.000 mal ausgeführt werden... Ja, du hast recht ich hab mal wieder die Brille schief aufgehabt und mich verlesen und dachte du meinst das das ewig dauert bis die daten aufm AVR sind ;) Sven Pauli wrote: > Jo, vorallendingen wenn man ein paar Zehntausend Datensätze nacheinander > durchackern will. Dann muß man ja erstmal entsprechend große Speichermedien an den AVR anbinden. Und was soll dann eigentlich wie oft ausgegeben werden? Beschreib dochmal, wozu das gut sein soll? > Aber C aufm AVR ist meiner Ansicht nach Murks... Ja, dieser irrigen Ansicht war ich früher auch mal, allerdings für den 8051. War aber noch vor AVR-Zeiten, daher konnte ich beim AVR schnell in C einsteigen und viel 8051 Code weiternutzen. > ich hab kein Problem > mit 2000 Zeilen Assembler^^ Doch hast Du, Du weißt es nur noch nicht. Du brauchst einfach viel länger für die gleiche Sache, als ein anderer in C. Du weißt es also erst, nachdem Du C gelernt hast. >> Ich habs in C gemacht: > Hihi, genau... ((a % 100) == 0). Hab ich sogar auch schon gemacht, um > dann im Assembler-Listing festzustellen, dass es nen Sprung in eine > div-Unterroutine gibt... leider. Aber nicht bei meinem Code. Mein Code bezieht sich auf eine Startzeit von der aus die Sekunden als 32Bit Wert gezählt werden (DS1994 RTC). Damit sind 136 Jahre zählbar. Die Schaltjahrerkennung benutzt keine Division, sondern nur einige Vergleiche:
Peter Sven Pauli wrote: > mit 2000 Zeilen Assembler^^ Hab ich auch schon unter Beweis gestellt > (Anhang). Welcher Anhang? Peter dezimal binär 100 1100100 200 11001000 300 100101100 400 110010000 500 111110100 600 1001011000 700 1010111100 800 1100100000 ... 1200 10010110000 1600 11001000000 2000 11111010000 2400 100101100000 Wie man leicht sieht, gibt es gewisse Muster in den Binärdarstellungen: - Eine Zahl, deren letzte beide Bits != 0 sind, ist sicher nicht durch 100 teilbar - Eine Zahl, deren vier letzte Bits != 0 sind, ist sicher nicht durch 400 teilbar Damit kann man den Prüfungsaufwand schon auf 1/4 bzw. 1/16 reduzieren Das ist zum einen weiter oben schon festgestellt worden und das eigentliche Problem (Division durch 25) muss immer noch gelöst werden. Dafür waren die anschließend vorgeschlagenen Varianten gedacht. >Damit kann man den Prüfungsaufwand schon auf 1/4 bzw. 1/16 reduzieren
Der Prüfaufwand reduziert sich nicht, es ändert sich nur der Intervall
in der die zu testende Zahl liegt.
Kai Giebeler wrote: >>Damit kann man den Prüfungsaufwand schon auf 1/4 bzw. 1/16 reduzieren > Der Prüfaufwand reduziert sich nicht, es ändert sich nur der Intervall > in der die zu testende Zahl liegt. Der Test, daß eine Zahl nicht durch 100 teilbar ist lautet: if (zahl & 3) <zahl ist nicht durch 100 teilbar> daran scheitern 3 von 4 Zahlen, also ist der Gesamtaufwand auf 1/4 gefallen - egal, wie man dieses Viertel weiter untersuchen muß. Die Teilbarkeit durch 5 könnte man mit einer Tabelle prüfen - wenn es sich um Jahreszahlen handelt, mit sagen wir +/- 100 Jahren von Heute, sollte das kein Problem sein. Peter Dannegger: Dieser Anhang.... au Mann, is schon so später Abend... Der Sprache C bin ich mächtig, und avr-gcc hab ich auch schon für einige Projekte eingesetzt, aber so richtig wohl fühl ich mich aufm AVR immer noch nur mit Assembler. Ich hab eben Spaß an nacktem Code^^ Na...mal ernsthaft, was ich aufm AVR hinleg, sind entweder so Popelprogrämmchen, die ich irgendwo schneller von Hand (=ASM) hingepfuscht hab, als bis ich mir mal erst ein sauberes (!) C-Projektchen zusammenschuster. Oder sie sind großteils Zeitkritisch, dass C einfach zu kompliziert wäre, oder ich dann doch wieder mit inline-ASM schaffen müsste (und den begreif ich zugegebenermaßen kein bisschen). >daran scheitern 3 von 4 Zahlen, also ist der Gesamtaufwand auf 1/4 >gefallen - egal, wie man dieses Viertel weiter untersuchen muß. Hast natürlich recht - war blöd ausgedrückt. Die Division wird nicht beschleuningt, aber es fallen natürlich weniger davon an. Uhu Uhuhu wrote: > Die Teilbarkeit durch 5 könnte man mit einer Tabelle prüfen - wenn es > sich um Jahreszahlen handelt, mit sagen wir +/- 100 Jahren von Heute, > sollte das kein Problem sein. Das bringts natürlich nicht... Man könnte aber z.B. für die Zahlen, die den & 3 - Test bestehen, einen Bitvektor ablegen, in dem steht, ob die betreffende Zahl durch 100 teilbar ist - dann braucht man pro Jahreszahl 1/4 Bit. Der Test auf Teilbarkeit auf 400 läßt sich mit einem >> 2 darauf zurückführen. Und ums perfekt zu machen, macht man für Zahlen, die außerhalb des hochoptimierten Bereiches liegen, eben eine Division mit Rest... Bitte 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
Noch kein Account? Hier anmelden.
|
|
Thread beobachten
Seitenaufteilung abschalten