Dezimal -> Binär

[Meisterschmied]

Eine ganz einfache Frage: Wie setze ich eine Dezimalzahl in die Binärdarstellung und wieder zurück?

:hi: Thanks,
Meisterschmied

[Duffy]

Hallo Meisterschmied,
Schau Dir mal diesen Beitrag an. Das solte Dir schon mal weiterhelfen. Den Rest gibt es auch in diesem Forum. Einfach mal die Suche benutzen.
bye
Claus

[Meisterschmied]

Danke, klar, hätte mir auch selbst auffallen können, dass ich wohl nicht der erste bin, der das fragt... :oops:

Thanks,
Meisterschmied

[negaH]

Du möchtest bestimmt herausbekommen welches Bit in einer Zahl gesetzt ist ?

Delphi-Quellcode:

if Odd(Value shr Bit) then ...;

Value ist zb. ein Cardinal und Bit die Bitnummer mit 0 basiertem Index.
Für 32Bit/64Bit Zahlen funktioniert dies noch sehr effizient, bei größeren Zahlen aber nicht mehr. Dort ist es dann besser mit den Assembler Bit Funktionen zu arbeiten.

Delphi-Quellcode:

type
  TNumber = array[0..31] of Cardinal;

function IsBitSet(const Number: TNumber; BitIndex: Integer): Boolean;
asm
   BT   [EAX],EDX
   SETC AL
end;

In TNumber ist die lange Zahle in Litte Endian gespeichert. D.h. Number[0] ist des niedrigste Digit und Number[31] dashöchstweritge Digit.

Gruß Hagen

[Meisterschmied]

Hey Hagen,

Zitat:

Du möchtest bestimmt herausbekommen welches Bit in einer Zahl gesetzt ist ?

nein :) die Frage war genauso einfach gemeint wie sie gestellt war. Ich muss mich jetzt mal weiter mit dem Rechnen im Dualsystem beschäftigen, da ich gerade merke, dass ich, um das RSA-Verfahren richtig und sicher auszuführen, nur in diesem Modus vernünftig rechnen kann. Das kann ja noch ein Spass werden... :spin:

Vielen Dank auf jeden Fall,

Meisterschmied

[negaH]

Zitat:

um das RSA-Verfahren richtig und sicher auszuführen, nur in diesem Modus vernünftig rechnen kann

Verrenne dich da nicht geistig :)

Es gibt keinen Unterschied zwischen Binär, Hexadezimal oder zur Basis 2^32. Wichtig ist nur das Berechnungen zur Basis 2,16,2^32 kompatibel in den gespeicherten Datenstrukturen sind !!

Angenommen die Zahl 11 wird in einem Cardinal gespeichert, da enthält er
01011b = 0Bh = 11 intern ändert sich nichts an dessen Speicherung.
Wird nun 11 + 2 gerechnet entsteht in der gleichen Variable 13, = 01101h = 0Dh.

D.h. für deine Berechnungs Funktionen ist es nur wichtig das du zu einer Basis arbeitest wie 2^16 oder 2^32. Zb. 2^32 ist nichts anderes als obige TNummer = array[0..x] of Cardinal. Jedes Array Element ist dann ein Digit zu Basis 2^32.

Zahl = Number[0] + Number[1] * 2^32 + + Number[2] * 2^64 + Number[3] * 2^96
Zahl = Number[0] * 2^(32 * 0) + Number[1] * 2^(32 * 1) + Number[2] * 2^(32 * 2) + ... + Number[i] * 2^(32 * i).

Je besser diese Basis an die CPU angepasst ist um so besser und schneller arbeitet dein Code. Würdest du deinen Code aufbauend auf Strings die die Zahlen im Binärformat enthalten, dann wäre dies ca. 32 mal ineffizienter als zur Basis 2^32. Da die heutigen CPU's 32Bit Rechner sind sind sie mit einer basis von 2^32 am effizientesten.

Um also RSA Berechnungen durchführen zu können ist die Darstellung der Zahl als String irrelevant.

Falls du Interesse hast und dein Projekt privater Natur ist kann ich dir meine Large Integer Math. Library mailen. Darin enthalten ist auch RSA usw. Wichtig für dich wäre sie dann als Verifizierung deines eigenen Codes. Wenn man an hand einer fertigen Lib. seinen Code vergleichen kann ist dies viel wert.


