mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik AVR/ Teilbarkeit durch 100 und 400


Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ahoi,

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:
Zähler <- 0

wiederhole solange Zahl > 0
  Zahl <- Zahl - 100

wenn Zahl = 0
  restlos teilbar durch 100

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

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

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

Autor: 6644 (Gast)
Datum:

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

Autor: 6644 (Gast)
Datum:

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

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Rest ist 0 bei Ganzahldivision?

Autor: 6644 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die division will man scheinbar vermeiden...

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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:
if (wert & 0x0F) {
  return 0; // nicht teilbar
}
)
den Rest wie gehabt in der schleife, nur halt check auf "teilbar durch 
25".

Autor: 6644 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Na. wenn man durch 5, oder 25 teilt, kann man gleich durch hundert 
teilen...

Autor: HannsW (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie wärs denn mit Modulo 100 resp. modulo 100?

Hanns

Autor: Εrnst B✶ (ernst)
Datum:

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

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja WENN er mal sagt wie groß z.B. sein Zahlenbereich ist ;)
Aber... er schweigt ja :)

Autor: Kai G. (runtimeterror)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dreckig, sollte aber seinen Zweck erfüllen:
if (zahl > 51200) zahl -= 51200 // (100 << 9)
if (zahl > 25600) zahl -= 25600 // (100 << 8)
if (zahl > 12800) zahl -= 12800 // (100 << 7)
if (zahl > 6400) zahl -= 6400   // (100 << 6)
if (zahl > 3200) zahl -= 3200   // (100 << 5)
if (zahl > 1600) zahl -= 1600   // (100 << 4)
if (zahl > 800) zahl -= 800     // (100 << 3)
if (zahl > 400) zahl -= 400     // (100 << 2)
if (zahl > 200) zahl -= 200     // (100 << 1)
if (zahl > 100) zahl -= 100     // (100 << 0)

if (zahl == 0) /*glatt teilbar*/

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.

Autor: Kai G. (runtimeterror)
Datum:

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

Autor: Sven P. (haku) Benutzerseite
Datum:

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

Autor: Wolfgang Mües (Gast)
Datum:

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

Autor: Peter Dannegger (peda)
Datum:

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

Autor: Sven P. (haku) Benutzerseite
Datum:

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

Autor: Sven P. (haku) Benutzerseite
Datum:

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

Autor: Kai G. (runtimeterror)
Datum:

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

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

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

Autor: Kai G. (runtimeterror)
Datum:

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

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

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

Autor: Peter Dannegger (peda)
Datum:

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

    dayofyear = 365;
    if( (year & 3) == 0 ){
      dayofyear = 366;          // leap year
      if( year == 0 || year == 100 || year == 200 )  // 100 year exception
        if( --leap400 )          // 400 year exception
          dayofyear = 365;
    }



Peter

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sven Pauli wrote:
> mit 2000 Zeilen Assembler^^ Hab ich auch schon unter Beweis gestellt
> (Anhang).

Welcher Anhang?


Peter

Autor: Uhu Uhuhu (uhu)
Datum:

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

Autor: Kai G. (runtimeterror)
Datum:

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

Autor: Kai G. (runtimeterror)
Datum:

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

Autor: Uhu Uhuhu (uhu)
Datum:

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

Autor: Sven P. (haku) Benutzerseite
Datum:
Angehängte Dateien:

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

Autor: Kai G. (runtimeterror)
Datum:

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

Autor: Uhu Uhuhu (uhu)
Datum:

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

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.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

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