Entwickler-Ecke :: Thema anzeigen

Horst_H - Mi 10.09.14 11:53

Hallo,

Ein schöne und schnelle Idee, die Basis umzuwandeln.
ich bekomme andere Ziffern für 2^n . die -1 habe ich mir gespart:

Quelltext

1:
2:
3:
4:

m521.mrs:
  00000000686  47976601306  0971>>5216655  09252662610  57310425694
  12123558385  29111589101  85045491772  87963985315  16754035837
  96413728569  13217193348  27283448061  93896227066<<  91115057151

Quelltext

1:
2:
3:
4:
5:

verdoppel.dpr zwischen >> << sind dann die andere Ziffernfolge
000006864|797660130|60971>>4981|900799081|393217269|435300143|305409394|463459185|
543183397|656052122|559640661|454554977|296311391|480858037|121987999|716643812|
5740282<<91|115057152|
00:00:00.000

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:
67:
68:
69:
70:
71:

program verdoppel;//.dpr
{$IFDEF FPC}
  {$MODE DELPHI}
{$Else}
  {$APPTYPE console}
{$Endif}
uses
  sysutils;
const
  STELLEN_MAX   = 40000;//*9 Dezimalen 
type
  tFeldIndex    = 0..STELLEN_MAX+1;
  tZiffer       = LongWord;
  tBasisZiffern = array[tFeldIndex] of tZiffer;

Procedure Doppel_Zahl(var Feld    :tBasisZiffern;
                      var MaxIndex:tFeldINdex;
                          Basis   : tZiffer);
{ Verdoppeln einer Zahl in einer beliebigen Basis >1}
var
  Uebertrag,
  Sum       ,//: tZiffer;
  i         : NativeInt;