Gruß Hagen

[Meisterschmied]

Hey Hagen,

also, mein Projekt ist privater Natur, genauer genommen ist es ein Teil meiner Facharbeit über das RSA-Verfahren (Mathe-LK, versteht sich). a) erstmal tausend dank, dass du dir so viel Mühe gibts :o , auch wenn ich manch mal nur die Hälfte verstehe. Das mit der Library hört sich gut an, auch wenn du mir dann kurz erklären müsstest, wie ich sie einsetze, grundsätzlich ist es aber so, dass ich den Code alleine schreiben sollte (was nicht die Hilfe von Dritten ausschließt). Auch ist eine Optimierung erst dann von Nöten, wenn es überhaupt erst mal funktioniert. Es funktioniert zwar zurzeit alles, nur eben mit sehr kleinen Primzahl. Deshalb arbeite ich zurzeit am Miller-Rabin-Verfahren (was schon weitestgehend klappt, nur ein kleiner Hacken ist noch irgendwo :roll: ) Dazu gehört ja dann auch Euklidischer Algorithmus (ok, billig) und schnelle Exponention (hab besten Dank, ist dein Verdienst). Wenn der Teil fertig ist und richtig in den anderen Code hineingebastelt ist und alles klappt, dann wollte ich mich an die Optimierungsarbeiten machen, und die Primzahl in den Bereich von 512Bit zu steigern (wenn ichs nicht schaffe, ist es nicht weiter tragisch, aber schön wärs schon...). Mit dem Zusatz sind Primzahl im INT64-Bereich möglich. Jetzt kennst du wenigstens den Hintergrund meiner Fragereien.

Aber um jetzt noch auf das zurück zu kommen, was du gepostet hast. Mein Problem ist, dass ich die Zahlen, egal zu welcher Basis, irgendwie speichern muss, aber das kann ich doch nur auf Stringebene (als Integer doch wohl kaum?). Und wenn ich die binäre schnelle Exponention zugrunde lege, wäre es doch das Beste, alles im Binärmodus auszuführen (obwohl... arrrgghh, ich bin gerade verwirrt :pale: ....). Denn wie soll ich sonst über den gesamten Programmablauf ein Format einhalten, hier eine binäre Exponention, hier diese Basis, denn ich muss doch für die verschiedenen Verfahren (also jeweils Addition und Multiplikation sowie die Umsetzung in das andere Format) jeweils Prozeduren schreiben, oder?

Nein, jetzt versteh ich gar nichts mehr, ich stell mich doch sonst nicht so blöd an (glaub ich :P ).

Hast du aus meinem Wust ungefähr verstanden, was ich meinte?

Ich hoffs,

Beste Grüße

Wieland (alias Meisterschmied :-D )

[Edit] Ein Haufen Rechtschreibfehler, sorry, die letzten Abende waren lang...[/Edit]

[negaH]

Hi

ich habe sehr wohl verstanden was du meinst, und sehe auch das du wie ich und viele andere am gleichen "Denk" Problem verhacken :) Nämlich wie representiere und speichere ich die großen Zahlen im Speicher !?

Es hängt ganz einfach von der willkürlichen Definition ab was du als bestest empfindest. Dies ist die einzigst richtige Antwort.
D.h. egal ob in Strings, array of Double, array of Word oder array of Cardinal, egal ob in Little Endian, also kleinste Einheit im kleinsten Array Index oder in Big Endian, größtes Element an Array index 0, man kann mit allem so rechnen als meinte man eine sehr große Zahl.

Entscheidend bei der Wahl ist es nur was das effizientes auf der jeweiligen Rechnerarchitektur ist, und ob in der jeweiligen Programmiersprache alle nötigen Operationen verfügbar sind.

Nun in deinem Falle empfehle ich dir

Delphi-Quellcode:

type
  TDigit  = Cardinal; // 0..10^4-1;
  TNumber = array of TDigit;

D.h. in TNumber wird in Little Endian jeweils zur Basis 10^4 die einzelnen Digits gespeichert.
10^4 weil der Datentyp Cardinal bis 10^9 nicht überlaufen kann.

