Conway Sequence Generator [obsolete]

Miscellaneous programs and scripts, opensource or not, and sometimes, random mathematical stuff.
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Rhâh saloperie !

Pourtant j'utilise pas les MFC ! Juste la libc tout ce qu'il y a de plus basique...

J'ai pas l'habitude de programmer sous Windows... :cry

Ca le fait aussi pour conway.exe ?
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Ca le fait sous les deux ;)

En fait, empiriquement je dirais que tous les progs compilés avec VC++2005 utilisent les MFC, même les progs console.

Donc j'ai pris l'habitude de compiler avec les MFC statiques. (il y a un champ très accessible pour ça dans les propriétés du projet)
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Je pige pas... j'utilise exactement les mêmes options de compilation (en fait le même fichier de projet) entre ici et le boulot (c'est aussi VS2005, mais pas SP1), et quand je compile du boulot t'as visiblement pas ce problème :(

C'est pas un pauvre SP1 qui va foutre en l'air mes compils non mais oh, déjà qu'il fait grossir mes exécutables ! :monstre

Je tenterai de compiler la dernière version demain du boulot, ce soir flemme de chercher d'où ça vient ici ou de suivre tes conseils ! (fatigue -_-)

Bonne nuit :love
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Hop, compilé du boulot. Mise à jour du fichier de mon post.

J'ai regardé, les deux softs fournissent exactement le même assembleur... c'est à n'y rien comprendre, pourquoi ils linkent pas pareil ? :cry

Désolé de pourrir le thread qui à la base concerne ton programme à toi au fait :blush

Edit : j'ai regardé pour ton option de compilation, pour moi c'est sur "use windows standard libraries" et pas MFC en fait, alors bon si tous les Windows n'ont pas les bibliothèques standard de Windows... où va le monde ? :nanan???re Je peux spécifier ailleurs dans la config d'utiliser ces standard libraries en static aussi, mais forcément le prog prend 50Ko et j'aime pas les gros exes, le but de ce programme est d'être le plus petit et rapide possible :assassin

PS : Java j'aime pas non plus ! :))
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Ne touche plus à rien ca marche :yahoo :super
Kafou wrote:Désolé de pourrir le thread qui à la base concerne ton programme à toi au fait :blush
Mais non, tu ne me pourris pas mon thread :foufou

D'autant moins que ton prog fout la patée au mien en termes de performances.?.. rang 70 en 29 secondes avec sortie.... et 6 sans !

Bon, je n'avais pas essayé d'optimiser, mais dans tous les cas je pense que j'aurai du mal à faire mieux :lol
Kafou wrote:mais forcément le prog prend 50Ko et j'aime pas les gros exes, le but de ce programme est d'être le plus petit et rapide possible
Ce n'est pas parce que le prog est plus gros qu'il est moins rapide. En fait, lier statiquement aurait plutôt tendance à augmenter (infinitésimalement) les performances qu'à les diminuer ;)
Kafou wrote:PS : Java j'aime pas non plus !
Ca ne sert pas à la même chose du tout :lol On lance le troll C vs C++ vs Java ? dis ? :foufou
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Gamall wrote:Ne touche plus à rien ca marche :yahoo :super
Cool. Mais entre-temps j'ai compris la raison du problème. Tu dois avoir MSVCR80.dll (sûrement installé par une quelconque application) mais pas la dernière version. Or dans le "manifest" (enfin compris à quoi servaient ces trucs là...) des exe que je compile chez moi il est spécifié qu'il faut la dernière version de ce fichier. Ceux que je compile ici ont juste besoin d'une plus vieille version. Donc en fait ça marche chez toi mais marchera pas chez d'autres.
Mais non, tu ne me pourris pas mon thread :foufou
Bon bah je continue alors :love
D'autant moins que ton prog fout la patée au mien en termes de performances.?.. rang 70 en 29 secondes avec sortie.... et 6 sans !
Héhé c'est ça la classe :OO3
Pour sauver ton honneur je précise au cas où tu l'avais pas remarqué que seule la dernière ligne est écrite dans le fichier, pas les précédentes (contrairement à ton prog).
Bon, je n'avais pas essayé d'optimiser, mais dans tous les cas je pense que j'aurai du mal à faire mieux :lol
Meuh si, en te penchant sur la chimie des éléments de Conway. ... ...... .. :ouin
Ce n'est pas parce que le prog est plus gros qu'il est moins rapide. En fait, lier statiquement aurait plutôt tendance à augmenter (infinitésimalement) les performances qu'à les diminuer ;)
Je suis d'accord sur la théorie. Mais ces derniers temps j'ai bien galéré parce que mon programme prenait genre 30% de temps de plus si je rajoutais une pauvre ligne qui n'est même pas dans la boucle principale (un simple check sur les arguments qui prend rien en temps). Y'a une histoire de taille de code mais j'ai jamais compris :huh: Et puis finalement ça le fait plus... mais ça revient parfois... bref. Et puis y'a pas que la rapidité du programme qui compte, j'aime aussi qu'ils soient très petits, "juste histoire de" :lol
Ca ne sert pas à la même chose du tout :lol On lance le troll C vs C++ vs Java ? dis ? :foufou
Ben, c'était le but de mon PS :monstre

