Entwickler-Ecke :: Thema anzeigen - Sehr großer Integer

lemming - Do 31.07.03 08:56
Titel: Sehr großer Integer

Hallo,

ich würde gerne Berechnungen mit sehr großen Zahlen anstellen. Mit sehr großen meine ich wirklich ausserordentlich große Zahlen. Ich rede hier von Zahlen die bis zu 100.000 Stellen vor dem Komma haben. Hinter dem Komma null.

Wie stelle ich das an wenn ich die vier Grundrechenarten noch verwenden will? Ich denke da an WideStrings (brauche ja zwei um eine Rechnung auszuführen) die ich dann verunde oder verodere.

Was habt ihr für Ideen?

-lemmi

Aya - Do 31.07.03 09:20

Hi,

also ich kann mich täuschen, aber ich glaube eine Zahl mit 100.000 Stellen kann heutzutage kein normaler PC berechnen.. (wie gesagt, KA *g*)

Die größte zahl mit der du noch recht einfach rechnen kannst ist glaub ich nen In64..

Ob/Wie es bei noch größeren geht.. KA.. (wieso poste ich dann eigentlich? *g*)

Au'revoir,
Aya~

lemming - Do 31.07.03 09:41

Zitat:

also ich kann mich täuschen, aber ich glaube eine Zahl mit 100.000 Stellen kann heutzutage kein normaler PC berechnen..

Ich hab vor mir einen Computer mit 512 Megabyte RAM. Da werd ich wohl doch eine größere Zahl als 8 Byte ausrechnen können... Also eine art Int1024 sollte schon drin sein.

Man kann es ja auch mit Tricks versuchen. Ein riesiges Byte Array und vier Prozeduren zum selber ausrechnen.

-lemming

inselberg - Do 31.07.03 09:44

ich hab damals zu c64 zeiten mit zeichenketten (feldern) gerechnet ....
das ist zwar nicht genau so schnell wie normale operationen, aber es g eht ;)

Aya - Do 31.07.03 09:48

Hi,

das is auch ne idee... du nimmst deine 100.000 stellige zahl und tielst die in Byte-Werte auf, also für jede Ziffer 1 Byte-Wert = 100.000 Byte-Werte... damit kannst du dann, wenn auch sehr umständlich, deinen kram ausrechnen :)

Au'revoir,
Aya~

lemming - Do 31.07.03 09:49

könntest du mir das genauer erklären Inselberg. Geschwindigkeit ist nicht so wichtig.

inselberg - Do 31.07.03 09:54

du musst halt nur die grundoperationen umsetzen zb

s1 := '1234567890123456789012345678901234567890'
s2 := '4567890123456789012345678901234567890123'

für ne addition/subtraktion machst du das jetzt - wie früher in der schule -
hinten anfangen
0 + 3 dann 9 + 2 ... übertrag merken usw

multiplikation führst du dann auf addtion zurück oder auch wie in der schule ;)
usw.

siehst du was ich meine ?

natürlich kann man die ganze geschichte mit nem array of bytes oder was auch immer machen, ich persönlich finds mit zeichenketten aber schöner da man sich auch das erfinden von ausgaberoutinen spart

lemming - Do 31.07.03 10:57

Juhu ich habs! Ich hab jetzt eine Prozedur für's addieren geschrieben:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:

function TForm1.Add(s1, s2: WideString): WideString;
var
  i1, i2: Integer;
  iPos: Integer;
  iTempSum: Integer;
  iRest: Integer;

begin
  if Length(s1) > Length(s2) then
  repeat
    s2 := '0' + s2;
  until Length(s2) = Length(s1);

  if Length(s1) < Length(s2) then
  repeat
    s1 := '0' + s1;
  until Length(s2) = Length(s1);

  iPos := Length(s1);
  iRest := 0;

  repeat
    //ShowMessage('iPos: ' + IntToStr(iPos));

    if iPos <= 0 then
      i1 := 0
    else
      i1 := StrToInt(Copy(s1, iPos, 1));

    if iPos <= 0 then
      i2 := 0
    else
      i2 := StrToInt(Copy(s2, iPos, 1));

    //ShowMessage('i1: ' + IntToStr(i1));
    //ShowMessage('i2: ' + IntToStr(i2));

    iTempSum := i1 + i2 + iRest;
    //ShowMessage('iTempSum: ' + IntToStr(iTempSum));

    if iTempSum > 9 then
    begin
      iRest := StrToInt(Copy(IntToStr(iTempSum), 1, Length(IntToStr(iTempSum)) - 1));
      //ShowMessage('Rest ' + IntToStr(iRest));
      iTempSum := StrToInt(Copy(IntToStr(iTempSum), Length(IntToStr(iTempSum)), 1));
      //ShowMessage('iTempSum: ' + IntToStr(iTempSum));
    end
    else
      iRest := 0;

    Result := IntToStr(iTempSum) + Result;
    iPos := iPos - 1;
  until (iRest = 0) and (iPos <= 0);
end;

procedure TForm1.Button2Click(Sender: TObject);
const
  val1 = '3298472378946127845459359236458234691237461238974673'
    + '648912376478236548135634761341342314';
  val2 = '4974623847923784623897468123382645234891235412356412'
    + '3654058712365125342372390382301298409123840129408975483'
    + '7612563123873437812458123749123848237649781236481736489'
    + '1237649356451902384891276384791238564';
begin
  ShowMessage(Add(val1, val2));
end;

Subtraktion ist ungefähr gleich. Nur mit dem Rest etwas anders. Multiplikation ist sogar noch leichter. Aber Disivison, das wird schwieing und ist auch noch ausgerechnet das was ich am dringensten brauche.

