4. Umrechnen von sehr grossen Zahlen in ein anderes Zahlensystem

Umrechnen von sehr grossen Zahlen in ein anderes Zahlensystem

  • I

    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.

    0
  • I

    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 * 64    lg(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... 😉

    0
  • I

    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

    0
  • S

    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.

    0
  • I

    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 * (264)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?

    0
  • I

    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

    0
  • S

    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.

    0
  • I

    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

    0
  • S

    Häh???

    0
  • I

    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

    0
  • ?

    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 😉

    0
Anmelden zum Antworten