Autor Beitrag
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: Do 05.07.12 22:41 
:gruebel: Okay, dein Add/Reverse in einem versteh ich nicht.

Dafür hab ich nochmal 120% rausgeholt durch viel Assembler. Dieser Ansatz ist damit aber quasi am Ende, jetzt geht nur noch CALLs einsparen durch Inlining oder halt das Kombinierte. Da muss ich aber nochmal drüber nachdenken ;)

ausblenden Quelltext
1:
2:
3:
4:
5:
     48150 it     20000 dig      4.571300 s
1991208502591586282902869 ... 0206730937179519421471319

    241389 it    100000 dig    117.477378 s
1316113735615475349297100 ... 5799080295258450663731151

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Do 05.07.12 22:54 
Hallo Martok,
ich staune immer wieder, was Assembler bringt, und bin beeindruckt. Wenn ich es nur könnte!
Eine Kleinigkeit:
user profile iconMartok hat folgendes geschrieben Zum zitierten Posting springen:
ausblenden Quelltext
1:
2:
3:
4:
5:
     48150 it     20000 dig      4.571300 s
1991208502591586282902869 ... 0206730937179519421471319

    241389 it    100000 dig    117.477378 s
1316113735615475349297100 ... 5799080295258450663731151

Meiner Meinung nach fehlt bei der Zahlausgabe die letzte Stelle. Müsste es nicht
1316113735615475349297100 ... 57990802952584506637311513
sein?
Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Für diesen Beitrag haben gedankt: Martok
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: Do 05.07.12 23:16 
Ja, du hast Recht, es muss natürlich Copy(s, length(s) - 2425); lauten, nicht Copy(s, length(s) - 2525);.

Sinnloseste Optimierung des Tages: bringt knapp 0.1s...

Also ich würde auch lieber was sinnvolles tun als den Assembler spielen, aber Delphi fehlt ja allein schon die RegisterVariables-Optimierung... viel mehr hab ich gar nicht gemacht.

EDIT: Habs verstanden, was user profile iconHorst_H da tut, und als ASM eingebaut:
ausblenden Quelltext
1:
2:
    241389 it    100000 dig     88.742270 s
1316113735615475349297100 ... 7990802952584506637311513

Damit sind wir auf eine Größenordnung ran, ein mir bekannter Physiker sagte mal, das reicht :lol:
Hab auch mal die Zeiten geplottet, dass ist jetzt exakt quadratisch. Mal die Million Stellen vollmachen.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Fr 06.07.12 08:55 
Hallo,


Danke für den Tipp, dass man das Feld nicht halb umkopieren muss.
Kommutativ a+b= b+a ...
Du speicherst Du Summe direkt an Stelle von a und an der Stelle von b
ausblenden Delphi-Quelltext
1:
2:
3:
4:
procedure NumberAddReversed(var Number: TNumber); 
...
    mov byte ptr [ecx], al            // speichern in number
    mov byte ptr [edx], al            // ...

Aber dann muss ich den Übertrag auch in einem zweiten Schritt bearbeiten.
Und diese nicht vorhersagbaren Sprünge kosten doch enorm Zeit ( bei mir 20 Takte (AMD Phenom II 3,2 Ghz ) ), deshalb bringt die Tabelle bei mir etwas, weil ich nur eine Schleife ( leicht vorhersagbar ) ohne Sprünge darin habe.
Wenn Du ohnehin die Überträge später bearbeiten willst, kann man dann nicht auch BSWAP benutzen?
Dann addierst Du, solange es geht in 32-Bit.
Dazu brauchst aber ein paar mehr Register.
Aber mir ist immer noch nicht klar, wie ich einen Faktor 8 in der Geschwindgikeit einbauen könnte.

Gruß Horst
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Fr 06.07.12 09:46 
Hallo Martok und Horst_H,
dass ich mit einfachen Feldern und ohne Assembler nicht an Eure schnellen Programme herankomme, ist mir klar.
Nun dachte ich, wenigstens die Idee eines Consolen-Programms zu nutzen. Mein Versuch:
ausblenden volle Höhe 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:
{$APPTYPE console}
program p196console;