Ah et puis, vive le C. (mon prog est fait en C pur)
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Toi aussi tu aimes faire la Guerre des Quotes, hein ?

Astuce: quand tu postes, tu peux sélectionner n'importe quelle partie de texte dans les messages précédents, et appuyer sur le bouton quote, et ça marche tout seul ;) Ma fonction préférée dans phpBB3 :)
Kafou wrote:Cool. Mais entre-temps j'ai compris la raison du problème. Tu dois avoir MSVCR80.dll (sûrement installé par une quelconque application) mais pas la dernière version. Or dans le "manifest" (enfin compris à quoi servaient ces trucs là...) des exe que je compile chez moi il est spécifié qu'il faut la dernière version de ce fichier. Ceux que je compile ici ont juste besoin d'une plus vieille version. Donc en fait ça marche chez toi mais marchera pas chez d'autres.
C'est pour éviter ce genre de calembredaines à la graisse de hérisson que je compile statiquement :ouioui
Kafou wrote:Et puis y'a pas que la rapidité du programme qui compte, j'aime aussi qu'ils soient très petits, "juste histoire de" :lol
Comme je suis fine psychologue, j'avais bien compris ça comme ça :mdr
Kafou wrote:Pour sauver ton honneur je précise au cas où tu l'avais pas remarqué que seule la dernière ligne est écrite dans le fichier, pas les précédentes (contrairement à ton prog).
J'avais remarqué :P

Nan, mais bon, mon honneur, moi tu sais, pfffouit... j'utilise des strings et je concatène à tout va, ça réalloue la mémoire à chaque fois... une horreur du point de vue perfs. L'algo fait 5 lignes en revanche... je suppose que le tien est un peu moins lisible :foufou
Kafou wrote:Meuh si, en te penchant sur la chimie des éléments de Conway. ... ...... .. s:ouin s:ouin
Sans rire, plutôt que de générer brutalement la suite, ce serait peut-être intéressant de faire un prog générant la notation atomique de la suite: ce serait nettement plus lisible et il y aurait peut-être des observations à faire :?
Ah et puis, vive le C. (mon prog est fait en C pur)
Bhhheuuuârk : :deg
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Gamall wrote:Toi aussi tu aimes faire la Guerre des Quotes, hein ?
Tu rigoles ? J'adore !
Gamall wrote:Astuce: quand tu postes, tu peux sélectionner n'importe quelle partie de texte dans les messages précédents, et appuyer sur le bouton quote, et ça marche tout seul Ma fonction préférée dans phpBB3
Yo. Testé, approuvé. Par contre ça quote pas les smileys contrairement au bouton quote directement sur ton message.
Gamall wrote:j'utilise des strings
Je veux bien une photo :ange En plus comme ça avec mon super sens de l'observation je pourrai peut-être du même coup confirmer ou infirmer mes théories concernant ton sexe.
Gamall wrote:et je concatène à tout va, ça réalloue la mémoire à chaque fois... une horreur du point de vue perfs. L'algo fait 5 lignes en revanche... je suppose que le tien est un peu moins lisible
Ah tu veux jouer à ça ?
Eh bien j'utilise des opérateurs binaires et des macros. Là, dans les dents :monstre
(Edit : par contre l'algo lui-même - c'est-à-dire sans le contenu des macros - fait... plus ou moins 8 lignes, mais je triche dans une macro)
Gamall wrote:Sans rire, plutôt que de générer brutalement la suite, ce serait peut-être intéressant de faire un prog générant la notation atomique de la suite: ce serait nettement plus lisible et il y aurait peut-être des observations à faire
Je ne riais pas, je pense sérieusement que c'est une très bonne piste pour accélérer la chose (quant aux observations, je laisse ça aux matheux).
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Kafou wrote:Yo. Testé, approuvé. Par contre ça quote pas les smileys contrairement au bouton quote directement sur ton message.
Yep :? Ce sera peut-être règlé dans les prochaines versions (je ne suis pas tout à fait à jour de toutes façons :D )
Kafou wrote:Je veux bien une photo :ange En plus comme ça avec mon super sens de l'observation je pourrai peut-être du même coup confirmer ou infirmer mes théories concernant ton sexe.
C'est fin, ça ! Et original ! Sauf que voilà, on me l'a déjà faite, celle-là !
Beldin wrote:A Quoi qu'ça sert un générateur aléatoire de culottes légères?
Nanmého ! :monstre
Kafou wrote: Là, dans les dents :monstre
Même pas mal :gni
Kafou wrote:très bonne piste pour accélérer la chose
Tu es un obsédé de la vitesse toi :foufou

