Konvertierung Binär Dezimal

[JocalAreaNetwork]

Hallo,

das Thema klingt ja auf den ersten Blick ganz trivial, aber ich finde nicht unbedingt, dass es das ist. Das Problem, das ich habe, ist, dass ich versuche einen eigenen Datentyp zu erstellen. Nun lege ich ein Array von Byte Werten an, je nachdem wie hoch die gewünschte Präzision ist.
Ich scheitere leider nun schon daran eine beliebig lange Zahl in einen String zu konvertieren.

Hat jemand eine Idee, wie es möglich ist, einen String einer beliebig langen Zahl im Binärsystem ( also z. Bsp 512 Bit Genauigkeit ) in einen String der Zahl im Dezimalsystem zu konvertieren ohne dabei auf die Grenzen eines Datentyps zu stoßen? Mir fällt momentan leider keine Möglichkeit ein und auch über Google habe ich nichts gefunden.

Sollte jemand freie Bibliotheken für beliebig genaue Datentypen für Delphi kennen, dann wäre das natürlich auch interessant, aber generell frage ich mich, wie man ein solches Problem umgehen kann.

Viele Grüße
JocalAreaNetwork

[glkgereon]

Such mal nach dem DEC, dem Delphi Encryption Compendium von Hagen Reddmann (hier als negaH bekannt)

In einem Thread der sich "unendlich große Zahlen" oder so schimpfte, hat er mal für verschiedene Delphi Versionen den entsprechenden Teil veröffentlicht.

[ichbins]

...



...



...

Du wirst ein Array von Zahlen (0..9) anlegen müssen, in dem du die Berechnungen durchführst...

Delphi-Quellcode:

function binaraytostring(const bins:array of boolean):string;
var
  intarray:array of 0..9;
  value2add:array of 0..9;
  i,j,k,l,factor:integer;
  einsweiter:boolean;
  weiter:integer;
begin
  factor:=1;
  for i:=0 to length(bins)-1 do begin
    //in value2add den integerwert des bins speichern
    setlength(value2add,1);
    if bins[i]=true then
      value2add[0]:=1
    else
      value2add[0]:=0;
    //value2add multiplizieren
    for j:=2 to factor do begin
      for k:=length(value2add)-1 downto 0 do begin
        einsweiter:=value2add[k]>=5;
        value2add[k]:=(value2add[k]*2) mod 10;
        weiter:=(value2add[k]*2) div 10;
        l:=k+1;
        while einsweiter do begin
          if l=length(value2add) then
            setlength(value2add,l+1);
          if value2add[l]+weiter<10 then
          begin
            value2add[l]:=value2add[l]+weiter;
            einsweiter:=false;
          end else begin
            einsweiter:=true;
            value2add[l]:=value2add[l]+(weiter mod 10);
            weiter:=weiter div 10;
          end;
        end;
      end;
    end;
    //value2add zu intarray hinzufügen
    setlength(intarray,max(length(intarray),length(value2add)));
    for k:=length(value2add)-1 downto 0 do
    begin
        einsweiter:=value2add[k]+intarray[k]>=10;
        intarray[k]:=(value2add[k]+intarray[k]) mod 10;
        weiter:=(value2add[k]+intarray[k]) div 10;
        l:=k+1;
        while einsweiter do begin
          if l=length(intarray) then
            setlength(intarray,l+1);
          if intarray[l]+weiter<10 then
          begin
            intarray[l]:=intarray[l]+weiter;
            einsweiter:=false;
          end else begin
            einsweiter:=true;
            intarray[l]:=intarray[l]+(weiter mod 10);
            weiter:=weiter div 10;
          end;
        end;


    end;

    //stellenwert um 1 erhöhen
    factor:=factor+1;
  end;
  result:='';
  for i:=0 to length(intarray)-1 do
    result:=inttostr(intarray[i])+result;
end;

irgendwo is noch ein Fehler drin...

Beim verdoppeln von 16 kommt 22 raus...

[JocalAreaNetwork]

@glkgereon: Vielen Dank, ich schaue es mir gleich mal an.

@ichbins: Ah, gute Idee auch den zu addierenden Wert in ein Array aufzuteilen. Ich glaube ich wüsste jetzt, wie ich es mache.

[ichbins]

So funktionierts:

Delphi-Quellcode:

type
  t0t9=0..9;
  t0t9a=array of t0t9;
 
[...]

procedure addt0t9(var value:t0t9a; const add:t0t9a);
var
  i,j,k,rest,newrest:integer;
begin
  for i:=length(add)-1 downto 0 do begin
    if length(value)<=i then begin
      setlength(value,i+1);
      value[i]:=0;
    end;
    rest:=(add[i]+value[i]) div 10;
    value[i]:=(add[i]+value[i]) mod 10;
    j:=i+1;
    while rest>0 do begin
      if length(value)<=j then
      begin
        setlength(value,j+1);
        value[j]:=0;
      end;
      newrest:=(rest+value[j]) div 10;
      value[j]:=(rest+value[j]) mod 10;
      rest:=newrest;
      j:=j+1;
    end;
  end;