uses
  SysUtils,
  Windows;

const zmax:integer=999;
var k:string;
    i,anz,laenge,laenge1:integer;
    gefunden:boolean;
    z,e:array of byte;
    Time1, Time2, Freq: Int64;
begin
  repeat
    write('Startzahl: ');
    readln(k);
    if k='' then k:='196';
    laenge:=length(k);
    write('maximale Laenge: ');
    readln(zmax);
    if zmax<100 then zmax:=100;
    writeln('');

    setlength(z,zmax+2);
    setlength(e,zmax+2);
    for i:=0 to zmax do begin z[i]:=0; e[i]:=0 end;
    for i:=laenge downto 1 do begin
      z[laenge-i]:=ord(k[i])-48;
      e[laenge-i]:=ord(k[i])-48;
    end;
    anz:=0;
    laenge1:=laenge-1;

    QueryPerformanceFrequency(Freq);
    QueryPerformanceCounter(Time1);

    repeat
      inc(anz);
      for i:=0 to laenge1 do inc(e[i],z[laenge1-i]);
      for i:=0 to laenge1 do begin
        if e[i]>9 then begin
          inc(e[i+1]);
          dec(e[i],10);
        end;
      end;
      if e[laenge]>0 then inc(laenge);
      laenge1:=laenge-1;

      gefunden:=true;
      i:=0;
      repeat
        if e[i]<>e[laenge1-i] then gefunden:=false;
        inc(i);
      until (not gefunden) or (i>laenge div 2);

      if gefunden then
      begin
        writeln('Palindrom im Schritt '+inttostr(anz));
        k:='';
        for i:=0 to laenge1 do k:=chr(e[i]+48)+k;
        writeln(k);
      end
      else
        z:=copy(e,0,laenge);

      if anz mod 2000 = 0 then begin
        QueryPerformanceCounter(Time2);
        writeln(anz:10,' It ',(Time2-Time1)/freq:10:6,' s');
      end;
    until gefunden or (laenge=zmax);

    QueryPerformanceCounter(Time2);
    writeln(anz:10,' It ',(Time2-Time1)/freq:10:6,' s');
    if (laenge=zmax) then
    begin
      writeln('Folgenglied im Schritt '+inttostr(anz));
      writeln('Laenge '+inttostr(laenge));
      k:='';
      for i:=0 to 25 do k:=chr(z[i]+48)+k;
      k:=' ... '+k;
      for i:=laenge-26 to laenge-1 do k:=chr(z[i]+48)+k;
      writeln(k);
    end;
    setlength(z,0);
    setlength(e,0);
    writeln('');
  until false;
end.

