Re: Conway's Sequence Generator
Posted: Wed Aug 22, 2007 11:03 am
Cet article est illisibleGamall wrote: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).
Plus ou moins compris...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à.
Ben ouais c'est le principe des "atomes", non ?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.
Tu veux regrouper les atomes avec des "molécules" toujours plus grosses quoi ? (molécules qui seraient tes éléments de dico)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.
Muahaha, moi je te compresse l'infinité des termes de la suite sur un seul octet, voire deux bits, d'ailleurs je t'ai déjà fourni le décompresseur, un peu plus haut dans ce thread Mais oui c'est hyper redondant. Ceci dit en y récléchissant 2 minutes on trouve déjà un codage bidon qui fait mieux que 1/5 (coder chaque paire de chiffres sur 3 bits, la paire "33" n'existant pas) D'ailleurs dans mon prog puisque je suis un gros malade je code mes chiffres sur 2 bits, ce qui permet certaines optimisations à côté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 !)
Mon idée était de laisser complètement tomber la notation 123 (sauf pour la sortie) en la remplaçant par les atomes de la liste (la suite qui commence avec un 3 est entièrement codable par atomes, celle qui commence avec un 1 l'est à partir de la ligne 7 ou 8 je crois).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.
Je m'y connais *un petit peu* là dedans mais je vois pas exactement ce que tu veux en faire en faitL'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
Si tu m'expliques ton idée plus en détails et avec des exemples (et qu'elle est effectivement réalisable), je pourrai t'aider.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
Tout atome se décompose (= en passant à la ligne suivante) avec les autres atomes. Initaliser ton dictionnaire avec les 92 atomes me semble le minimum.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 )
Dit-elle, et le lendemain à 9h du mat' :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
Héhé elle a fini par se remettre à ConwayGamall wrote: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ô !