Rien que pour te contrarier, je vais faire mon prog de conway par atomes en Java, na ! :P
(quant aux observations, je laisse ça aux matheux).
Vous êtes trop généreux, monseigneur :love
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Gamall wrote:C'est fin, ça ! Et original ! Sauf que voilà, on me l'a déjà faite, celle-là !
Sauf que moi c'était plus fin et original que lui :fear
Gamall wrote:Tu es un obsédé de la vitesse toi
Oui. Pourquoi crois-tu que j'ai plus de voiture depuis un an ?
Gamall wrote:Rien que pour te contrarier, je vais faire mon prog de conway par atomes en Java, na !
Oui. Comme ça, ensuite je ferai le même en C et il sera à nouveau 10 fois plus rapide.
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Kafou wrote:Sauf que moi c'était plus fin et original que lui :fear
Si tu te lances dans un concours de finesse et d'originalité avec Beldin, moi je retourne chez ma mère :hum
Kafou wrote:Oui. Comme ça, ensuite je ferai le même en C et il sera à nouveau 10 fois plus rapide.
Fi! O(10*f(n)) == O (f(n)) :P

Et c'est même pas sûr: d'après ce que je vois là http://mathworld.wolfram.com/CosmologicalTheorem.html , les résidus ont vraiment tendance à s'écrouler :?

Mettons que je définisse les 52 premiers termes comme atomes, notés chacun par un carac alphabétique, et stocke leur décomposition dans une base de données, en adoptant une notation concise (3A = 3 répétitions du motif A, par exemple) après ça, tous les termes jusqu'à un rang très élevé seront représentables par une chaîne très courte en notation atomique, et le calcul de la décomposition sera très rapide, puisque quasiment tout sera précalculé. (le plus long étant de traduire le résidus en notation atomique, mais c'est du O(longueur du résidus), dont je prétends que ça croit très lentement. Si j'ai du bol, c'est peut-être même borné ! (mais je rêve eut-être un peu, là :snif ))

Donc (sous réserve que mon intuition d'"écrasement" soit juste) il n'y aura quasiment pas de calculs, même à rang très élevé. Donc la puissance brute et musculaire du C ne lui servira pas à grand-chose :foufou

Et si mon intuition est fausse... ben là je serai très malheureuse :cry
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Hum...

Ca devient sérieux là dis-moi :Oo

Bon, après triple lecture de ta tirade :
  • Pourquoi 52 et pas 92 ?
  • Tu en as vu beaucoup des éléments qui se décomposaient en plusieurs fois le même de suite ? Je ne crois pas que ça se produise (donc ton RLE adieu :p)
  • La "chaîne" sera plus courte qu'avec des 1 des 2 et des 3 mais elle aura quand même une croissance exponentielle, a priori, puisque chaque élément se décompose en au moins un autre et que chacun correspond à un nombre fini de chiffres de la suite d'origine, qui elle, est bien à croissance exponentielle on le sait.
  • Qu'est-ce que tu appelle "résidu" ? (ça se trouve à cause de ça j'ai compris tout ce que tu me disais absolument de travers en fait)
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Kafou wrote:Ca devient sérieux là dis-moi :Oo
C'est de ta faute, t'avais qu'à ne pas faire de nécromancie sur ce topic :nanan???re
Kafou wrote:Pourquoi 52 et pas 92 ? /// (donc ton RLE adieu :p)
Parce qu'en fait, je ne pensais pas utiliser la "vraie" définition d'un atome :tomates (cf la def de conway dans l'article joint, c'est le truc le plus proche de l'article original que j'ai pu trouver).
cct.pdf
(146.9 KiB) Downloaded 1083 times
Je pensais simplement nommer mes atomes (qui du coup ne mérient pas ce nom) arbitrairement, en prenant un nombre arbitraire de premiers éléments de la suite, et exprimer les suivants en fonction de ceux-là. En regardant les chiffres, on voit que les séquences des termes de rang supérieur utilisent énormément les séquences des premiers termes. En gros, je compte définir un dictionnaire, en en faisant varier la taille en fonction du rang que je veux calculer (edit: en fait ce n'est pas une bonne idée, pourquoi je m'acharne à voulir absolument coder un caractère de la suite sur un octet ? Je vais plutôt prendre une notation adhoc pour exprimer le terme de rang N en fonction de tous les termes de rang < N, on verra bien ce que ça donne) (edit 2: aie, ça ne marche bien que pour les tout premiers rangs, mais après bof bof... il y a certainement une astuce) :? L'idée que j'essaye, sans doute très maladroitement, d'appliquer, c'est exploiter la redondance de la suite.

