Conway Sequence Generator [obsolete]

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

Re: Conway's Sequence Generator

Postby Kafou » Mon Aug 20, 2007 10:30 pm

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 ?

User avatar
Gamall
Hic sunt dracones
Posts: 4126
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Postby Gamall » Mon Aug 20, 2007 10:33 pm

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 }

User avatar
Kafou
Poulidor Gnomonique
Posts: 1501
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Postby Kafou » Mon Aug 20, 2007 10:52 pm

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

User avatar
Kafou
Poulidor Gnomonique
Posts: 1501
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Postby Kafou » Tue Aug 21, 2007 10:42 am

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

User avatar
Gamall
Hic sunt dracones
Posts: 4126
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Postby Gamall » Tue Aug 21, 2007 5:29 pm

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 }

User avatar
Kafou
Poulidor Gnomonique
Posts: 1501
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Postby Kafou » Tue Aug 21, 2007 6:02 pm

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)

User avatar
Gamall
Hic sunt dracones
Posts: 4126
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Postby Gamall » Tue Aug 21, 2007 7:18 pm

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 }

User avatar
Kafou
Poulidor Gnomonique
Posts: 1501
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Postby Kafou » Tue Aug 21, 2007 7:35 pm

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

User avatar
Gamall
Hic sunt dracones
Posts: 4126
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Postby Gamall » Tue Aug 21, 2007 8:31 pm

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 }

User avatar
Kafou
Poulidor Gnomonique
Posts: 1501
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Postby Kafou » Tue Aug 21, 2007 8:41 pm

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.

User avatar
Gamall
Hic sunt dracones
Posts: 4126
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Postby Gamall » Tue Aug 21, 2007 9:13 pm

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 }

User avatar
Kafou
Poulidor Gnomonique
Posts: 1501
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Postby Kafou » Tue Aug 21, 2007 9:37 pm

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)

User avatar
Gamall
Hic sunt dracones
Posts: 4126
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Postby Gamall » Tue Aug 21, 2007 11:02 pm

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

User avatar
Kafou
Poulidor Gnomonique
Posts: 1501
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway's Sequence Generator

Postby Kafou » Tue Aug 21, 2007 11:24 pm

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

User avatar
Gamall
Hic sunt dracones
Posts: 4126
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway's Sequence Generator

Postby Gamall » Wed Aug 22, 2007 10:12 am

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 }


Return to “Freewares, game mods, Java, C++, OCaml & Maths”

Who is online

Users browsing this forum: No registered users and 13 guests