Begin
   Uebertrag := 0;
   {Von der kleinsten bis zur hoechsten Stellen die Ziffern addieren}
   for i := 0 to MaxIndex do
   begin
      Sum := Feld[i] shl 1 + UeberTrag;
      If Sum < Basis then
         Uebertrag := 0
      else
      Begin
         Sum := Sum-Basis;
         Uebertrag := 1;
      end;
      Feld[i] := Sum;
   end;
   {Falls ein Uebertrag in der hoechsten Stelle}
   {Korrektur des MaxIndex und speichern des Uebertrag's}
   If Uebertrag = 1 then
      If MaxIndex < High(MaxINdex) then
      begin
         MaxINdex := MaxIndex+1;
         Feld[MaxINdex] := 1
      end
      else
         writeln('Konvertierungsueberlauf');
end;

var
  T1,t0: TDateTime;
  Zahl : tBasisZiffern;
  i    : tZiffer;
  MaxIndex :tFeldIndex;
Begin
  {Kann man sich sparen: 
  MaxIndex := 0;
  fillchar(Zahl, SizeOf(Zahl),#0);
  }
  Zahl[0] := 1;

  T0 := Time;
  For i := 1 to 521 do
    Doppel_Zahl(Zahl,MaxINdex,1000*1000*1000);
  T1:=time;
  for i := MaxIndex downto 0 do
    write(Format('%.*d|',[9,Zahl[i]]));
  writeln;
  writeln(FormatDateTime('HH:NN:SS.ZZZ',T1-t0));
END.

Wenn ich Deine Version von extended auf LongWord umstelle, kommen die selben Ziffern, wie bei Verdoppel, wobei es sogar etwas schneller wird ( 7,2 statt 9 Sekunden für 2^(1000*1000) )

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:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:

unit Mersennezahlengenerator;

{$IFDEF FPC}
  {$MODE Delphi}
{$ENDIF}

interface

uses
{$IFnDEF FPC}
  Windows,
{$ELSE}
  LCLIntf, LCLType, LMessages,
{$ENDIF}
  Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, Menus, FileUtil;

const
  Dezimalen = 9;
  T = 1000 * 1000 * 1000;//= 10^Dezimalen;
  ExCo = 32;
  BG = (UInt64(1) shl ExCo);
  AusgabeDezi = 10;
  ZahlProZeile = 90 div (AusgabeDezi + 1);
  Max = 90000000;

type
  TFeld = array of LongWord;

  TMersenneZahl = class(TForm)
    LabelExponent: TLabel;
    EditExponent: TEdit;
    LabelZiffernanzahl: TLabel;
    LabelZiffern: TLabel;
    LabelRechenzeit: TLabel;
    LabelSek: TLabel;
    LabelBereich: TLabel;
    LabelUeberSchrift: TLabel;
    OpenDialog: TOpenDialog;
    SaveDialog: TSaveDialog;
    MainMenu: TMainMenu;
    Datei: TMenuItem;
    Laden: TMenuItem;
    Speichern: TMenuItem;
    N1: TMenuItem;
    Beenden: TMenuItem;
    Berechnen: TMenuItem;
    Ausgabe: TMemo;
    procedure BerechnenClick(Sender: TObject);
    procedure BeendenClick(Sender: TObject);
    procedure SpeichernClick(Sender: TObject);
    procedure LadenClick(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure EditExponentKeyPress(Sender: TObject; var Key: char);
  private
    { Private-Deklarationen }
    P: TFeld;
    Grenze, ZL,ZZ,Exponent: cardinal;
    Verzeichnis: string;
    procedure Ausgeben;
  public
    { Public-Deklarationen }
  end;

var
  MersenneZahl: TMersenneZahl;

implementation

{$R *.dfm}

{$R-,Q-}

function TimeSekunden: extended;
var
  H, M, S, MS: word;
begin
  DecodeTime(Now, H, M, S, MS);
  TimeSekunden := 3600.0 * H + 60.0 * M + S + MS / 1000;
end;

procedure TMersenneZahl.Ausgeben;
var
  I, K, L: integer;
  Zeile, ZahlStr: string;
  slAusgabe: TStringList;
begin
  slAusgabe := TStringList.Create;

  ZahlStr := Format('%d', [P[ZL]]);
  for I := ZL - 1 downto 1 do
    ZahlStr := ZahlStr + Format('%.*d', [Dezimalen, P[I]]);
  // passend '0' davor  setzen
  L := length(ZahlStr);
  ZZ := L;

  K := L mod AusgabeDezi;
  if k > 0 then
  begin
    K := AusgabeDezi - K;
    setlength(ZahlStr, L + K);
    Move(ZahlStr[1], ZahlStr[K + 1], L);
    fillchar(ZahlStr[1], K, '0');
  end;

  L := length(ZahlStr) div AusgabeDezi;
  K := 1;
  I := ZahlProZeile;
  Zeile := '';
  repeat
    Zeile := Zeile + '  ' + copy(ZahlStr, K, AusgabeDezi);
    Inc(K, AusgabeDezi);
    Dec(i);
    if I <= 0 then
    begin
      slAusgabe.Add(Zeile);
      Zeile := '';
      i := ZahlProZeile;
    end;
    Dec(L);
  until L <= 0;

  if Zeile <> '' then
    slAusgabe.Add(Zeile);

  Ausgabe.Lines.Assign(slAusgabe);
  slAusgabe.Free;
end;

procedure TMersenneZahl.BerechnenClick(Sender: TObject);
var
  Zeit:TDateTime;
  H,U : Uint64;
  pCar : ^LongWord;
  ExDiv,ExMod,K,L,IZ :Cardinal;
begin
 LabelZiffern.Caption := '0';
 LabelSek.Caption := '0.00 sek.';
 Ausgabe.Lines.Clear;
 if EditExponent.Text = '' then
   EditExponent.Text := '521';
 if StrToInt64(EditExponent.Text) > Grenze then
 begin
   MessageDlg('Der Exponent ist zu groß!', mtError, [mbRetry], 0);
   EditExponent.Text := '521';
   exit;
 end;
 Screen.Cursor := crHourglass;

 Exponent := StrToInt(EditExponent.Text);

 // Komplette Stellen zur Basis
 ExDiv:=Exponent div ExCo;
 // fehlende Stellen
 ExMod:=Exponent mod ExCo;

 ZL:=trunc(Exponent*LN(2.0)/LN(T))+1;
 SetLength(P,0);
 SetLength(P,ZL+1);

 P[1]:=1;
 IZ:=1;
 U:=0;

 Zeit:=Time;
 for K:=ExDiv downto 1 do
 begin
   pCar := @P[1];
   for L:=1 to IZ do
   begin
     H:=UInt64(pCar^) SHL ExCo +U;
     U:=H DIV T;
     pCar^:= H-U*T;
     inc(pCar);
   end;
   while U>0 do
   begin
     inc(IZ);
     H:=U;
     U:= U DIV T;
     pCar^:=H-U*T;
     inc(pCar);
   end;
 end;

 // U ist hier 0
 for L:=1 to ZL do
 begin
   H:=UInt64(P[L]) SHL ExMod+U;
   U:=H DIV T;
   P[L]:=H-U*T
 end;
 Zeit:=Time-Zeit;
 Screen.Cursor := crDefault;


 LabelSek.Caption := Format('%0.3f', [Zeit*86400]) + ' sek.';
 Update;
 application.ProcessMessages;
 sleep(100);

 P[1] := P[1] - 1;

 ausgeben;
 LabelZiffern.Caption := IntToStr(ZZ);
end;


procedure TMersenneZahl.BeendenClick(Sender: TObject);
begin
  Close;
end;

procedure TMersenneZahl.SpeichernClick(Sender: TObject);
begin
  if ZL = 0 then
  begin
    MessageDlg('Du mußt erst eine Mersennezahl berechnen!', mtError, [mbOK], 0);
    exit;
  end;
  with SaveDialog do
  begin
    InitialDir := Verzeichnis;
    Filter := 'MersenneDateien (*.mrs) |*.mrs';
    FileName := 'M' + IntToStr(Exponent);
    DefaultExt := 'mrs';
    Options := [ofOverWritePrompt];
    if Execute then
    begin
      Ausgabe.Lines.SaveToFile(FileName);
      MessageDlg(ExtractFileName(FileName) + ' ist gespeichert worden!',
        mtInformation, [mbOK], 0);
    end;
  end;
end;

procedure TMersenneZahl.LadenClick(Sender: TObject);
var
  I, K: integer;
  Zeile: string;
  T1: extended;
begin
  with OpenDialog do
  begin
    InitialDir := Verzeichnis;
    Filter := 'MersenneDateien (*.mrs) |*.mrs';
    FileName := '';
    DefaultExt := 'mrs';
    if Execute then
    begin
      Ausgabe.Lines.LoadFromFile(FileName);
      Zeile := ExtractFileName(FileName);
      Zeile := copy(Zeile, 2, Length(Zeile) - 5);
      EditExponent.Text := Zeile;
      Exponent := StrToInt(EditExponent.Text);
      ZL := trunc(Exponent * LN(2.0) / LN(T)) + 1;
      T1 := StrToFloat(copy(Ausgabe.Lines[0], 1, AusgabeDezi));
      LabelZiffern.Caption := IntToStr(AusgabeDezi * ZL - AusgabeDezi+1 + trunc(LN(T1 + 1) / LN(10)));
      LabelSek.Caption := '0.00 sek.';
    end
    else
      MessageDlg('Keine Datei geladen!', mtInformation, [mbOK], 0);
  end;
end;

procedure TMersenneZahl.FormCreate(Sender: TObject);
begin
  Grenze := trunc(Max * LN(T) / LN(2.0));
  LabelBereich.Caption := '1 bis ' + IntToStr(Grenze);
  LabelZiffern.Caption := '0';
  LabelSek.Caption := '0.00 sek.';
  Verzeichnis := GetCurrentDirUTF8; { *Converted from GetCurrentDir* }
end;

procedure TMersenneZahl.EditExponentKeyPress(Sender: TObject; var Key: char);
begin
  if not (Key in ['0'..'9', #8]) then
    Key := #0;
end;

end.

vielleicht wäre ein ExCo <= 32 auch bei der extended Version hilfreich.Denn 34*34 Bit passen auch nicht mehr in extended mit 64 Bit Mantisse.

Gruß Horst
EDIT:
Schon ab 2^101 geht es schief ( Binäre Suche 2^64 klappte 2^128 nicht, falls voher etwas nicht stimmte ??..
// wieso werden diese unförmigen 11 Dezimalen ausgegeben:

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

2^100
0000126765 0600228229 4014967032 05376
  00126765 0600228229 4014967032 05375
2^101
0000253530 1200456458 8029934064 10752
  00253530 1200456458 8028934064 10751
                         ^
2^102
0000507060 2400912917 6059868128 21504
  00507060 2400912917 6060868128 21503
2^103

Man hätte eine Ziffernstring erzeugen können, den man anschliessend aufteilt.

Horst_H - Do 11.09.14 15:01

Hallo,

Gammatester hat doch schon sehr gute Arbeit geleistet!

Für Exponent = 10*1000*1000 braucht es 0,458 Sekunden für 2^Exponent und mit Ausgabe insgesamt um die 27 Sekunden.
Da die Laufzeit quadratisch ist hätte es statt 7 für 1e6 nun 700 Sekunden nur für die Rechnerei gedauert.
Irgendwie auch knackig kurz ( OK, mp_base hat über 10000 Zeilen ;-) )

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

uses
  ..... FileUtil,mp_types,mp_base;
...

 Zeit:=Time;
 mp_init(mpa);
 mp_set_pow(mpa,2,Exponent);
 ZahlStr := mp_adecimal(mpa);
 mp_clear(mpa);
 Zeit:=Time-Zeit;

Gruß Horst.
EDIT:
ich hatte mal eine Version, ala schnelle Exponentatation in der Mache, um erst einmal Zahlen zur Basis 1E8 zu quadrieren.
Es kommen bei 2^(2^20) = 2^1048576 die gleichen Zahlen, wie bei gammatester, das läßt hoffen ;-)
Der Trick war die Verwendung eines temporären Feldes mit doppelter Breite, also statt 32 Bit dann 64 Bit.
Dadurch muß ich nur alle BASKORCNT = 1843, die Basis wieder korrigieren.
Beim multilpizeiren addiere ich die Zahlen in der entsprechenden Spalte also meist ohne Basiskorrektur, weil Divisionen recht langsam sind.
Damit dauert die Berechnung und Ausgabe 0,94 Sekunden ist ist damit einen Hauch schneller als user profile icon

Gammatester mit knapp über 1 Sekunde.
Keine Sorge, ohne Stringumwandlung braucht user profile icon

Gammatester unerreichbare 0,017 Sekunden.
Quadrieren kann man noch etwas beschleunigen, denn Ziff[a]xZiff[b] = Ziff[b]xZiff[a] kommen als Summand immer in der selben Spalte a+b vor, da kann man also direkt 2* Ziff[a]xZiff[b] aufsummieren, außer a=b .
Also muss Position a <= Position b, bei gleich einfach summieren sonst doppelt.Nicht reden, machen...
DIe Umwandlung in einen String dauert anteilmäßig fast nichts.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

{
   a   b   c   d   e   x   a   b   c   d   e
a* a*a a*b a*c a*d a*e 
b*     b*a b*b b*c b*d b*e   
c*         c*a c*b c*c c*d c*e   
d*             d*a d*b d*c d*d d*e   
e*                 e*a e*b e*c e*d e*e }

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:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:

{$IFDEF FPC}
  {$MODE DELPHI}
  {$OPTIMIZATION ON}
  {$OPTIMIZATION Peephole}
  {$OPTIMIZATION CSE}
  {$OPTIMIZATION ASMCSE}
  {$OPTIMIZATION DFA}
  {$OPTIMIZATION RegVar}
{$Else}
  {$APPTYPE console}
{$Endif}
uses
  sysutils,classes;
const
  Dezimalen     = 8;
  BAS10E8       = 100*1000*1000;//= 10EDezimalen < 2^ 32
  STELLEN_MAX   = 35100 *9 DIV Dezimalen;
  // bei 1e8 alle 1843 bei 1E9 alle 17
  BASKORCNT     = Trunc(High(UINT64) DIV (BAS10E8*BAS10E8))-1;

  AusgabeDezi   = 10;
  ZahlProZeile  = 90 Div (AusgabeDezi+1);
type
  tFeldIndex    = 0..STELLEN_MAX+1;
  tZiffer       = LongWord;
  tpZiffer      = ^tZiffer;
  tTmpZiff      = Uint64;
  tpTmpZiff     = ^tTmpZiff;
  tBasisZiffern = array[tFeldIndex] of tZiffer;
  tTmpZiffern   = array[tFeldIndex] of tTmpZiff;
  tpBasisZiffern = ^tBasisZiffern;
  TLangZahl = record
                lzCount,
                lzBase   : NativeUInt;
                lzZahl   : tBasisZiffern;
              end;
  TTmpLangZahl = record
                   lzCount,
                   lzBase   : NativeUInt;
                   lzZahl   : tTmpZiffern;
                 end;
var
  tmpZ : tTmpLangZahl;
  Ausgabe : TStringlist;

procedure ZahlAusgabe(var Zahl: TLangZahl);
var
  I,K,L: integer;
  Zeile,ZahlStr:String;
begin
  Ausgabe := TStringList.create;
  With Zahl do
  begin
    I := lzCount;
    while lzZahl[i] = 0 do
      dec(i);
    ZahlStr:=Format('%d',[lzZahl[i]]);
    while i > 0 do
    begin
      dec(i);
      ZahlStr:=ZahlStr+Format('%.*d',[Dezimalen,lzZahl[i]]);
    end;
  end;
  // passend '0' davor  setzen
  L := length(ZahlStr);
  K := L MOD AusgabeDezi;
  IF k > 0 then
  begin
    K :=  AusgabeDezi-K;
    setlength(ZahlStr,L+K);
    Move(ZahlStr[1],ZahlStr[K+1],L);
    fillchar(ZahlStr[1],K,'0');
  end;

  L := length(ZahlStr) DIV AusgabeDezi;
  K := 1;
  I := ZahlProZeile;
  Zeile := '';
  repeat
    Zeile := Zeile+' '+copy(ZahlStr,K,AusgabeDezi);
    inc(K,AusgabeDezi);
    dec(i);
    IF I <= 0 then
    begin
      Ausgabe.Add(Zeile);
      Zeile := '';
      i := ZahlProZeile;
    end;
    dec(L);
  until L <= 0;
  if Zeile<>'' then
    Ausgabe.Add(Zeile);

  Ausgabe.savetoFile('out.txt');

  Ausgabe.free;
end;

procedure TmpBasCorrect(var Z : TTmpLangZahl);
var
  i,base: NativeUInt;
  pZiff : tpTmpZiff;
  MulWert,Quot : Uint64;
begin
  Base:= Z.lzbase;
  pZiff := @Z.lzZahl[0];
  Quot := 0;
  For i := Z.lzCount downto 0 do
  begin
    MulWert := pZiff^ +Quot;
    Quot := MulWert DIV Base;
    pZiff^ := MulWert-Quot * Base;
    inc(pZiff);
  end;
  while Quot > 0 do
  begin
    MulWert := pZiff^ +Quot;
    Quot := MulWert DIV Base;
    pZiff^ := MulWert-Quot * Base;
    inc(pZiff);
    inc(Z.lzCount);
  end;
end;

procedure Quadrat_Zahl (var Zahl : tLangZahl);
var
  i,j,F1,cnt : NativeUInt;
  pF2     : tpZiffer;
  pErg    : tpTmpZiff;

begin
  IF Zahl.lzCount > STELLEN_MAX DIV 2 then
  Begin
    Writeln('Zahl zu grosz');
    EXIT;
  end;

  fillChar(tmpZ,SizeOf(tmpZ),#0);
  cnt := Zahl.lzCount;
  tmpZ.lzCount := cnt -1;// dmit es gleich passt
  tmpZ.lzBase  := Zahl.lzBase;;

  i := 0;
  repeat
    inc(tmpZ.lzCount);
    F1   :=  Zahl.lzZahl[i];
    pF2  := @Zahl.lzZahl[0];
    pErg := @tmpZ.lzZahl[i];
    For j := 0 to cnt do
    Begin
      pErg^:= pErg^+ Int64(F1)*pF2^;
      inc(pF2);
      inc(pErg);
    end;
    inc(i);
    IF i MOD BASKORCNT = 0 then
      TmpBasCorrect(TmpZ);
  until i > cnt;
  TmpBasCorrect(TmpZ);
  For i := 0 to tmpZ.lzCount do
    Zahl.lzZahl[i] := tmpZ.lzZahl[i];
  Zahl.lzCount := tmpZ.lzCount;
end;

var
  T1,t0: TDateTime;
  Zahl : tBasisZiffern;
  i    : tZiffer;

  probe :tLangZahl;
Begin
  fillchar(Zahl, SizeOf(Zahl),#0);
  fillchar(Probe,SizeOf(Probe),#0);
  Probe.lzCount := 0;
  Probe.lzBase  := BAS10E8;
  Probe.lzZahl[0] := 2;
  T0 := Time;
  // Ergibt 2^(2^20) = 2^1048576
  For i := 1 to 20 do
    Quadrat_Zahl(Probe);
  ZahlAusgabe(Probe);
  T1:=time;

  writeln(FormatDateTime('HH:NN:SS.ZZZ',T1-t0));
END.

Fiete - Mi 17.09.14 10:41

Moin Horst,
habe noch eine Assemblerprozedur im Archiv gefunden.

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:

procedure TMersenneZahl.Potenz(Var P:TFeld;ExpoDiv,ExMod,ZL,T,Faktor:DWord);
  begin
   asm
           PUSHAD
           MOV EDI,P           // EDI:=Zeiger auf P
           MOV ESI,ExpoDiv     // ESI:=ExpoDiv
           MOV ECX,ZL          // ECX:=ZL
           PUSH ECX            // ECX auf den Stapel
           MOV EBX,Faktor
           PUSH EBX
           MOV EAX,ExMod
           PUSH EAX
           MOV ECX,1           // IZ:=1
           MOV EBP,T           // EBP:=T
           XOR EAX,EAX         // EAX:=0
           CMP ESI,0           // ESI=0?,
           JE @Korrek          // falls ja, dann zu @Korrek
    @ForK: PUSH EDI            // EDI und ECX auf den Stapel,
           PUSH ECX            // da sich die Werte ändern
    @ForL: MOV EDX,[EDI]       // EDX:=P[L] SHL 32!!!
           DIV EBP             // EDX:EAX (64 Bit!!!)div EBP
           MOV [EDI],EDX       // EDX:=H mod T UND EAX:=H div T !!!
           ADD EDI,4           // wegen DWord
           LOOP @ForL          // Schleife für L
           POP ECX             // alten Wert von IZ laden
     @Ut:  CMP EAX,0           // U>0?
           JE @Weiter          // falls nein, dann zu @Weiter
           INC ECX             // Inc(IZ)
           XOR EDX,EDX         // EDX:=0, da sonst die Division falsch wird
           DIV EBP
           MOV [EDI],EDX
           ADD EDI,4
           JMP @Ut
   @Weiter:POP EDI             // alte Werte vom Stapel holen
           DEC ESI             // Dec(K)
           JNE @ForK           // K>0, dann zu @ForK
   @Korrek:POP EAX             // EAX:=ExMod
           POP EBX             // EBX:=Faktor
           POP ECX             // ECX:=ZL
           CMP EAX,0           // ExMod=0?
           JE @ENDE
           XOR EAX,EAX         // EAX:=0
    @ForL2:MOV ESI,EAX         // U:=0
           MOV EAX,[EDI]       // EAX:=P[L]
           MUL EBX             // EAX:=EAX*EBX, EDX:EAX enthält das Ergebnis
           ADD EAX,ESI         // Übertragsbehandlung
           ADC EDX,0
           DIV EBP
           MOV [EDI],EDX
           ADD EDI,4
           LOOP @ForL2
    @ENDE: POPAD
   end
  end;

Braucht nur noch die halbe Zeit. Die Kombination EDX:EAX bringt einiges.
Gruß Fiete

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!