NXC / C Numerik: Pi auf tausende Stellen nach Spigot-Algorithmus

Modelle zum Nachbauen oder wo gibt es etwas interessantes oder Projekte?

Moderator: Moderatoren

Benutzeravatar
HaWe
Administrator
Administrator
Beiträge: 5395
Registriert: 11. Jan 2006 21:01
Wohnort: ein kleiner Planet in der Nähe von Beteigeuze

NXC / C Numerik: Pi auf tausende Stellen nach Spigot-Algorithmus

Beitragvon HaWe » 21. Mai 2014 22:36

hi,
hatte gerade die Idee, den Spigot-Algorithmus zur Berechnung von Pi mit mehreren hundert oder gar tausend Nachkommastellen (!!) auf den NXT zu übertragen.
Das Interessante: er berechnet jede Stelle singulär per Integer-Arithmetik, ohne jegliche Fließkommazahlen, und das mit fast beliebiger Genauigkeit (nur begrenzt durch den Rechenspeicher).

Hier im Beispiel berechnet er die ersten 255 Stellen (Anzahl der Dezimalstellen ist i.P. frei wählbar, 2000 Stellen habe ich auch schon berechnet, doch das braucht seine Zeit).

Da NXC leider zur Bildschirm-Ausgabe kein richtiges printf() mit Zeichenvorschub und Zeilen- und Seitenumbruch kennt, musste ich für die Bildschirmausgabe eine Eigenkreation verwenden (printfEx(), das das "richtige" ANSI-C printf() halbwegs simuliert):

Code: Alles auswählen

// program: PI_Spigot
// the PI number,
// calculated by the Spigot algorithm
// PL: NXC, enhanced firmware, BCC 3.3.8.11
// ported to NXC by Helmut Wunder
// v. 1.2


#define N 255 // the number of decimal digits (validated; customizable! )


int _cur_x_=0, _cur_y_=56;      // cursor home for NXC  = upper left = (0,56)
int _tab_width_=24;             // tab width by default = 24 = 4* 6-point letter

unsigned long _TEXTSTYLE_ = DRAW_OPT_NORMAL;   // text style by default

#define cls()             { ClearScreen();  _cur_x_=0; _cur_y_=56; }

#define gotoxy( x, y )    { _cur_x_=x; _cur_y_=y; }   // move cursor to position
#define curxy( x, y )     { _cur_x_=x; _cur_y_=y; }   // move cursor to (alias)
#define curx( x )         { _cur_x_=x; }              // move cursor to x-pos
#define cury( y )         { _cur_y_=y; }              // move cursor to y-pos
#define curhome()         { _cur_x_=0; _cur_y_=56; }  // move cursor home
#define settabwidth( t )  { _tab_width_ = t; }        // redefine tab width
#define settextstyle( t ) { _TEXTSTYLE_ = t; }        // redefine text style


int _page_=1;                   // current screen page

int FINISHED=INT_MAX;           // last screen page written
int d;                          // digits written

#define endoflastline     ((_cur_x_ >=95)&&(_cur_y_ <=16))


inline string strsplit(string &src, string mark) {
  string s="";
  int p=-1, l;
  p=Pos(mark, src);
  if (p>=0) {
    l=strlen(mark);
    s= SubStr(src, 0, p);
    src=SubStr(src, p+l, strlen(src)-p);
  }
  return s;
}


string strexch(string src, string ex, string ch) {
  string s;
  s=strsplit(src,ex);
  return (StrCat(s,ch,src));
}


// printfxy()
// featuring "\i" for writing inverted
//******************************************************************************
#define printfxy( x_, y_, f_, v_) {       \
  _cur_y_=y_;   string s1_, s2_, sv_;     \
  s2_=f_;                                 \
  if (Pos("\i",s2_)>=0) {                 \
    _TEXTSTYLE_= DRAW_OPT_INVERT;         \
    s2_=strexch(s2_,"\i","");             \
  }                                       \
  int len=0;                              \
  if (Pos("%",s2_)==-1)  { sv_=s2_; }     \
  else { sv_ = FormatVal(s2_, v_);  }     \
  TextOut(x_, y_, sv_, _TEXTSTYLE_);      \
  len=strlen(sv_);                        \
  _cur_x_=x_+6*(len);                     \
  _TEXTSTYLE_= DRAW_OPT_NORMAL;           \
}


// printfEx redefined as printf()
// featuring \n, \t, and "\i" for writing inverted
//******************************************************************************
#define printfEx(_fmt, _val) {            \
  int _x=_cur_x_; int _y=_cur_y_;         \
  string _sf, _s;                         \
  _sf=_fmt;                               \
  while (Pos("\n",_sf)>=0) {              \
    _s=strsplit(_sf,"\n");                \
    while (Pos("\t",_s)>=0) {             \
      _x=(1+_x/_tab_width_)*_tab_width_;  \
      _s=strexch(_s, "\t", ""); }         \
    printfxy( _x, _y, _s, _val);          \
    _x=0;  _y-=8;                         \
  }                                       \
  while (Pos("\t",_sf)>=0) {              \
      _x=(1+_x/_tab_width_)*_tab_width_;  \
      _sf=strexch(_sf, "\t", ""); }       \
  if(_x>=94){_x=0;_y-=8;}                 \
  printfxy( _x, _y, _sf, _val);           \
}



inline bool btnhit(){
/******************************************************************************/
   return ( ButtonPressed(BTN1, false) || ButtonPressed(BTN2, false)
         || ButtonPressed(BTN3, false) || ButtonPressed(BTN4, false));
}


