Dezimal zu Dual, alternative zum Horner-Schema

[hanssarpei]

Hallo,

ich bin gerade dabei einen Typen für größere Zahlen zu schreiben, dabei erstelle ich ein Array mit 127 Element mit booleanschen Werten, d.h. jedes Element im Array entspricht einem Bit aus dem dualen System.

Ein neue Instanz des Typs wird dabei über die Angabe der Zahl zur Basis 10 als String angegeben, d.h. '124564710', da in Delphi jedoch der größmögliche dezimale Wert 2^64 ist, benötige ich eine alternative zum Horner Schema (also Zahl durch 2, Rest entspricht dem Bit).

Viele unnötige Worte, kurz um gesagt, ich brauche eine alternative zum Horner-Schema. Hab schon vergebens gegoogelt, da ich jedoch keinen Namen kenne und das Horner-Schema ziemlich verbreitet ist (verständlicherweise), ist es schwer entsprechende Alternativen zu finden.

Daher bin ich für jegliche Alternativen sehr dankbar.

[Aphton]

Ich neheme an, du möchtest einen langen Zahlenstring ~"123123123123123123123" in ein Bit (Boolean) Array umwandeln?!

Das kannst du lösen, indem du eine String-Math Library benützt (strAdd, strSub, strMul, strDiv) oder du sorgst dafür, das der Input kein Zahlenstring ist sondern direkt Bit-Daten - bzw Datenstrom ~

Delphi-Quellcode:

//..
function DataToBitArray(const Data: PByte; const SizeInBits: Integer): TDynBitArray;

Weiterer Rat von mir - kann es sein, dass das ganze in die kryptographische Richtung geht? Falls ja, dann lass die Finger von Booleans, nimm direkt ein Array of DWord.
Ich hab nämlich zunächst auch einmal ein BooleanBigInteger implementiert und eben bemerkt, dass es klarerweise doch um einiges schneller geht. Ich habs aber nur aus Neugier programmiert (was dann in RSA ausgeartet ist und ich es dann bei der Mathe-Matura präsentieren durfte..)

[Bjoerk]

Bevor du dir viel Arbeit machst, schau mal hier:

Delphi-Quellcode:

function PowerAndMod(A, E, M: int64): int64;
begin
  Result := 0;
  if E < 0 then
    Exit;
  if (M = 1) or (M = -1) then
    Exit;
  if (A = 0) and (E > 0) then
    Exit;
  Result := 1;
  try
    while E > 0 do
      if E mod 2 <> 0 then // Odd 
      begin
        Result := (Result * A) mod M;
        E := E - 1;
      end
      else
      begin
        A := (A * A) mod M;
        E := E div 2;
      end;
  except
    raise Exception.Create('Int64 Overflow');
  end;
end;