www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Fakultaet berechnen auf dem STK500mit AtMega16


Autor: Paul P. (cpn)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 :-)

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Ü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.

Autor: Lasse S. (cowz) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ich würde einfach eine LUT für die 200 Werte machen...

Martin

Autor: Tim Seidel (maxxie)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wofür eigentlich?

Ich kann mir gerade keine sinnvolle Aufgabenstellung vorstellen, bei der 
man entsprechend große Fakultäten braucht.

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> Selbst Matlab ...

Seit wann ist denn Matlab ein Maßstab?

http://www.wolframalpha.com/input/?i=200!

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;-)

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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?".

Autor: Udo R. S. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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. ;-)

Autor: Udo R. S. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klingt für mich eher nach einer Aufgabe für einen Azubi oder 
Anfangssemester der keine Lust auf selber programmieren hat.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Klingt für mich eher nach...

An so etwas Schlimmes wollen wir mal lieber nicht denken ;-)

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: Paul P. (cpn)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
-> 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

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hagen Re schrieb:
> Ja gibt es, sogar sehr effizient.

Link bitte?

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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ß!

Autor: Tim Seidel (maxxie)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 :-)

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: Hagen Re (hagen)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
@mark:

http://www.delphipraxis.net/topic65632.html&postda...

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

Autor: Tim Seidel (maxxie)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
"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.

Autor: avr (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>"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

Autor: Tim Seidel (maxxie)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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

Autor: doofi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Fakultät ist langweilig.
Die Harten rechnen das Ackermannsche Funktional auf dem 8-Bitter...

Autor: Ben ___ (burning_silicon)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Für ne Zahl mit 375 Dezimaltellen braucht man 156 Byte.
Das ganze Programm paßt also dicke in nen ATtiny45 rein.


Peter

Autor: Ben ___ (burning_silicon)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
klar passen die kleinen zahlen. interessant wirds ja erst bei den 
richtig großen.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
#include <stdio.h>
#include <string.h>


#define LAENGE 400

void to_bcd(int fak,unsigned char *bcd)
{
   while(fak)
   {
      *bcd++ = fak%10;
      fak /= 10;
   }
}

void print_bcd(unsigned char *bcd)
{
   unsigned char *pBcd = bcd +(LAENGE-1);

   while(pBcd>=bcd && *pBcd ==0)
      pBcd--;

   while(pBcd>=bcd)
   {
      putchar('0' + *pBcd--);
   }
   putchar('\n');
}


void bcd_mul(unsigned char *multiplikator,unsigned char *multiplikand ,unsigned char *produkt)
{
   unsigned char temp;
   unsigned char *pro,*mul;
   int i,j;

   memset(produkt,0,LAENGE);
   for(i=0;i<3;i++)
   {
      mul = multiplikand;
      for(j=0;j<(LAENGE-1)-i;j++)
      {
         pro = produkt+i+j;
         temp = *multiplikator * *mul;
//printf("%i * %i = %i  (%i)\n",*multiplikator,*mul,temp,i+j);
         do 
         {
            temp  += *pro;
            *pro++ = temp%10;
            temp /= 10;
         } while(temp);

         mul++;
      }
      multiplikator++;
   }
}

unsigned char mul[LAENGE];
unsigned char tmp[LAENGE];
unsigned char fakulaet[LAENGE];

int main(int argc, char* argv[])
{
   int fak;
   while(1)
   {
     printf("Fakultaet (1-200 0=Abruch)\n");
      scanf("%i",&fak);
      if(fak<1) break;
      if(fak<=200)
      {
         memset(tmp,0,sizeof(tmp));
         to_bcd(fak,tmp);
//print_bcd(tmp);
         while(--fak)
         {
//printf("---%i\n",fak);
            memset(mul,0,sizeof(mul));
            to_bcd(fak,mul);
//print_bcd(mul);
            bcd_mul(mul,tmp,fakulaet);
//            print_bcd(fakulaet);
            memcpy(tmp,fakulaet,LAENGE);
         }
         fputs(" = ", stdout );
         print_bcd(fakulaet);
      }
   }
  return 0;
}


Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie ist denn die Laufzeit deines Programms, Volker?

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Habe ich noch nicht gemessen. Läuft bislang auch nur auf dem PC.

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Tim Seidel (maxxie)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
   33ms  mit Ausgabe ins XTerm-Fenster
  700µs  mit Ausgabe nach /dev/null
  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.
#include <stdio.h>
#include <stdint.h>
#define MAXDIGITS 375

typedef struct {
  uint16_t ndigits;
  uint8_t digits[MAXDIGITS];
} bignum_t;

void mul(bignum_t *pn1, uint8_t n2) {
  uint16_t nd = pn1->ndigits, i, prod;
  uint8_t *pd = pn1->digits, carry=0;

  for(i=0; i<nd || carry && i<MAXDIGITS; i++) {
    prod = (i<nd ? *pd * n2 : 0) + carry;
    carry = prod / 10;
    *pd++ = prod - 10 * carry;
  }
  pn1->ndigits = i;
}

void print_bignum(bignum_t *pn) {
  uint16_t i = pn->ndigits;
  uint8_t *pd = pn->digits+i;

  while(i--)
    putchar(*--pd + '0');
  putchar('\n');
}

int main(void) {
  bignum_t x = {1, {1}};
  uint8_t i;

  for(i=1; i<=200 ; i++) {
    mul(&x, i);
    print_bignum(&x);
  }
  return 0;
}

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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... 
;-)

Autor: Tim Seidel (maxxie)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Nick Müller (muellernick)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Übrigens berechnet 200! der "TI-enspire CAS" im Bruchteil einer Sekunde.

Gruß,
Nick

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Software aus obigem Link rechnet 1.000.000! in 800ms auf meinem PC 
aus. Diese Zahl hat 5.565.709 Dezimalstellen.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
müdelächel Mein Quantenrechner braucht für 6.022E23! ne Handvoll 
Planckzeiten. Theoretisch zumindest :-)

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tja das ist der Unterschied zwischen Theorie und Praxis ;)

Autor: Altona (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ihr könntet das ganze jetzt noch rekursiv programmieren.

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Rekursion sollte mann auf einem µC vermeiden, da hoher Stackbedarf.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.