void statusln(int &page) {
   if (page<INT_MAX) {printfxy(0,0,"page%2d-pressBtn  ", page++);}
   else if (page>=INT_MAX)  {
     printfxy(0,8,"READY!%3d digits  ", d);
     printfxy(0,0,"page%2d >Btn:quit ", _page_);
   }
   while (!btnhit()); while (btnhit());
   cls();
   printfxy(0,0,"calc. PI, page%2d", page);  curhome();

}


task main() {

  int len, nines, predigit;
  int A[];

  SetSleepTimeout(0);

  cls();
  printfxy(0,0,"calc. PI, page%2d", _page_);  curhome();

  len = floor(10 * N/3) + 1 ;
  ArrayInit(A,2,len);          // for(int i = 0; i < len; ++i) { A[i] = 2;}

  nines = predigit = 0;

  for(int j = 1; j < N + 1; ++j) {
    int q = 0;

    for(int i = len; i > 0; --i) {
      int x  = 10 * A[i-1] + q*i;
      A[i-1] = x % (2*i - 1);
      q = x / (2*i - 1);
    }

    A[0] = q%10;
    q    = q/10;

    if (9 == q) {
      ++nines;
    }
    else if (10 == q) {
      printfEx("%d", predigit + 1); ++d;
      if (endoflastline)  {statusln(_page_); }

      for (int k = 0; k < nines; ++k) {
        printfEx("%d", 0); ++d;
        if(endoflastline)  {statusln(_page_); }
      }

      nines = predigit = 0;

    }

    else {

      if((d==0)&&(predigit==0)) {printfEx(" ", "");}  // delete leading zero
      else  {printfEx("%d", predigit); ++d;}

      if(endoflastline)  {statusln(_page_); }
      predigit = q;

      if (0 != nines) {
        for (int k = 0; k < nines; ++k) {
          printfEx("%d", 9); ++d;
          if(endoflastline)  {statusln(_page_); }
        }

        nines = 0;
      }
    }
  }

  printfEx("%d", predigit); d++;
  statusln(FINISHED);
}


Über die Theorie:
http://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&ved=0CEAQFjAC&url=http%3A%2F%2Fwww.mathpropress.com%2Fstan%2Fbibliography%2Fspigot.pdf&ei=-v99U_rCN8GTywPv5IGQCw&usg=AFQjCNEnsqr0GLHLQLWOD1AufBAmF93_8w

Benutzeravatar
HaWe
Administrator
Administrator
Beiträge: 5395
Registriert: 11. Jan 2006 21:01
Wohnort: ein kleiner Planet in der Nähe von Beteigeuze

Re: NXC / C Numerik: Pi auf tausende Stellen nach Spigot-Algorithmus

Beitragvon HaWe » 25. Mär 2015 10:23

zum Vergleich: selber Code in C, optimiert für Arduino, serielle Terminal-Ausgabe (>2000 Stellen, Ausgabe normiert auf je 50 Zeichen pro Zeile),
Laufzeit: etwa 1 sec:

Code: Alles auswählen

/*
program Spigot PI
ver 001
*/


//=====================================================================================
void setup() {
   Serial.begin(9600);
   Serial.println();

   Serial.println("#: Serial() started");
}
//=====================================================================================


//=====================================================================================
void loop() {

  #define N 2049       //  <<<<<<<<<<<<<<<<<<<<<< number of decimals, customize !
 
  int16_t  d=0;
  int16_t  len = floor(10 * N/3) + 1;
  int16_t  A[len];

  for(int16_t  i = 0; i < len; ++i) {
    A[i] = 2;
  }

  int16_t   nines    = 0;
  int16_t   predigit = 0;
 
  Serial.println();
  Serial.print("Calculating PI by "); Serial.print(N); Serial.println(" decimals");
  Serial.println();

  for(int16_t  j = 1; j < N + 1; ++j) {       
    int q = 0;
   
   

    for(int16_t  i = len; i > 0; --i) {
      int x  = 10 * A[i-1] + q*i;
      A[i-1] = x % (2*i - 1);
      q = x / (2*i - 1);
    }

    A[0] = q%10;
    q    = q/10;

    if (9 == q) {
      ++nines;
    }
    else if (10 == q) {
      Serial.print(predigit + 1);
      ++d;
      if( d%50==0)  { Serial.println(); }
     
      for (int16_t  k = 0; k < nines; ++k) {
        Serial.print(0);
        ++d;
        if( d%50==0)  { Serial.println(); }
      }
      predigit, nines = 0;
    }
   
    else {
      if(d==1) { Serial.print("."); ++d; }
     
      if((d==0)&&(predigit==0)) {
        Serial.print("");          // delete leading zero
       
      }
      else  {
        Serial.print(predigit);
        ++d;
        if( d%50==0)  { Serial.println(); }
      }
     
      predigit = q;

      if (0 != nines) {   
        for (int16_t  k = 0; k < nines; ++k) {
          Serial.print(9);
          ++d;
          if( d%50==0)  { Serial.println(); }
        }

        nines = 0;
      }
    }
     
  }
  Serial.print(predigit);
 
  Serial.println();
  Serial.println();
  Serial.print(d);
  Serial.print(" decimals written !");
 

 
  while(true);

}
Gruß,
HaWe
±·≠≈²³αβγδε∂ζλμνπξφωΔΦ≡ΠΣΨΩ∫√∀∃∈∉∧∨¬⊂⊄∩∪∅∞®
NXT NXC SCHACHROBOTER: https://www.youtube.com/watch?v=Cv-yzuebC7E


Zurück zu „Projekte, Showcase, Bauanleitungen“

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 25 Gäste

Lego Mindstorms EV3, NXT und RCX Forum : Haftungsauschluss