bringt mir aber nur 3 Sekunden Gewinn, statt 174 Sekunden bei 100k Stellen, mit "schönem" Formular usw., nun 171 Sekunden.
Ist der Unterschied wirklich so gering oder was mache ich falsch?
Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Fr 06.07.12 09:50 
Moin, falls es noch jemanden interessiert: Im Anhang eine PurePascal-Implemenation von gestern abend (hab's eben noch auf dyn. Arrays umgestellt), mit
ausblenden Quelltext
1:
2:
1316113735615475349297100 ... 7990802952584506637311513
    241389 it    100000 dig     71.290302 s
Mit ASM-Optimierung sollte also noch etwas herauszuholen sein. Hauptfeatures: Wieder einführen des Carry, dafür kein Umkopieren/Reverse (deshalb werden die Iteration immer paarweise gemacht).

Gruß Gammatester
Einloggen, um Attachments anzusehen!
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Fr 06.07.12 11:44 
Hallo,

Dein Kompilat erreicht bei mir:
ausblenden Quelltext
1:
2:
1316113735615475349297100 ... 7990802952584506637311513
    241389 it    100000 dig     75.367305 s

Mit FPC2.6.0 kompiliert:
ausblenden Quelltext
1:
2:
1316113735615475349297100 ... 7990802952584506637311513
    241389 it    100000 dig     89.618406 s

Mit meinem SumCarryFeld wird es wieder schnell.
ausblenden Quelltext
1:
2:
1316113735615475349297100 ... 7990802952584506637311513
    241389 it    100000 dig     52.276415 s

Meine ganze Pointerei zuvor hat sich also nicht gelohnt, auch das noch eine reine Pascal Ausarbeitung.

Ob Byte oder word gab bei mir keinen Laufzeitunterschied.
Freepascal mag diese dynamischen Felder nicht besonders, zwei Befehle um die Adreesse des Feldes heraus zu bekommen, wobei diese auf dem Stack liegt und das innerhalb der Schleife 2-fach jedesmal ...

Gruß Horst
Einloggen, um Attachments anzusehen!
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Fr 06.07.12 12:20 
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Mit meinem SumCarryFeld wird es wieder schnell.
ausblenden Quelltext
1:
2:
1316113735615475349297100 ... 7990802952584506637311513
    241389 it    100000 dig     52.276415 s

...
Freepascal mag diese dynamischen Felder nicht besonders

In der Tat :zustimm: Sehr schnell Deine Modifikation :!: Mit Delphi hat man jetzt schon brauchbare Zeiten, auf meinem Rechner:
ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
FPC2.6.0
=
1316113735615475349297100 ... 7990802952584506637311513
    241389 it    100000 dig     54.138380 s

Delphi 12
=
1316113735615475349297100 ... 7990802952584506637311513
    241389 it    100000 dig     35.098787 s
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 918
Erhaltene Danke: 158

Win 10
VS 2013, VS2015
BeitragVerfasst: Fr 06.07.12 13:44 
Hi,
ich habe das ganze mal in C# umgesetzt :-)

Ich erreiche bislang folgende Werte:
Zitat:
241390 Iterationen in 62,35 Sekunden.
Die Zahl hat jetzt 100000 Stellen.


Ich habe leider schon Pointer einsetzen müssen (-20% Laufzeit) um darauf zu kommen. Zudem wird im Moment nicht geprüft ob ein Palindrom vorhanden ist :angel:
Außerdem habe ich eine MultiThreading Variante gebaut, aber die ist deutlich langsamer - Laufzeit +160%
Ich habe hier aber nicht ganz den Überblick, was ihr schon alles Optimiert habt; das SumCarryFeld hat bei mir keinen Vorteil gebracht. (Array in C# sind wohl nicht so perfomant) könnte ich aber nochmal mit Pointern probieren.
Edit:
Okay, mit dem SumCarryFeld und Pointerzugriff darauf bin ich noch etwas schneller:
Zitat:
241390 Iterationen in 31,09 Sekunden.
Die Zahl hat jetzt 100000 Stellen.

Ich baue dann heute Abend mal die Palindromüberprüfung ein, dann wird das vergleichbar :)

Für diesen Beitrag haben gedankt: Martok
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: Fr 06.07.12 16:14 
Kurze Durchsage zwischendurch: die Programme an sich funktionieren:
ausblenden Quelltext
1:
2:
3:
4:
5:
   2415600 it    999900 dig       10519.0 s
   2415800 it    999983 dig       10520.5 s
=
   2415836 it   1000000 dig  10520.815838 s
1321620866345900792403087 ... 1880303207999544559027122

Richtige Stellenzahl nach richtigen Iterationen mit richtigen ersten 25 (Vgl.)


Das von user profile iconGammatester ist bei mir wesentlich langsamer, was mach ich falsch?
ausblenden Quelltext
1:
2:
1316113735615475349297100 ... 7990802952584506637311513
    241389 it    100000 dig    135.658393 s

Die Feldzugriffe sind allerdings tödlich, ja. So als Record hatte ich das auch mal kurz, das ist nicht wirklich gut. Denke damit das was wird muss man ein statisches Array hinten rein hängen, und dann den ganzen Record per ReallocMem selber verwalten:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
  TNumber = packed record
    Length: integer;
    Digits: array[0..0of TDigit;
  end;


user profile iconjfheins: endlich mal jemand mit einem Compiler, der ordentlichen Code erzeugt, und wenns nur JIT ist :)

EDIT: 2 Sekunden geholt, indem ich die Carries nicht mehr einzeln nachführe sondern gleich mit behandle. Und eine echte Überraschung: ein Tabellen-Lookup ist langsamer als echtes CMP/SUB. Hätte ich nicht erwartet.

EDIT2: what
ausblenden Das sind 20 Sekunden ggü. meinem letzten
1:
2:
    241389 it    100000 dig     67.761056 s
1316113735615475349297100 ... 7990802952584506637311513

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Fr 06.07.12 20:11 
Hallo,
das SumCarryFeld von Horst_H ist genial. Selbst bei meinem Programm und meiner "alten Mühle" konnte ich die Zeit fast halbieren. Danke.
ausblenden Quelltext
1:
2:
    241389 it    100000 dig          82.5 s
13161137356154753492971008 ... 57990802952584506637311513

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein


Zuletzt bearbeitet von Mathematiker am So 04.11.12 00:56, insgesamt 2-mal bearbeitet
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 918
Erhaltene Danke: 158

Win 10
VS 2013, VS2015
BeitragVerfasst: Fr 06.07.12 20:58 
Okay, also hier mal meine exe Datei.

Er schafft jetzt auf meinem Rechner:
Zitat:
241389 Iterationen in 31,21 Sekunden.
Die Zahl hat 100000 Stellen.
Palindrom? False
131611373561547534929...02952584506637311513


Es wird auf Palindrome geprüft (aber nicht abgebrochen) und nach dem Cancel-Button wird die geplante Anzahl an Iterationen ausgegeben.
Sonst geht's eigentlich schon ganz gut :-)
Einloggen, um Attachments anzusehen!
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Fr 06.07.12 21:07 
Hallo,

mal eine ganz andere Überlegung, ob es zum Palindrom kommt oder nicht.
Gäbe es keine Überträge bei Addition hat man immer ein Palindrom.
Kein Carry vorgekommen -> Palindrom
Carry vorgekommen -> kein Palindrom, denn Carry wirkt in eine Richtung und ist damit unsymmetrisch.Muesste man mal testen, indem man die Summe der Carry erzeugt.
Also bestimmt man eigentlich die Wahrscheinlichkeit, dass alle Stelle[i]+Stelle[Laenge-i] in der Summe unter der Basis bleiben.
Mit zunehmender Stellenzahl muss die doch verschwindet gering sein.

Ist es nicht auch erstaunlich, dass es 2,41... Iterationen braucht, bis zu einer neue Stelle kommt.
Die mittlere Summe zweier zufälliger Ziffern zur Basis B ist doch (B-1), also müsste nach (1+1/Basis) eine neue Ziffern kommen, aber die Neue Ziffer ist immer der Übertrag und damit 1.
Im Dezimalsystem ist das 1,1. Die mittlere Ziffer ist (Basis-1)/2 = 4.5
10 = 2,599...^2,41, das hieße die mittlere Ziffer in der ersten und letzten Stelle wäre 2,6
Zu Beginn ist die oberste Ziffer 1 und die unterste <= der zweitobersten Stelle ( Carry wandert ja nur nach oben ) also zwischen 0 und 8, nie die 9.
1.Iteration 1+ (0..8 ) ergibt im Schnitt 5 bleibt immer kleiner Basis
2.Iteration Müsste doch jetzt im Mittel einen Überlauf erzeugen, tut es aber nicht.
Das kann der Mathematiker sicher erklären, er hat ja jetzt etwas mehr Zeit, weil das Programm schneller ist ;-)

