C++ , Berechnung Fakultät mit BCD-Charakter-Arrays

[LeDay (Gast)]

Guten Abend,

ich möchte ein Programm für einen Atmega Mikrocontroller schreiben, mit 
dem man große Fakultäten berechnen kann.
Da ein jener Mikrocontroller nicht über eine riesige Menge an 
Speicherplatz verfügt, möchte ich nicht wie bei dem aktuellen Stand 
meines Programms pro Zahl ein Charakter-Array-Element verwenden,
sondern möchte in jedes Charakter-Array-Element zwei BCD-codierte Zahl 
abspeichern.
Ich verwende ein großes Array, um das Ergebnis jeder Multiplikation 
darin abzuspeichern und anschließend für die weitere Berechnung zu 
verwenden.
Das Element 0 des Arrays ist meine niederwertigste Zahl und die Zahl vor 
meinem terminierenden '0xFF' ist die höchstwertigste Zahl.

Mir fehlt nun leider der richtige Denkanstoß, wie ich korrekt die obere 
Hälfte und die untere Hälfte eines 8-Bit-Charakter anspreche.
Ich überlegte mir dies mit bitweiser Verundung/Veroderung und mit 
Bitschiebeoperationen.
Dies habe ich dann versucht und bin leider gescheitert.
Gibt es eine einfachere Möglichkeit das mit den BCD-Zahlen zu 
realisieren?
Ich brauche nur einen Denkanstoß bzw. ein kleines Beispiel.
Vielleicht könnt ihr mich auch auf uneffektive Stellen in meinem Code 
hinweisen.

Anbei mein Programm, dass ich für den Ablauf am PC etwas abgeändert 
habe(Ausgabe) (lauffähig für C++ Compiler)

Mit freundlichen Grüßen
LeDay

#include <iostream>
using namespace std;
#define SIZEUCHAR 500000 
#define BIN_STR_TERM 0xFF

long funct(unsigned char* erg, unsigned long* mult)
{
  unsigned long k = 0, l = 0;
  unsigned long temperg = 0, tempmult = 0;
  while (erg[k] != BIN_STR_TERM)
  {
    tempmult = *mult;
    l = 1;
    while (tempmult)
    {
      temperg = temperg + erg[k] * (tempmult % 10)*l;
      tempmult = tempmult / 10;
      l = l * 10;
    }
    erg[k] = temperg % 10;
    temperg = temperg / 10;
    k++;
  }
  while (temperg)
  {
    erg[k] = temperg % 10;
    temperg = temperg / 10;
    k++;
  }
  erg[k] = BIN_STR_TERM;
  return (k);

}
int main()
{
  unsigned long StelleEndeZahl = 0;
  unsigned long zaehl = 0;
  while (1)
  {
    long Eingabe = -1;
    while ((Eingabe < 0) || (Eingabe >= 100000))
    {
      cout << "Geben Sie eine positive Ganzzahl zur Berechnung ihrer Fakultaet an: ";
      cin >> Eingabe;
    }
    unsigned char Ergebnis[SIZEUCHAR] = { 1,BIN_STR_TERM };
    if (Eingabe == 0)
      cout << 1;
    else {
      for (zaehl = 1; zaehl <= Eingabe; zaehl++)
      {
        StelleEndeZahl = funct(Ergebnis, &zaehl);
      }
      while (StelleEndeZahl != 0)
      {
        StelleEndeZahl--;
        cout << (char)(Ergebnis[StelleEndeZahl] + 48); // +48 um als ASCII-Zeichen auszugeben
      }
    }
    cout << endl;
  }
}

[guest (Gast)]

LeDay schrieb:
> Ich überlegte mir dies mit bitweiser Verundung/Veroderung und mit
> Bitschiebeoperationen.
> Dies habe ich dann versucht und bin leider gescheitert.

Wo ist das Problem?

uint8_t bla;
bla & 0x0f;  // lower nibble
bla >> 4;    // upper nibble

[S. R. (svenska)]

LeDay schrieb:
> Da ein jener Mikrocontroller nicht über eine riesige Menge an
> Speicherplatz verfügt, möchte ich nicht wie bei dem aktuellen Stand
> meines Programms pro Zahl ein Charakter-Array-Element verwenden,
> sondern möchte in jedes Charakter-Array-Element zwei BCD-codierte Zahl
> abspeichern.

Wenn du einen Integer in einem Byte speicherst, dann kannst du in 8 Bits 
die Werte von 0 bis 255 speichern (also 8 Bit an Information).

Wenn du stattdessen eine gepackte BCD-Zahl in einem Byte speicherst, 
dann kannst du in 8 Bits die Werte von 0 bis 99 speichern (also 6.63 Bit 
an Information).

Also sind 8 Bit-Integer ungefähr 20% speichereffizienter als 8 Bit 
packed BCD. Dazu kommt noch, dass BCD-Arithmetik vom AVR nicht direkt 
unterstützt wird, du also zusätzlich Rechenzeit und Flashspeicher 
brauchst, um damit zu arbeiten.

[tictactoe (Gast)]

Ich würde außerdem nicht BCD verwenden, weil das fürs Rechnen echt 
Scheibenkleister ist. Besser ist es, in einem Byte ganz normal mit den 
Werten 0 bis 99 zu rechnen. Verschenkt zwar ein Bit, aber ist noch 
relativ bequem zum Umwandeln in Dezimaldarstellung.

Alternativen wären noch uint16_t mit 0 bis 9999 (kein echter Gewinn). 
Oder, wenn man sowieso gaaaanz große Zahlen arbeiten will, uint32_t mit 
0 bis 1e9-1 da hat man gleich eine ganze Dezimalstelle mehr als mit zwei 
uint16_t.

[LeDay (Gast)]

@tictactoe , Vielen Dank für die Idee einfach die Zahlen 0-99 in einem 
char-Element zu verwenden.
Ich habe das jetzt so umsetzen können. Es führte auch zu einer deutlich 
gesteigerten Geschwindigkeit.