Il y a une redondance gigantesque dans cette suite ! Compresse un des fichiers de sortie de ton conway_output, pour rire :lol ( rang 60 et 7z, j'ai quatre millièmes :nanan???re à comparer avec le taux de 1/5 obtenu avec une mauvaise chaîne pseudo-aléatoire de 1, 2 et 3 de même longeur ! Donc cette suite a visiblement une entropie quasi-nulle !)

Je pense que le meilleur moyen d'aller très très vite et loin dans le calcul de cette suite sans faire exploser la bécane c'est de trouver une notation compressée et une sorte de morphisme des règles de calcul du rang suivant entre la notation 123 et la notation compressée.

L'ennui c'est que je n'y connais pas grand-chose en matière d'algorithmes de compression... donc je pense que je vais pas mal ramer avant de trouver une méthode satisfaisante :bobo
Kafou wrote:La "chaîne" sera plus courte qu'avec des 1 des 2 et des 3 mais elle aura quand même une croissance exponentielle, a priori, puisque chaque élément se décompose en au moins un autre et que chacun correspond à un nombre fini de chiffres de la suite d'origine, qui elle, est bien à croissance exponentielle on le sait.
Avec les atomes de base, oui. Mais avec un dictionnaire adhoc on pourra exploiter la redondance de la bête :barbare Mainfestement il y a moyen. Le tout c'est de le trouver :bobo
Kafou wrote: que tu appelle "résidu" ? (ça se trouve à cause de ça j'ai compris tout ce que tu me disais absolument de travers en fait)
Oooops, pardon, j'appelais résidu tout ce qui ne peut pas s'exprimer en fonction du dictionnaire choisi; donc dans le cas des atomes de conway, tous les 12 et 3 qui restent collés à chaque élément sont des résidus pour moi. (encore que par exemple pour Rn on pourrait utiliser Ac etc :?)



Bon, je suis un peu stone -- beaucoup -- (j'ai toujours du sommeil en retard), donc je pense que je vais me prendre un bouquin qui ne prenne pas trop la tête et aller au dodo, avant de voir des éléphants roses :bobo

edit: Je me relis et constate que ce n'est pas très clair, ce que j'écris. J'essayerai de formuler ça plus clairement quand je serai reposée :hum
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Post by Kafou »

Gamall wrote:Bon, je suis un peu stone -- beaucoup -- (j'ai toujours du sommeil en retard), donc je pense que je vais me prendre un bouquin qui ne prenne pas trop la tête et aller au dodo, avant de voir des éléphants roses
Ditto !

J'ai pas arrêté de rafraichir ton forum en attendant impatiemment ta réponse à mes questions, et puis au moment où je me dis "allez dodo", tu as répondu et je ne suis plus en état de te lire !

Bonne nuit donc, moi aussi j'ai du sommeil de retard et pourtant je dois me lever le matin ! :sweat
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Post by Gamall »

Bon, je suis mal embarquée :lol

J'ai commencé à bidouiller un peu, mais pour l'instant je me bats plus avec l'encodage unicode de Java qu'avec le problème lui-même :D Mais j'auraisapô !
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Locked

Who is online

Users browsing this forum: Bing [Bot] and 181 guests