Wir bezeichnen also ein Element aus dem TNumber Array als Digit oder Ziffer, wobei es aber 10^4 verschiedene Ziffern pro Digit gibt. Also statt 10 wie im Dezimalsystem, oder 16 im Hexdezimalsystem oder 2 im Binärsystem, arbeiten wir im 10^5 - System !.

Der Vorteil besteht darin das deine Berechnungen alle in PASCAL programmierbar sind, ohne Assembler, und das bei jedem Schritt du die Zahl sofort ablesen kannst.

TNumber = [1234, 567, 89] ist nämlich -> 01234, 00567, 00089 -> 89.00567.01234

Wie du siehst enthielte
TNumber[0] den Rest der Zahl X mod 10.000
TNumber[1] den Rest der Zahl X div 10.000 mod 10.0000
TNumber[2] den Rest der Zahl X div 10.000*10.0000 mod 10.0000

Also im array Element 0, dem kleinsten Element steht, der kleinste am wenigsten Wertentscheidene Anteil der gesamten Zahl.

Wenn sich die Zahl vergrößert und mehr speicher benötigt so würde einfach TNumber[3] <> 0 werden.

Um es noch einfacher für dich zu machen könntest du aber TNumber als festes Array[0..x] definieren und von Rechts nach Links arbeiten. Obige Zahl sähe gespeichert dann so aus:

TNumber = [0,0,0,0,0,0,0,0, 89, 567, 1234] -> 89.00567.01234

Allerdings verhinderst du damit die einfache Erweiterbarkeit im Darstellungsbereich.

Nun eine solche Zahl in einen Dezimalen String umzuwandeln ist einfach:

Delphi-Quellcode:

function NumberToString(const Number: TNumber): String;
var
  I: Integer;
begin
  for I := 0 to High(Number) do
    Result := Format('%s%0.5d', [Result, Number[I]]);
end;

Soweit so gut. Wenn wir statt 10^5 die Basis auf 2^16 ändern dann kann man ohne Gefahr zwei TDigit multiplizieren auf 2^32 ohne das der Zahlenbereich überläuft. Statt 0 bis 10.000 -1 wärem im TDigit nun 0 bis 65.535 -1 gespeichert, also ca 6,5 mal zuviel an Information. Wir benötigen also weniger Speicher. Der zweite Vorteil ist das alle Operationen wir Multiplikation * 2^x oder Divisionen durch 2^x oder die Boolschen Operatoren AND,XOR,OR direkt auf das TNumber array angewendet werden können. D.h. zur Basis 10^5 haben wir ohne Konvertierungen sofort eine "lesbare" Dezimale Zahl in TNumber, bei der Basis 2^16 aber nicht. Dafür ist die Basis 2^16 einfacher umzusetzen und besser zu verstehen und schneller.

Bis hier hin haben wir über die Darstellung von Natürlichen Zahlen gesprochen, also Zahlen die immer positiv und nicht gebrochen sind. Wird benötigen für RSA Zahlen die Ganzzahlen sind, also Natürliche Zahlen die ein Vorzeichen besitzen können.

Es ist sinnvoll TNumber zu erweitern auf:

Delphi-Quellcode:

type
  TNumber = record
    Negative: Boolean;
    Digits: array of TDigit;  
  end;

Das Feld Negative bestimmt also ob TNumber negativ oder positiv ist.
Digits ist das immer die absolute Representation der Zahl, was nun sehr viele Operationen stark vereinfacht. Z.b. sollen zwei TNumbers A und B addiert werden so schaut man nach ob beide Nummer gleiches Vorueichen besitzen, also A.Negative = B.Negative. Sollte dies der Fall sein su müssen wir A.Digits + B.Digits ausrechnen. Sollte A.Negative <> B.Negative sein so müssen wir A.Digits - B.Digits rechnen. Die Logiken vereinfachen sich also.

Wie könnte eine Addition nun aussehen ?

Delphi-Quellcode:

procedure Add(var R: TNumber; const A,B: TNumber);
// R = A + B
var
  I,J: Integer;
  Carry: Cardinal;
