Conway Sequence Generator [obsolete]

[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...

Ca le fait aussi pour conway.exe ?

[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)

[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 !

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

[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 ?

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

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 ? 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

PS : Java j'aime pas non plus !

[Gamall]

Ne touche plus à rien ca marche

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

Mais non, tu ne me pourris pas mon thread

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

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

PS : Java j'aime pas non plus !

Ca ne sert pas à la même chose du tout On lance le troll C vs C++ vs Java ? dis ?

[Kafou]

Ne touche plus à rien ca marche

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

Bon bah je continue alors

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
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

Meuh si, en te penchant sur la chimie des éléments de Conway. ... ...... ..

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 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"

Ca ne sert pas à la même chose du tout On lance le troll C vs C++ vs Java ? dis ?

Ben, c'était le but de mon PS

Ah et puis, vive le C. (mon prog est fait en C pur)

[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

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

Et puis y'a pas que la rapidité du programme qui compte, j'aime aussi qu'ils soient très petits, "juste histoire de"

Comme je suis fine psychologue, j'avais bien compris ça comme ça

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é

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

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 :

[Kafou]

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

Tu rigoles ? J'adore !

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.

j'utilise des strings

Je veux bien une photo 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.

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
(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)

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]

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 )

Je veux bien une photo 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à !

A Quoi qu'ça sert un générateur aléatoire de culottes légères?

Nanmého !

Là, dans les dents

Même pas mal

très bonne piste pour accélérer la chose

Tu es un obsédé de la vitesse toi

Rien que pour te contrarier, je vais faire mon prog de conway par atomes en Java, na !

(quant aux observations, je laisse ça aux matheux).

Vous êtes trop généreux, monseigneur

[Kafou]

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

Tu es un obsédé de la vitesse toi

Oui. Pourquoi crois-tu que j'ai plus de voiture depuis un an ?

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]

Sauf que moi c'était plus fin et original que lui

Si tu te lances dans un concours de finesse et d'originalité avec Beldin, moi je retourne chez ma mère

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))

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à ))

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

Et si mon intuition est fausse... ben là je serai très malheureuse

[Kafou]

Hum...

Ca devient sérieux là dis-moi

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]

Ca devient sérieux là dis-moi

C'est de ta faute, t'avais qu'à ne pas faire de nécromancie sur ce topic

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 (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 1222 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 ( rang 60 et 7z, j'ai quatre millièmes à 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

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 Mainfestement il y a moyen. Le tout c'est de le trouver

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

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

[Kafou]

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 !

[Gamall]

Bon, je suis mal embarquée

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 Mais j'auraisapô !