Hallo, ich würde gerne wissen ob eine ziemlich große Zahl (40 Bit) durch 3 und durch 5 teilbar ist. Ich bin auf der Suche nach einem schnelleren Weg als eine normale Division. Im Dezimalsystem kann man die Teilbarkeit durch 3 ja mit Hilfe der Quersumme feststellen. Gibt es was vergleichbares im Binärsystem oder muss ich erst die Dezimalstellen meiner Zahl bestimmen? Bei der 5 ein ähnliches Problem, mich interessiert nur die letzte Dezimalziffer der Zahl. Wie krieg ich das am besten raus? Danke.
Ja, /5 geht mit alternierenden Quersummen. Durch 3 ging auch irgendwie, soweit ich mich erinnere. Beitrag "Teilen durch 100 per Schieberegister?" Sehr interessante Sache, das. Cheers
Dr. Frust schrieb: > Hallo, ich würde gerne wissen ob eine ziemlich große Zahl (40 Bit) durch > 3 und durch 5 teilbar ist. Ich bin auf der Suche nach einem schnelleren > Weg als eine normale Division. Die gute Nachricht wäre: Da 255 sowohl durch 5 als auch durch 3 teilbar ist, würde es genügen nur das unterste Byte durch 5 bzw. 3 zu dividieren. Das ist ja jetzt nicht sooo der große Aufwand, d.h. da wird die Latte für alternative Methoden schon sehr eng.
Karl Heinz Buchegger schrieb: > Da 255 sowohl durch 5 als auch durch 3 teilbar ist, würde es genügen nur > das unterste Byte durch 5 bzw. 3 zu dividieren. ??? Dann müsste aber 256 durch 3 und 5 Teilbar sein, weil die größere Zahl ein Vielfaches von 256 ist und nicht von 255. Siehe analog zur Dezimalzahl teilbar duch 4 oder 5. Da sieht man sich auch nur die letzten 2 Ziffern an weil 100 (und nicht 99) durch 4 und 5 teilbar sind.
Karl Heinz Buchegger schrieb: > Die gute Nachricht wäre: Leider ist die schlechte, daß es nicht funktioniert. Ist 259 durch 3 teilbar? 259 / 3 = 86,33333. Also nein. 259 & 0xFF = 3 3 / 3 = 1 Also ja. Oder hab' ich da was völlig falsch verstanden? mfg.
Thomas Eckmann schrieb: > Karl Heinz Buchegger schrieb: >> Die gute Nachricht wäre: > Leider ist die schlechte, daß es nicht funktioniert. Wie wahr, wie wahr. > Oder hab' ich da was völlig falsch verstanden? Leider nicht :-( Ich hab den Bock geschossen.
Hallo Karl Heinz, vielen Dank. Eine 8 bit Division ist ja noch relativ flott. Wirklich super deine Idee!
Dr. Frust schrieb: > Im Dezimalsystem kann man die Teilbarkeit > durch 3 ja mit Hilfe der Quersumme feststellen. Gibt es was > vergleichbares im Binärsystem Mathematik ist aber nicht von Zahlendarstellunugssystemen abhängig. Was im Dezimalsystem gilt, gilt auch im Binärsystem. Ein Beispiel: 14.076.277.767 1+4+7+6+2+7+7+7+6+7 = 54 54/3 = 18 14.076.277.776 = 0x34702F407 das 0x spar' ich mir jetzt mal 3+4+7+2+F+4+7 = 2A 0x2A / 3 = E bzw. 0x2A % 3 = 0 Binär ist mir zuviel Schreiberei, funktioniert aber genauso. mfg.
Hallo, im Binärsystem addiere ich doch nur 1 und 0. 6dez = 110bin Quersumme 10 5dez = 101bin Quersumme 10 und nu?
Horst Hahn schrieb: > und nu? Hast recht. Mit Binärzahlen funktioniert es nicht. Aber mit Hexzahlen. Und das reicht für seine Berechnung. mfg. Thomas Eckmann schrieb: > Binär ist mir zuviel Schreiberei, funktioniert aber genauso. Den Satz bitte steichen.
> ... (40 Bit) durch 3 und durch 5 teilbar ist ...
Wie liegt die Zahl vor? Controller? Dann bietet sich eventuell die
alternierende Quersumme an. Wenn die alternierende Quersumme der
Binärzahl durch, sagen wir 11b teilbar ist, dann ist auch die Zahl durch
11b teilbar.
Beispiel (alles Binärzahlen):
10111011
u u u u
g g g g
ungerade Positionen (u) 1 + 0 + 1 + 0 = 010
gerade Positionen (g) 1 + 1 + 1 + 1 = 100
u - g = -10 (alternierende Quersumme)
-10 ist nicht durch 3 teilbar.
Hallo, kann man das mit der alternierende Quersumme auch mal beweisen? Man könnte auch den Rest einer Division durch 5*3 = 15 nutzen. 1/ 15 ist Binär = 0.00_1000_ , aka Periode '1000' das lässt sich leicht als Additionen aus den richtigen Bytes der Ausgangszahl und der um 4 Bit verschobenen Zahl erzeugen.
Dr. Frust schrieb: > Ich bin auf der Suche nach einem schnelleren > Weg als eine normale Division. Kommt drauf an, was für eine CPU du hast. Ellenlange Additionen von Quersummen kosten auch Zeit und die Teilbarkeit einer Quersumme muß auch wiederum festgestellt werden. Also doch besser Zahl mod 3 oder Zahl mod 5 rechnen und Rest betrachten. W.S.
Horst Hahn schrieb: > kann man das mit der alternierende Quersumme auch mal beweisen? Da verweise ich dich an das Internet. Oder vielleicht möchtest du dich selbst daran versuchen? Ist nicht so schwer.
Dr. Frust schrieb: > Hallo, ich würde gerne wissen ob eine ziemlich große Zahl (40 Bit) durch > 3 und durch 5 teilbar ist. Ich bin auf der Suche nach einem schnelleren > Weg als eine normale Division. Im Dezimalsystem kann man die Teilbarkeit > durch 3 ja mit Hilfe der Quersumme feststellen. Gibt es was > vergleichbares im Binärsystem oder muss ich erst die Dezimalstellen > meiner Zahl bestimmen? Boah, wie hochtrabend hier geantwortet wird. Da staune ich nur. Ich fange mal an mit dem Modulo-Operator und Ganzzahlarithmetik:
1 | long long langezahl; |
2 | langezahl=123456789101111LL; |
3 | if ((langezahl % 3)==0) DoTeilbarDurch3(); |
4 | else DoNichtTeilbarDurch3(); |
5 | |
6 | if ((langezahl % 5)==0) DoTeilbarDurch5(); |
7 | else DoNichtTeilbarDurch5(); |
Für den allgemeinen Fall gesprochen ist es für mich sehr fraglich, ob man da eine schnellere "hochtrabende" Methode finden kann, die in jedem Fall schneller ist. Wenn ich so eine Frage lese, dann gehe ich jedenfalls davon aus, dass da jemand mit Mathe-Schwächen nach einer Hilfestellung fragt und nicht ein Anwärter für die Fields-Medallie nach einer ganz kniffeligen Lösung.
Jürgen S. schrieb: > Boah, wie hochtrabend hier geantwortet wird. > Da staune ich nur. > > Ich fange mal an mit dem Modulo-Operator und Ganzzahlarithmetik: Ich glaube, dass man das Teilbarkeitsproblem mittels Division bzw. Modulo-Operation lösen kann, ist dem Threadstarter schon bewusst :) Die Frage war eben, ob es auch ohne, und damit vielleicht etwas schneller geht.
Jürgen S. schrieb: > Für den allgemeinen Fall gesprochen ist es für mich sehr fraglich, ob > man da eine schnellere "hochtrabende" Methode finden kann, die in jedem > Fall schneller ist. Für die 3 haben wir ja schon die sache mit der alternierenden Quersumme. Für die 5 ist eine BCD Zerlegung mit anschließender Betrachtung der letzen Ziffer bestimmt auch schneller. Vorallem wenn man gleich 64 bit benutzt wie du. Yalu X. schrieb: > Ich glaube, dass man das Teilbarkeitsproblem mittels Division bzw. > Modulo-Operation lösen kann, ist dem Threadstarter schon bewusst :) Zumal das auch zufrifft.
Hier wäre mein Vorschlag, der durch die obige Idee von Karl Heinz getriggert wurde: Wegen
kann man das Problem von 40 Bit auf 11 Bit reduzieren, indem man einfach die 5 Bytes zusammenaddiert. Wenn man die bei den Einzeladditionen ent- stehenden Überträge gleich mit zur Summe addiert (das geht in Assembler besonders leicht), ist das Ergebnis sogar nur 8 Bit breit. Ansonsten muss man eben am Ende die oberen 3 Bits der 11-Bit-Zahl zu den unteren 8 Bits addieren und erhält ebenfalls einen 8-Bit-Wert. Jetzt muss noch festgestellt werden, ob dieser 8-Bit-Wert durch 3 bzw. 5 teilbar ist. Man kann die Zahl bspw. in zwei Gruppen à 4 Bits aufteilen und diese wieder addieren, denn auch 16 hat einen Dreier- und den Fün- ferrest von 1. Wenn man auch hier den Übertrag zur Summe hinzuaddiert, erhält man einen 4-Bit-Wert. Bis hierher verlaufen die Berechnung für die Teilbarkeit durch 3 und 5 genau gleich, brauchen also nur einmal für beide ausgeführt zu werden. Man könnte die Zahl auf ähnliche Weise weiter zusammengestauchen, aber irgendwann wird es praktikabler, das Ergebnis stupide mit den noch verbleibenden Vielefachen von 3 bzw. 5 zu vergleichen. Bei einer 4-Bit- Zahl kommen als Vielfache von 5 nur 0, 5, 10 und 15 in Frage, als Vielfache von 3 zusätzlich 3, 6, 9 und 12. Man könnte aber auch schon bei der 8-Bit-Zahl aufhören, sie weiter zu reduzieren, und stattdessen das Ergebnis aus einer Lookup-Tabelle mit 256 Elementen lesen. Oder vielleicht ist auch eine 8-Bit-Division eine akzeptable Lösung, das müsste man mal ausprobieren. Wie man das Ganze im Detail realisiert, hängt sehr stark davon ab, ob man C oder Assembler benutzt. Assembler hat da wesentlich mehr Tricks auf Lager.
1. Die Bytes der 40-Bit Zahl werden zu einem Word addiert. 2. Die Bytes des Words werden zu einem Word addiert. Die Bytes des Words werden zu einem Byte addiert. // wg. Überlauf 3. Die Nibbles des Bytes werden zu einem Byte addiert. Die Nibbles des Bytes werden zu einem Byte addiert. // wg. Überlauf 4. Ist das Byte 0 oder 15, dann ist die Zahl durch 15 teilbar.
Yalu X. schrieb: >
WOW! Was für ein genialer Ansatz, um ein Rechenproblem mit 64-bit Riesenzahlen auf ein Rechenproblem mit popeligen 8- und 16-bit Zahlen zurückzuführen! Auf diesen Ansatz wäre ich von alleine mit Ausknobeln wahrscheinlich in 100 Jahren nicht gekommen. Ich bin äußerst schwer beeindruckt! Und noch mehr beeindruckt bin ich, seitdem ich den Ansatz auf meinem Arduino mal umgesetzt und einen Benchmark mit 64-bittigen long long Zahlen habe laufen lassen. Getestet auf Arduino/GCC, mit 64-bittigen "long long" Variablen, Zielplattform Atmega328. Selbst diese Version, bei der die Bytes einzeln mit heftigen Bitschiebereien aus der 64-bittigen long long Variablen einzeln rausgequetscht werden, und die am Ende nur mit einem "%5" angewendet auf eine 16-bit Variable abschließt, läuft schon weniger als halb so lange wie ein auf die long long Variable angewendetes "%5":
1 | byte doForumMod5( long long a) |
2 | { // schnelleres "modulo 5" für sehr lange Zahlen auf 8-bit Plattformen |
3 | unsigned int temp; |
4 | temp = a & 0xFF; |
5 | temp+= (a>>8) & 0xFF; |
6 | temp+= (a>>16) & 0xFF; |
7 | temp+= (a>>24) & 0xFF; |
8 | temp+= (a>>32) & 0xFF; |
9 | temp+= (a>>40) & 0xFF; |
10 | temp+= (a>>48) & 0xFF; |
11 | temp+= (a>>56) & 0xFF; |
12 | while (temp>=256) temp-=255; |
13 | return (temp %5); |
14 | } |
Aber den richtigen Boost gibt es erst, wenn man sich das Herauspressen der Bytes mit Bitschiebereien aus der langen Eingangsvariablen erspart und stattdessen eine "union" Struktur als Zahl an die Funktion übergibt, bei der man auf die einzelnen Bytes mittels Byte-Array zugreifen kann: Dann komme ich sogar auf die 17,5-fache Geschwindigkeit gegenüber einem "long long %5". Die tatsächlich erzielbare Geschwindigkeit hängt also nicht nur vom Ansatz und dem prinzipiellen Weg ab, sondern auch von der tatsächlichen Implementation. In ASM geht's wahrscheinlich noch schneller als in C++.
Mir ist gerade eingefallen, dass man die Teilbarkeit einer 8-Bit-Zahl auch ohne Division und größere Bitschieberen ermitteln kann. Man braucht dazu allerdings eine 8-Bit-Multiplikation, die aber kaum Rechenzeit braucht, wenn der Prozessor über einen Hardware-Multiplizierer verfügt. Die komplette Berechnung würde in Assembler für einen ATmega folgender- maßen aussehen:
1 | byte0 = 16 |
2 | byte1 = 17 |
3 | byte2 = 18 |
4 | byte3 = 19 |
5 | byte4 = 20 |
6 | out3 = byte0 |
7 | out5 = byte1 |
8 | tmp = byte2 |
9 | |
10 | ; input: 40 bit number byte0..byte4 |
11 | ; output: out3 (byte0): 1 if number is multiple of 3, else 0 |
12 | ; out5 (byte1): 1 if number is multiple of 5, else 0 |
13 | ; destroys: R0, R1 |
14 | |
15 | add byte0, byte1 |
16 | adc byte0, byte2 |
17 | adc byte0, byte3 |
18 | adc byte0, byte4 |
19 | clr tmp |
20 | adc byte0, tmp |
21 | |
22 | ldi tmp, 205 |
23 | mul byte0, tmp |
24 | ldi tmp, 51 |
25 | ldi out5, 1 |
26 | cp tmp, r0 |
27 | sbci out5, 0 |
28 | |
29 | ldi tmp, 171 |
30 | mul byte0, tmp |
31 | ldi tmp, 85 |
32 | ldi out3, 1 |
33 | cp tmp, r0 |
34 | sbci out3, 0 |
Das Code-Fragment benötigt nur 20 Taktzyklen, um die Teilbarkeit einer 40-Bit-Zahl durch 3 und 5 festzustellen. Mit drei weiteren ADC-Befehlen verarbeitet sie auch 64-Bit-Zahlen und braucht dann 23 Zyklen. Das gleiche Prinzip funktioniert übrigens nicht nur mit 3 und 5, sondern mit jedem Teiler von 255, also auch mit 15, 17, 51, 85 und 255.
Respekt, aber kannst du mir mal erklären wie genau das funktioniert? Und ja, ich benutze einen Atmega :)
Moin! Also auch ich habe noch ein kleines Problem damit, zu verstehen, was Du hier genau machst. (Bzw. in dem Block darunter) Du multiplizierst das Ergebnis der Quersumme mit 205 und vergleichst dann die unteren 8 Bit des Ergebnises (welches Modulo 256 ist) mit 51 - warum? Yalu X. schrieb: > ldi tmp, 205 > mul byte0, tmp > ldi tmp, 51 > ldi out5, 1 > cp tmp, r0 > sbci out5, 0 Edit: (blödsinn) Gruß Jobst
Dr. Frust schrieb: > kannst du mir mal erklären wie genau das funktioniert? Ja, hier ist etwas Mathemagie dazu: k sei ein beliebiger Teiler von 255, für den die Teilbarkeit untersucht werden soll. In der ursprünglichen Fragestellung ist k=3 oder k=5, aber wie schon erwähnt, funktioniert das Verfahren für alle Teiler von 255. Es sei weiterhin
Wegen k|255 ist c ganzzahlig. Die Teilbarkeit einer 8-Bit-Zahl n durch k ist dann durch folgende Beziehung gegeben:
Das obige Assemblerprogramm führt genau diese Prüfung durch. Sie funktioniert aus folgendem Grund: n kann zerlegt werden in ein Vielfaches von k und einen Rest:
Es werden nun zwei Fälle unterschieden: 1. Fall: n ist durch k teilbar, d.h. r=0 ———————————————————————————————————————— Dann ist
und
Damit ist
und (1) ist für den Fall k|n erfüllt. 2. Fall: n ist nicht durch k teilbar, d.h. r>0 —————————————————————————————————————————————— Dann ist
und
Wegen der Ungleichungen für r und i in (2) ist schließlich
womit (1) auch für dann erfüllt ist, wenn n kein Vielfaches von k ist. █▋ Die "magischen" Konstanten im Assemblerprogramm sind also einfach nur die Werte von c bzw. 255/k:
1 | k c 255/k |
2 | ——————————————————— |
3 | 1 1 255 |
4 | 3 171 85 |
5 | 5 205 51 |
6 | 15 239 17 |
7 | 17 241 15 |
8 | 51 251 5 |
9 | 85 253 3 |
10 | 255 255 1 |
11 | ——————————————————— |
Wobei der Fall k=1 trivial ist und für k=255 zumindest auf die Multipli- kation verzichtet werden kann.
Eine natürliche Zahl ist genau dann durch 3 teilbar, wenn ihre alternierende Quersumme (bezüglich ihrer Binärdarstellung) durch 3 teilbar ist:
Für Teilbarkeit durch 5 geht es genauso, ausser daß man die Zahl zur Basis 4 darstellt und entsprechend ihre alternierende Quersumme zur Basis 4 bestimmt:
die q_i sind die Ziffern zur Basis 4, d.h. 2-er Päckchen von Binärziffern.
Nö, nö, nö ... 0 ist nicht durch 5 teilbar ... Okay - Du multiplizierst mit -1/5 (204.8/256) und nimmst Dir dann den Teil unter 1 um dort festzustellen, wie groß der Rest ist. Ist er unter 1/5 bzw. 51.2/256, handelt es sich um eine Zahl die durch 5 teilbar ist ... okay ... Fein! Aber der Sonderfall 0 muss nochabgefangen werden: Einfach, indem byte0 mit outX multipliziert wird ... Gruß Jobst
Jobst M. schrieb: > Nö, nö, nö ... 0 ist nicht durch 5 teilbar ... Wieso denn? Für n≠0 ist 0/n=0 eine ganze Zahl, also ist 0 durch jede Zahl n≠0 teilbar, so auch durch 5. Siehe auch hier: http://de.wikipedia.org/wiki/Teilbarkeit#Formale_Definition > Okay - Du multiplizierst mit -1/5 (204.8/256) und nimmst Dir dann den > Teil unter 1 um dort festzustellen, wie groß der Rest ist. > Ist er unter 1/5 bzw. 51.2/256, handelt es sich um eine Zahl die durch 5 > teilbar ist ... okay ... Naja, ganz so einfach ist es nicht, da man ja nicht mit gebrochenen Zahlen wie 204,8 rechnen will. Wenn man die Zahl aber aufrundet, muss man sich erst vergewissern, dass dieser Unterschied nicht in irgendeinem Einzelfall zum Fehler führt.
Hallo, das ist ja nun beeindruckend schnell, dank yalus genialer Idee. Er hat wohl viel mit Primzahltests zu tuen ;-) Vielen Dank an gjlayde.Es ist schön, wenn solche Dinge, wie die alternierdende Quesumme, nicht einfach vom Himmel fallen.
Yalu X. schrieb: > Wieso denn? Für n≠0 ist 0/n=0 eine ganze Zahl, also ist 0 durch jede > Zahl n≠0 teilbar, so auch durch 5. Okay. Stimmt schon, es ist kein Rest vorhanden ... > Naja, ganz so einfach ist es nicht, da man ja nicht mit gebrochenen > Zahlen wie 204,8 rechnen will. Wenn man die Zahl aber aufrundet, muss > man sich erst vergewissern, dass dieser Unterschied nicht in irgendeinem > Einzelfall zum Fehler führt. Scheint zu passen. Ich habe mal eine Tabelle zum überprüfen, spielen und verstehen gemacht - und hänge sie hier an. Gruß Jobst
Hallo, Yalu X. schrieb: > Das gleiche Prinzip funktioniert übrigens nicht nur mit 3 und 5, sondern > mit jedem Teiler von 255, also auch mit 15, 17, 51, 85 und 255. Könnte man dieses Vorgehen nicht in die Codesammlung als "Schneller Test auf restlose Teilbarkeit für 3,5,15,17,51,85,255" packen? Man könnte ja noch 6,10,30,...,510 dazu packen, weil nur zusätzlich das LSB-it der Ausgangszahl auf 0 getestet werden muss.Analog 3*4,5*4,15*4, wenn die unteren 2 Bits der Ausgangszahl gleich 0 sind etc.
Jobst M. schrieb: > Scheint zu passen. Ich habe mal eine Tabelle zum überprüfen, spielen und > verstehen gemacht - und hänge sie hier an. Das ist eine feine Tabelle und macht die Berechnungen sehr klar. Für Eingangswerte bis zu 255. Allerdings habe ich bei der Umsetzung in einen Algorithmus noch ein Problem. Möglicherweise, weil ich das Vorgehen und die Erklärungen von yalu nicht restlos verstanden habe. Mit Assembler kenne ich mich schon gar nicht aus. Also die Summe der einzelnen Bytes der Zahl kann ja deutlich größer als 255 werden, weil jedes einzelne Byte schon bis zu 255 betragen kann. Wie muss diese Bytesumme noch auf ein einzelnes Byte eingedampft werden, damit man das von Jobst in der "Tabelle nach yalu" dargestellte Berechnungsverfahren anwenden kann?
Jürgen S. schrieb: > Also die Summe der einzelnen Bytes der Zahl kann ja deutlich größer als > 255 werden, weil jedes einzelne Byte schon bis zu 255 betragen kann. Nicht wenn diese Quersumme == modulo (2^8-1) -> == modulo 255 berechnet wurde. Und darum geht es hier: berechnene die Quersumme aller "Ziffern" einer Zahl modulo (2^x-1) x = quersumme(y) mod 255 Gruß hagen
Zur Berechnung dieser Modulo-255-Summe gibt zwei Möglichkeiten: 1. Man berechnet erst die komplette Quersumme, wobei das Ergebnis aber evtl. nicht in einem einzelnen Byte Platz hat. Ist das Ergebnis zwei Bytes groß (oder bei entsprechend vielen Summanden noch größer), bildet man einfach von der Quersumme nochmals die Quersumme, und das solange, bis das Ergebnis nur noch 1 Byte groß ist. 2. Man kann die Methode 1 schon bei jeder Einzeladdition anwenden. Die Summe von zwei 8-Bit-Werten ist maximal 9 Bits groß (das 9. Bit ist der Übertrag). Addiert man diesen sofort zur Quersumme hinzu, bleibt diese auch bei vielen Summanden immer auf die 8 Bits beschränkt, was der Berechnung auf einem 8-Bit-Controller sehr entgegen kommt. Der AVR-Assemblerbefehl ADC (add with carry) addiert zwei Bytes und den Übertrag der vorangegangen Addition und liefert ein 8-Bit-Ergeb- nis mit Übertrag. Er ist also für diese Aufgabe wie geschaffen. Nach- dem alle 5 Bytes auf diese Weise addiert worden sind, muss noch der letzte Übertrag addiert werden. Dies geschieht durch ein ADC mit 0. Genau so habe ich es in obigem Assembler-Programm gemacht. Horst Hahn schrieb: > Könnte man dieses Vorgehen nicht in die Codesammlung als > "Schneller Test auf restlose Teilbarkeit für 3,5,15,17,51,85,255" > packen? Hmm, ich weiß nicht. Meinst du, solche Teilbarkeitsalgorithmen sind außer für den Threadstarter noch für andere Leute interessant? Ich selber habe so etwas auf einem µC noch nie gebraucht :)
Horst Hahn schrieb: > Es ist schön, wenn solche Dinge, wie die > alternierdende Quesumme, nicht einfach vom Himmel fallen. Geht allerdings viel einfacher zu zeigen, denn 2 = -1 mod 3 und 4 = -1 mod 5.
Vielen Dank Hagen Re (hagen) und Yalu X. (yalu)! Ich hab's nun gerafft. Die Addition mit Eindampfung auf 1 Byte funktioniert bei der Teilbarkeitsprüfung mit den magischen Zahlen exakt genau so wie bei der weiter oben im Text besprochenen Mod5/Mod3 Prüfung. Im Beitrag von yalu am 02.11.2012 19:59 zu mod5/mod3 war mir das irgendwie völlig klar geworden, aber bei den komplexeren Rechnungen mit den magischen Zahlen muss ich vor lauter neuen Infos irgendwie einen Blackout gehabt haben und habe nicht erkannt, dass es dort genau so funktioniert. Anyway, ich habe mich jedenfalls als Programmierübung mal dran gesetzt und eine Teilbarkeitsfunktion nach dem oben erläuterten Algorithmus hinbekommen! Yalu X. schrieb: > Hmm, ich weiß nicht. Meinst du, solche Teilbarkeitsalgorithmen sind > außer für den Threadstarter noch für andere Leute interessant? Ich > selber habe so etwas auf einem µC noch nie gebraucht :) Für mich war es jedenfalls eine hübsche Programmierübung. Mit meiner Arduino-Plattform und C++ bin ich ja eher Anfänger und kann ein wenig Programmierübung noch gebrauchen. Wenn ich den C++-Code der Teilbarkeitsfunktion noch etwas anhübsche, könnte ich ihn auch hier posten, falls gewünscht. Mit Assembler und 23 Taktzyklen bei 64-bittigen "long long" Zahlen kann ich aber nicht dienen. Ich kann kein Assembler und mein Code in C++ ist schon deutlich weniger effizient. Aber Dank yalu weiss ich nun wenigstens, was ein "Add mit Carry" Befehl unter Assembler bewirkt! Und auch wenn man den ADC-Befehl unter C nicht genau so umsetzen/verwenden kann, habe ich durch diese Programmierübung doch wieder etwas gelernt! :-)
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.