begin
  if A.Negative = B.Negative then
  begin // hier addition von .digits
    I := Length(A.Digits);
    J := Length(B.Digits);
    if I < J then
    begin // A > B
      R.Negative := A.Negative; 
    end else
    begin // B >= A
      R.Negative := B.Negative;
      J := I;
    end;
    SetLength(R.Digits, J);
    Carry := 0;
    for I := 0 to J -1 do
    begin
      Carry := Carry + A.Digits[I] + B.Digits[I];
      R.Digits[I] := Carry and $FFFF;  // mod 2^16
      Carry := Carry shr 16;  // div 2^16      
    end; 
    if Carry <> 0 then
    begin
      SetLength(R.Digits, J +1);
      R.Digits[J] := Carry; 
    end;
  end else
  begin // hier subtraktion von .digits
    
  end;
end;

type
  TBase = 2..16;

function NumberToStr(const A: TNumber; Base: TBase = 10): String;
// wir haben
//  A[i] = ai*2^16^i
// und konvertieren die Zahl in A in einen String der diese Zahl zur Basis Base darstellt.
const
  Chars: array[0..15] of Char = '0123456789abcdef';
var
  R: Cardinal;
  T: TNumber;
begin
  T := A;
  while not IsZero(T) do
  begin
    R := DivMod(T, Base);  // R := T mod Base und T := T div Base
    Result := Chars[R] + Result;
  end;
  if Result = '' then Result := '0' else 
    if A.Negative then Result := '-' + Result;
end;

Es ist also recht simpel. Als Vergleich zu NumberToStr() hier mal mit In64 Zahlen.

Delphi-Quellcode:

function NumberToStr(const A: Int64; Base: TBase = 10): String;
const
  Chars: array[0..15] of Char = '0123456789abcdef';
var
  T: Int64;
  R: Byte;
begin
  T := A;
  while T <> 0 do
  begin
    R := T mod Base;
    T := T div Base;
    Result := Chars[R] + Result;
  end;
  if Result = '' then Result := '0' else
    if A < 0 then Result := '-' + Result; 
end;

Natürlich ist obiger Code eine Demonstration und nur suboptimal, mit ineffizientem String Handling und ineffizienter Modularer Reduktion.

Gruß Hagen

[Meisterschmied]

Hi Hagen,

der war ja schon ziemlich ausführlich. Ich zwar noch ein paar Probleme mit meinem RSA-Algorithmus (der aber zurzeit nur mit kleinen Primzahlen funktionieren kann). Sobald ich diese Probleme beseitigt habe, mache ich mich sofort an das, was du mir geschrieben hast, um diesen Bereich zu erweitern. Ich glaub, ich hab jetzt eine ganz gute Ahnung :idea: (obwohl, wie sagte doch Bohr in Anspielung an die Quantenmechanik: "Wer glaubt, sie verstanden zu haben, hat keine Ahnung") von was du sprichst. Hast dir ja auch große Mühe gegeben, es möglichst einfach auszudrücken :thuimb: Danke! Eins ist mir beim Ersten überfliegen des Codes aufgefallen: Du schreibst bei der Addition

Delphi-Quellcode:

    R.Digits[I] := Carry and $FFFF;  // mod 2^16

Was bedeutet das $FFFF? Echt noch mal vielen Dank, dass du dir so viel Mühe gibst :thuimb: Werd mich die nächsten Tage mal bemühen und sehen, was dabei rauskommt. Sag mal, hast du eigentlich Informatik studiert?

Thanks,

Wieland

[himitsu]

$FFFF ist die hexadezimale Darstellung von 65535.

Delphi-Quellcode:

2^16 - 1 = 65535 = $FFFF

Und da die Binäroperationen schneller arbeiten als die Mathematischen, hat er an dieser Stelle den Quellcode etwas optimiert.

Delphi-Quellcode:

Y and $FFFF    entspricht    Y mod 2^16

Diese Optimierung funktioniert allerdings nur bei Potenzen von 2 (2 hoch X).



Für die Division und Multiplikation, sieht es z.B. so aus:

Delphi-Quellcode:

Var Y, X: Integer; {Ganze Zahlen - auch Byte, Word...}

Y / 2^X  =  Y div 2^X  =  Y shr X

Y * 2^X  =  Y shl X

PS: es ist doch richtig!
Bit 0 = 1. Bit
...