Hallo, weil ich gerne Zahlen auf dem Arduino (Bitte steinigt mich nicht, ist ja auch bloss ein DevBoard) größer als 32Bit auf dem Arduino verarbeiten will, aber auf keine vernünftige Lösung ohne zeitraubende Bitschubserei komme, wollte ich gerne von euch wissen, ob und gegebenenfalls wie man möglichst effizient 64 oder 128 Bit breite Daten auf einem 8-Bit AVR verarbeitet :) Jeromyo
Jeromyo2 schrieb: > komme, wollte ich gerne von euch wissen, ob und gegebenenfalls wie man > möglichst effizient 64 oder 128 Bit breite Daten auf einem 8-Bit AVR > verarbeitet :) Was heisst verarbeitet ?
Einfache Festkommaarithmetik, dafür aber so zügig wie es geht, RAM noch fast unverbraucht, 7,5kB zur Verfügung :)
Jeromyo2 schrieb: > *Nur Addition und Subtraktion Array benutzen, mit Carry addieren oder subtrahieren. Oder ist das eine Trickfrage ?
:
Bearbeitet durch User
> wie man möglichst effizient 64 oder 128 Bit breite Daten auf einem 8-Bit > AVR verarbeitet :) Was spricht gegen [u]int64_t für 64 Bits? Ansonsten halt selberschreiben, ist für nur Addition/Subtraktion jetzt nicht wirklich aufwendig.
64 Bit Arithmetik kann der AVR-gcc direkt (Datentyp long long). Ich hab mal für ein Projekt 48-Bit Arithmetik in Assembler geschrieben, andere haben 64-Bit Arithmetik in (inline) Assembler gemacht. Alles hier im Forum zu finden (einfach mal die Suche benutzen). 64-Bit Arithmetik kann relativ problemlos auf 128 Bit aufgebohrt werden. XL
Okay danke, werde das mal ausprobieren :) Hatte jetzt nur eine leichte Denkblockade, dachte für 128 Bit muss ich jetzt unzählige (16) 8-Bit Register einzeln händisch abarbeiten, das hätte die Arbeitsgeschwindigkeit schon gedrückt...
Jeromyo2 schrieb: > Okay danke, werde das mal ausprobieren :) Hatte jetzt nur eine leichte > Denkblockade, dachte für 128 Bit muss ich jetzt unzählige (16) 8-Bit > Register einzeln händisch abarbeiten, das hätte die > Arbeitsgeschwindigkeit schon gedrückt... Sicher, unheimlich. Und dein Compiler hat 128 bit breite Register parat.
:
Bearbeitet durch User
Jeromyo2 schrieb: > Hallo, > > weil ich gerne Zahlen auf dem Arduino (Bitte steinigt mich nicht, ist ja > auch bloss ein DevBoard) größer als 32Bit auf dem Arduino verarbeiten > will, aber auf keine vernünftige Lösung ohne zeitraubende Bitschubserei > komme, wollte ich gerne von euch wissen, ob und gegebenenfalls wie man > möglichst effizient 64 oder 128 Bit breite Daten auf einem 8-Bit AVR > verarbeitet :) > > Jeromyo Hast du auch nur ansatzweise eine Vorstellung was eine Binärzahl mit 128 Stellen repräsentiert? 2^128 ~ 3.4×10^38 Damit kannst du den Durchmesser des Universums auf 1Planklänge genau angeben!
Wenn das Sarkasmus ist, tue ich mich hart, ihn zu verstehen :/ Bisher hatte ich nur mit 8 Bit, höchstens mal mit 16 Bit Datentypen gearbeitet, von einem unsigned 64 Bit Typ für dem AVR wusste ich zum Beispiel gar nichts...
Es brauche ihn nur, um auszureizen, bis auf welche Stellen ich die Fibonacci Zahlen ohne Lookup o.Ä. berechnen kann. Bis jetzt bin ich bei der 46. Zahl PS: Hat keinen ernsteren Hintergrund
Max Mustermann schrieb: > Damit kannst du den Durchmesser des Universums auf 1Planklänge genau > angeben! Was ? Wer und wann hat das ausgemessen ? Wo fand der Urknall statt ? In einem früheren Universum ? In einem nicht mehr existierendem Universum ? Mit Universum sollte man sehr, sehr vorsichtig umgehen. So, wie die meisten sich das vorstellen, ist es sicher nicht.
Max Mustermann schrieb: > Hast du auch nur ansatzweise eine Vorstellung was eine Binärzahl mit 128 > Stellen repräsentiert? > > 2^128 ~ 3.4×10^38 > > Damit kannst du den Durchmesser des Universums auf 1Planklänge genau > angeben! Nunja ein wenig übertrieben, die Planklänge liegt doch in der Größenordnung von 10^-35 Metern? Also könntest du in Planklängen lediglich was in der Größenordnung von 3.4Km angeben. ;-). Aber ich seh den Punkt schon, den du verdeutlichen wolltest. MfG Chaos
Marc Vesely schrieb: > Was ? > Wer und wann hat das ausgemessen ? > Wo fand der Urknall statt ? > In einem früheren Universum ? > In einem nicht mehr existierendem Universum ? :D Dazu fällt mir Douglas Adams ein: Es gibt eine Theroie, nach der das Weltall unglaublich kompliziert ist. Und sollte tatsächlich einmal jemand rausfinden, wie das alles funktioniert, wird es augenblicklich durch etwas noch viel komplizierteres ersetzt. Es gibt eine andere Theorie, nach der das schon passiert ist. MfG Chaos
j. t. schrieb: > Max Mustermann schrieb: >> Hast du auch nur ansatzweise eine Vorstellung was eine Binärzahl mit 128 >> Stellen repräsentiert? >> >> 2^128 ~ 3.4×10^38 >> >> Damit kannst du den Durchmesser des Universums auf 1Planklänge genau >> angeben! > > Nunja ein wenig übertrieben, die Planklänge liegt doch in der > Größenordnung von 10^-35 Metern? Also könntest du in Planklängen > lediglich was in der Größenordnung von 3.4Km angeben. ;-). > > Aber ich seh den Punkt schon, den du verdeutlichen wolltest. > > MfG Chaos Weiss doch dass das übertrieben ist! Aber wollte doch mal sehen ob das Jemand merkt ;-)
Max Mustermann schrieb: > Damit kannst du den Durchmesser des Universums auf 1Planklänge genau > angeben! Meinen Sie "Planck-Länge"?
j. t. schrieb: > Es gibt eine Theroie, nach der das Weltall unglaublich kompliziert ist. > Und sollte tatsächlich einmal jemand rausfinden, wie das alles > funktioniert, wird es augenblicklich durch etwas noch viel > komplizierteres ersetzt. Es gibt eine andere Theorie, nach der das schon > passiert ist. Agree. Ich glaube, wir sind einfach um eine Dimension zu kurz. Und wenn wir die entdecken, wird irgendeiner beweisen, dass es einfach noch eine Dimension geben muss. Und wenn wir die entdecken, wird irgendeiner ...
Jeromyo2 schrieb: > Es brauche ihn nur, um auszureizen, bis auf welche Stellen ich die > Fibonacci Zahlen ohne Lookup o.Ä. berechnen kann. Bis jetzt bin ich bei > der 46. Zahl > PS: Hat keinen ernsteren Hintergrund Mit 64-Bit Integer zu rechnen ist auf dem Arduino keine Schwierigkeit, das funktioniert standardmäßig. Signed oder unsigned. Komplizierter wird es erst, wenn Du die berechnete Zahl irgendwo ausgeben möchtest, z.B. auf Serial. Die standardmäßigen Formatierungsroutinen versagen dabei. Und auch Formatierungs-Makros wie "PRIu64" kannst Du in der Arduino-IDE nicht so ohne weiteres nutzbar machen. Da mußt Du also die Ausgabeformatierung der Zahl im Dezimalformat im Zweifelsfall selbst schreiben.
http://www.mikrocontroller.net/articles/AVR_Arithmetik speziell die Library Math32 (siehe Literaturangaben) von Andre Birua befasst sich mit schnellen oder kompakten Routinen für 32 Bit
>Da mußt Du also die Ausgabeformatierung der Zahl im Dezimalformat im >Zweifelsfall selbst schreiben. Also du meinst sein AVR tut zu Lebzeiten noch diesen Zahlenbereich erreichen? ;) Ich glaub eher nicht... Gruß Jonas
Kai S. schrieb: > Max Mustermann schrieb: >> Damit kannst du den Durchmesser des Universums auf 1Planklänge genau >> angeben! > > Meinen Sie "Planck-Länge"? Ja "Planck-Länge"! Danke für die Berichtigung!
Ich habe mir zu der Fibonacci-Fragestellung und wie weit man damit auf einem 8-Bit Atmega kommt nochmal Gedanken gemacht. Im Prinzip kann man "sehr lange" Zahlen doch als Strings definieren und dann die Addition wie mit Bleistift und Papier rechnen. Am Beispiel von 50 Zeichen langen Zahlen-Strings: 00000000000000000000000000000000000000000000000001 00000000000000000000000000000000000000000000000001 -------------------------------------------------- 00000000000000000000000000000000000000000000000002 Oder: 00000000000000000000000000000354224848179261915075 00000000000000000000000000000573147844013817084101 -------------------------------------------------- 00000000000000000000000000000927372692193078999176 Bei Fibonacci hat man es nur mit Addition zu tun und stets nur mit drei Zahlen. Man kann also einfach den freien Arbeitsspeicher ungefähr Dritteln. Auf einem Controller mit 8KB RAM z.B. 7.5 KB / 3 = 2.5 KB = ca. 2500 Bytes lange Char-Arrays für die drei Zahlen definieren. Damit rechnet man dann mit Zahlen, die 2500 Stellen haben. Mit 2500 Stellen dürfte man bis ungefähr die ersten zehntausend Zahlen der Fibonacci-Folge ausrechnen können. Also etwas mehr als mit uint64_t. Ich habe mal auf einem Arduino UNO mit 2 KB RAM und 550 Ziffern langen Zahlen getestet: Wenn man es etwas geschickt anstellt, kann man eine Addition von Zahlen mit 550 Ziffern in ca. 1,5 Millisekunden durchführen. Die Länge der Zahlen, die man addieren kann, ist nur vom freien RAM-Speicher abhängig. Und der Algorithmus für die Addition skaliert mit der Zahlenlänge, also die Addition von Zahlen mit 2000 Stellen dauert viermal so lange wie bei Zahlen mit 500 Stellen. Falls jemand Bedarf hat, könnte ich auch Beispielcode für Arduino und AVR-GCC posten zum Ausrechnen von Additionen bzw. der Fibonacci-Folge bis zu "sehr großen Zahlen" auf einem 8-Bit Controller.
j. t. schrieb: > :D Dazu fällt mir Douglas Adams ein: > Es gibt eine Theroie, nach der das Weltall unglaublich kompliziert ist. > Und sollte tatsächlich einmal jemand rausfinden, wie das alles > funktioniert, wird es augenblicklich durch etwas noch viel > komplizierteres ersetzt. Es gibt eine andere Theorie, nach der das schon > passiert ist. Wo wir schon bei Zitaten sind: Falsch! Es gibt eigentlich kein Universum. Da schwingt auch nichts. Wieso auch? Na, von wem könnte das stammen?
Für einen reziproken Frequenzzähler mit 8 1/2 Stellen habe ich mal eine Kehrwertbildung mit 32 Bit auf AVR geschrieben. Wenn ich nicht irre, braucht man dafür in Integerarithmetik eine Division 64/32Bit. Vor der Kehrwertbildung sind es 32 Bit vor dem Komma, danach 32 Bit nach dem Komma, sodass man es um 32 Bit nach oben verschoben rechnen muss. Das hat auch funktioniert, das prinzipielle Vorgehen habe ich aus der genannten Math32-Library entnommen.
>..aber auf keine vernünftige Lösung ohne zeitraubende Bitschubserei
komme,
Der Compiler macht ueberigens genau das.
Jürgen S. schrieb: > Man kann also einfach den freien Arbeitsspeicher ungefähr Dritteln. Auf > einem Controller mit 8KB RAM z.B. 7.5 KB / 3 = 2.5 KB = ca. 2500 Bytes > lange Char-Arrays für die drei Zahlen definieren. Damit rechnet man dann > mit Zahlen, die 2500 Stellen haben. > > Mit 2500 Stellen dürfte man bis ungefähr die ersten zehntausend Zahlen > der Fibonacci-Folge ausrechnen können. Also etwas mehr als mit uint64_t. Und wenn du die Bytes nicht mit ASCII-Ziffern zumüllst, sondern mit Bytes, dann kannst du bis 256^2500, also 6020 Dezimalstellen rechnen. Und schneller rechnen kannst du damit auch noch... Nur das Umrechnen des Ergebnisses von der Basis 256 auf die Basis 10 wird etwas happig...
Siebzehn Zu Fuenfzehn schrieb: > Der Compiler macht ueberigens genau das. Je weniger ein Programmierer selbst Ahnung hat, desto mehr traut er einem Compiler zu, auch dass er aus dem Nichts 64bit-Register schafft - deswegen spricht man ja von compiler magic. Georg
kann mna die Größe des Universums überhaupt messen? Es expandiert ja schneller (oder genau gleich schnell) wie die schnellste denkbare Messung. Der Compiler setzt Arithmetik schon recht gut auf die Register des Mikrocontrollers um. Das ein 8bit Mikrocontroller für 12bit Variablem viel länger braucht, als für 8bit Variablen liegt auf der Hand. Daran kann man "manuell" auch viel verbessern.
tictactoe schrieb: > Und wenn du die Bytes nicht mit ASCII-Ziffern zumüllst, sondern mit > Bytes, dann kannst du bis 256^2500, also 6020 Dezimalstellen rechnen. > Und schneller rechnen kannst du damit auch noch... Ja klar: Für eine Dezimalziffer zwischen 0 und 9 ein ganzes Byte an RAM zu reservieren ist schon etwas verschwenderisch. Denn schließlich braucht man für eine Darstellung von 0 bis 9 rein rechnerisch nur "knappe 4 Bits" und nicht volle 8 Bits. Andererseits: Um die Ausgabeformatierung als Dezimalzahl braucht man sich dann keinerlei Gedanken machen, denn als String sind "interne Zahlendarstellung" und "menschenlesbare Dezimaldarstellung" ein und dasselbe, wenn man meinem Vorschlag folgt. > Nur das Umrechnen des Ergebnisses von der Basis 256 auf die Basis 10 > wird etwas happig... Genau! Und weil ich mal davon ausgehe, dass man sich eine Fibonacci-Zahlenfolge mit mehreren hundert oder gar mehreren tausend signifikanten Stellen nicht als HEX-Ziffernfolge ausgeben lassen möchte sondern als Dezimalziffernfolge, ist mein Vorschlag so wie ich ihn gemacht habe. Wenn man das RAM trotz Demimalausgabe der Ziffern effektiver nutzen möchte als mit meinem String-Vorschlag, wäre meine nächste Idee eine interne BCD-Darstellung im Array: Je vier Bits repräsentieren dann eine dezimale Ziffer im Array, so dass in einem Byte RAM-Speicher jeweils zwei Dezimalziffern in BCD-Codierung dargestellt werden können. Mit 2500 Bytes großen Arrays könnte man also in BCD Zahlen bis zu 5000 signifikanten Ziffern darstellen. Und das ließe sich dann mit wenig Aufwand auch leicht wieder als Dezimalzahl ausgeben. Der Threadstarter hatte oben geschrieben "Bis jetzt bin ich bei der 46. Fibonacci-Zahl". Und ich wollte ihm eigentlich nur zeigen, dass er sich nicht mit einer Verdoppelung zufrieden geben braucht, wie es mit uint64_t "unsigned long long" Integern möglich wäre, sondern dass er auf seinem Controller ganzzahlige Additionen auch leicht mit mehreren tausend signifikanten Stellen durchführen kann.
Jeromyo2 schrieb: > Okay danke, werde das mal ausprobieren :) Hatte jetzt nur eine leichte > Denkblockade, dachte für 128 Bit muss ich jetzt unzählige (16) 8-Bit > Register einzeln händisch abarbeiten, das hätte die > Arbeitsgeschwindigkeit schon gedrückt... Wenn du einen schon verfügbaren Datentyp nimmst, ändert sich daran nur, daß du es nicht mehr "händisch" machen mußt. Aber auf magische Weise schneller wird es dadurch nicht. Max Mustermann schrieb: >> Meinen Sie "Planck-Länge"? > > Ja "Planck-Länge"! > Danke für die Berichtigung! Und ich hab mich schon gefragt, ob Plan-Klänge mal wieder irgendso eine neue Theorie über den Aufbau des Universums sind ;-)
stefanus schrieb: > kann mna die Größe des Universums überhaupt messen? Nein. Man weiß ja auch gar nicht wirklich wie groß es ist. Man kann lediglich abschätzen wie groß das beobachtbare Universum ist. Das ist nach aktuellem Wissensstand eine Kugel von gut 90 Mrd. Lichtjahren Durchmesser. Ob und was hinter dem Sichbarkeitshorizont kommt, weiß man nicht.
Jürgen S. schrieb: > weil ich mal davon ausgehe, dass man sich eine > Fibonacci-Zahlenfolge mit mehreren hundert oder gar mehreren tausend > signifikanten Stellen nicht als HEX-Ziffernfolge ausgeben lassen möchte > sondern als Dezimalziffernfolge Das eine ergibt so wenig Sinn wie das andere. Wenn ich eine 2000-stellige Zahl auf ein Blatt Papier drucke und es dir in die Hand drücke, wie lange brauchst du dann, um festzustellen ob das wirklich eine Fibonacci-Zahl ist und nicht nur eine geschickt gewählte Zufallszahl? Als Kompromiß könnte man natürlich mit BCD-Zahlen rechnen. Ergibt immer noch die doppelte Anzahl an Dezimalstellen. Nicht zuletzt gibt es auch eine explizite Formel für die n-te Fibonacci- Zahl. Rekursion ist nur für kleine Werte von n überhaupt sinnvoll. XL
Es gibt 4 2000-stellige Fibonacci-Zahlen. Die größte ist die 9565.: (siehe angehängte Textdatei) Wer nachrechnen möchte: (Shell-Script)
1 | export summeA=1 ; export summeB=0 ; for ((i=0;i<9566;i++)) ; do export summe=`echo $summeA+$summeB | bc | sed s,'\\\','',g | tr "\n" ":" | sed s,":","",g` ; export summeA=$summeB ; export summeB=$summe ; echo $i $summe `echo $summe | wc -c` ; done |
Im Controller muss man nur Platz für zwei Zahlen haben, denn die 'andere' Summe muss nur auf die bereits vorhandene Zahl aufaddiert werden. So addiert man immer hin und her - 8-Bit Beispiel in AVR-asm: LDI R0, 0 LDI R1, 1 ADD R0, R1 ADD R1, R0 ADD R0, R1 : : Wenn man binär rechnet, muss man auch bedenken, dass die Umwandlung ca. 225% des Speicherplatzes einer Binärzahl benötigt. Es kann also evtl. günstiger sein, gleich in BCD zu rechnen. Vom Rechenaufwand ist die Binärrechnung zu bevorzugen. Hier dauert ein Additionsvorgang in ASM nur etwa 16000 Takte bei 2000 Byte - Bei 20MHz ist man also in weniger als 10s fertig mit der Berechnung. Die Umwandlung (Double-dabble) besteht aus 16000 Schiebeoperationen in einem 36000-Bit langen Schieberegister. Nach jedem Schiebeschritt müssen 2500 Vergleiche und im Mittel 1250 4-Bit Additionen durchgeführt werden. Wenn man das halbwegs vernünftig macht, schiebt man erst die untersten 2000 Byte um ein Bit nach oben (12000 Takte), dann fährt man mit den oberen 2500 Bytes fort und führt dort gleich 2 Vergleiche und mögliche Additionen durch (30000 Takte) - also 42000 Takte für einen Schiebeschritt. Wären also 672Mio. Takte bzw. 34s bei 20MHz. In Summe also 44s. Am günstigsten wäre vermutlich, mit Zahlen von 0-99 in einem Byte zu rechnen. Die kann man anschliessend gut in BCD umwandeln. Sollte das Ergebnis einer Addition =>100 sein, einfach 100 abziehen und einen Übertrag bilden. Wären 22000 Takte für einen Additionsgang. Hier würde das Ergebnis schon nach 11s zur Verfügung stehen - Die Umwandlung der Bytes in zwei BCD-Zahlen kann on-the-fly bei der Ausgabe passieren (ca. 16000 Takte.) Die Zahlen sind nicht ausgedacht - ich habe gerade konkreten Code im Kopf. Ich brauchte gerade etwas Beschäftigung - sorry :-D Gruß Jobst
Jobst M. schrieb: > Am günstigsten wäre vermutlich, mit Zahlen von 0-99 in einem Byte zu > rechnen. Wohl eher die Zahlen von 0-(10^19-1) in 8 Bytes. Das quetscht in 8 Bytes 19 statt nur 16 Stellen hinein, und man kann immer noch mit uint64_t rechnen.
Ein sehr hohe Auflösung kann man ggf. gut gebrauchen, wenn man Algorithmen hat, die bei Zwischenergebnissen große Zahlen nutzen und dann Differenzen bilden. Beispiele sind etwa das lösen linearer Gleichungssysteme oder die Berechnung der Steigung einer geraden. Meist gibt es Lösungen die numerisch besser sind, aber das erfordert ggf. längeren Code und mehr Überlegungen. Da ist manchmal der "Brute Force" Weg über sehr lange Zahlen schon passend. Wenn es nur um Addition / Subtraktion geht, wäre ggf. die Rechnung als BCD schon einfacher, weil man sich die Umwandlung spart.
Axel Schwenke schrieb: > Das eine ergibt so wenig Sinn wie das andere. Ja, es ist nichts weiter als eine Zahlenspielerei, Zahlen mit möglichst vielen signifikanten Stellen auf einem 8-Bit Controller zu berechnen und auszugeben. Jobst M. schrieb: > Im Controller muss man nur Platz für zwei Zahlen haben, denn die > 'andere' Summe muss nur auf die bereits vorhandene Zahl aufaddiert > werden. So addiert man immer hin und her Sehr guter Vorschlag! Irgendwie war ich auf dem Trip, dass man für "Summand1 plus Summand2 = Summe" immer drei Zahlen braucht. Tatsächlich reichen für die Rechnungen mit der Fibonacci-Folge aber bereits zwei Zahlen, zu denen man abwechselnd draufaddiert. Dadurch kann man pro Zahl nicht nur ein Drittel des freien RAM-Speichers verwenden, sondern sogar die Hälfte! Jobst M. schrieb: > Am günstigsten wäre vermutlich, mit Zahlen von 0-99 in einem Byte zu > rechnen. Die kann man anschliessend gut in BCD umwandeln. Sollte das > Ergebnis einer Addition =>100 sein, einfach 100 abziehen und einen > Übertrag bilden. Sehr guter Vorschlag! Gegenüber meinem "String" Vorschlag bekommt man damit doppelt so viele Ziffern im Array untergebracht. Plus zwei Ziffern extra, die man sonst wegen des Nullzeichens \0 am Ende des Strings nicht nutzen könnte. Allerdings muss man sich selbst eine Ausgaberoutine dafür schreiben. Ich habe das mal in einen Arduino-Sketch umgesetzt. Mit Ausgabe der Fibonacci-Folge auf Serial mit 115200 Baud. Ausgegeben wird i, Fibonacci(i) und die Länge der Fibonacci-Zahl. Standardmäßig werden nur die ersten 20 Fibonacci-Zahlen ausgegeben, jede 64. Fibonacci-Zahl und die allerletzte zu berechnende Fibonacci-Zahl. Die letzte auf einem Arduino-UNO mit meinem Sketch zu berechnende Zahl ist Fibonacci(8183), das ist eine Zahl mit 1710 signifikanten Ziffern. Eigentlich schon nicht schlecht für einen 8-Bit Controller mit nur 2KB RAM. Wenn man noch mehr möchte, müßte man wohl auch noch den Vorschlag von "tictactoe (Gast)" berücksichtigen, und nicht immer 2 Ziffern in einem Byte, sondern 19 Ziffern in einem uint64_t in 8 Bytes verarbeiten. Ich hänge mal die nach .c umbenannte Arduino-Datei an, damit man sich den Code hier im Forum ansehen kann. Der Code ist aber ein Arduino-Sketch (.ino Datei).
:
Bearbeitet durch User
Max Mustermann schrieb: > Hast du auch nur ansatzweise eine Vorstellung was eine Binärzahl mit 128 > Stellen repräsentiert? > > 2^128 ~ 3.4×10^38 > > Damit kannst du den Durchmesser des Universums auf 1Planklänge genau > angeben! Und was will und das jetzt sagen? Ich hatte schon mal ne Anwendung wo eine Genauigkeit von über 1000 Dezimalstellen (für die Mantissen komplexer Zahlen) erforderlich war — zugegebenermaßen nicht auf einem AVR. Die Plancklänge oder Anzahl Elementarteilchen in Universum ist da komplett Schnurz...
tictactoe schrieb: > Wohl eher die Zahlen von 0-(10^19-1) in 8 Bytes. Das quetscht in 8 Bytes > 19 statt nur 16 Stellen hinein, und man kann immer noch mit uint64_t > rechnen. Die Umwandlung in eine Dezimalzahl bereitet dann allerdings wieder Probleme, welche recht Zeitaufwändig sind. Das wollte ich vermeiden. Gruß Jobst
Der Code für + und - ist fix hingeschrieben und auch nicht lange; hier ein Auszug aus MuliPrezzl, einer low-Level, low-Overhead Implementierung in Assembler: Addition
1 | DEFUN adc |
2 | push NUM |
3 | lsr CARRY |
4 | |
5 | 0: ld TMP, X |
6 | ld CARRY, Z+ |
7 | adc TMP, CARRY |
8 | st X+, TMP |
9 | dec NUM |
10 | brne 0b |
11 | |
12 | set |
13 | XJMP restore_carry |
14 | ENDF adc |
15 | |
16 | DEFUN add0 |
17 | push NUM |
18 | sbrc r25, 7 |
19 | com ZERO |
20 | |
21 | ld TMP, X |
22 | add TMP, r25 |
23 | rjmp 1f |
24 | |
25 | 0: ld TMP, X |
26 | adc TMP, ZERO |
27 | 1: st X+, TMP |
28 | dec NUM |
29 | brne 0b |
30 | |
31 | clr ZERO |
32 | clt |
33 | XJMP restore_carry |
34 | ENDF add0 |
Subtraktion
1 | DEFUN sub |
2 | push NUM |
3 | clr CARRY |
4 | |
5 | 0: ld TMP, X |
6 | ld CARRY, Z+ |
7 | sbc TMP, CARRY |
8 | st X+, TMP |
9 | dec NUM |
10 | brne 0b |
11 | |
12 | set |
13 | XJMP restore |
14 | ENDF sub |
Ein- und Ausgabe werden via Z bzw. X referenziert. Weil der Schleifenzähler nur 8 Bit groß ist, bleibt die Arithmetik auf 2040 Bits limitiert. Was noch fehlt ist Restore
1 | DEFUN restore_carry |
2 | clr CARRY |
3 | rol CARRY |
4 | ENDF restore_carry |
5 | |
6 | DEFUN restore |
7 | pop NUM |
8 | sub r26, NUM |
9 | sbc r27, ZERO |
10 | brtc 0f |
11 | sub r30, NUM |
12 | sbc r31, ZERO |
13 | 0: ret |
14 | ENDF restore |
sowie der ganze Plüsch für die Präambel mit Makros etc: Plüsch
1 | #include <avr/io.h> |
2 | #undef __SFR_OFFSET |
3 | #define __SFR_OFFSET 0 |
4 | |
5 | #define MP(name) mp_##name##_asm |
6 | |
7 | #if defined (__AVR_HAVE_JMP_CALL__) |
8 | .macro XCALL name |
9 | call MP(\name\()) |
10 | .endm |
11 | .macro XJMP name |
12 | jmp MP(\name\()) |
13 | .endm |
14 | #else |
15 | .macro XCALL name |
16 | rcall MP(\name\()) |
17 | .endm |
18 | .macro XJMP name |
19 | rjmp MP(\name\()) |
20 | .endm |
21 | #endif |
22 | |
23 | #define ZERO r1 |
24 | #define TMP r0 |
25 | |
26 | #define NUM r24 |
27 | #define CARRY r25 |
28 | |
29 | .macro DEFUN name |
30 | .section .text.libmp.asm.\name, "ax", @progbits |
31 | .global MP(\name\()) |
32 | .func MP(\name\()) |
33 | MP(\name\()) : |
34 | .endm |
35 | |
36 | .macro ENDF name |
37 | .size MP(\name\()), . - MP(\name\()) |
38 | .endfunc |
39 | .endm |
Um die Funktionen von C aus zu verwenden gibt es Inline-Funktionen, die
transparente Calls zu den Assembler-Funktionen ausführen und die
Interface-Beschreibungen enthalten, siehe libmp.h im Anhang.
Die Funktionen sind zwar selbsterklärend, hier aber trotzdem nochmal
ausgedeutscht:
mp_adc: Addition mit Carry zweier n-Byte Zahlen.
mp_add0: Addition einer vorzeichenbehafteten 1-Byte Zahl auf eine
n-Byte Zahl.
mp_sub: Subtraktion zweier n-Byte Zahlen.
Jeromyo2 schrieb: > Hallo, > > weil ich gerne Zahlen auf dem Arduino (Bitte steinigt mich nicht, ist ja > auch bloss ein DevBoard) größer als 32Bit auf dem Arduino verarbeiten > will, aber auf keine vernünftige Lösung ohne zeitraubende Bitschubserei > komme Das verstehe ich nicht. Für den von Arduino verwendeten AVR-GCC Compiler existieren die Datentypen int64_t und uint64_t mit allen üblichen Verarbeitungsfunktionen wie Addieren, Subtrahieren, Multiplizieren und Ganzzahl-Division einschließlich Modulo-Funktion. Was brauchst Du noch? Das einzige, was in der Arduino-IDE für 64-Bit Ganzzahlen fehlt, ist eine Ausgabeformatierung, aber dafür kann man sich ja leicht selbst etwas schreiben. Und ja: Die 64-Bit Funktionen für Ganzzahl-Arithmetik sind sehr langsam im Vergleich zu 16-Bit-Arithmetik.
Jürgen S. schrieb: > Das verstehe ich nicht. 3 Jahre später ... Wenn's mal wieder länger dauert ... Gruß Jobst
Jobst M. schrieb: > Jürgen S. schrieb: >> Das verstehe ich nicht. > > 3 Jahre später ... > > Wenn's mal wieder länger dauert ... > > Gruß > Jobst Ja, und wenn man beim Kontrollieren über "Threads mit meinen Beiträgen" nach einer Viertelstunde selbst merkt, dass man versehentlich auf ein uraltes und totes Thema geantwortet hat und den Beitrag wieder löschen oder ändern möchte, dann ist das in diesem Forum nicht mehr möglich und man sieht nur die Mitteilung, dass man dazu keine Berechtigung hätte. Seltsames Forum hier, das einem Verfasser eines Beitrags schon nach ganz kurzer Zeit jede Berechtigung zum Ändern oder Löschen des selbstverfaßten Beitrags entzieht.
Jürgen S. schrieb: > Seltsames Forum hier, Das ist nicht "seltsam", das ist beabsichtigt, sobald auf den verfassten Beitrag ein anderer folgt. Das alles wurde in den vergangenen Jahren bereits ad nauseam ausdiskutiert. Wesentliche Punkte, die hier berücksichtigt werden, sind diese: "Geschichtsklitterung" - Forist A stellt Behauptung X in den Raum. - Forist B antwortet darauf mit einem Widerspruch. - Forist A ändert seine Behauptung dergestalt, daß der Widerspruch zu Unfug wird, und Forist B als Trottel dasteht. "Informationslücken" Durch nachträgliches Löschen von Beiträgen können Threads komplett unverständlich werden.
Na, ist doch alles halb so schlimm. Sein Arduino ist doch eh noch am Rechnen. Gruß Andreas
Jürgen S. schrieb: > Ja, und wenn man beim Kontrollieren über "Threads mit meinen Beiträgen" > nach einer Viertelstunde selbst merkt, dass man versehentlich auf ein > uraltes und totes Thema geantwortet hat und den Beitrag wieder löschen > oder ändern möchte Dann hättest Du ihn ja melden können ... Ist Dir der rote, fette Absatz nicht aufgefallen? Gruß Jobst
Andreas B. schrieb: > Na, ist doch alles halb so schlimm. Sein Arduino ist doch eh noch am > Rechnen. > > Gruß > Andreas Ja tatsächlich, woher weißt Du? Immer noch die Zahl PI auf etliche tausend Stellen genau mit Atmega328! Zur Zeit experimentiere ich mit modifizierten Versionen des Codes, wie er hier 2012 vorgestellt wurde: Beitrag "ATtiny2313 berechnet π auf 4000 Stellen" Das hat mir keine Ruhe gelassen, dass nach 4000 Stellen Schluß mit der Berechnung auf 8-Bit Controllern sein soll. Und inzwischen kann mein Arduino UNO (Atmege328) nach einigen Modifikationen auch mehr als 8000 Stellen von Pi berechnen. Dauert nur seine Zeit. Das ist hier heute morgen über meinen seriellen Monitor in der Arduino-IDE gelaufen:
1 | Start calculating 128 hex digits of PI |
2 | first digit is digit #:8000 |
3 | last digit is digit #:8127 |
4 | |
5 | calculating... |
6 | 5
|
7 | 6E16369788D273CCDE96629281B949D04C50901B71C65614E6C6C7BD327A140A |
8 | 45E1D006C3F27B9AC9AA53FD62A80F00BB25BFE235BDD2F671126905B204022 |
9 | FINISHED
|
10 | Calculation time in seconds: 2170.60 |
Also die Berechnung von 128 Hex-Digits nach demBailey-Borwein-Plouffe Algorithmus zwischen derachttausendsten und der 8127sten Stelle. Völlig fehlerfrei in allen berechneten Stellen, aber die letzten 128 Stellen bis zur 8127sten dauern auch schon 36 Minuten bei 16 MHz auf Atmega328.
Jürgen S. schrieb: > Andreas B. schrieb: >> Na, ist doch alles halb so schlimm. Sein Arduino ist doch eh noch am >> Rechnen. >> >> Gruß >> Andreas > > Ja tatsächlich, woher weißt Du? Auf meine Glaskugel ist Verlass. ;-) Gruß Andreas
Thread beobachten
Seitenaufteilung abschaltenBitte 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.