Hallo Leute, Ich möchte gerne ein Programm schreiben, bei dem die Fakultäten der Zahlen 1-200 berechnet werden (Auf die letzte Stelle genau). Diese sollen in Arrays berechnet werden und die Ein/Ausgabe geschieht über Hyperterminal, also über die RS323 Verbindung. Programme für Fakultäten gibt es viele im Netz, nur leider alle für PC's und Assembler. Ich lege zwei Arras für zwischenberechnung mit einer größe von jeweils 400 an. (In jede Stelle vom Array kommt eine Zahl hinein. Das Array hat 400 Stellen, da die Fakulltät von 200 insgesamt 375Stellen hat.) Mich würde interessieren, wie ich die Zwei Schleifen zur berechnung schreiben soll/kann... Desweiteren, wie ich den Carry(Übertrag) realisiere. Vielen Dank für eure Antworten. lg Paul
Paul P. schrieb: > Ich lege zwei Arras für zwischenberechnung mit einer größe von jeweils > 400 an. (In jede Stelle vom Array kommt eine Zahl hinein. Das Array hat > 400 Stellen, da die Fakulltät von 200 insgesamt 375Stellen hat.) > > Mich würde interessieren, wie ich die Zwei Schleifen zur berechnung > schreiben soll/kann... Genauso wie du es sonst auch machen würdest. Der einzige Unterschied besteht darin, dass du nicht die eingebauten Operatoren * und + benutzen kannst, sondern auf deine eigenen Funktion zurückgreifen musst, die die Multiplikation von grossen Zahlen erledigt (dort wirst du auch den + Operator benötigen) > Desweiteren, wie ich den Carry(Übertrag) realisiere. In einer Addition, wo der Carry einer einzigen Stelle maximal 0 ooder 1 sein kann: Digit = DigitA + DigitB + Carry; if( Digit > 10 ) { Carry = 1; Digit -= 10; } else Carry = 0; Du machst genau dasselbe, was du auch mit Papier und Bleistift machst, wenn du mit großen Zahlen rechnest (also mit dem auswendig gelernten kleinen EinmalEins nicht mehr weiterkommst). Vielleicht solltest du erst mal beobachten, was genau du am Papier machst, wenn du 2 Zahlen addierst und das in einem Program (am PC) nachbilden. Ich denke übrigens nicht, dass du das am Mega16 hinkriegen wirst. Überschlagsmässig benötigst du nämlich 3 400-stellige 'Variablen'. In der Multiplikation wird noch ein zusätzliches 'Register' benötigt. Aber das werden dir deine Vorübungen am PC schon zeigen :-)
>Überschlagsmässig benötigst du nämlich 3 400-stellige 'Variablen'.
Für was denn das? Er braucht a) Speicherplatz für eine einzige
375-stellige BCD-Zahl und b) das Know-How, wie man diese Zahl mit einer
Zahl multipliziert, die zwischen 1 und 200 liegen darf. Dann muss er
sich nur noch die zur Fakultätsdefinition n° = 1 2 3 * ... * n
passende Schleife konstruieren. Ich schätze die Berechnung von 200! auf
einem ATMega16 als völlig unproblematisch ein. Er sollte das Ergebnis
innerhalb eines Sekundenbruchteils errechnen können.
Selbst Matlab auf meinem Rechner sagt nur noch: factorial(200) = inf ich würde daher von einer Umsetzung auf dem AVR absehen (wofür eigentlich?) und entweder auf eine Näherung oder eine Tabelle ausweichen. Gruß Lasse
Gast schrieb: >>Überschlagsmässig benötigst du nämlich 3 400-stellige 'Variablen'. > > Für was denn das? Er braucht a) Speicherplatz für eine einzige > 375-stellige BCD-Zahl und b) das Know-How, wie man diese Zahl mit einer > Zahl multipliziert, die zwischen 1 und 200 liegen darf. Du hast recht. Der Multiplikator wird ja gar nicht so gross. Hab ich übersehen.
ich würde einfach eine LUT für die 200 Werte machen... Martin
Wofür eigentlich? Ich kann mir gerade keine sinnvolle Aufgabenstellung vorstellen, bei der man entsprechend große Fakultäten braucht.
>> Selbst Matlab ... Seit wann ist denn Matlab ein Maßstab? http://www.wolframalpha.com/input/?i=200!
Martin schrieb: > ich würde einfach eine LUT für die 200 Werte machen... Je nach verwendetem Zahlenformat könnte das etwas knapp werden: Nimmt man BCD, braucht man etwas mehr als 16KiB, der ATmega16 ist dafür zu klein. Nimmt man die Binärdarstellung, reichen schon etwas weniger als 14KiB, dafür braucht man zusätzlichen Code für die benutzerfreundliche Ausgabe (falls das überhaupt erwünscht ist). > Seit wann ist denn Matlab ein Maßstab? > > http://www.wolframalpha.com/input/?i=200%21 Das Problem hat sich damit auf die Implementierung eines einfachen HTTP-Clients reduziert ;-)
>wofür eigentlich?
Vielleicht einfach, um etwas dabei zu lernen? Um Erkenntnisse zu
gewinnen? Um ein Gefühl dafür zu bekommen, welche Aufgaben mit einem µC
von der Leistungsklasse leicht, schwer oder garnicht zu lösen ist? Um
sich am Erlebnis zu freuen, ein Problem erfolgreich gelöst zu haben? Man
kann es als Denksportaufgabe und geistige Herausforderung betrachten. Es
ist sicher ein besserer Zeitvertreib als nur zu fragen "wofür
eigentlich?".
Wenn Du die Zahlen BCD kodierst kannst Du 2 Ziffern in ein Byte packen. Nur die Multiplikation und Additionsfunktion wird dann etwas unübersichtlicher. Oder Du machst einen Übertag bei 100, dann hast Du auch 2 Ziffern in einem Byte, kannst die Ziffern aber nicht mehr so schön eine nach dem anderen ausgeben. Die Funktionen zum Addieren und Multiplizieren selbst mach mal schön selber sonst ist der Lerneffekt = null :-)) Gruß, Udo
Es klingt eher so, als ob man hier einen Algorithmus braucht, mit dem man eine bestimmte Ziffer des Ergebnisses berechnen kann. Für pi gibt es so einen, wenn ich micht nicht irre, vielleicht ja auch für die Fakultät? Hat nur irgendwie eher wenig mit Mikrocontrollerprogrammierung zu tun, sondern mehr mit Mathematik... man könnte das Problem (mit dem obigen Ansatz) ja auch erst mal auf einem PC oder Mac grundsätzlich lösen, und sich dann an die Portierung machen. Wobei ich mir jetzt sinnvollere Aufgaben vorstellen kann, als im Debugger 375 Stellen eines Arrays durchzugehen. Zum Beispiel eine schöne Fouriertransformation mit Ausgabe auf einem LCD... da lernt man auch viel wenn man sie selbst ausprogrammiert, genug Mathe ist allemal drin, und es gibt sogar sinnvolle Anwendungen dafür. ;-)
Klingt für mich eher nach einer Aufgabe für einen Azubi oder Anfangssemester der keine Lust auf selber programmieren hat.
>Klingt für mich eher nach...
An so etwas Schlimmes wollen wir mal lieber nicht denken ;-)
>Für pi gibt es >so einen, wenn ich micht nicht irre, vielleicht ja auch für die >Fakultät? Ja gibt es, sogar sehr effizient.
-> Ich bin nicht zu faul zum selber programmieren, mir fehlt nur ein Ansatz. -> Desweiteren kenne ich auch die Stirling Formel zur Näherung. Aber bis ich die geschrieben habe, hab ich die Additio/multiplikation selber schneller gemacht. Ich habe halt sowas noch nie geschrieben, aber jetzt hab ich ein paar Anhaltspunkte und versuche mal übers Wochenende eine Addierfunktion zu schreiben, die so addiert, wie man selber von Hand. In den Arrays werden die Zahlen binär abgespeichert. Ich muss dann nur noch den Nulloperator zum beenden von Strings auf 0xFF ändern. Kp wie^^ Also danke für eure Antworten, ich meld mich :) lg Paul
Hagen Re schrieb:
> Ja gibt es, sogar sehr effizient.
Link bitte?
Vergiss die Stirlingformel.
Der Dreh- und Angelpunkt ist die Frage, wie man 625371837 x 946
(allgemeiner: eine sehr große Zahl mit einer dreistelligen Zahl)
berechnen kann, wenn man nur (1) das kleine Einmaleins kennt und (2)
addieren kann.
Das geht so:
6 x 9 = 54
6 x 4 = 24
6 x 6 = 36
2 x 9 = 18
2 x 4 = 08
2 x 6 = 12
5 x 9 = 45
5 x 4 = 20
5 x 6 = 30
3 x 9 = 27
3 x 4 = 12
3 x 6 = 18
7 x 9 = 63
7 x 4 = 28
7 x 6 = 42
1 x 9 = 09
1 x 4 = 04
1 x 6 = 06
8 x 9 = 72
8 x 4 = 32
8 x 6 = 48
3 x 9 = 27
3 x 4 = 12
3 x 6 = 18
7 x 9 = 63
7 x 4 = 28
7 x 6 = 42
------------
591601757802
Überrascht? :-) Warum das aber so funktioniert und warum man die vielen
zweistelligen Zahlen genau so und nicht anders einrücken muss und wie
man daraus eine Routine für nen µC basteln kann, und dass der
Rechenaufwand für eine Multiplikation nach diesem Schema lächerlich
gering ist (nämlich nur proportional zur Stellenanzahl der großen Zahl)
und dass Du so z. B. auch problemlos das Produkt 945! x 946 berechnen
könntest, wenn nur die Dezimalziffern von 945! in einem Array
gespeichert vorliegen - das alles herauszufinden überlasse ich Dir :-)
Viel Spaß!
Gast schrieb: >>wofür eigentlich? > > Vielleicht einfach, um etwas dabei zu lernen? Um Erkenntnisse zu > gewinnen? Um ein Gefühl dafür zu bekommen, welche Aufgaben mit einem µC > von der Leistungsklasse leicht, schwer oder garnicht zu lösen ist? Um > sich am Erlebnis zu freuen, ein Problem erfolgreich gelöst zu haben? Man > kann es als Denksportaufgabe und geistige Herausforderung betrachten. Es > ist sicher ein besserer Zeitvertreib als nur zu fragen "wofür > eigentlich?". Versteh mich nicht falsch, ich mag es selber Dinge auszuprobieren. Allerdings halte ich die Fakultät für sehr langweilig dazu. Hier gibt es kaum etwas "Neues" für jemanden, der (schriftlich) Addieren und Multiplizieren kann. Zudem ist der Anwendungsbereich des "Spielzeuges" am Ende sehr mau. Man will dann doch auch mal sein entwickeltes Programm in einem entsprechenden Kontext laufen sehen. Wenn du an soetwas aber echt Interesse hast, empfehle ich dir den nächsten Schritt: Die Ackermann-Funktion :-)
>Ackermann-Funktion
(lach) Ich lehne dankend ab ;-) (Mir ist das ganze Zeug bekannt...)
Das mit dem Interesse kann man nicht so verallgemeinern, denke ich. Das
ist doch individuell höchst unterschiedlich. Der eine findet ein
Knight-Rider-Lauflicht oder die Propellerclock interessant, der andere
ein Programm, dass eintausend pi-Nachkommastellen ausrechnet (was
übrigens auch auf einem ATmega16 möglich wäre), oder selbst eine
Quicksort-Routine zu schreiben, obwohl das auch schon tausendmal gemacht
wurde. Auch das Schreiben von Programmen ohne am Ende vorzeigbar
blinkendes oder dröhnendes Ergebnis kann Spaß machen. Finde ich :-)
Leute, die nicht schriftlich multiplizieren und addieren können, scheint
es übrigens durchaus zu geben. Jeder, der behauptet hat, dass ein
ATmega16 mit der Aufgabe überfordert ist, gehört dazu.
@mark: http://www.delphipraxis.net/topic65632.html&postdays=0&postorder=asc&start=20 erklärt dir erstmal wie man die Fakultät mit der geringsten Komplexität berechnen kann. Dh. dieser Rechenweg basierend auf A.Schönhage ist der schnellste um die Fakultät zu großen Zahlen zu berechnen. Mit ihm kann man aber auch viel mehr sehr schnell berechnen, zb. eben die Anzahl der endenen Dezimalstellen zu einer belieben Zahlenbasis der Fakultät. Benutzt man modulare Arithmetik zb. zur Basis 10000 so kann man mit einfachen Integern die letzten Ziffern der Fakultät berechnen. Alle anderen kombinatorischen Funktionen wie Permutation/Kombination kann man damit sehr effizient berechen. Im Attachment mal meine Versuche mit solchen Berechnungen, allerdings auf PCs mit ordentlich Leistung da man ja rechnen möchte und nicht unbedingt die Herausforderung sucht sowas mit 4 Bit Mini-Low-Power-MCUs zu berechnen ;) Ist schon eine ziemlich verrückte Idee. Gruß Hagen
"sehr Effizient" Naja ich weiss ja nicht. Ich tendiere dazu von Effizienz zu reden, wenn es in polynomieller Zeit zur Eingabegröße berechenbar ist. Da aber bereits die Ziffernzahl der Ausgabe zur Ziffernzahl der Eingabegröße exponential steigt dürfte das hier nicht der Fall sein.
Das Problem ist wohl nur der Speicher. Mit 2 Feldern (altes/neues Ergebnis) in Binär ist es wohl leicht. Spassig wäre in "packed BCD" (ein Byte enthält 2 Ziffern) um die serielle Übertragung zu vereinfachen (Übertragung als ASCII durch BCD-Nibble +48). Richtig gut ist, wenn nur ein Feld benötigt wird. So ist es wirklich reizvoll wenn auch unnütz. Aber Sudoku ist auch unnütz und trotzdem beliebt ;) avr
>"sehr Effizient" >Naja ich weiss ja nicht. Ich tendiere dazu von Effizienz zu reden, wenn >es in polynomieller Zeit zur Eingabegröße berechenbar ist. >Da aber bereits die Ziffernzahl der Ausgabe zur Ziffernzahl der >Eingabegröße exponential steigt dürfte das hier nicht der Fall sein. Laber laber, es gibt zZ. kein besseres Verfahren und mehr kannst du bei Arnold Schönhage und Peter Borwein nachlesen. Davon abgesehen frage ich mich wie du von "exponentielles Wachstum der Eingabeziffernzahl zu Ausgabeziffernzahl" zu dem Schluß kommst das die verwendete Formel eine spezifische Komplexität hätte. Das eine hat mit dem anderen garnichts zu tun. Die Komplexität dieser Formel, basierend auf der Primfaktorzerlegung, ist O(n*(log(n)*log(log(n))^2) und besser gehts heutzutage nicht, rechne dir mal das aus ! Gruß Hagen
Ich behaupte auch nicht, dass es besser geht. Ich behaupte, dass es nicht effizient geht. Ich würde gern mal sehen, wie du mit p(n) Aufwand eine Ausgabe von x^n für alle n > N. n,N in setN Länge erzeugen kannst...
>Ich behaupte auch nicht, dass es besser geht. Ich behaupte, dass es >nicht effizient geht. ich verstehe dich schon richtig. Mein Problem ist das du "effzient" absolut betrachtest und nicht in Relation zu den Alternativen. >"sehr Effizient" >Naja ich weiss ja nicht. Ich tendiere dazu von Effizienz zu reden, wenn >es in polynomieller Zeit zur Eingabegröße berechenbar ist Du leitest also Effizienz absolut von der Eingangsgröße ab. Ich leite Effizienz von der Eingangsgröße in Relation zu den zur Alternative stehenden Verfahren ab. Warum halte ich das für sinnvoller ? Ganz einfach nach deiner Meinung kann man 1+1 sehr effizient berechnen und N! kann man nicht effizient berechen. Das problem dabei: Was hat die Berechnung von 1+1 mit N! zu tun ? Gruß Hagen
Fakultät ist langweilig. Die Harten rechnen das Ackermannsche Funktional auf dem 8-Bitter...
wozu das eigentlich? die dinger sind konstanten und alle die ein atmega in seinem leben berechnen könnte sind bekannt. mit den größeren zahlen hat ja ein 3ghz core2 schon seine probleme wenn man es mit mul/add durchrechnet. nur um rauszukriegen ob der µC das kann? klar kann der das, solange es in sein RAM passt - was die zahlen wohl eher im unteren bereich halten dürfte. oder du bastelst noch ein interface für ein externes RAM, aber dann ist der atmega nicht mehr viel schneller als ein besserer taschenrechner. in meinen augen ist das entweder eine nette programmier-idee wenn man zuviel zeit hat oder stromverschwendung.
Für ne Zahl mit 375 Dezimaltellen braucht man 156 Byte. Das ganze Programm paßt also dicke in nen ATtiny45 rein. Peter
klar passen die kleinen zahlen. interessant wirds ja erst bei den richtig großen.
Ben _ schrieb: > klar passen die kleinen zahlen. interessant wirds ja erst bei den > richtig großen. Na ja. Soooo interessant ist das auch wieder nicht. Nichts gegen BCD Arithmetik. Aber in der Praxis braucht man die eher selten. Wenn schon, dann ist das höchstens eine Übung im Umgang mit Arrays, wobei da der Wert allerdings zweifelhaft ist. Lerneffekt ist IMHO maximal, dass ein gewisses Verständnis entsteht wie Zahlensysteme eigentlich funktionieren und was wir tun, wenn wir mit Papier und Bleistift rechnen. Das geht aber auf dem PC genausogut. Da muss ich mir nicht die Tortur antun, das alles auf einem µC zu implementieren, bei dem ich keinen Unterbau habe, der mir die Routineaufgaben wie zb. Ausgabe, abnimmt.
Anbei meine Fingerübung. Es ist zwar speziell auf die Aufgabe angepasst, aber nicht optimiert. Also wer kan es besser (performanter & efizienter). Der Programmierwetbewerb ist eröffnet! @OT Versuch mal das Programm zuverstehen. Dabei kan man auch eine Menge lernen.
1 | #include <stdio.h> |
2 | #include <string.h> |
3 | |
4 | |
5 | #define LAENGE 400
|
6 | |
7 | void to_bcd(int fak,unsigned char *bcd) |
8 | {
|
9 | while(fak) |
10 | {
|
11 | *bcd++ = fak%10; |
12 | fak /= 10; |
13 | }
|
14 | }
|
15 | |
16 | void print_bcd(unsigned char *bcd) |
17 | {
|
18 | unsigned char *pBcd = bcd +(LAENGE-1); |
19 | |
20 | while(pBcd>=bcd && *pBcd ==0) |
21 | pBcd--; |
22 | |
23 | while(pBcd>=bcd) |
24 | {
|
25 | putchar('0' + *pBcd--); |
26 | }
|
27 | putchar('\n'); |
28 | }
|
29 | |
30 | |
31 | void bcd_mul(unsigned char *multiplikator,unsigned char *multiplikand ,unsigned char *produkt) |
32 | {
|
33 | unsigned char temp; |
34 | unsigned char *pro,*mul; |
35 | int i,j; |
36 | |
37 | memset(produkt,0,LAENGE); |
38 | for(i=0;i<3;i++) |
39 | {
|
40 | mul = multiplikand; |
41 | for(j=0;j<(LAENGE-1)-i;j++) |
42 | {
|
43 | pro = produkt+i+j; |
44 | temp = *multiplikator * *mul; |
45 | //printf("%i * %i = %i (%i)\n",*multiplikator,*mul,temp,i+j);
|
46 | do
|
47 | {
|
48 | temp += *pro; |
49 | *pro++ = temp%10; |
50 | temp /= 10; |
51 | } while(temp); |
52 | |
53 | mul++; |
54 | }
|
55 | multiplikator++; |
56 | }
|
57 | }
|
58 | |
59 | unsigned char mul[LAENGE]; |
60 | unsigned char tmp[LAENGE]; |
61 | unsigned char fakulaet[LAENGE]; |
62 | |
63 | int main(int argc, char* argv[]) |
64 | {
|
65 | int fak; |
66 | while(1) |
67 | {
|
68 | printf("Fakultaet (1-200 0=Abruch)\n"); |
69 | scanf("%i",&fak); |
70 | if(fak<1) break; |
71 | if(fak<=200) |
72 | {
|
73 | memset(tmp,0,sizeof(tmp)); |
74 | to_bcd(fak,tmp); |
75 | //print_bcd(tmp);
|
76 | while(--fak) |
77 | {
|
78 | //printf("---%i\n",fak);
|
79 | memset(mul,0,sizeof(mul)); |
80 | to_bcd(fak,mul); |
81 | //print_bcd(mul);
|
82 | bcd_mul(mul,tmp,fakulaet); |
83 | // print_bcd(fakulaet);
|
84 | memcpy(tmp,fakulaet,LAENGE); |
85 | }
|
86 | fputs(" = ", stdout ); |
87 | print_bcd(fakulaet); |
88 | }
|
89 | }
|
90 | return 0; |
91 | }
|
Wie ist denn die Laufzeit deines Programms, Volker?
Habe ich noch nicht gemessen. Läuft bislang auch nur auf dem PC.
So hier die Laufzeiten:
Profile: Function timing, sorted by time
Date: Fri Nov 27 14:55:20 2009
Program Statistics
------------------
Command line at 2009 Nov 27 14:55:
"C:\projects\fakultaet\Debug\fakultaet"
Total time: 6161,032 millisecond
Time outside of functions: 1,326 millisecond
Call depth: 2
Total functions: 4
Total hits: 401
Function coverage: 100,0%
Overhead Calculated 4
Overhead Average 4
Module Statistics for fakultaet.exe
-----------------------------------
Time in module: 6159,706 millisecond
Percent of time in module: 100,0%
Functions in module: 4
Hits in module: 401
Module function coverage: 100,0%
Func Func+Child Hit
Time % Time % Count Function
---------------------------------------------------------
6122,115 99,4 6159,706 100,0 1 _main (fakultaet.obj)
31,967 0,5 31,967 0,5 199 _bcd_mul (fakultaet.obj)
5,535 0,1 5,535 0,1 1 _print_bcd
(fakultaet.obj)
0,091 0,0 0,091 0,0 200 _to_bcd (fakultaet.obj)
Nict sehr aussagekräftig, weil da offenbar die scanf Zeit auch mit dabei ist. Mach doch eine Schleife von 1 bis 200 und lass die jeweilige Fakultät ausrechnen. Mittels clock misst die die Laufzeit für jede einzelne Zahl. Das ist viel interessanter, wie die Zeit wächst, wenn die Zahlen größer werden. Bei derartigen Laufzeitmessungen ist der Trend interessant, nach dem die Zeit größer wird, wenn die Argumente anwachsen.
Kleine Verbesserungsvorschläge: Die BCD-Mul, die du benötigst muss nicht über die vollständige reservierte Zahlenlänge laufen. In der n-ten Multiplikation ist die Anzahl der zu betrachtenden Stellen nach oben durch n * log_10(multiplikant) < n * 3 beschränkt. Spart dir für die ersten 130 Multiplikationen viel Aufwand. Durch den Übertrag in der do-while deiner Multiplikation kann es in deiner Implementierung zu Pufferüberläufen kommen (wenn das unsigned char ausgereizt wird) ist zwar ausserhalb der Anforderungen, sollte dann aber nur zu einem fehlerhaften Ergebnis aber zu keiner Korruption des Speichers führen.
Hier mal die Laufzeiten der Verschiedenen Fakultäten: Pentium4 2,4GHz (Debug) freq is 3579545 p 3 0.239 ms 4 0.357 ms 5 0.475 ms 6 0.593 ms 7 0.712 ms 8 0.831 ms 9 0.949 ms 10 1.068 ms 11 1.188 ms 12 1.345 ms 13 1.426 ms 14 1.546 ms 15 1.665 ms 16 1.834 ms 17 1.905 ms 18 2.026 ms 19 2.147 ms 20 2.265 ms 21 2.475 ms 22 2.509 ms 23 2.710 ms 24 2.753 ms 25 2.871 ms 26 2.995 ms 27 3.140 ms 28 3.314 ms 29 3.365 ms 30 3.486 ms 31 3.610 ms 32 3.757 ms 33 3.864 ms 34 3.987 ms 35 4.109 ms 36 4.310 ms 37 4.365 ms 38 4.491 ms 39 4.639 ms 40 4.755 ms 41 4.872 ms 42 5.001 ms 43 5.191 ms 44 5.254 ms 45 5.382 ms 46 5.537 ms 47 5.646 ms 48 5.929 ms 49 5.933 ms 50 6.026 ms 51 6.242 ms 52 6.292 ms 53 6.447 ms 54 6.575 ms 55 6.684 ms 56 6.850 ms 57 6.958 ms 58 7.127 ms 59 7.246 ms 60 7.529 ms 61 7.515 ms 62 7.648 ms 63 7.788 ms 64 7.982 ms 65 8.052 ms 66 8.246 ms 67 8.347 ms 68 8.759 ms 69 8.633 ms 70 8.754 ms 71 9.014 ms 72 9.012 ms 73 9.199 ms 74 9.300 ms 75 9.519 ms 76 10.397 ms 77 9.706 ms 78 10.167 ms 79 10.122 ms 80 10.159 ms 81 10.501 ms 82 10.450 ms 83 10.605 ms 84 11.325 ms 85 10.885 ms 86 11.027 ms 87 11.523 ms 88 13.114 ms 89 11.584 ms 90 11.726 ms 91 11.759 ms 92 11.914 ms 93 12.105 ms 94 12.234 ms 95 12.386 ms 96 13.344 ms 97 13.485 ms 98 13.127 ms 99 13.039 ms 100 13.203 ms 101 13.263 ms 102 13.443 ms 103 13.650 ms 104 13.851 ms 105 13.958 ms 106 14.074 ms 107 14.218 ms 108 14.555 ms 109 14.571 ms 110 14.670 ms 111 14.910 ms 112 15.047 ms 113 15.503 ms 114 15.375 ms 115 15.487 ms 116 15.809 ms 117 15.870 ms 118 16.202 ms 119 16.925 ms 120 16.327 ms 121 16.471 ms 122 16.651 ms 123 16.920 ms 124 17.073 ms 125 17.146 ms 126 17.271 ms 127 18.015 ms 128 17.641 ms 129 17.777 ms 130 17.923 ms 131 18.188 ms 132 22.747 ms 133 18.441 ms 134 18.618 ms 135 18.778 ms 136 19.145 ms 137 19.179 ms 138 19.314 ms 139 20.207 ms 140 20.051 ms 141 19.850 ms 142 20.065 ms 143 20.303 ms 144 21.228 ms 145 20.541 ms 146 20.687 ms 147 21.081 ms 148 21.157 ms 149 21.298 ms 150 21.484 ms 151 21.947 ms 152 21.904 ms 153 22.780 ms 154 22.519 ms 155 22.308 ms 156 22.682 ms 157 22.836 ms 158 23.184 ms 159 23.629 ms 160 23.294 ms 161 23.727 ms 162 25.501 ms 163 23.843 ms 164 24.257 ms 165 24.237 ms 166 24.521 ms 167 25.736 ms 168 24.807 ms 169 25.044 ms 170 25.196 ms 171 25.668 ms 172 25.634 ms 173 25.819 ms 174 26.365 ms 175 27.310 ms 176 26.425 ms 177 26.590 ms 178 27.104 ms 179 27.102 ms 180 27.156 ms 181 27.297 ms 182 27.960 ms 183 27.947 ms 184 28.318 ms 185 28.636 ms 186 28.403 ms 187 30.433 ms 188 28.999 ms 189 30.303 ms 190 31.001 ms 191 30.979 ms 192 29.936 ms 193 30.180 ms 194 30.712 ms 195 31.733 ms 196 30.873 ms 197 31.020 ms 198 31.182 ms 199 32.057 ms 200 31.715 ms
Jetzt, wo die Sau raus ist: Ich habe gestern auch mal so ein Programm zusammengestrickt, habe es aber nicht gleich veröffentlicht, da ich dachte, Paul möchte sich sicher erst selber ein paar Gedanken dazu machen ;-) Das Programm berechnet (ohne Benutzerinteraktion) nacheinander alle Fakultäten bis 200 und gibt sie auf dem Bildshirm aus. Dazu braucht es
1 | 33ms mit Ausgabe ins XTerm-Fenster |
2 | 700µs mit Ausgabe nach /dev/null |
3 | 175µs ohne Ausgabe (mit auskommentiertem print_bignum-Aufruf) |
Zur Messung der Zeiten habe ich den Inhalt von main 100- bzw. 100000- mal ausführen lassen. Der Rechner hat einen Core2 Duo T7500 mit 2,2GHz. Das Programm bräuchte auf einem ATtiny85 508B Flash und etwa 400B RAM. Ich hab's aber noch nicht damit getestet.
1 | #include <stdio.h> |
2 | #include <stdint.h> |
3 | #define MAXDIGITS 375
|
4 | |
5 | typedef struct { |
6 | uint16_t ndigits; |
7 | uint8_t digits[MAXDIGITS]; |
8 | } bignum_t; |
9 | |
10 | void mul(bignum_t *pn1, uint8_t n2) { |
11 | uint16_t nd = pn1->ndigits, i, prod; |
12 | uint8_t *pd = pn1->digits, carry=0; |
13 | |
14 | for(i=0; i<nd || carry && i<MAXDIGITS; i++) { |
15 | prod = (i<nd ? *pd * n2 : 0) + carry; |
16 | carry = prod / 10; |
17 | *pd++ = prod - 10 * carry; |
18 | }
|
19 | pn1->ndigits = i; |
20 | }
|
21 | |
22 | void print_bignum(bignum_t *pn) { |
23 | uint16_t i = pn->ndigits; |
24 | uint8_t *pd = pn->digits+i; |
25 | |
26 | while(i--) |
27 | putchar(*--pd + '0'); |
28 | putchar('\n'); |
29 | }
|
30 | |
31 | int main(void) { |
32 | bignum_t x = {1, {1}}; |
33 | uint8_t i; |
34 | |
35 | for(i=1; i<=200 ; i++) { |
36 | mul(&x, i); |
37 | print_bignum(&x); |
38 | }
|
39 | return 0; |
40 | }
|
Schau an, schon am nächsten Tag gibt es zwei fertige Proggis im Thread. Und just jene, die eben noch erklärt haben, wie uninteressant und langweilig diese Sache doch ist, sind die ersten, die Verbesserungsvorschläge zu den Programmen präsentieren. Leute, Leute... ;-)
Erm ... es ist uninteressant. Es gibt andere Gründe ausser Interesse dafür Verbesserungsvorschläge zu posten. Ich helfe meinen Kindern auch das zu lernen woran sie Interesse haben. Da mag ich es noch für so uninteressant oder zwecklos halten ... Nennt man anderen zu helfen.
Übrigens berechnet 200! der "TI-enspire CAS" im Bruchteil einer Sekunde. Gruß, Nick
Die Software aus obigem Link rechnet 1.000.000! in 800ms auf meinem PC aus. Diese Zahl hat 5.565.709 Dezimalstellen.
müdelächel Mein Quantenrechner braucht für 6.022E23! ne Handvoll Planckzeiten. Theoretisch zumindest :-)
Tja das ist der Unterschied zwischen Theorie und Praxis ;)
Ihr könntet das ganze jetzt noch rekursiv programmieren.
Rekursion sollte mann auf einem µC vermeiden, da hoher Stackbedarf.
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.