Gruß Horst
P.S.
Was habt jheins für einen schnellen Rechner??p196_Net
Einloggen, um Attachments anzusehen!
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Fr 06.07.12 21:49 
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Gäbe es keine Überträge bei Addition hat man immer ein Palindrom.
Kein Carry vorgekommen -> Palindrom
Carry vorgekommen -> kein Palindrom, denn Carry wirkt in eine Richtung und ist damit unsymmetrisch.

Das ist mit größter Wahrscheinlichkeit so. Einen Beweis kann ich aber nicht liefern. Leider.
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Was habt jheins für einen schnellen Rechner??

Das möchte ich auch wissen. Bei mir braucht sein Programm 99,29 Sekunden für 100k Stellen.
Übrigens könnt Ihr alle stolz sein. "Mathematica" brauchte bei einem Test 10,6 Stunden für 250000 Iterationen.
mathworld.wolfram.com/196-Algorithm.html :zwinker:
Das war zwar schon vor 10 Jahren auf einem 450 MHz Pentium II, aber wer kann schon von sich behaupten besser als "Mathematica" zu sein.
Man kann ja so rechnen: Mein PC 1,7 GHz ist 3,8 mal schneller als der genannte Test-PC. D.h., ich muss nach 2 Stunden 48 min 250000 Iterationen haben. Und somit sind wir alle mindestens 100mal schneller als "Mathematica". :beer:

@jheins: Wie schaffst Du es, dass Dein Programm mit Windows-Oberfläche nur 15 k groß ist?

Beste Grüße
Mathematiker

Nachtrag: "Carry vorgekommen -> kein Palindrom" stimmt doch nicht. Beispiel: 999222 wird zum Palindrom 1222221.

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein


Zuletzt bearbeitet von Mathematiker am Fr 06.07.12 23:23, insgesamt 2-mal bearbeitet
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: Fr 06.07.12 21:59 
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
mal eine ganz andere Überlegung, ob es zum Palindrom kommt oder nicht.
Gäbe es keine Überträge bei Addition hat man immer ein Palindrom.
Kein Carry vorgekommen -> Palindrom
Carry vorgekommen -> kein Palindrom, denn Carry wirkt in eine Richtung und ist damit unsymmetrisch.Muesste man mal testen, indem man die Summe der Carry erzeugt.
Also bestimmt man eigentlich die Wahrscheinlichkeit, dass alle Stelle[i]+Stelle[Laenge-i] in der Summe unter der Basis bleiben.
Mit zunehmender Stellenzahl muss die doch verschwindet gering sein.

Hihi.

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Übrigens könnt Ihr alle stolz sein. "Mathematica" brauchte bei einem Test 10,6 Stunden für 250000 Iterationen.
Interessant wäre ja das Programm, um das heute mal laufen zu lassen...

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
@jheins: Wie schaffst Du es, dass Dein Programm mit Windows-Oberfläche nur 15 k groß ist?
.NET. Die restlichen 250MB sind im Framework.


Aktueller Stand: 62s für 100k Stellen, nach 5550s 922884 Stellen. Laut AMD CodeAnalyst das langsamste:
ausblenden uNumbers.pas
 
217:
218:
219:
220:
{ ... }
asm
        mov al, byte ptr [edx]           //wert
        mov byte ptr [ecx], al
end;
Klar - read-modify-write, gleich zweimal. Ein mov m8,m8 wäre da echt praktisch. Ist leider der Carry-Durchlauf, da brauch ich die einzeln...

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Fr 06.07.12 22:39 
Hallo,

dann hat sich das mit der Summe der Carry erledigt.
Aber ist Dir im dem Text www.p196.org/files/kruppa.txt aufgefallen, das Summe der zu addierenden Ziffern immer 11 oder 0 ist. Aber auch das zu testen ist Kokolores.

Nein , ich benutze kein mathematica, das ist was für Mathematiker.

Gruß Horst
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Fr 06.07.12 22:45 
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Nein , ich benutze kein mathematica, das ist was für Mathematiker.

