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 ?
> 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.
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 ;-)
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.
>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.
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).
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.
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.
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:
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 abschalten