end;

function binaraytostring(const bins:array of boolean):string;
var
  intarray:t0t9a;
  value2add:t0t9a;
  i,j,k,l,m,factor:integer;
  einsweiter:boolean;
  weiter:integer;
begin
  factor:=1;
  for i:=0 to length(bins)-1 do begin
    //in value2add den integerwert des bins speichern
    setlength(value2add,1);
    if bins[i]=true then
      value2add[0]:=1
    else
      value2add[0]:=0;
    //value2add multiplizieren
    for j:=2 to factor do begin
      addt0t9(value2add,value2add);
    end;
    //value2add zu intarray hinzufügen
    addt0t9(intarray,value2add);
    //stellenwert um 1 erhöhen
    factor:=factor+1;
  end;
  result:='';
  for i:=0 to length(intarray)-1 do
    result:=inttostr(intarray[i])+result;
  setlength(intarray,0);
  setlength(value2add,0);
end;

Die Binaries müssen so angegeben werden dass die 1er-Stelle vorne ist (0), die 2er element 1, die 4er element 2, die 8er element 3 usw...

[negaH]

Code:

.                            Rest                      
. 23456789 div 10 =  2345678,  9
.  2345678 div 10 =   234567,  8
.   234567 div 10 =    23456,  7
.    23456 div 10 =     2345,  6
.     2345 div 10 =      234,  5
.      234 div 10 =       23,  4
.       23 div 10 =        2,  3
.        2 div 10 =        0,  2

Teile X wiederholt solange durch 10 bis es < 10 ist. Der Rest im jedem Zwischenschritt wird in eine Ziffer ds Dezimalsystemes umgewandelt.

Das wäre der naive Ansatz wenn man zb. keine schnellen Multipliaktion oder Divisionen für große Zahlen hat. Hat man diese, wie die meisten guten Libraries, dann geht es schneller !

Code:

.                      23456789 div 10000 = 2345 , 6789
.        2345 div 1000 = 23, 45                          6789 div 1000 = 67 , 89
.  23 div 20 = 2, 3            45 div 10 = 4,5   67 div 10 = 6,7                  89 div 10 = 8,9

In diesem, sehr idealistischen Beispiel, entsteht eine Pyramide von 10'er Potenzen von 10 -> 100 -> 10000, also 10 -> 10*10 -> 10*10*10*10, also 10^1 -> 10^2 -> 10^4 -> 10^8 -> 10^16 usw.. also Base^(2^i) {i=1..j}.

Meine DECMath Library benutzt exakt diesen Weg, aber für die Konvertierung von Strings<->>Zahlen in beiden Richtungen.

Ausnahmen sind Basen die direkt kompatibel zu Basis deiner internen Zahlendarstellungen sind. Du benutzt 2^32 = 2^(2^5) und diese ist zu alle Basen 2^(2^x) direkt kompatibel. Diese Basen werden in der Konverierung durch einfach Bitextraktionen umgewandelt.


Gruß Hagen

[edit]
man ist das ein shit, es gibt keine Möglichkeit mal eben einen Text auf einfache Art&Weise per FixedFont und Leerzeichen sauber zu formatieren ! Soll ich erst ein CAD Program starten um sowas sauber hinzubekommen,wenn ich mal eben in 2 Minuten eine Antwort schreiben möchte ?
[/edit]

[ichbins]

Aber das geht ja nur bis zur int64-Grenze, also 2^63 = 9223372036854775808 = 10^18, oder?

Meins geht (theoretisch bei genug RAM) bis zu 2 GB, also 10^(2*1024^3) = 10^2147483648.

[negaH]

Wie kommst du darauf ? Du hast doch oben eine Methode gezeigt die mit mehr als 64 Booleans in deinem Array[] funktioniert, oder ? Also müsste dir klar sein das wenn die Booleans komprimiert a 32 Stück in einen Cardinal reinpassen, es ergo auch eine Möglichkeit gibt dann ein Array[] of Cardinal mit fast unbegrenzter Größe zu rechnen.

Ich vermute mal das du meine obige Beschreibung missverstehst. Sie erklärt nur wie man es mathematisch macht. Die Definition der Zahlengrenzen hängt nun von der Implementation der DivMod und Multiplikation ab. Im einfachten Fall benötigt mal also eine DivMod Funktion die ein großes Bitarry mit Zahlen < 2^32 dividiert und den Rest liefert. Bei einem Array[] of Cardinal sind das ca. 9 Zeilen Assembler.

Lade dir mein DECMath und schaue es dir an. Es geht.

Gruß Hagen

[ichbins]

Könnt wirklich sein dass ich deine Beschreibung ein bisschen sehr miss- oder garnicht verstanden habe...

aber die mathematischen Grundlagen hab ich mir auch selber erdacht, ich kann ja nicht einfach drauflosschreiben und dann erst überlegen ob das auch funktioniert.

bei deinem DECMath (hab ich schon mal geladen) gibst du aber keine Source frei.

[JocalAreaNetwork]

Wie auch immer, vielen Dank für die hilfreichen Antworten, ich weiß jetzt, was ich machen muss.