Aber nicht für "arme" Mathematiker. 3185 € für die Standard-Version von Mathematica ist mir einfach zu "billig". :lol:
Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 918
Erhaltene Danke: 158

Win 10
VS 2013, VS2015
BeitragVerfasst: Sa 07.07.12 00:50 
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:

[...]
Was habt jheins für einen schnellen Rechner??


user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:

[...]
Das möchte ich auch wissen. Bei mir braucht sein Programm 99,29 Sekunden für 100k Stellen.
[...]
@jheins: Wie schaffst Du es, dass Dein Programm mit Windows-Oberfläche nur 15 k groß ist?


Hallo,
ich habe einen Intel Q6600 aus dem Jahr 2009, übertaktet auf 3 GHz. Also ohne TurboBoost und eigentlich nicht besonders schnell. Dachte ich.
Da hatte ich mich schon gefreut dass ich als Späteinsteiger mithalten kann und dann sowas :nixweiss:

Das mit der exe-Größe liegt, wie schon richtig gesagt, am .net Framework. Momentan baut das Programm auf .net 4 auf.

Okay, Gegenfrage: was habt ihr denn so für (langsame) Rechner?
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Sa 07.07.12 06:32 
user profile iconjfheins hat folgendes geschrieben Zum zitierten Posting springen:
Da hatte ich mich schon gefreut dass ich als Späteinsteiger mithalten kann und dann sowas :nixweiss:

Du kannst auf jeden Fall mithalten. Auf dem Rechner mit 1,7 GHz braucht Dein Programm, wie schon gesagt, 99 Sekunden; auf einem zweiten Rechner 2,6 GHz nur 43 Sekunden, ist also richtig schnell.
Für mein Programm dagegen ermittle ich: 82 s auf dem ersten und 56 s auf dem zweiten PC. Du überholst mich also deutlich.
Es liegt scheinbar nicht nur an der Taktfrequenz des Prozessors. Kann es auch an Windows selbst liegen? Der 1.PC läuft mit Vista, der zweite mit Windows 7. Ich habe keine Ahnung.
Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Sa 07.07.12 08:01 
Hallo,

für AMD CPU'S ist die Net Framework wohl nicht so performant.Wie oben geschrieben braucht es mit 3,2 Ghz 54 Sekunden.
Ich hatte gehofft, es wäre eine Core i5/i7 CPU die ja doch erheblich mehr pro Takt erledigen.
Ich verstehe das nicht:
www.tomshardware.de/...ichte-240232-11.html
Wo taucht denn da die Q6600 auf beim Drystone-Test auf , garnicht mehr!
Bei multimedia-integer (MMX SSE ) aber an allen AMD vorbei, und zwar mehr als doppelt so schnell wie diese.
NET 4.5 habe ich mal probiert. Es bringt eine Reduktion des Speicherbedarfs zur Laufzeit von 18 auf 15 MB und eine Laufzeitreduktion ( bei mir ) von 54 auf 50 Sekunden.
Ich tippe also auf den Einsatz von SSE und Konsorten.
Durch das SumCarryFeld braucht es ja auch keinen Übertrag zwischen den Bytes in der Rechnung, es sind nur Wertzuweisungen.
Aber wir sind noch Ewigkeiten von 51 Sekunden für 250000 Stellen weg.Das sind umgerechnet 8.1 Sekunden für 100000 Stellen und das auf einem Pentium4 2.8 Ghz mit HyperThreading, wenn ich das recht erinnere.
//250000 Stellen in 320 Sekunden bei maximal 22 MB belegt.
Selbst mit Multithreading auf 2 CPUs müssten wir die Geschwindigkeit verdreifachen.

Gruß Horst

P.S.:
Ein paar Nebensächlichkeiten:
Führende Nullen werden bei der Stringeingabe nicht gekürzt und Palindrome wie 990099 werden nicht abgefangen.Auch wenn dieses kein Palindrom in >50000 Iterationen mehr wird.
Das ist Feintuning zum Schluß, falls es den gibt.