Wie heißt eigentlich die Funktion um x Zeichen in einen String einfügen?

inselberg - Do 31.07.03 11:01

Zitat:

Wie heißt eigentlich die Funktion um x Zeichen in einen String einfügen?

insert

Zitat:

division

guck dir einfach an wie du es "von hand" rechnen würdest

lemming - Do 31.07.03 11:05

Ich habs gefunden, es ist DupeString()

Das hab ich in der Delphi hilfe gefunden.

Zitat:

Beschreibung

DupeString gibt einen String zurück, der ACount Wiederholungen des Strings AText enthält. Ein Beispiel:

S := DupeString('Ha', 5);

Diese Anweisung gibt den String 'HaHaHaHaHa' zurück.

Da hat der Autor wohl'n Clown gefrühstückt.[/delphi]

Motzi - Do 31.07.03 15:35

Guck mal hier: http://www.delphi-forum.de/viewtopic.php?t=13954

lemming - Do 31.07.03 16:26

Motzi, hast du sie schon fertig? Ich hab mir heute selbr eine Bibliothek geschrieben. Addition, Subtraktion, davon dann abgeleitet Multiplikation und Division. Theoretisch kann ich Zahlen mit 2.000.000.000 Stellen berechnen. Theoretisch.
Hab's bis jetzt nur mit 5.000 Stellen getestet und geht wunderbar schnell.

Leider nur Zahlen ohne Komma und keine negativen Zahlen.

MSCH - Do 31.07.03 17:41

lasst es mich wissen wenn ihr bei der Wurzel, quadrate seit. Natürlich nicht nur mit reellen zahlen. Ich bräuchte auch komplexe. :lol:
Interessant wirds dann mit PI und Primzahlen und - faktorenzerlegung.

grez
Msch

Motzi - Do 31.07.03 19:13

Nein, ich hab noch nicht mal angefangen... (hat sich ja auch keiner gemeldet der mithelfen würde)

So eine Bibliothek wie du (auf Basis von Strings) hab ich auch schon mal geschrieben.. und von schnell kann da keine Rede sein!! Rechne mal 2^4096 und mach dabei mal ne Zeitmessung..!

Unter http://www.x-spy.net/personal findest du meine Fachbereichsarbeit zu Public-Key-Kryptographie. Zu dieser Arbeit musste ich eine RSA-Implementierung in Delphi vorlegen - also brauchte ich auch eine Bibliothek für große Zahlen! Ursprünglich wollte ich die C/C++-Bibliothek aus dem Buch "Kryptographie in C und C++" von Michael Welschenbach auf Delphi übersetzen, aber das wäre zu viel Arbeit gewesen. Also hab ich eine "Wrapper-Dll" geschrieben die von meinen Delphi-Objekten intern benutzt wird. Auf Basis dieser Objekte mit der Wrapper-Dll hab ich jetzt 2 Progs geschrieben: einen Rechner für lange Zahlen und einen RSA-Crypter (die max. Länge der Zahlen der Bibliothek beträgt 2^4096). Damit du mal einen ungefähren Vergleich anstellen kannst was die Geschwindigkeitsunterschiede von "String-Implementierungen" zu vernünftigen(!) Implementierungen sind kannst du hier mal den Rechner runterladen: download [http://www.x-spy.net/personal/Rechner.zip]

PS: die Sourcen darf ich aufgrund geltender Copyrights leider nicht freigeben!

@MSCH: wenn du mir bei der Übersetzung des GMP hilfst ( http://www.delphi-forum.de/viewtopic.php?t=13954 ) hast du alles was du brauchst! ;)

lemming - Fr 01.08.03 10:25

Das meine Prozeduren nicht die allerschnellsten sind, da bi ich auch schon drauf gekommen. Vorallem wird's mir Speiübel wenn ich daran denke was ich durch die Strings an Speicher wegschmeisse.

²MSCH, Primzahlen sind indemfall ja kein problem. Ist halt mit dieser Methode nur sehr Zeitaufwändig diese zu finden.

-lemmi

Motzi - Fr 01.08.03 12:17

Der Speicher ist noch das Wenigste.. das Problem ist die ständige umwandlung von String in Integer und wieder zurück! Und solche sachen wie "Copy(s1, iPos, 1)" kann man doch sehr gut durch direkte Zugriffe auf die Zeichen des Strings optimieren: s1[iPos]

Und einzelne Zahlen (0-9) kann man auch wesentlich einfacher in den entsprechenden Integer umwandeln - zB so:

Delphi-Quelltext

1:
2:
3:
4:
5:

function CharToByte(c: Char): Byte;
begin
  if c in ['0'..'9'] then
    Result := Ord(c) - Ord('0');
end;

Aber selbst mit diesen Optimierungen bleibt eine String-Implementierung wesentlich langsamer - was aber hauptsächlich an den Algorithmen liegt! Mit einer String-Implementierung kann man die Algorithmen bei weitem nicht so effizient umsetzen!!

hansano - Do 07.08.03 21:19

was ihr da tut wird im allgemeinen als "very long integer", kurz VLI, bezeichnet, und es gibt dazu im internet bereits verschiedene units, die via google leicht zu finden sind. spannendes thema!
übrigens: was PI angeht, so gibt es hierfür diverse algotithmen, die das errechnen einer beliebigen nachkommestelle von PI ermöglichen. auch diese sind via google schnell gefunden.
mfg

catweasel - So 21.12.03 10:03

Zitat:

Hmmm..

Ist eine Division eigentlich nichts anderes als eine multiplikation mit dem Kehrwert....
Wenn dividieren so leicht ist.....
Kehrwert bilden.... und multiplizieren...

Catweasel