Autor |
Beitrag |
Bergmann89
Beiträge: 1742
Erhaltene Danke: 72
Win7 x64, Ubuntu 11.10
Delphi 7 Personal, Lazarus/FPC 2.2.4, C, C++, C# (Visual Studio 2010), PHP, Java (Netbeans, Eclipse)
|
Verfasst: Sa 07.07.12 17:36
Hey Leute,
ich verfolge das Thema jetzt schon ne Weile. Leider hatte ich bis jetzt noch nicht die Zeit selbst was zu implementieren, bzw. hab ich mich mit Martok unterhalten und er hat meine Illusionen zerstört, jemals einen besseren Algorithmus zu finden als er Doch gerade eben unter der Dusche ist mir ein Licht aufgegangen. Wie wäre es, wenn man die Berechnungen auf die Grafikkarte auslagert? Da läuft das Ganze dann schön parallel. Zwei Offscreen-Render-Buffer für die Daten. Der eine zum lesen als Textur gebunden, der zweite als Target für den Renderer. Im nächsten Durchlauf wird dann getauscht. Nen simplen Shader, der die Daten aus der Textur ließt und berechnet. Das einzige wofür mir noch nix eingefallen ist, ist das Carry. Man kann nicht quer über den ganzen Buffer schreiben, sondern nur an dem Pixel, an dem man sich gerade befindet. Wenn wir dazu ne Lösung finden, dann sollte das alles andere in den Schatten stellen. Denn dann wird die komplette Addition von den 3200 Stream-Prozessoren meiner Graka erledigt
Ne Alternative dazu wäre CUDA, oder ein vergleichbares Toolkit.
MfG Bergmann.
_________________ Ich weiß nicht viel, lern aber dafür umso schneller^^
|
|
jfheins
Beiträge: 918
Erhaltene Danke: 158
Win 10
VS 2013, VS2015
|
Verfasst: Sa 07.07.12 19:32
Hi,
ich habe eine neue Version am Start Da die Geschwindigkeit ja doch nicht sooo schlecht scheint habe ich mir die mühe gemacht und die Usability verbessert. (Geschwindigkeit sollte ungefähr gleich geblieben sein)
- Berechnung erfolgt jetzt in einem seperaten Thread
- Berechnung lässt sich pausieren und wiederaufnahmen
- Quellcode wurde kommentiert und aufgeräumt
Wenn ihr auf den "Weiter"-Button klickt, werden nochmal x Iterationen berechnet. Also wenn ihr auf Pause klickt und es wurden 24896 von 50000 Iterationen berechnet und ihr klickt auf Weiter, hört das Programm erst bei 74896 auf. Iterationen und Zeit werden aufsummiert, gemessen wird auch nur die Rechenzeit.
Und damit ihr auch was davon habt, habe ich den Sourcecode angehängt
Btw.: Für jede Ziffer einen Int32 zu benutzen ist zwar leider etwas Platzverschwendung, aber deutlich schneller als byte. Int64 ist auf meinem System nochmal 3% schneller....
@Bergmann: Ich hatte auch schon die Idee, meinen Quadcore besser auszulasten. Leider ist das Problem nicht besonders gut parallelisierbar
Eine Iteration ließe sich schon in 4 seperate Teile einteilen, nur der Übertrag zwischen den Blöcken muss dann am Schluss sequentiell eingepflegt werden.
Da eine Iteration auf meiner CPU vll. so 250µs dauert dürfte die Kommunikation und Synchronisierung erheblich sein.
Zumindest bei den Zahlen wie wir sie hier gerade rechnen. Wenn die Zahl groß genug wird, lohnt es sich schon.
Hinzu kommt, dass du die Blockgröße ständig anpassen musst, da die Zahl ja alle paar Iterationen größer wird. Blockgrößen ändern heißt auch wieder Daten austauschen.
Ich hab es gerade mal rechnen lassen, und die Dauer einer Iteration steigt natürlich an. Nach 1 Mio Stellen (2,4 Mio Iterationen) dauert eine Iteration bei mir schon 2,7 ms.
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Sa 07.07.12 22:11
Hallo jfheins,
jfheins hat folgendes geschrieben : | - Berechnung lässt sich pausieren und wiederaufnahmen |
Schön, auf diese Idee hätte ich auch kommen können, bin es aber natürlich nicht.
Die Geschwindigkeit ist auf meinem PC tatsächlich etwa gleich.
jfheins hat folgendes geschrieben : | Für jede Ziffer einen Int32 zu benutzen ist zwar leider etwas Platzverschwendung, aber deutlich schneller als byte. Int64 ist auf meinem System nochmal 3% schneller.... |
Irgendwie müssen PCs doch manchmal vollkommen verschieden sein. Wenn ich bei meinem Programm von byte zu integer übergehe, erhöht sich der Zeitbedarf auf das Dreifache, bei int64 noch einmal auf das Doppelte.
Fazit: Ich brauche einen neuen Computer.
@Bergmann89: Klingt richtig interessant und ich hoffe sehr, dass es Dir gelingt. Wenn ich nur wüsste, wovon du redest. 3200 Stream-Prozessoren??? Ich verstehe gar nichts.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Sa 07.07.12 23:20
Hallo ihr,
auch, wenn ich Zahlentheorie per se nicht so interessant finde (es ist auf dem Gebiet einfach viel zu einfach, Probleme abzuwandeln. So könnte ich jederzeit 50 Aussagen im Stil der Goldbach'schen Vermutung aufstellen, "jede Zahl mit * lässt sich als Summe von n Zahlen mit # schreiben", und wenn mir jemand zeigt, dass die Aussage für n falsch ist vermute ich neu für n+1 ): hier mal mein Ketchup dazu, wirklich weiterhelfen kann ich euch leider nicht.
Erstmal muss man wie bei jedem Problem, das von der Wahl des Stellenwertsystems abhängt, einsehen, dass es leider hässlich ist. (Tut mir leid, liebes Problem ). Der Sinn hinter der Einführung von Basen ist eigentlich, dass die betrachteten Operationen Basisunabhängig funktionieren. Eine besondere Eigenschaft hat 196 bestimmt nicht, höchstens das Paar (196, 10).
Ohne Carry ist die Sache eigentlich klar, an Stelle i steht nach n Rekursionsaufrufen:
>> 2^{n-1} \cdot (x[i] + x[len - i]).
Jetzt dachte ich eigentlich, man könnte den Effekt des Carry mit einer unendlichen Matrix beschreiben und davon Potenzen bilden. Leider ändert sich mit Carry ständig die Berechnungsvorschrift, und zwar bei jedem Überlauf von x[len], d.h. wenn sich len ändert.
Wenn das wenigstens ein bisschen seltener passieren könnte, wäre dazwischen durchaus noch etwas Optimierung mit theoretischen Hilfsmitteln drin, so lohnt sich das kaum.
Auch sehr ungünstig ist, dass aus einem Palindrom im nächsten Schritt wieder ein nicht-Palindrom werden kann: Das hat meine bisherigen Bemühungen zerstört, die Anzahl der Prüfvorgänge zwischen Rekursionsaufrufen zu reduzieren. Eventuell lässt sich aber doch noch etwas darüber aussagen, bei welchen Zahlen oder Carrys kein Palindrom entstehen kann; womöglich sogar für die nächsten n Aufrufe. Da sehe ich so das meißte Potential, in diesen Fällen könnte man in einer Schleife mehrere Rekursionsschritte in einem machen.
Wenn für Basis 2 schon gezeigt ist, dass jede Startposition irgendwann ein Palindrom liefert, könnte man auch einmal versuchen, die einzelnen Ziffern durch ihre Binärdarstellung zu substituieren. So erhalten wir eine 0-1-Folge, über die man mit diesem Vorwissen vielleicht etwas aussagen kann.
PS: @Martok, der Mensch ist witzig. Was er hier unten schreibt, trifft auf Mathematik doch gerade nicht zu. Wir können Probleme abstrakt formulieren, die weit größer sind als die Anzahl der Zustände unseres Universums, und deren Wahrheitswert ist unabhängig von der konkreten Prüfbarkeit.
Die meißten Mathematiker akzeptieren ja sogar das Auswahlaxiom, mit dem sich prinzipiell nicht nachvollziehbare und niemals konstruierbare Aussagen ableiten lassen. Sogar die Menge der reellen Zahlen ist schon ein solches Objekt: Die berechenbaren Zahlen (durch eine endliche Maschine) sind abzählbar und damit ein verschwindend kleiner Teil. Das heißt, niemand hat oder wird jemals eine "echte" reelle Zahl sehen .
_________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 08.07.12 00:08
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: So 08.07.12 00:12
Hidden hat folgendes geschrieben : | Wenn für Basis 2 schon gezeigt ist, dass jede Startposition irgendwann ein Palindrom liefert, könnte man auch einmal versuchen, die einzelnen Ziffern durch ihre Binärdarstellung zu substituieren. So erhalten wir eine 0-1-Folge, über die man mit diesem Vorwissen vielleicht etwas aussagen kann. |
Tut mir leid, aber im Dualsystem ist es sicher, dass nicht(!) jede Zahl schließlich zu einem Palindrom führt. 10110 wird dort niemals palindromisch.
Ansonsten stimme ich Dir schon zu, dass nicht die 196 an sich besonders ist, sondern nur im Dezimalsystem.
Widersprechen muss ich aber auch. Dieses Problem ist nicht wirklich hässlich, es ist wunderschön.
Schließlich beschäftigt es hier eine Menge Mitstreiter. Und das soll ein Problem ja.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: So 08.07.12 07:05
Hallo,
aber der "sittliche Nährwert" ist gegen Null.
Es rettet nicht die Welt, es schadet ihr nicht.
OK, da hat jemand mehrere Jahre seinen Rechner und Umgebung mit geheizt.
@Hidden:
Ohne Carry ist im nächsten Schritt ein Palindrom da.
Schliesslich schreibt man die Summe, der um die mittlere Stelle gespiegelten Ziffern, an diese beiden Stelle.
In dem Text über Beispiele, in denen mit Übertrag ein Palindrom erzeugt wird, www.p196.org/files/kruppa.txt , ist die Summe der Ziffern entweder Basis+1, hier also 11 oder beide Ziffern 0.
Diese Zahlen haben ein einfaches Bildungsgesetz.
Erzeuge eine Hälfte einer Zahl, packe dort beliebig Ziffern aus [0,2..Basis-1] rein. Packe an die gespiegelte Stelle die Ergänzung zu Basis+1 oder wenn es 0 ist die 0.Wenn die Zahl eine ungerade Zahl an Ziffern braucht, packe eine 0 in die Mitte.
Wie sagt Homer Simpson: "Langweilig".
Vielleicht sollte man es umdrehen.
Ich habe ein Palindrom, wie viele Aufteilungen in eine Summe zweier Zahlen, deren Ziffern gespiegelt sind, sind möglich.
Wenn man rekursiv betrachtet, kann man jede dieser Zahlen wieder aufteilen.Witzig, die Zahlen werden immer kürzer, aber immer mehr, was natürlich Unsinn ist.
Also weitermachen:
"Ein Neger mit Gazelle zagt im Regen nie"
Gruß Horst
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: So 08.07.12 23:35
Horst_H hat folgendes geschrieben : | Es rettet nicht die Welt, es schadet ihr nicht.
OK, da hat jemand mehrere Jahre seinen Rechner und Umgebung mit geheizt. |
Wow! Die Ursache für die sagenumwobene "globale Erwärmung" ist gefunden. Der 196-Algorithmus!
Ich werde also meinen Rechner jetzt 24 h am Tag laufen lassen. Bei uns schüttet es seit Tagen. Vielleicht wird es ja wärmer.
Nebenbei: Mein aktueller Stand 77 s für 100k Stellen, durch Weiterverwendung der Summe. An Martoks Assembler-Lösung oder jfheins' C#-Programm werde ich aber niemals(!) 'rankommen.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 09.07.12 06:38
Hallo,
jetzt muss man das Verfahren verändern, irgendwie mehrere Ziffern gleichzeitig, wie Martok es mal probiert hat mit BSWAP, aber man darf dabei den Übergang nicht verpassen, wo man dies nicht mehr machen kann.Wenn man 4 Ziffern gleichzeitig verarbeitet muss man bei einem Abstand <8 wieder mit einzelnen Ziffern arbeiten.
Bei Multlithreading kann man das Carry doch zu Beginn schon mal grob abschätzen, indem beispielsweise alle Threads ihre jeweiligen letzten X Ziffern addieren und diesen Übertrag dem nächstem Thread bereitstellen läßt und dann alle gleichzeitig loslegen.
Das es dann eine Korrektur geben muss wird mit zunehmenden X immer unwahrscheinlicher, denn es müsste eine Ziffernfolge nur aus Basis-1 entstehen.Bei 8 Ziffern wohl in der Nähe von Basis^-8.
Gruß Horst
|
|
papa69
Beiträge: 79
Erhaltene Danke: 23
Win 10, Ubuntu
C#, Java, C
|
Verfasst: Mo 09.07.12 10:55
Hallo zusammen,
ihr habt mich ja von Anfang an mit DIESEM Pa(l)indrom-Virus angesteckt .... grrr
JA: Mathe macht Spass, wenn es so gut verkauft wird !!!
Aber mal zu was anderem: Es geht ja wohl darum, mit der "196" ein Palindrom zu finden ?!
Auf Geschwindigkeit sollte es dabei eigentlich nicht ankommen.
Letzte Nacht kam mir dann fogende Idee:
C#-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| [Denkansatz]
Was ihr braucht:
[*] das Programm, um die (Teil-) Summen auszurechnen [*] ein weiteres Programm, um diese (Teil-) Summen auf ein Palindrom zu prüfen
Von verteiltem Rechnen habt ihr doch schon gehört !? Also fehlt noch das 3. (bzw. das nach dem 1. kommende) Programm, wechles eine gewisse Anzahl von errechneten (Teil-) Summen dem 2. Programm zur Verfügung stellt... [/Denkansatz] |
_________________ Daniel Bauer
... fatal ist nur, wenn sich das Licht am Ende des Tunnels als entgegenkommender ICE entpuppt ...
|
|
jfheins
Beiträge: 918
Erhaltene Danke: 158
Win 10
VS 2013, VS2015
|
Verfasst: Mo 09.07.12 14:27
Hi,
also auf Geschwindigkeit kommt es natürlich schon an. Es ist ja (zumindest in meinen Augen) so gut wie sicher, dass 196 niemals zu einem Palindrom wird.
Was wir hier machen ist also ein "Wer schafft die Iterationen in der kürzesten Zeit" oder so ähnlich
Dein Ansatz zur Parallelisierung ist leider relativ nutzlos, da die Prüfung relativ flott geht.
Ich habe die Prüfung ja erst nachträglich eingebaut, daher lässt sich das gut vergleichen:
Ohne Prüfung: 241390 Iterationen in 31,09 Sekunden.
Mit Prüfung: 241389 Iterationen in 31,21 Sekunden.
Der Grund dafür dürfte in der Prüfung liegen: Logischerweise bricht man diese sofort ab, wenn sicher ist dass die Zahl kein Palindrom ist. Meistens ist schon noch den ersten 3 Ziffern klar, dass es kein Palindrom ist und die Prüfung ist beendet.
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 09.07.12 15:43
Hallo,
ich denke darüber nach, SumCarry um eine Variante zu erweitern und mit einem vierstelligem Feld zu arbeiten.
Kost' ja nix.
Beispiel:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7:
| type record ZiffernfolgeOhneCarry : Dword; ZiffernfolgeMitCarry : Dword; CarryOhneCarray : word; CarryMitCarray : word; end; |
Dazu will ich die Feldposition umrechnen
2497-> (((2*16 +4)*16+9)*16+7 = 2 shl 12 + 4 shl 8 + 9 shl 4 + 7
Beispiel:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| 2497 -> (((2*16 +4)*16+9)*16+7 ==> Feldnummer 9367 Feld[9367].ZiffernfolgeOhneCarry = $00040309 ( 0* 4096 +4*256+3*16+9 ) Feld[9367].ZiffernfolgeMitCarry = $00040400 Feld[9367].CarryOhneCarray = 1 Feld[9367].CarryMitCarray = 1
4455 -> (((4*16 +4)*16+5)*16+5 ==> Feldnummer 17493 Feld[17493].ZiffernfolgeOhneCarry = $09090909 Feld[17493].ZiffernfolgeMitCarry = $00000000 Feld[17493].CarryOhneCarray = 0 Feld[17493].CarryMitCarray = 1 |
Fragt sich nur, ob die Rechnerei für die Feldposition nicht zu aufwendig ist.
Oder man sogar mit *Basis statt shl rechnen kann, das spart ja einiges an Platz. ( Nur noch 120 kb )
In der untere Hälfte Der neuen Zahl kann man Carry ja mitnehmen, aber in der oberen nicht.
Deshalb habe ich an ein Feld/Liste für die Übertrage der oberen Hälfte gedacht, indem nur Pos in der Zahl, die den Übertrag korrigiert haben muss, eintrage.
Mal schauen, ob ich richtig ziele.
Gruß Horst
|
|
Palladin007
Beiträge: 1282
Erhaltene Danke: 182
Windows 11 x64 Pro
C# (Visual Studio Preview)
|
Verfasst: Di 10.07.12 02:30
Morgen ^^
Das Eingangs-Problem ist ein mathematisches Problem und damit ein gutes Problem zum Freizeit-Vertreib mit Programmieren. ^^
Ich hab mich auch mal daran versucht und erst ein Konsolen-Programm geschrieben und anschließend eine Forms-Anwendung, die die gleichen Methoden nutzt. exe und Quellcode im Anhang.
Da ich das bisher mit Decimalzahlen gemacht habe, liege ich nach dem, was mir Mathematiker gesagt habe, etwas hinten, oder?
Es wäre trotzdem nett, wenn ihr mal da drüber schauen und euren Senf abgeben könnt. ^^
Wer dabei nur an der Berechnung interessiert ist, schaut einfach die statische Klasse Palindrom an, da ist alles drin.
Kommentiert habe ich noch nicht, kann das aber gerne auf Nachfrage machen.
Da ich selber nur wenig Ahnung davon habe, wie man im Dualsystem rechnet, würde ich mich freuen, wenn mir jemand eine kurzen Crash-Kurs gibt, wie das abläuft und zu welchen Schlüssen ihr hier bisher gekommen seid, da ich von Delphi keine Ahnung habe und mir das drei Seiten lange lesen ersparen würde.
Wenn nicht, dann muss ich mich wohl hinein lesen -.-
Auf jeden Fall werde ich mir dazu das letzte Programm von jfheins anschauen und mir etwas abkupfern.
Aber bis dahin ist das meine Kampfansage für den Wettbewerb, bei dem ich nun freudig mit mischen werde. ^^
Gruß
Einloggen, um Attachments anzusehen!
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 10.07.12 06:59
Hallo,
guten Morgen, ich erhalte eine unerwartete Ausgabe:
Quelltext 1: 2: 3: 4: 5:
| Eingabe: 196 Es gab einen Fehler: Der Wert liegt außerhalb des erwarteten Bereichs.
Gesammte Zeit: 0 ms |
Gruß Horst
EDIT:
Wo war ich denn mit meinen Gedanken, einen Post darüber.
Zeile = Zahl1 und Spalte = Zahl2 geht ja vom Platz her fast nicht, und Zugriffszeit auf den Hauptspeicher ist ja dann ewig.
Es sind nur 10000+9999 Felder und diese sehen so aus. (
Zahl1, Zahl2 umrechnen nach word Summe bilden und dann auf das Feld zugreifen:
Delphi-Quelltext 1: 2: 3: 4: 5:
| Summe "2442" -> (((2*10 +4)*10+4)*10+2 ==> Feldnummer 2442 Feld[9367].ZiffernfolgeOhneCarry = $02040402 Feld[9367].ZiffernfolgeMitCarry = $02040403 Feld[9367].CarryOhneCarray = 0 Feld[9367].CarryMitCarray = 0 |
Diese Umrechnerei ist aber langsam, da gibt sicher nach ein analoges "ASCII" -> INT, das schnell ist.
|
|
Palladin007
Beiträge: 1282
Erhaltene Danke: 182
Windows 11 x64 Pro
C# (Visual Studio Preview)
|
Verfasst: Di 10.07.12 18:33
@Horst_H:
Das liegt daran, dass die Zahl bei der Berechnung den Wertebereich sprengt.
Das kann ich auch nicht ändern, bis ich nicht eine Möglichkeit gefunden habe, größere Zahlen zu berechnen.
Die Gesamtzeit darunter berechnen die Zeit aller Berechnungen.
Du kannst beliebig viele Zahlen eingeben, aber der Fehler oben wird immer auftreten, wenn eine Zahl im Berechnungs-Prozess den Wertebereich von double sprengt.
196 ist dabei die einzige kleine Zahl, die mir aufgefallen ist, dass sie diesen Fehler bringt. Alle anderen haben dann schon eine große Zahl Stellen und auch dann heißt das nicht, dass sie den Bereich sprengen.
PS: Da fällt mir ein, dass ich an einer Stelle Blödsinn gemacht habe...
Ich glaube, irgendwo habe ich UInt64 verwendet, was ja deutlich geringer ist, als double.
Bei meinem Konsolen-Programm war das durchaus sinnvoll, allerdings jetzt, wo die Eingabe-Kontrolle durch einfache-char-Überprüfung gesichert ist, kann ich dort double nutzen.
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 10.07.12 19:16
Hallo,
double ist wohl etwas klein geraten.Bisher rechnen die meisten hier bis 1E5 Stellen.
Ich habe mal in der Additionschleife zählen lassen, wie oft ein Carry vorkommt und wie oft eine Stelle addiert wird.
Wenn ich das richtig gerechnet habe, sind es 2,4*(100000*100001/2)=~12x10E9 Additionen für 100000 Stellen, was auch passt.
Das Verhältnis CarryCnt/AddsCnt ist fast genau 0.5 .
Quelltext 1: 2: 3: 4: 5:
| ...952584506637311513 241389 it 100000 dig
Einzelbyte Additionen 12080757065 Einzelbyte Uebertraege 6040358167 |
Bei 30 Sekunden und 3 GHz? sind das 120 Takte pro Byte Addition+Reverse.
Das ist doch erschreckend langsam.Meine 54 Sekunden noch viel mehr.
Gruß Horst
|
|
Palladin007
Beiträge: 1282
Erhaltene Danke: 182
Windows 11 x64 Pro
C# (Visual Studio Preview)
|
Verfasst: Di 10.07.12 19:37
Ich habe jetzt alles so geändert, dass nur noch double genutzt wird.
Der Wertebereich liegt dann noch über 1E307. Die genaue Zahl weiß ich gerade nicht aus dem Kopf.
Allerdings hab ich jetzt ein paar komische Fehler, die ich erst finden und beheben muss, bevor ich das neue Programm zeigen kann.
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mi 11.07.12 21:39
Zuletzt bearbeitet von Horst_H am So 16.03.14 23:36, insgesamt 1-mal bearbeitet
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Fr 13.07.12 08:50
Hallo,
Das mit dem Carry ist nicht so schön, wie erhofft hatte.
Für Martok ist sicher die C-Variante von Eric Goldstein mit Benutzung von SSE interessant.Da kann man sicher die Aufrufkonvention cdecl benutzen.
Das wäre sicher eine extrem schnelle Variante.
Gruß Horst
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: Martok
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: So 15.07.12 11:20
Hallo,
eine etwas schnellere Version ( als p196.dpr speichern )
15.1s für 100000 Stellen mit freepascal 2.6.4 ( -Xs -XX ).
Addition und Carry-Berechnung und getrennt.Dies war entscheidend.
Dann enthalten die Bytes statt 0..9 nun 0..18, diese Zahlen werde erst anschliessend immer zwei benachtbarte auf einmal korrigiert.
Carry Bestimmung braucht den Großteil der Rechenzeit.
Den Assemblerkram hätte man sich fast sparen können
Speicherzugriff ist teuer.Deshalb eine Variante, in der der Carry und neue Zahl in einem Word gespeichert und dann per Ausmaskierung und shift right umgemodelt werden
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: 282: 283: 284: 285: 286: 287: 288: 289: 290: 291: 292: 293: 294: 295: 296: 297: 298: 299: 300: 301: 302: 303: 304: 305: 306: 307: 308: 309: 310: 311: 312: 313: 314: 315: 316: 317: 318: 319: 320: 321: 322: 323: 324: 325: 326: 327: 328: 329: 330: 331: 332: 333: 334: 335: 336: 337: 338: 339: 340: 341: 342: 343: 344: 345: 346: 347: 348: 349: 350: 351: 352: 353: 354: 355: 356: 357: 358: 359: 360: 361: 362: 363: 364: 365: 366: 367: 368: 369: 370: 371: 372: 373: 374: 375:
| program p196; {$IFDEF FPC} {$MODE DELPHI} {$ASMMODE INTEL} {$Optimization ON} {$Optimization RegVar} {$Optimization PEEPHOLE} {$Optimization CSE} {$Optimization ASMCSE} {$Else} {$APPTYPE console} {$Endif}
uses SysUtils;
{$IFNDEF FPC} type nativeUint = LongWord; PtrUint = LongWord; {$Endif}
const NUMBER_BASE = 10; cMaxDigit = 100000; cDelta = 24139; CpuF = 3.5e9; type TDigit = byte; tDigit2 = word; tpDigit =^TDigit; tpDigit2 =^TDigit2; TNumber = array of TDigit; tSumCarry = record we: Word; end; tSumCarFeld = array[0..18*256+21] of tSumCarry; var MaxIndex : integer; Cycle: Cardinal; AddCnt : Int64; cSumCarFeld : tSumCarFeld;
procedure NumberFromString(var Number: TNumber; Str: string); var i: integer; begin SetLength(Number, Length(Str)); for i:= 0 to Length(Str) - 1 do Number[i]:= Ord(Str[Length(Str) - i]) - Ord('0'); end;
function NumberToString(var Number: TNumber): string; var i,l: integer; begin i := High(Number); If i <= 50 then begin l := i+1; SetLength(Result, l); for i:= 0 to High(Number) do begin Result[l]:= Chr(Ord('0') + Number[i]); dec(l); end; end else begin SetLength(Result, 50); fillchar(Result[1],50,'.'); For l := 1 to 24 do Begin Result[l] := Chr(Ord('0') + Number[i-l+1]); Result[l+26] := Chr(Ord('0') + Number[24-l]); end; end; end;
function NumAddAs(pDigit1,pDigit2 : tpDigit):NativeUInt; begin asm PUSHAD
MOV ESI,pDigit2 MOV EDI,pDigit1
MOV ECX,ESI SUB ECX,EDI INC ECX SAR ECX,3 TEST ECX,ECX MOV @result,ECX; JLE @UndTschuesz SUB ESI,3
CMP ECX,4 JLE @Reste @WeiteSchritte: SUB ECX,4
MOV EAX,[ESI] BSWAP EAX MOV EBX,[ESI-4] BSWAP EBX ADD EAX,[EDI] MOV EBP,[ESI-8] BSWAP EBP ADD EBX,[EDI+4] MOV EDX,[ESI-12] BSWAP EDX ADD EBP,[EDI+8] ADD EDX,[EDI+12]
MOV [EDI],EAX BSWAP EAX MOV [EDI+4],EBX BSWAP EBX MOV [EDI+8],EBP BSWAP EBP MOV [EDI+12],EDX BSWAP EDX
ADD EDI,16
MOV [ESI],EAX MOV [ESI-4],EBX MOV [ESI-8],EBP MOV [ESI-12],EDX
SUB ESI,16 CMP ECX,4
JG @WeiteSchritte;
@Reste: MOV EAX,[EDI] BSWAP EAX MOV EDX,[ESI] ADD EAX,EDX MOV EDX,EAX BSWAP EDX MOV [ESI],EAX SUB ESI,4 MOV [EDI],EDX ADD EDI,4 DEC ECX JNE @Reste;
@UndTschuesz: POPAD end; end;
function CarryCorrect(pDigit: tpDigit;cnt: integer):nativeUint; var Carry: nativeUint; begin Carry := 0; for cnt := cnt Downto 0 do begin Carry := Carry+pDigit^; result := Carry DIV 10; pDigit^ := Carry-10*result; inc(pDigit); Carry := result; end; end;
function CarryCorrect2(pDigit: tpDigit2;cnt: integer):nativeUint; var idx: NativeUint; begin result := 0; dec(cnt); IF cnt > 0 then repeat with cSumCarFeld[pDigit^+result] do begin idx := we; pDigit^ := idx shr 2; result := idx AND 3; end; inc(pDigit); dec(cnt,2); until cnt<0;
IF cnt >-2 then begin idx := (pDigit^ AND 255 )+result; result := idx DIV Number_Base; idx := idx -result*Number_Base; pDigit^ := pDigit^ AND (255*256)+idx; end; end;
procedure NumberAdd(var Number : TNumber); var pDigit1,pDigit2 : tpDigit; p, Carry: nativeUint; begin p := high(Number); inc(AddCnt, (p+1) DIV 2); pDigit1 := @Number[0]; pDigit2 := pDigit1; inc(pDigit2,p); Carry:=SizeOf(PtrUint)*NumAddAs(pDigit1,pDigit2); inc(pDigit1,Carry); dec(pDigit2,Carry);
Carry:= 0; IF PtrUint(pDigit2)>= PtrUint(pDigit1) then repeat Carry := pDigit1^+pDigit2^; pDigit1^ := Carry; pDigit2^ := Carry; inc(pDigit1); dec(pDigit2); until PtrUint(pDigit2) < PtrUint(pDigit1);
IF CarryCorrect2(@Number[0],p) = 1 then begin p := Length(Number)+1; SetLength(Number, p); Number[p-1] :=1; end; end;
function NumberCompare(const A: TNumber): boolean; var i,j: integer; begin i := Low(A); j := High(A); Repeat Result:= A[i]=A[j]; inc(i); dec(j); until Not(Result) OR (J<I);
IF MaxIndex <i then begin MaxIndex := i; writeln('Erster Unterschied bei Stelle ',i:2,' und Iteration ',cycle) end; end;
procedure SumCarFeldErstellen; var i,j,s,c,d1,d2,idx: integer; begin Fillchar(cSumCarFeld,SizeOf(cSumCarFeld),#0); For i := 0 to 18 do For j := 0 to 21 do begin idx := i*256+j; s := (i*Number_Base+j); c := s DIV sqr(Number_Base); s := s - c* sqr(Number_Base); d1 := s DIV Number_Base; d2 := s-d1*Number_Base; with cSumCarFeld[idx] do begin we := (d1*256+d2)*4+c; end end; end;
var Work : TNumber; delta: cardinal; Time1, Time2 : TDateTime; s: string; begin SumCarFeldErstellen;
Repeat Write('Startzahl: ( Beenden mit 0 ) '); ReadLn(s); if s='0' then break; If s= '' then s := '196'; writeln(s); NumberFromString(Work, s); Cycle:= 0; AddCnt := 0; delta := cDelta; Time1 := time; Repeat inc(Cycle); NumberAdd(Work); if Length(Work) >= cMaxDigit then break; dec(delta); if Delta=0 then begin delta := cDelta; Time2 := time; WriteLn(Cycle:10,' it',Length(Work):10,' dig',(Time2-Time1)*86400.0:10:3,' s'); end; until NumberCompare(Work); Time2 := time; WriteLn(NumberToString(Work)); WriteLn(Cycle:10,' Iterationen mit ',AddCnt,' Byte-Additionen ' ); time1 := (Time2-Time1)*86400; IF time1 > 0 then begin WriteLn('Takte/ Addition ',(Time1*CpuF)/AddCnt:6:3); WriteLn(Length(Work):10,' Digits ',Time1:10:7,' s'); end; until true; end. |
Gruß Horst
|
|
|