Umrechnen von sehr grossen Zahlen in ein anderes Zahlensystem

Ianamus

@all & c++.de:
Hallo zusammen!

Ich übe für mich privat ein wenig C++ und bin auf ein mir noch nicht lösbares Problem gestossen. Meine Kenntnisse in C++ sind Anfängerhaft, aber das Programmieren macht mir trotzdem Spass...

Zum Problem:
Ich will eine Klasse schreiben, die grosse ganze Zahlen repräsentieren kann. Ein Element ist ein unsigned long - Array. Ein weiters ist ein Integer. Der Betrag des Integer gibt an wieviele Elemente der Array hat. Ist der Integer negativ ist auch die Zahl negativ. Ist der Integer positiv ist die Zahl >= 0 . Die Methoden sollen beinhalten: Konstruktoren um das Objekt mit int, long, short, unsigned int, unsigned long, unsigned short, string und c-string initialisieren zu können. Kopierkonstruktor. Eine Funktion, die die Zahl als string oder c-string zurückgeben kann und Operatorüberladungen, so dass ich mit diesem Objekt wie üblich rechnen kann. D.h. ich will das Objekt wie ein int oder long nutzen können. a = (b + c + 123) * q; usw.

Zunächst wollte ich die Zahl so abspeichern, dass sie quasi in einem Zahlensystem der Basis 10^19 dargestellt wird, dass heisst in einjedem Array-Element kommt eine Zahl zwischen 0 und (10^19 - 1) zu liegen. Der Vorteil ist, dass es einfach ist die Zahl als string ein- bzw. auszugeben. In einem anderen Forum riet mir ein kluger Typ, dass ich doch die Zahl zur Basis 2^64 abspeichern soll. Das macht die Sache mit den Operatoren +/- // einfach, was mir auch einleuchtet, obwohl ich es noch nicht versucht habe zu implementiern. Das sei wichtig, weil diese Arbeitsschritte häufig vorkommen und ich ja will, dass das Rechnen mit meinen Zahlen schnell geht. Um die Ein- und Ausgabe sollte ich mich später kümmern. Aber wenn ich das mit der Ein- und Ausgabe nicht fehlerlos hinbringe, bringt es nichts all die Operatoren usw. zu implementieren.
Wenn ich jetzt einen string entgegennehme und die darin enthaltene Zahl in ein Zahlensystem zur Basis 10^19 abspeichere, ist das natürlich kein Problem. Und es ist eigentlich auch kein Problem diese Zahl jetzt in ein Zahlensystem zur Basis 2^64 umzuformen, sofern die Zahl hinreichend klein ist. Denn es gilt:
(2⁶⁴⁾n = (10¹⁹⁾m
2^(64n) = 10^(19m) |lg
64n * lg2 = 19m
(64lg2)/19 = m/n
Daraus folgt, dass bei Dezimalzahlen von etwa 150*19 Stellen aufwärts die binäre (2^64) merklich mehr Stellen benötigt, d.h. Array-Elemente, als die dezimale Zahl. Und mein Interger hat einen Wertebereich von 0 bis (2^31-1) im Gegensatz zu den "wenigen" 150. Jetzt habe ich das Gefühl,dass ich das nur mit einem Algorithmus lösen kann, der eine rekursiven Funktion verwendet. Das drängt mich aber wiederum zu der Vermutung, dass das nur dazu führt, dass die Funktion sich ev. eine Million mal auf dem Stack ablegt. Bei hinreichend grossen Zahlen würde dann die Initialisierung wahrscheinlich länger dauern als mein Leben. Vielleicht sogar länger als das Leben von Gott oder dem Universum - wer weiss.

Hat jemand eine Lösung? Oder weiss jemand, dass das Problem unlösbar ist, jedenfalls noch in diesem Leben. Hat ev. ein Mathematiker einen Algorithmus zur Hand der das im Handumdrehen schafft und zwar so, dass es auch einer versteht, der nicht zweifacher Nobelpreisträger ist.

Ich danke im Voraus für jede Bemerkung. Kritik erwünscht.

Ich grüsse euch herzlichtst!

Ianamus, der Newcomer

SG1

Was genau ist jetzt eigentlich Deine Frage? Wie Du die "binären" Zahlen an Ende ausgeben kannst? Du wirst doch sicher auch eine Division implementieren. Und dann halt immer durch 10 teilen und stellenweise ausgeben. Ja, das ist langsam - aber Ausgabe ist ja eh langsam und nicht performancekritisch.

Deine ganzen Rechnungen hab ich ehrlich gesagt nicht verstanden. Wieso sollte eine Darstellung, bei der die einzelnen Ziffern mehr unterschiedliche Werte annehmen können, MEHR Ziffern zur Darstellung einer Zahl benötigen???

Michael E.

Ianamus schrieb:

(64lg2)/19 = m/n
Daraus folgt, dass bei Dezimalzahlen von etwa 15019 Stellen aufwärts die binäre (2^64) merklich mehr Stellen benötigt, d.h. Array-Elemente, als die dezimale Zahl.

Wieso das denn? Da 64lg(2)/19 etwas größer als 1 ist, brauchst du im 10^19-System sogar ein paar Ziffern mehr als im 2^64-System.

Und mein Interger hat einen Wertebereich von 0 bis (2^31-1) im Gegensatz zu den "wenigen" 150.

Versteh ich nicht. Sollte das nicht 2^64 - 1 und 10^19 -1 heißen?

Jetzt habe ich das Gefühl,dass ich das nur mit einem Algorithmus lösen kann, der eine rekursiven Funktion verwendet. Das drängt mich aber wiederum zu der Vermutung, dass das nur dazu führt, dass die Funktion sich ev. eine Million mal auf dem Stack ablegt. Bei hinreichend grossen Zahlen würde dann die Initialisierung wahrscheinlich länger dauern als mein Leben. Vielleicht sogar länger als das Leben von Gott oder dem Universum - wer weiss.

Nene, das wird für hinreichend viele Stellen gut gehen. Zu große Zahlen kannst du eh nicht behandeln. Irgendwann ist immer Schluss.

Ianamus

Hallo und danke für deine schnelle Antwort!

Also, meine Frage ist: "Wie könnte ein Algorithmus aussehen, der mir z.B. eine 2000-stellige Zahl zur Basis 2^64 in eine Zahl zur Basis 10^19 umrechen kann?"

Diese Zahl hätte, nach meinen Berechnungen, kann natürlich falsch sein, im Zahlensystem zur Basis 10^19 etwa 2028 Stellen. Ich weiss nicht wie ich einen Algorithmus schreibe, der mit dieser Diskrepanz umgehen kann. Eine 50-stellige Zahl im einem Zahlensytem zur Basis 2^64 hat immer auch 50 oder 51 Stellen in einem Zahlensystem zur Basis 10^19.

Ich hoffe du verstehst jetzt was ich meine.

Gruss Ianamus

SG1

Einfach wiederholt durch 10^19 teilen - die jeweiligen Reste sind Deine Ziffern. Aber wieso willst Du sowas umrechnen? Entweder Du nimmst 2^64 als Basis, oder 10^19 - aber eben nur eins von beiden.

Ianamus

Auch dir danke ich für die schnelle Antwort!

"Wieso das denn? Da 64lg(2)/19 etwas größer als 1 ist, brauchst du im 10^19-System sogar ein paar Ziffern mehr als im 2^64-System.
Zitat:
Und mein Interger hat einen Wertebereich von 0 bis (2^31-1) im Gegensatz zu den "wenigen" 150.

Versteh ich nicht. Sollte das nicht 2^64 - 1 und 10^19 -1 heißen? "

1. Ja du hast recht es ist umgekehrt natürlich.

2. Mit dem Integer meine ich die Zahl, die die Anzahl Elemente des unsigned long angibt. Von (2^31-1) bis -(2^31). Das macht 2^31 mal ein long. Ein long sind bei mir 8 Byte = 64 Bit.

"Nene, das wird für hinreichend viele Stellen gut gehen. Zu große Zahlen kannst du eh nicht behandeln. Irgendwann ist immer Schluss."

Der kluge Typ erzählte mir vom "Karatsuba-Algorithmus" um das Multiplizieren zu beschleunigen bzw. effizienter zu gestalten. Vielleicht gibt es ja auch Algorithmen um mit ECHT grossen Zahlen zu rechnen?

Gruss Ianamus

P.S. Wie tue ich hier zitieren?

Ianamus

@SG1

"Einfach wiederholt durch 10^19 teilen - die jeweiligen Reste sind Deine Ziffern."

Das verstehe ich jetzt nicht. Was durch 10^19 teilen?

SG1

Ianamus schrieb:

Der kluge Typ erzählte mir vom "Karatsuba-Algorithmus" um das Multiplizieren zu beschleunigen bzw. effizienter zu gestalten. Vielleicht gibt es ja auch Algorithmen um mit ECHT grossen Zahlen zu rechnen?

http://en.wikipedia.org/wiki/Karatsuba_algorithm verlinkt auf 2 weitere Algorithmen.

P.S. Wie tue ich hier zitieren?

Rechts oben beim zu zitierenden Beitrag.

SG1

Ianamus schrieb:

@SG1

"Einfach wiederholt durch 10^19 teilen - die jeweiligen Reste sind Deine Ziffern."

Das verstehe ich jetzt nicht. Was durch 10^19 teilen?

Die Zahl, die Du von der Basis 2^64 in die Basis 10^19 umrechnen willst - wovon ich immernoch nicht verstehe, wozu das gut sein soll.

Michael E.

Ianamus schrieb:

2. Mit dem Integer meine ich die Zahl, die die Anzahl Elemente des unsigned long angibt. Von (2^31-1) bis -(2^31). Das macht 2^31 mal ein long. Ein long sind bei mir 8 Byte = 64 Bit.

Und wo kommt die 150 her?

Der kluge Typ erzählte mir vom "Karatsuba-Algorithmus" um das Multiplizieren zu beschleunigen bzw. effizienter zu gestalten. Vielleicht gibt es ja auch Algorithmen um mit ECHT grossen Zahlen zu rechnen?

Was denn rechnen? Multiplizieren? Im Dezimalsystem ausgeben? Ich weiß nicht so recht, wo dein Problem ist.

P.S. Wie tue ich hier zitieren?

Im Beitrag, den du zitieren möchtest, gibts rechts oben nen "Zitieren"-Link. Ansonsten im Eingabefenster [ quote="ursprünglicher Autor" ]Das hier hat ein anderer geschrieben[ /quote ] (ohne die Leerzeichen bei den Klammern) schreiben.

Ianamus

SG1 schrieb:

Ianamus schrieb:

@SG1

"Einfach wiederholt durch 10^19 teilen - die jeweiligen Reste sind Deine Ziffern."

Das verstehe ich jetzt nicht. Was durch 10^19 teilen?

Die Zahl, die Du von der Basis 2^64 in die Basis 10^19 umrechnen willst - wovon ich immernoch nicht verstehe, wozu das gut sein soll.

Angenommen im long-Element sind alles Einsen, d.h. es ist der Wert (2^64 - 1) darin gespeichert. Wenn ich jetzt durch 10^19 ist der Rest gleich (2^64 - 1) - 10^19. In welches Array-Element für die dezimal-Form speichere ich jetzt das?

Der Grund für die Umformung ist, dass ev. das Rechnen mit der Basis 2^64 sehr viel effizienter zu implementieren ist als zur Basis 10^19.

Ianamus

Michael E. schrieb:

Ianamus schrieb:

2. Mit dem Integer meine ich die Zahl, die die Anzahl Elemente des unsigned long angibt. Von (2^31-1) bis -(2^31). Das macht 2^31 mal ein long. Ein long sind bei mir 8 Byte = 64 Bit.

Und wo kommt die 150 her?

Der kluge Typ erzählte mir vom "Karatsuba-Algorithmus" um das Multiplizieren zu beschleunigen bzw. effizienter zu gestalten. Vielleicht gibt es ja auch Algorithmen um mit ECHT grossen Zahlen zu rechnen?

Was denn rechnen? Multiplizieren? Im Dezimalsystem ausgeben? Ich weiß nicht so recht, wo dein Problem ist.

P.S. Wie tue ich hier zitieren?

Im Beitrag, den du zitieren möchtest, gibts rechts oben nen "Zitieren"-Link. Ansonsten im Eingabefenster [ quote="ursprünglicher Autor" ]Das hier hat ein anderer geschrieben[ /quote ] (ohne die Leerzeichen bei den Klammern) schreiben.

Die 150 kommt so zustande: (Sorry)

Wenn gilt:
64lg(2)/19 = m/n
wann ist
n * 64lg(2)/19 > n + 2 (z.B. - wann braucht m 2 Stellen mehr)
...
n > 2/(64*lg(2)/19 - 1)

Das Rechnen betrifft dann nur das Überlanden der Operatoren, das eher zu implementieren sein wird. Aber das von string in eine Zahl zur Basis 10^19 (einfach) dann in eine Zahl zur Basis 2^64 (schwer). Jetzt kann damit gerechnet werden (einfach und effizient). Dann wieder in eine Zahl zur Basis 10^19 (schwer). Und schliesslich Ausgaben (einfach).

Sorry wenn ich mich schlecht ausdrücke. Ich gib mein bestes...

Ianamus

Also ich sag mal im Voraus Danke, dass ihr euch meiner angenommen habt und Gute Nacht!

Ich hätte auch ein wenig Code, der aber eigentlich nicht für die Öffentlichkeit gedacht war und desswegen vielleicht schlecht zu verstehen ist.

void bigi::o_bigi()
{
   cout << "AKG: " << AKG << endl;

   struct D_Block_s //Dezimal-Block-Struktur
   {
      unsigned long Deka;
      D_Block_s *naechster_Block;
   };

   D_Block_s *DBK = new D_Block_s;
   D_Block_s *Schieber = DBK;
   Schieber->naechster_Block = 0;
   Schieber->Deka = 0;

   short max_Stellen = log10((unsigned long)(-1));
   unsigned long Basis = pow(10, max_Stellen);
   unsigned long vorheriges_MEMO = 0;
   unsigned long naechstes_MEMO = 0;

   for(int i = 0; i < (AKG < 0 ? -AKG : AKG); ++i)
   {
      vorheriges_MEMO = Schieber->Deka;
      Schieber->Deka = BK[i];

      naechstes_MEMO = Schieber->Deka;
      naechstes_MEMO /= Basis;
      naechstes_MEMO *= Basis;
      Schieber->Deka -= naechstes_MEMO;
      naechstes_MEMO /= Basis;

      Schieber->Deka += vorheriges_MEMO;
      vorheriges_MEMO = Schieber->Deka;
      vorheriges_MEMO /= Basis;
      vorheriges_MEMO *= Basis;
      Schieber->Deka -= vorheriges_MEMO;
      vorheriges_MEMO /= Basis;

      naechstes_MEMO += vorheriges_MEMO;
      Schieber = new D_Block_s;
      Schieber->naechster_Block = DBK;
      DBK = Schieber;
      Schieber->Deka = naechstes_MEMO;
   }

   if(DBK->Deka == 0)
   {
      Schieber = Schieber->naechster_Block;
      delete DBK;
      DBK = Schieber;
   }

   while(Schieber)
   {
      cout << Schieber->Deka;
      Schieber = Schieber->naechster_Block;
      delete DBK;
      DBK = Schieber;
   }
   cout << endl;
}

Diese Funktion soll die Zahl im Terminal ausgeben. bigi ist die Klasse und steht für Big Integer. AKG ist die Anzahl Elemente des long-Arrays, also die Anzahl Ziffern im Zahlensystem zur Basis 2^64; steht für Anzahl Kettenglieder und ist der erwähnte Integer. BK steht für Blockkette und ist der long-Array. DBK steht für Dezimal-Blockkette und ist eine verkette Liste. Diese Funktion funktioniert "eigentlich" für "kleine" Zahlen, aber eben nicht für beliebig grosse.

Also, schlaft gut und schöne Träume von Problemen wie diesen :p

SG1

Ianamus schrieb:

Angenommen im long-Element sind alles Einsen, d.h. es ist der Wert (2^64 - 1) darin gespeichert.

Du sollst nicht die einzelnen Ziffern, Du sollst die Zahl als ganzes dividieren. Die Umrechnung von einem Zahlensystem ins andere ist übrigens Schulwissen. Keine Ahnung, welche Klasse - aber definitiv nicht Oberstufe.

Der Grund für die Umformung ist, dass ev. das Rechnen mit der Basis 2^64 sehr viel effizienter zu implementieren ist als zur Basis 10^19.

Dann rechne doch auf Basis 2^64. Das erklärt nicht, warum Du zwischendrin umrechnen willst. Wenn das nur für Ein-/Ausgabe ist, dann würde ich zur Basis 10 (und nicht 10^19) umrechnen - aber das habe ich Dir ja bereits in meiner ersten Antwort empfohlen.

Ianamus

Guten Morgen!

SG1 schrieb:

Ianamus schrieb:

Angenommen im long-Element sind alles Einsen, d.h. es ist der Wert (2^64 - 1) darin gespeichert.

Du sollst nicht die einzelnen Ziffern,

Sage ich auch nicht.

SG1 schrieb:

Du sollst die Zahl als ganzes dividieren.

Und darauf war meine Frage: "Wohin mit dem Rest?".

SG1 schrieb:

Die Umrechnung von einem Zahlensystem ins andere ist übrigens Schulwissen. Keine Ahnung, welche Klasse - aber definitiv nicht Oberstufe.

Ok. Nehmen wir mal an, dass ich vor lauter Bäumen den Wald nicht sehe...

Dann rechne mir doch mal im Computer aus, wieviel Stellen hat die Zahl
18446744070000000123 * (2⁶⁴⁾14378
im Dezimalsystem (Basis 10). Und wieviel Stellen hat die Zahl im Zahlensystem zur Basis 10^19 und, vorausgesetzt du weisst dass die Zahl im Zahlensystem zur Basis 10^19 z.B. m ist, wie lautet die Ziffer an der (m-9999)-sten Stelle - eine Zahl zwischen 0 und (10^19 - 1). Jetzt teile doch mal 18446744070000000123 durch 10^19. Macht 1 Rest 8446744070000000123, was machst du mit der 1 und was machst du mit dem Rest?

Ianamus

Anscheinend gibt es eine Lösung:

http://manderc.manderby.com/types/umrechner/index.php

ich verstehe aber den Code nicht (Java).

Um es noch einmal zu verdeutlichen:
Wie in der Schule. Wenn ich die Zahl 217 in eine binäre Zahl umwandeln will, mache ich das folgender Massen:

217 : 2^7 = 1 R 89 -> 1
 89 : 2^6 = 1 R 25 -> 11
 25 : 2^5 = 0 R 25 -> 110
 25 : 2^4 = 1 R  9 -> 1101
  9 : 2^3 = 1 R  1 -> 11011
  1 : 2^2 = 0 R  1 -> 110110
  1 : 2^1 = 0 R  1 -> 1101100
  1 : 2^0 = 1 R  0 -> 11011001

Voilà!

Jetzt ist es aber so, dass die grösste abspeicherbare Zahl die 9 ist. D. h. im ersten long-Array-Element steht die 7. Im zweiten die 1. Im dritten die 2. Wie soll ich jetzt vorgehen?

Gruss Ianamus

SG1

Ianamus schrieb:

Um es noch einmal zu verdeutlichen:
Wie in der Schule. Wenn ich die Zahl 217 in eine binäre Zahl umwandeln will, mache ich das folgender Massen:

*facepalm* Genau das sag ich doch seit Beginn an.

Jetzt ist es aber so, dass die grösste abspeicherbare Zahl die 9 ist. D. h. im ersten long-Array-Element steht die 7. Im zweiten die 1. Im dritten die 2. Wie soll ich jetzt vorgehen?

Du implementierst eine Division? Schriftliche Division solltest Du ja in der Schule gehabt haben.

Ianamus

SG1 schrieb:

Du implementierst eine Division? Schriftliche Division solltest Du ja in der Schule gehabt haben.

Dann rechne doch mal mit dem Taschenrechener 100 : 2 , aber ohne eine Zahl einzugeben, die nicht eine ganze Zahl und grösser als 9 ist. Wie machst du das?

Es grüsst herzlichst Ianamus

SG1

Häh???

Ianamus

SG1 schrieb:

Häh???

Was "Häh???" ? Was verstehst du nicht?

Verstehst du ev. was diese Funktion hier macht:

// Formats the given binary array to a decimal output string
function bintodecoutput(bin){
  var len = bin.length;
  var decoutput = String();
  var work = new Array(len);
  var outputlen = 0;
  for(var i=0; i<len; i++){work[i] = bin[i];}
  while(len){
    // as long as a remaining value exists
    var lead = false;
    var bit0;
    var bit1;
    var bit2;
    var bit3;
    var value;
    var i = 0;
    while(i < len-3){
      // walk through the remaining value
      bit0 = work[i+3];
      bit1 = work[i+2];
      bit2 = work[i+1];
      bit3 = work[i+0];
      value = (bit3<<3) | (bit2<<2) | (bit1<<1) | (bit0<<0);
      if(value >= 10){
        // For nibbles greaterequal than 10, adjust the bits accordingly.
        work[i+0] = true; work[i+1] = bit2 && bit1; work[i+2] = !bit1;
      }else{
        work[i+0] = lead;
        if(lead){
          // When the previous nibble was 8 or 9, adjust the bits accordingly
          work[i+1] = !bit1; work[i+2] = !bit1;
          lead = bit1;
        }else{
          // otherwise, just leave the bits as they are.
          if(value >= 8){lead = true;}
        }
      }
      i++;
    }
    // extract the decimal value of the remaining bits
    if(len==1){
      bit0 = work[0];
      bit1 = false;
      bit2 = false;
    }else if(len==2){
      bit0 = work[1];
      bit1 = work[0];
      bit2 = false;
    }else{
      bit0 = work[i + 2];
      bit1 = work[i + 1];
      bit2 = work[i + 0];
    }
    bit3 = lead;
    var value = (bit3<<3) | (bit2<<2) | (bit1<<1) | (bit0<<0);
    if(!(outputlen%3)){decoutput = ' ' + decoutput;}
    decoutput = value + decoutput;
    outputlen++;
    len = i;
  }
  // Remove zeros
  var i = 0;
  outputlen = decoutput.length;
  while((i < outputlen) && ((decoutput[i] == '0') || (decoutput[i] == ' '))){i++;}
  if(i == outputlen){
    return "0";
  }else{
    return decoutput.slice(i);
  }
}

Entnommen von hier:

http://manderc.manderby.com/types/umrechner/index.php

Es grüsst dich aus tiefstem Herzen Ianamus

Ianamus, wieso nicht einfach den Hersteller des Codes fragen? Dann müsste er nicht auf gut Glück auf diesen Thread stossen und sehen, dass die Leute nicht begreifen, was er da programmiert hat.

PS: Die Unterscheidung zwischen Ziffern und Zahlen, die scheint ein wenig durcheinander, wenn ich den Thread so überfliege.

Grüsse, Manderby