AVR/ Teilbarkeit durch 100 und 400

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

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:

1

if (wert & 0x0F) {

2

  return 0; // nicht teilbar

3

}

)
den Rest wie gehabt in der schleife, nur halt check auf "teilbar durch 
25".

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:

1

if (zahl > 51200) zahl -= 51200 // (100 << 9)

2

if (zahl > 25600) zahl -= 25600 // (100 << 8)

3

if (zahl > 12800) zahl -= 12800 // (100 << 7)

4

if (zahl > 6400) zahl -= 6400   // (100 << 6)

5

if (zahl > 3200) zahl -= 3200   // (100 << 5)

6

if (zahl > 1600) zahl -= 1600   // (100 << 4)

7

if (zahl > 800) zahl -= 800     // (100 << 3)

8

if (zahl > 400) zahl -= 400     // (100 << 2)

9

if (zahl > 200) zahl -= 200     // (100 << 1)

10

if (zahl > 100) zahl -= 100     // (100 << 0)

11

12

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.

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

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

>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:

1

    dayofyear = 365;

2

    if( (year & 3) == 0 ){

3

      dayofyear = 366;          // leap year

4

      if( year == 0 || year == 100 || year == 200 )  // 100 year exception

5

        if( --leap400 )          // 400 year exception

6

          dayofyear = 365;

7

    }

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.

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