Moin, ist zwar nur Hobby aber halt spannender als Kreuzworträtsel. Für meine ST32 Bastelei muss ich eine Funktion schreiben, die CRC32 Perioden erkennt. Exakte Digitalwerte, keine fehlerbehafteten Analogwerte. Der Array wird laufend und rolierend aktualisiert von einem INT. (20ms) der auch den Zeiger verwaltet. Idealerweise erkennt auch der INT Perioden, sonst eben im Hauptprogramm. Es kommt nicht drauf an wann eine Periode erkannt wird, nur dass sie erkannt wird, bevor sie wieder weg ist im Array. Perioden können 2 aber auch 3,4,5 Zyklen haben, daher nehme ich 3 x 5 = 15 Elemente a 32 Bit. Dann sind 3 Stück sicher drin, zumindest kurzzeitig. Es muss schnell gehen! In 20ms kommt immer schon der nächste Wert angeflogen. Wie würde man das programmtechnisch machen? Gruss, Christian
Auf jeden Fall nicht mit HAL/DriverLib, sondern mit CMSIS-Headerfile und schön zu Fuss :-) Du musst den Read- und Writepointer gegeneinander sichern, ein Überholen ist auch dein Testkriterium, ob du schnell genug bist. Im einfachsten Fall fängst du beim Readpointer an und suchst nach deiner Folge, bis du am Writepointer angekommen bist. Ggf. lässt sich noch einiges optimieren. Additionen mit Überlauf oder ähnliches als "Vorsuche". Die Arraylänge musst du ebenfalls optimieren. Ein zu kleines Array läuft dir zu schnell über, ein zu großes kannst irgendwann nicht mehr wegarbeiten. Eventuell bergen deine Zahlenfolgen ein paar Besonderheiten, mit denen du optimieren kannst. Als ersten Ansatz würde ich die Werte im Interrupt eintragen und im Hauptprogramm suchen. Oder andersrum aufgezäumt: Wenn du von vornherein weisst, was du suchst, scanne das doch beim Einlaufen der Zahlen mit, anstatt hinterher zu suchen. Dafür könntest du alle möglichen Folgen in einem Baum ablegen. Hast du eine Folge gefunden, wird irgendwas gemacht (z.B. Zähler incrementieren, oder Array Index / Weg durch den Baum dieser Folge speichern), fällst du bei der Prüfung raus, brichst du ab und startest neu.
:
Bearbeitet durch User
Wie schnell ist der Prozessor getaktet und wieviele Befehle werden pro Takt ausgeführt? Damit kannst Du ungefähr abschätzen, wieviele Takte Dir zum Erkennen einer Periode zur Verfügung stehen. Bei 50 Mhz Takt und im Schnitt zwei Takten pro Befehl hast Du etwa 500.000 Befehle zwischen zwei eingehenden Werten, minus das was zur Verwaltung und Ausgabe des Ergebnis gebraucht wird. Wie sehen Deine Perioden aus, wie sieht das Array aus? Wie lang ist das Array, ganzzahlige Werte, welcher Wertebereich und immer genaue wertgleiche Perioden? Oder können das auch analoge Messwerte sein und Perioden sollen trotz eines "leichten Rauschens" in den Messwerten erkannt werden?
Christian J. schrieb: > die CRC32 Perioden erkennt. "CRC32" und "Periode" ist mir ein Begriff. Ich hab aber keinen Schimmer wonach du suchst. Kannst du das anhand eines Beispiels erklären?
Hmm.... hilft mir jetzt nicht weiter. Und der Beitrag wo nur Gegenfragen drinstehen (Wie sieht ein Array aus? Es ist egal wie eine Periode aussieht, die wiederholt sich nur eben :-) auch nicht. Es geht nur um die Strategie Perioden zu erkennen. Das mit dem Timing mache ich schon, zwei Ints koppeln durch Puffer ist mir nicht neu. Welche Suchstrategie braucht man, das ist die Frage?
Weber schrieb: > Machst du irgendwas mit Glücksspielautomaten? Nein, Periodenerkennung bei "Game of Life"..... ich brauche kein Glücksspiel, ich bin Ingenieur.
Christian J. schrieb: > Wie sieht ein Array aus? Es ist egal wie eine Periode > aussieht, die wiederholt sich nur eben :-) auch nicht. Na, dann halt nicht! Wirst schon selber rausfinden. Irgendwie. Und wenn dir 20 ms als "muss schnell gehen", dann ist dir sowieso nicht zu helfen.
Ben B. schrieb: > Game of Life ist doch aber eine 2D-Oberfläche... Der Bitstrom in die Displays ist allerdings 1D. Die 2D Matrix wird ja umgerechnet in diesen Bitstrom der MAX7219 füttert und die sind alle in Reihe verkettet.
Nick M. schrieb: > Na, dann halt nicht! > Wirst schon selber rausfinden. Irgendwie. Mimimimii.... wer wird denn gleich weinen? Eine Periode ist eine Reihe von Zahlen, die sich periodisch wiederholt. Sowohl die Länge als auch der Inhalt sind undefiniert. Sie lassen sich aber hier auf 2 bis 5 eingrenzen und die Inhalte liegen zwischen 0 und 2^32. Vielleicht gibt es ja mathematische Verfahren sowas zu lösen ohne 1000Mal durch den Array zu kurven. Triviale Lösung wäre sich 2,3,4,5 aufeinander folgende Zahlen zu schnappen und diese dann per Maske schrittweise gegen alle weiteren Elemente zu vergleichen. Kostet irre Rechenzeit. Irgendjemand hat sowas sicher schon gemacht. Sogar nur digitale Werte ohne "Rauschen".
Also angenommen er hat ein 1D-Array mit hoher Länge, Werte nur Null oder Eins (Game-of-Life-Spielfeld). Was ich machen würde, den Abstand zwischen einem Wert und dem nächsten entgegengesetzten messen. Ist dieser Wert mehrmals in Folge konstant, habe ich eine Periode. Das geht sehr schnell, erkennt aber keine komplexeren Perioden wie "00011000110001100011000...", weil der Abstandswert ständig springt. Oder "000101000101000101000101000..." Noch eine Möglichkeit wenn alle wichtigen möglichen Perioden bekannt und nicht so viele sind wäre, das Array gezielt nach diesen abzusuchen. Quasi einen String in dem Array finden. Man könnte auch eine FFT drüberjagen und probieren, aus den Peaks Rückschlüsse zu ziehen...
Ben B. schrieb: > Noch eine Möglichkeit wenn alle wichtigen möglichen Perioden bekannt und > nicht so viele sind wäre, das Array gezielt nach diesen abzusuchen. > Quasi einen String in dem Array finden. Der eigentliche Bitstream hat keinen logischen Zusammenhang. Es sind sture Bitmuster mit Steuercodes vorne, die erst die Adresse des MAX7219 angeben, daher 8x8 Bytes als Muster. Aber auch diese sind vergleichbar, jedes 2D Muster hat genau einen Bitstream. Dieser Bitstream ist in 32Bit Vars organisiert, da ich die interne CRC32 benutze im Int, der das Display bedient. Während des Raushämmerns über die SPI wird gleich die CRC32 gebildet. Jedes Muster auf dem 24x32 Feld entspricht genau einem 32 Bit Wert. Diese werden in einem Array abgelegt. 15 Stück, da ich denke, dass man die braucht. Ich spiele schon länger damit herum und habe festgestellt, dass es nach zig Tagen Laufen immer wieder Muster gibt, die ich nicht erkenne als "endgültig", zb große pulsierende Sterne. Dazu habe ich das ohne Display mit maximaler Speed laufen lassen im debugger. Locker 1000 Generationen/Sekunden sind drin. Nur auf dem STm32 Board ohne was drum herum. Mein Zufall ist echt, ich nutze einen LDR mit um den Seed zu setzen, zusätzlich zur RTC 32 Bit. Gleiter und Raumschiffe werden nicht erkannt aber dafür habe ich schon was anderes gefunden, die haben nämlich nahezu konstante Anzahl Zellen.
1000 Generationen/s sind aber deutlich mehr als 50, für Deine 20ms. Sind also 768 Bit, 96 Byte, 24 32-Bit-Worte. Das ist wenig. Was spricht bei der geringen Speichermenge dagegen, z.B. 10.000 Spielfelder im Speicher zu halten (das braucht nur 1Mbyte) und zu schauen, ob sich da Bilder wiederholen? Sprich ob das neue Bild einem der letzten 10.000 entspricht?
Christian J. schrieb: > Triviale Lösung wäre sich 2,3,4,5 aufeinander folgende Zahlen zu > schnappen und diese dann per Maske schrittweise gegen alle weiteren > Elemente zu vergleichen. Kostet irre Rechenzeit. Das sind 4·n-14 Vergleiche (n ist die Länge des Arrays). Christian J. schrieb: > 15 Elemente a 32 Bit Also 46 Vergleiche. Die schafft selbst ein langsamer Prozessor locker in Christian J. schrieb: > 20ms Christian J. schrieb: > Locker 1000 Generationen/Sekunden sind drin. Auch in 1ms sind die 46 Vergleiche noch gut machbar.
Ben B. schrieb: > 1000 Generationen/s sind aber deutlich mehr als 50, für Deine 20ms. In der Simulation, nicht im Demo-Mode an der Wand. In der Simu läuft nur der reine Zell Automat, damit ich möglichst schnell sehen kann wohin der Hase läuft. Dazu brauche ich keine spi bedienen, maximale Geschwindgkeit ohne jedes Delay fahren. Das geht fix bei einem stm32 mit 72 Mhz Clock.
Yalu X. schrieb: > Das sind 4·n-14 Vergleiche (n ist die Länge des Arrays). Ja.... ok, dachte vielleicht es gibt da kluge Verfahren für sowas. Stures Vergleichen ist nicht gerade das Ei des Kolumbus und etwas größere Zahlen und Arrays und schon potenziert sich das. Ich kann mir also die 2,3,4,5 ersten Elemente einfach rausholen und per memcmp vergleichen mit dem Rest, der schrittweise durchlaufen wird, immer ein Byte vorsetzen auf den Ringpuffer angewendet. Dazu einen eigenen Zeiger definieren, der unabhängig vom Writze Zeiger des INTs ist. Kriegen wir hin....
ben eater hat doch vor urzeiten mal diese hübsche CRC berechnung in hardware ausgeführt (youtube) n paar XOR gates und ne Hand voll flipflops und fertig. wenn sich die Muster nun ausreichend vordefinieren lassen, kannst Du vollständig Analog zu Bens CRC die hardware die Muster erkenenn lassen, noch ein detection pin und schwupp sended dein detector ein binäres signal an den µC bei Fund eines Musters.
sid schrieb: > n paar XOR gates und ne Hand voll flipflops und fertig. Der STM32 hat eine CRC Hardware intern, die das in 2-3 Zyklen erledigt.... dauert keine paar Mikrosekunden bei mir für das ganze Feld. Das Polynom ist allerdings fix, mir aber auch egal. XOR taete es auch.
Christian J. schrieb: > Der STM32 hat eine CRC Einheit intern, die das in 2-3 Zyklen > erledigt.... jo, aber er braucht ja keinen CRC sondern eine Mustererkennung ;)
sid schrieb: > Christian J. schrieb: >> Der STM32 hat eine CRC Einheit intern, die das in 2-3 Zyklen >> erledigt.... > > jo, aber er braucht ja keinen CRC sondern eine Mustererkennung ;) Genau: deswegen (s.o.): Autokorrelation
Christian J. schrieb: > Stures Vergleichen ist nicht gerade das Ei des Kolumbus und etwas > größere Zahlen und Arrays und schon potenziert sich das. Was potenziert sich da? Der Aufwand ist O(n) (n = Länge des Arrays). Besser als O(n) ist auch kein anderes Verfahren, da jedes Arrayelement mindestens einmal gelesen werden muss.
Yalu X. schrieb: > Was potenziert sich da? Der Aufwand ist O(n) (n = Länge des Arrays). > Besser als O(n) ist auch kein anderes Verfahren, da jedes Arrayelement > mindestens einmal gelesen werden muss. Ich widerspreche nicht, da ich weiss, dass Du ziemlich was auf dem Kasten hast in Sachen Software :-) Ok, ich baue es so ein......
Ist jetzt noch nicht ganz fertig aber geht das auch noch pfiffiger? Habe versucht das alles in Schleifen zu erschlagen. 2er bis 5er Perioden. compVal als HilfsVar zunächst mal, kann man auch weglassen. Habe es im Debug Mode mit "Life View" mehrmals durchlaufen lassen, auf 2er Perioden reagiert er jedenfalls sofort. Eine 2er wird allerdings durch den Vergleich auf 3er auch abgedeckt. D.h auf 2 bräuchte man gar nicht zu prüfen, 1,2,1,2,1,2,... wird auch mit Vergleich auf 1,2,1 abgedeckt. Die Switch Case kann man sicherlich noch etwas eleganter formulieren aber das später. Da ich lokale Vars auf dem Stack nicht debuggen kann sind die erstmal global.
1 | /* 15 x 32 Bit Checksummen als aufeinander folgende Abbilder der Matrix */
|
2 | #define CRC32_MAX 15
|
3 | volatile int WP_CRC32Stream = 0; /* Write Pointer, rolierend, INT gesteuert */ |
4 | volatile uint32_t CRC32Stream[CRC32_MAX+1]; |
5 | |
6 | #define MAX_COMP 5
|
7 | uint32_t compVal[MAX_COMP]; |
8 | |
9 | static
|
10 | int CheckForPeriod() |
11 | {
|
12 | int round = 2; |
13 | int ptr = 0; |
14 | |
15 | while (round <= MAX_COMP) { |
16 | /* Erste Werte als Vergleich speichern */
|
17 | for (int i = 0; i < round; i++) |
18 | compVal[i] = CRC32Stream[i]; |
19 | |
20 | ptr = round + 1; |
21 | |
22 | /* Vergleiche die n 32 Bit Werte schrittweise mit dem Rest des Arrays */
|
23 | _Bool treffer = false; |
24 | while (ptr < CRC32_MAX) { |
25 | |
26 | switch (round) |
27 | {
|
28 | case 2: if ((compVal[0] == CRC32Stream[ptr]) && \ |
29 | (compVal[1] == CRC32Stream[ptr + 1])) |
30 | treffer = true; |
31 | break; |
32 | case 3: if ((compVal[0] == CRC32Stream[ptr]) && \ |
33 | (compVal[1] == CRC32Stream[ptr + 1]) && \ |
34 | (compVal[2] == CRC32Stream[ptr + 2])) |
35 | treffer = true; |
36 | break; |
37 | case 4: if ((compVal[0] == CRC32Stream[ptr]) && \ |
38 | (compVal[1] == CRC32Stream[ptr + 1]) && \ |
39 | (compVal[2] == CRC32Stream[ptr + 2]) && \ |
40 | (compVal[3] == CRC32Stream[ptr + 3])) |
41 | treffer = true; |
42 | break; |
43 | case 5: if ((compVal[0] == CRC32Stream[ptr]) && \ |
44 | (compVal[1] == CRC32Stream[ptr + 1]) && \ |
45 | (compVal[2] == CRC32Stream[ptr + 2]) && \ |
46 | (compVal[3] == CRC32Stream[ptr + 3]) && \ |
47 | (compVal[4] == CRC32Stream[ptr + 4])) |
48 | treffer = true; |
49 | break; |
50 | default:
|
51 | break; |
52 | }
|
53 | |
54 | /* Pointer n Bytes weiter setzen */
|
55 | ptr = ptr + round; |
56 | }
|
57 | |
58 | round++; |
59 | }
|
60 | |
61 | return 0; |
62 | }
|
Christian J. schrieb: > ptr = round + 1; Sollte da nicht
1 | ptr = round + 1; |
stehen? Sollte das Verfahren statt bei Index 0 nicht bei Index WP_CRC32Stream, d.h. nicht am Anfang des Array, sondern am Anfang des Ringpuffers starten? Wenn round ein Teiler der Array-Länge ist, ist das egal. Aber für round=2 und round=4 ist die letzte Periode im Array nicht vollständig. Es paarmal wird über das Array-Ende hinaus gelesen. Die Variable treffer wird schon dann auf true gesetzt, wenn sich der betrachtete Block einziges Mal wiederholt. Sollten die Daten nicht über die gesamte Array-Länge periodisch sein? Die Funktion CheckForPeriod liefert keine Information darüber zurück, ob die Daten periodisch sind oder nicht (der Wert von treffer verschwindet im Nirwana).
Yalu X. schrieb: > Sollte das Verfahren statt bei Index 0 nicht bei Index WP_CRC32Stream, > d.h. nicht am Anfang des Array, sondern am Anfang des Ringpuffers > starten? Ja, so ist das wenn man etwas postet und nachher noch weiter macht. Fehler ist korrigiert. Außerdem muss das Feld erst voll sein.
1 | /* Eintragen in BitStream */
|
2 | CRC32Stream[WP_CRC32Stream] = CRC32Bitstream; |
3 | /* Zeiger rolieren */
|
4 | WP_CRC32Stream = (WP_CRC32Stream + 1) % CRC32_MAX; |
5 | |
6 | /* Feld muss voll sein für Auswertung */
|
7 | if (WP_CRC32Stream == 0) |
8 | f_IsFull = true; |
9 | |
10 | if (!f_IsFull) |
11 | return 0; |
Aber wo man anfängt.... es ist egal ob das sofort oder erst später erkannt wird, Periode ist Periode und die bleibt so. Nur sind 2er Treffer auch zufällig möglich. 3er unwahrscheinlicher und ein 3er deckt den 2er mit ab.
Nur mal als Hinweis: Game of Life ist deterministisch - auf einen bestimmten State X folgt immer der gleiche State X+1. D.h., wenn ich zwei States gefunden habe, die gleich sind, brauch ich nicht mehr weiter zu vergleichen, da sie eh immer die gleichen Folgestates generieren. Das Finden eines Zyklus' reduziert sich also auf die Suche, ob der neue State schon einmal vorgekommen ist.
foobar schrieb: > Das Finden eines Zyklus' reduziert sich also auf die Suche, ob der neue > State schon einmal vorgekommen ist. Innerhalb welchen Zeitraumes? Bzw Periodenraumes hier... d.h. ich muss nur schauen, ob ich bei N States schon einmal meinen gemerkten State hatte? Eben weil sich aus einem Muster immer die gleichen Folgemuster entwickeln. Ein Muster wird durch eine einzige 32 Bit CRC32 eindeutig beschrieben.
Christian J. schrieb: > Für meine ST32 Bastelei muss ich eine Funktion schreiben, die CRC32 > Perioden erkennt. CRC32 ? Woher auch immer, Perioden sind Zahlenfolgen. Der ZIP ZLW Ziv Lemoel Welsh Algorithmus erkennt, ob eine Bytefolge früher schon mal vorlag, man kann einstellen wie viel früher und wie lang. Compress von http://ftp.ntu.edu.tw/pub/cpatch/h/helpdeco/helpdc21.zip ist eine kurze Version.
MaWin schrieb: > RC32 ? Woher auch immer, Perioden sind Zahlenfolgen. Jedes grafische 24x32 Muster wird bei mir durch einen CRC32 abgelegt, da ich nur so feststellen kann, ob es ein Muster schon mal gab. Dieser Algorithmus funktioniert auch für Binärzahlen? Sieht eher nach Text Zippen aus.
>> Das Finden eines Zyklus' reduziert sich also auf die Suche, ob der neue >> State schon einmal vorgekommen ist. > > Innerhalb welchen Zeitraumes? Bzw Periodenraumes hier... d.h. ich muss > nur schauen, ob ich bei N States schon einmal meinen gemerkten State > hatte? Wenn du die letzten N States merkst, kannst du Zyklen bis Länge N erkennen.
Christian J. schrieb: > [...] > Ein Muster wird durch eine einzige 32 Bit CRC32 eindeutig > beschrieben. Soweit ich den Sachverhalt CRC verstanden habe, gilt das nur und hängt auch von dem Polynom ab, falls die Menge der Eingangsdaten (bei CRC32) kleiner oder gleich 32 Bit sind. Anders herum. Für 33 Bit Eingangsdatenlänge wird ein CRC32 verschiedene Eingangsdaten auf die gleich CRC-Summe abbilden. Ich hoffe, ich habe nichts übersehen, was meinen Einwand überflüssig macht.
Christian J. schrieb: > Sieht eher nach Text Zippen aus Text zippen besteht aus der Aufgabe, früher schon mal auftretende Bytefolgen schnell erkennen zu können. Beim GoL sind aber sehr lange Perioden denkbar, über tausende von States, eine sichere Erkennung ab wann das Muster wiederholt wird (und ab dann das Spiel in eine Periodd läuft) ist also nicht möglich.
MaWin schrieb: > Beim GoL sind aber sehr lange Perioden denkbar, über tausende von > States, Sind sie nicht. Oder nur bei konstruierten Welten. Jede Zufallswelt bleibt früher oder später einfach stehen. Blinker und Stilleben. Ich habe es nur ganz selten gehabt, dass komplexe Blinker entstehen, die aus mehr als 5 Zyklen bestehen. Das Ding läuft Tag und Nacht bei mir, ca 1 x Woche entstehen Zustände, die noch nicht erfasst habe.
foobar schrieb: > Nur mal als Hinweis: Game of Life ist deterministisch - auf einen > bestimmten State X folgt immer der gleiche State X+1. Wollte nochmal Danke sagen für diesen Hinweis! Man muss wirklich keine Perioden durchsuchen, da eine einzige Wiederholung schon ausreicht um zu erkennen, dass es eine Periode mit ? Zyklen ist. Es kann keine 2 gleichen Muster beginnend ab Start geben bis Ende. Ich hatte öfter mal einen Zustand mit zwei parallel fliegenden Gleitern, der unendlich war aber auch die kriege ich mit einer 100er Histrory erfasst, da das Feld ja "rund" ist, was obenr raus fliegt, fliegt unten wieder rein. Schaue mir das heute abend mal an, nach ner Weile wird man eh etwas "gaga" vom Zuschauen ;-)
1 | static
|
2 | int CheckForPeriod() |
3 | {
|
4 | static int WP_CRC32 = 0; /* Write Pointer, rolierend, INT gesteuert */ |
5 | static _Bool f_IsFull = false; |
6 | |
7 | /* Aktuelles Muster eintragen in BitStream */
|
8 | CRC32Stream[WP_CRC32] = CRC32Bitstream; |
9 | uint32_t CRC32Now = CRC32Bitstream; |
10 | |
11 | /* Zeiger rolieren */
|
12 | WP_CRC32 = (WP_CRC32 + 1) % CRC32_MAX; |
13 | |
14 | /* Feld muss voll sein für Auswertung */
|
15 | if (WP_CRC32 == 0) |
16 | f_IsFull = true; |
17 | |
18 | if (!f_IsFull) |
19 | return 0; |
20 | |
21 | /* Werte vor Write Pointer bis direkt hinter ihm durchsuchen */
|
22 | int ReadPtr = WP_CRC32; |
23 | do { |
24 | /* Read Pointer auf nächstes Element */
|
25 | ReadPtr = (ReadPtr + 1) % CRC32_MAX; |
26 | if (CRC32Now == CRC32Stream[ReadPtr]) |
27 | /* Muster schon vorgekommen! */
|
28 | return 1; |
29 | } while (ReadPtr != WP_CRC32); /* RP holt WP ein */ |
30 | |
31 | return 0; |
32 | }
|
Christian J. schrieb: > Sind sie nicht Doch. Allerdings muss ich einschränken: nur in Toruswelten, wo also links und rechts, oben und unten verbunden sind. Aber das halte ich für die normale GoL Welt. Es gibt Gleiter, die fliegen endlos wenn sie mit nicht mit was anderem kollidieren, Periodenlänge abhängig von Brettgrösse. Davon mehrere unterschiedlich fliegende nicht kollidierende, und der Zyklus ist das KGV davon.
MaWin schrieb: > Allerdings muss ich einschränken: nur in Toruswelten, wo also links und > rechts, oben und unten verbunden sind. Aber das halte ich für die > normale GoL Welt. Ist bei mir auch so und ja, wenn ich 2 davon habe fliegen die auch endlos über das 32x24 Feld. Bzw bei STM32409 Disco Board mit seinen 640px noch weiter, da kann es ewig dauernd bis 3 zusammen stossen. Somit wäre das richtig. Aber den Zustand erkenne ich schnell über die Zellzahl, da diese sich dann innerhalb fester Differenzen bewegt.
PS: Habe hier grad ein recht komplexes Muster, was sich aber laufend in mehr als 50 Zyklen wiederholt.... faszinierend :-)
Christian J. schrieb: > Sind sie nicht. Oder nur bei konstruierten Welten. Jede Zufallswelt > bleibt früher oder später einfach stehen. Der Witz am Zufall ist ja gerade, dass er auch so extrem Unwahrscheinliches wie eine "konstruierte" Welt erschaffen kann. Er muss nur oft genug die Chance haben, wirksam zu werden. Ich persönlich finde übrigens diese konstruierten Welten mit ihren Zyklen einigermaßen langweilig. Wenn ich nach irgendwas suchen würde, wären das zufallsgenerierte Welten, die eine möglichst lange Phase "Chaos" haben, bevor sie in Statik oder einem Zyklus enden. Das sind für mich die spannendsten Welten. Vermutlich hat auch der TO genau dieses Ziel. Er wird aber wahrscheinlich daran scheitern. Ein statistische Analyse zeigt, warum. Am besten fängt man mit sehr kleinen Toroiden an, da die Sache dann noch einfach beherschbar ist und der volle Suchraum durchexerziert werden kann. Bei schrittweiser Vergrößerung des Toroiden und Auswertung der jeweiligen Ergebnisse erkennt man dann schnell, wohin der Hase läuft... OK, die dabei empirisch ermittelte "Gesetzmäßigkeit" ist mathematisch gesehen natürlich noch kein Beweis dafür, dass das bis zur unendlichen Ausdehnung der Toroide so weitergeht...
> static int CheckForPeriod() > ... Ich denke, deine Routine ist .. verbesserungswürdig ;-) Findet wohl immer den gerade neu eingetragenen State; das isFull erscheint mir unnötig (bei Programmstart wird ne CRC von 0 als Zyklus erkannt - who cares); den neuen State muß man nur eintragen, wenn er noch nicht drin ist; globale Variable als versteckter Funktionsparameter; ... Btw, ich bin kein Fan von vielen Großbuchstaben in Identifiern, erst recht bei lokalen Variablen. Insb sind komplett großgeschriebene immer defines.
1 | #define MAX_CYCLE_LEN 16
|
2 | |
3 | /*
|
4 | * Add new state to history. Returns true if 'state' really is new.
|
5 | */
|
6 | |
7 | static int |
8 | new_state(uint32_t state) |
9 | {
|
10 | static uint32_t history[MAX_CYCLE_LEN]; |
11 | static unsigned wp; |
12 | |
13 | for (unsigned i = 0; i < MAX_CYCLE_LEN; ++i) |
14 | if (history[i] == state) |
15 | return 0; // not new - start of a cycle |
16 | |
17 | history[wp++] = state; |
18 | wp %= MAX_CYCLE_LEN; |
19 | return 1; |
20 | }
|
foobar schrieb: > Ich denke, deine Routine ist .. verbesserungswürdig ;-) Yupp! Deswegen habe ich mir das auch grad nochmal vorgenommen, eh besch.. Wetter draussen. Leider ist es so, dass sich CRC32 wiederholen. Nicht oft aber eben doch. Erst wenn man 3 Treffer als erfüllte Bed. einstuft passt es.
c-hater schrieb: > Wenn ich nach irgendwas suchen würde, wären das zufallsgenerierte > Welten, die eine möglichst lange Phase "Chaos" haben, bevor sie in > Statik oder einem Zyklus enden. Das geht leider nur mit dem STm32F4xxx, da dieser einen Zufall hat, der von einer Rauschdiode erzeugt wird und zudem auch für Sicherheitssysteme geeignet ist. Was ich mache ist immer die gleiche Chose, die exakt so abläuft wie der Startwert es vorgibt. Andere lösen Kreuzworträtsel oder gehen auf FFF Demos, mir ist das hier lieber...
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.