Conway Sequence Explorer

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

Post by Kafou »

OK !

Tu peux me dire quelle est ton idée "qui marcherait probablement mais" ?

Je poste mes sources d'ici 1h, le temps de rentrer chez moi ^^

Si tu veux je pourrai aussi expliquer l'algorithme, même s'il est relativement clair dans le code (enfin, je pense).

Je serais pas contre la dernière version de ton programme aussi (voire même tes sources ? :ange ) parce que la 0.1 ça date quand même :P
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway Sequence Explorer

Post by Kafou »

Pouf, v'la les sources.

L'algo consiste à faire un parcours en profondeur (autrement dit vertical plutôt qu'horizontal) du graphe des dérivations plutôt que de calculer ligne par ligne.

Il est texto dans le code (avec des macros à la place des fonctions de base, pour des raisons de performance), je vais donc plutôt donner un exemple ici.

Jamais plus de 4 chiffres ne sont stockés par ligne. J'ai noté entre parenthèses les chiffres qui "disparaissent" quand on dérive la ligne. En pratique, ils sont simplement supprimés.

Ca donne :

1 - (1), on est sûr de pouvoir dériver ainsi parce qu'on sait que la ligne précédente est vide (la case 0 de mon tableau est initialisée à 0)
2 - (11), on est sûr de pouvoir dériver ainsi parce qu'on sait que la ligne précédente ne contenait en tout et pour tout qu'un 1 (puisqu'elle est maintenant vide)
3 - (2)1, on ne dérive pas encore le 1 car on ne fait qu'une dérivation à la fois
4 - (1)2, idem, on ne dérive pas encore le 2
5 - 11, là on a deux fois le même chiffre dans la ligne courante alors qu'il y a encore des chiffres à dériver à la ligne précédente : on ne peut donc pas trancher, il faut revenir à la ligne précédente et dériver une nouvelle fois
4 - 2, mais cette ligne ne contient plus qu'un 2, le même problème se pose, il faut encore remonter d'un cran !
3 - (1), là on peut dériver puisque la ligne précédente est vide
4 - (2)11
5 - (111)2
6 - (3)1
7 - (1)3
8 - 11, on doit remonter car on ne peut pas trancher
-> etc. !

Quand on est à l'avant-dernière ligne, on passe automatiquement à la dérivation suivante au lieu de passer à la ligne suivante.
L'algo se termine quand on vient de dériver les derniers chiffres de l'avant-dernière ligne parce que l'avant-avant dernière ligne est vide (autrement dit quand on n'a plus aucun chiffre à traiter).
Avec les atomes c'est encore plus simple, on ne stocke qu'un atome par ligne (mais il faut se souvenir d'où on en est dans la dérivation de chaque atome et donc de chaque ligne, via un tableau secondaire).
Attachments
conway.zip
(44.17 KiB) Downloaded 937 times
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway Sequence Explorer

Post by Gamall »

Kafou wrote:Tu peux me dire quelle est ton idée "qui marcherait probablement mais" ?
Nan, je poste assez de bêtises par inadvertance, je ne vais pas en plus faire exprès d'en poster et les disséquer :lol Surtout maintenant que tu as posté ton algo de dingue :oO
Kafou wrote:Je serais pas contre la dernière version de ton programme aussi (voire même tes sources ? s:ange s:ange ) parce que la 0.1 ça date quand même
Différence entre 0.1 et 0.2 (qui marche)... Il y a juste l'algo sur le codage binaire "sans astuce". La partie atome n'est pas finie, et risque de rester comme ça un bout de temps :lol:

Je poste quand même la partie "brutale" de la classe ConwaySequence, qui n'est pas vraiment une classe, tu vas me dire, puisque toutes ses méthodes sont statiques :D Mais bon, c'est là qu'il y a les méthodes getSuccessor, qui calculent la dérivation d'une ligne à partir de la ligne précédente.

La méthode est surchargée, il y a la version String et la version byte[].

Et il y a les fonction de conversion entre String (entrée et sortie) et byte[].

Tu vas sans doute trouver plein de trucs à critiquer, ne t'en prive pas, mais ne tape pas trop fort non plus, je n'ai jamais appris à programmer, moi :P (bon, ya déjà tous les masques binaires que j'aurais pu regrouper dans une boucle...)

(note: sauf avec IE6, le bloc de code devrait avoir une scrollbar et ne pas tenir trop de place :?)

Code: Select all

public class ConwaySequence
{
    @SuppressWarnings("unused")
    private String startingTerm;
    
    /**
     * Constructor
     * @param startingTerm
     */
    public ConwaySequence(String startingTerm)
    {
        this.startingTerm = startingTerm;
    }
    
    /**
     * Default Constructor
     *
     */
    public ConwaySequence()
    {
        this.startingTerm = "1";
    }
    
    /**
     * non-optimised
     * @param term: "1", etc
     * @return next term
     */
    public static String getSuccessor(String term)
    {
        char [] cterm = (term + (char)1).toCharArray();
        // char 1 plays the part of 'end of stream'
        StringBuilder out = new StringBuilder(term+term);
        // 1.3 < 2, so I'm positive I'll have room enough ;)
        
        char last = 0; // last read char
        byte count = -1; // how many of those have been read ?
        int i = 0; //position in output;
        
        for (char curr : cterm)
        {
            if (last == 0)
            {// first term
                count++;
            }
            else
            { // not first term
                if (curr == last && curr != 1)
                { // the same mid term
                    count++;
                }
                else
                { // different or last term: flush
                    out.setCharAt(i++, GTK.getCharFromNumber(++count));
                    count = 0;
                    out.setCharAt(i++, last);
                }
            }
            last = curr; // memorize last read
        } // for each char
    
        return out.toString().substring(0, i);
    } // end getSuccessor
    
    /**
     * 
     * @param term
     * @return length of the derived term (without computing it)
     */
    public static int getSuccessorLength(String term)
    {
        char [] cterm = (term + (char)1).toCharArray();
        
        int l = 0;
        char last = 0;
        for (char c : cterm)
        {
            if (c == (char)1)
                break;
            if (c != last)
                l += 2;
            last = c;
        }
        
        return l;
    } // end getSuccessorLength
    
    
    /*
     * Sets all bytes to 0 USELESS
     * @param b : byte array
     /
    public static void clearByteArray(byte [] b)
    {
        for (int i = 0; i< b.length ; i++)
            b[i] = 0;
    }
    */
    
    /**
     * Encodes a string of 1, 2 and 3 into a byte array
     */
    public static byte [] stringToByteArray(String s)
    {
        byte [] b = new byte [(int)Math.ceil(s.length()/4.0)+1];
        int i = 0; // position in byte array
        int position = 1; // binary multiplicator
        boolean hasBennWarnedOnce = false;
        
        char [] a = s.toCharArray();
        for (char c : a)
        {
            switch (c)
            {
            case '1':
                b[i] |= position;
                break;
            case '2':
                b[i] |= 2*position;
                break;
            case '3':
                b[i] |= 3*position;
                break;
            default:
                if (!hasBennWarnedOnce)
                {
                    GTK.warnBox("Attempting to convert to " +
                            "optimized binary code a string " +
                            "with something else than 1, 2 and 3... not good.\n" +
                            "Offending string : \"" + s + "\"");
                    hasBennWarnedOnce = !hasBennWarnedOnce;
                }
                position /= 4; // one step back
                break;
            }
            
            if (position < 64) 
            { // goto more significant bit
                position *= 4;
            }
            else 
            { // reached MSB: goto next byte
                position = 1;
                i++;
            }
        }
        return b;
    }
    
    /**
     * Displays a byte array in the console
     * @param byteArray
     */
    public static void displayByteArray(byte [] byteArray)
    {
        for (byte b : byteArray)
        {
            GTK.icout("[" + (b & 3) + "," + (b & 12)/4 + "," + (b & 48)/16 + "," + (b & 192)/64 + "] ");
        }
        GTK.cout("");
    }
    
    /**
     * Converts the coded byte array to a String
     * @param bytes
     * @return decoded string
     */
    public static String byteArrayToString(byte [] bytes)
    {
        char [] out = new char [bytes.length*4];
        int j = 0;
        
        int value;
        for (byte b : bytes)
        {
            for (int i = 1 ; i < 256 ; i *= 4)
            {
                value = (b & (3*i))/i ;
                if (value != 0)
                    out[j++] = (char)('1' + value - 1);
                else
                    break;
            }
        }
        String r = new String(out);
        return r.substring(0, j);
        
    }
    
    /**
     * Much better for memory, and quite good for speed.
     * Still room for improvement though.
     * @param input
     * @return byte-coded successor
     */
    public static byte [] getSuccessor(byte [] input)
    {
        
        int realBytesNumber = input.length;
        while (input[--realBytesNumber] == 0){}
        
        byte [] r = new byte [1+(int)Math.ceil((realBytesNumber+1)*1.4)];
        // should always be enough. See error handling below.
        
        int writingPos = 0, writingMask = 1, C = -1;
        int curr = 0, last = 0;
        boolean isFirstTerm = true;
        loop:for (byte b : input)
        {
            for (int i = 1 ; i < 256 ; i *= 4)
            {
                curr = (b & (3*i))/i ;
                
                if ((curr == last || isFirstTerm) && curr != 0 )
                {
                    isFirstTerm = false;
                    C++;
                }
                else
                { // lets write something
                    try
                    {
                        r[writingPos] |= (++C)*writingMask;
                    }
                    catch (ArrayIndexOutOfBoundsException e)
                    {
                        GTK.warnBox("ERROR in public static byte [] getSuccessor(byte [] input)\n" +
                                "\nSomehow, not enough memory was allocated...\n" +
                                "Please report this error to the author, telling exactly which " +
                                "sequence you were attempting to compute, and at which rank " +
                                "this error occured.\n\n" +
                                "The output will henceforth be meaningless.");
                        return r;
                    }
                    if (writingMask < 64)
                        writingMask *= 4;
                    else
                    {
                        writingMask = 1;
                        writingPos++;
                    }
                    //GTK.icout(""+C+""+last);
                    C = 0;
                    r[writingPos] |= last*writingMask;
                    if (curr == 0)
                        break loop;
                    
                    if (writingMask < 64)
                        writingMask *= 4;
                    else
                    {
                        writingMask = 1;
                        writingPos++;
                    }
                }
                last = curr;
            } // intern for
        }// extern for
        return r;
    }// end getSuccessor byte

    /**
     * 
     * @param codedSeq: the binary coded conway term
     * @return the nomber of 1, 2 and 3s
     */
    public static int getByteSequenceRealLength(byte[] codedSeq)
    {    
        int rnb = codedSeq.length;
        int len;
        while(codedSeq[--rnb] == 0) {}
        rnb++;
        // rnb = real number of bytes
        if (rnb == 0) return 0;
        len = 4*rnb--;        
        if ((codedSeq[rnb] & 192) != 0)
            ;
        else if ((codedSeq[rnb] & 48) != 0)
            len -= 1;
        else if ((codedSeq[rnb] & 12) != 0)
            len -= 2;
        else if ((codedSeq[rnb] & 3) != 0)
            len -= 3;
        else
        {
            GTK.errorBox("LOGIC ERROR in public static int " +
                    "getByteSequenceRealLength(byte[] codedSeq): " +
                    "This should NEVER, ever happen... Blast it!");
            len = -1;
        }
        
        return len;
    }

... partie sur les atomes supprimée :P
     
Kafou wrote:Jamais plus de 4 chiffres ne sont stockés par ligne.
:oO :oO :oO :oO :oO :oO :oO :oO :oO :oO :oO

*20 minutes de réflexion plus tard*

Ben, il est génial, ton algo.

Je n'avais jamais pensé à me débarrasser des chiffres qui n'interviennent plus comme tu le fais là, j'essayais d'y aller avec de gros blocs et de raccorder les wagons à la va-comme-j'te pousse... :snif

Je ne pense pas que j'aurais trouvé ça toute seule :?

Le seul problème, c'est qu'effectivement, c'est la galère pour avoir toutes les lignes, contrairement à un algo trivial.

J'ajoute que :hi :garde :super .
{<§ 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 Sequence Explorer

Post by Kafou »

Gamall wrote:Tu vas sans doute trouver plein de trucs à critiquer, ne t'en prive pas, mais ne tape pas trop fort non plus, je n'ai jamais appris à programmer, moi
Pas ce soir, pas envie de voir du code là -_-
Gamall wrote:(note: sauf avec IE6, le bloc de code devrait avoir une scrollbar et ne pas tenir trop de place )
...
J'utilise IE6.
...
:ouin
...
MAIS J'ASSUME ! :OO3
Gamall wrote:Ben, il est génial, ton algo.
Lol, ptet pas quand même.
Gamall wrote:Le seul problème, c'est qu'effectivement, c'est la galère pour avoir toutes les lignes, contrairement à un algo trivial.
Ben non, il suffit d'écrire les chiffres sur fichier en plus de la ligne suivante quand on fait une dérivation.
Mais vu qu'on calcule les lignes par fragments et dans le désordre, on peut pas tout mettre sur le même stream.
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway Sequence Explorer

Post by Gamall »

Kafou wrote:...
J'utilise IE6.
...
:ouin
...
MAIS J'ASSUME ! :OO3
:mdr

Tu l'englobes dans un truc genre Avant Browser quand-même, non ? :? Parce qu'IE6 tout nu... c'est du masochisme.
Kafou wrote:Pas ce soir, pas envie de voir du code là -_-
Gnap :mosc
Kafou wrote:Lol, ptet pas quand même.
Sisisisi, c'est :ouioui J'insiste.
Kafou wrote:Mais vu qu'on calcule les lignes par fragments et dans le désordre, on peut pas tout mettre sur le même stream.
C'est bien ce que je dis, c'est la galère :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 Sequence Explorer

Post by Kafou »

Gamall wrote:Tu l'englobes dans un truc genre Avant Browser quand-même, non ? :? Parce qu'IE6 tout nu... c'est du masochisme.
Non... le seul truc que je reproche à IE6 c'est d'être un peu trop loin des normes du W3C, et éventuellement de pas supporter le RSS (mais je peux toujours installer un prog dédié si j'en ai vraiment besoin).
Mais sinon il me va très bien (jamais aimé les onglets, entre autres).
Gamall wrote:
Kafou wrote:Lol, ptet pas quand même.
Sisisisi, c'est :ouioui J'insiste.
:ouioui... est si fier de sa belle voiture jaune et rouge !
:ouioui... montez avec lui, il vous emmènera au pays des jouets !
wiwi ! wiwi !

Sinon, je n'accepterai pas ce compliment de ta part tant que tu ne m'auras pas dit s'il est possible d'exprimer cette transformation :

X = tan ( x * pi/4 )
Y = tan ( y * pi/4 )
Z = 1

avec x et y variant (éventuellement par balayage discret) dans { -1 ... 1 }
sous une forme matricielle qui n'inclut pas de fonction trigonométrique :fear

Pour la petite histoire il s'agit d'une projection gnomonique inverse (à une normalisation près) :mosc

J'ai de gros doutes sur la faisabilité mais je préfère demander à un matheux :ange

Ou bien tu peux me dire ton prénom, au choix :archange
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway Sequence Explorer

Post by Gamall »

Kafou wrote:Non... le seul truc que je reproche à IE6 c'est d'être un peu trop loin des normes du W3C, et éventuellement de pas supporter le RSS.Mais sinon il me va très bien (jamais aimé les onglets, entre autres).
Moi je ne pourrais plus me passer des onglets :D (perso IE6 un bout de temps, puis avant browser, puis Opera)

Chacun ses goûts.
Kafou wrote:s'il est possible d'exprimer cette transformation :
tuféchié (c'est japonais :mosc:) j'aimerais me concentrer sur mes autres machins, et ya pas moyen, tu me pilonne le cerveau avec des trucs qui vont encore m'empêcher de dormir :monstre :monstre :monstre :monstre

Bon alors, je te préviens, la trigo n'a jamais été mon truc en maths. :assassin

*regarde la proj*

Tu fais un prog de cartographie ou d'optique ou bien c'est juste pour me casser les neurones ?
forme matricielle qui n'inclut pas de fonction trigonométrique
C'est trivialement possible en utilisant une notation complexe (merci Euler) :ouioui

Ok je triche.

Si tu ne veux pas d'exponentielle non plus, et que tu veux juste calculer avec une certaine précision, et que tu veux éviter cos et cie pour des raisons de perf, utilise un développement limité.

Ok, je triche encore.

Franchement, d'un point de vue mathématico-mathématique, je ne me serais même pas posée la question: j'ai beau chercher, je ne vois pas comment on peut exprimer une transformation trigonométrique sans trigonométrie... :?

Je serais tentée de répondre qu'évidemment NON. Mais je suis une daube en trigo donc sans démo, bof :D

[supprimé un passage où je m'interrogeais sur le truc, je ne voyais pas pourquoi c'était une proj gnomonique, je viens seulement de voir le "inverse". Vérification du cache, c'est toi qui as édité ton message :monstre :monstre :monstre ]

D'ailleurs, même inverse, j'ai des doutes. Si c'est une transfo gono inverse, ton espace d'arrivée est une sphère Image; or là c'est manifestement un plan.

C'est même le mouchoir de poche carré de côté 2 centré autour du point (0,0,1), dans le plan Z=1.

Et avec une vraie transfo gnomo en notation cartésienne, il te faudrait des tan(arccos) dans un sens et des arccos de tan (edit, non c'est pas ça, des cos de arctan) dans l'autre :?. Peu importe.

Tu es sûr que c'est bien la bonne transfo ?


Enfin dans tous les cas, cherche pas d'écriture sans trigo et sans exponentielle, je pense pas qu'il y en ait. Mais je suis loin d'être une autorité sur le sujet :lol
{<§ 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 Sequence Explorer

Post by Kafou »

Gamall wrote:Moi je ne pourrais plus me passer des onglets (perso IE6 un bout de temps, puis avant browser, puis Opera)
Attends, je viens tout juste de me mettre à la barre d'outils google pour simplifier mes recherches il y a un mois, chaque chose en son temps :mosc <- smiley plus adapté que jamais.
Ceci dit si un jour je change de browser, ça sera sûrement entre IE7 et Opera que ça se jouera. Veux pas de Firefox, parce que ses défenseurs sont des espèces d'intégristes stupides (pléonasme ?).
Gamall wrote:j'aimerais me concentrer sur mes autres machins, et ya pas moyen, tu me pilonne le cerveau avec des trucs qui vont encore m'empêcher de dormir
Héhé :OO3 (c'est quoi tes autres machins ?)
Gamall wrote:Tu fais un prog de cartographie ou d'optique ou bien c'est juste pour me casser les neurones ?
Company confidential (ou plus précisément pas envie de parler de ça ici, mais c'est pour mon boulot). Donc non c'est pas juste pour te faire chier.
Gamall wrote:Vérification du cache, c'est toi qui as édité ton message
:blush
Gamall wrote:Tu es sûr que c'est bien la bonne transfo ?
Je souhaite juste obtenir une direction, donc notamment le point du plan qui se trouve sur la droite passant par le centre de la sphère et suivant cette direction.
Ensuite il me suffit de normaliser mon vecteur, chose que je sais heureusement faire sans trigo :fear
Ceci dit je suis fatigué, c'est peut-être des arctan qu'il me faut en effet, j'y repenserai demain.

Merci pour ta tentative d'aide, mais vu que tu n'es pas sûre de toi et que tu ne donnes pas non plus ton prénom, je ne peux toujours pas accepter de ta part d'être traité de génie.
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway Sequence Explorer

Post by Gamall »

Kafou wrote:Je souhaite juste obtenir une direction, donc notamment le point du plan qui se trouve sur la droite passant par le centre de la sphère et suivant cette direction.
Hé ben alors c'est bien une projection gnomonique directe, et non pas inverse. :monstre :monstre

Vérification : est-ce qu'on a bien la même def : -> http://www-irem.univ-fcomte.fr/bulletin ... x26-25000a.


Et si c'est ça, d'ailleurs je compredns de moins en moins ce que tu cherches... :bobo
Kafou wrote:Je souhaite juste obtenir une direction, donc notamment le point du plan qui se trouve sur la droite passant par le centre de la sphère et suivant cette direction.Ensuite il me suffit de normaliser mon vecteur,
Le vecteur directeur de la droit passant par l'origine et le point " point du plan qui se trouve sur la droite passant par le centre de la sphère et suivant cette direction" a la direction

*tadaaaaam*

...dont tu es partie :oO (jolie disposition de thalès sur le triangle (0,0,0)(0,0,1)(ton point) , avec le triangle (000) (00z) (xyz) à l'intérieur.... )

C'est une jolie façon de définir l'identité entre deux vecteurs normalisés :lol


Ceci dit, ce n'est pas vrai dans le cas d'un vecteur défini par deux point distincts de l'origine cependant, mais ce n'est pas ce que tu décris :?

Je suppose que c'est ça que tu veux, sinon tu ne te serais pas embêté avec la trigo en premier lieu :foufou
Kafou wrote:Ceci dit je suis fatigué, c'est peut-être des arctan qu'il me faut en effet, j'y repenserai demain.
Moi aussi je suis fatiguée. Et j'ai mal à la tête à cause de toi.

Mais j'ai une bonne nouvelle pour toi quand-même:

tan(arccos x) = racine de (1-x^2) sur x
et
cos (arctan x) = 1 sur racine de (x^2 + 1)

La démo ce sera pour demain, hein. Ou plus tard, parce que j'ai des trucs à faire, non mais. C'est un truc classique.

Donc si c'est de ça que tu as besoin, oui c'est possible de se passer de cos et tout :P




Bon, aspirine et au lit.
Kafou wrote: Veux pas de Firefox, parce que ses défenseurs sont des espèces d'intégristes stupides (pléonasme ?).
C'est pour ça que je refuse mordicus d'utiliser Firefox. Les fan-boyz d'Opera sont plus discrets quand-même :?
Kafou wrote:Héhé s:OO3 s:OO3 (c'est quoi tes autres machins ?)
version mtliplaftforme de mon convertisseurs de packs de smileys, que j'avais promise il y a un bout de temps pour avant que phpbb passe Gold.

refonte de mon BaseJKA security fix (et opensourcisation parce qu"e)

éditeur hexadécimal parce que tous ceux que j'aime sont payants et que je n'en ai pas trouvé de bons gratuits, avec fonction pôur créer et utiliser automatiquement des fichiers de 'patch', parce que je veux ça.

entre autres.
Kafou wrote: Donc non c'est pas juste pour te faire chier.
J'aime bien ce "juste" en italique... :mosc
Kafou wrote:Attends, je viens tout juste de me mettre à la barre d'outils google pour simplifier mes recherches il y a un mois, chaque chose en son temps s:mosc s:mosc <- smiley plus adapté que jamais.
Moi j'aime pas les barred'outils àlakon:

sous opéra, je tape "g X Y" dans la barre d'adresse, et ça m'envoie sur la recherche google de X et Y. ;)
{<§ 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 Sequence Explorer

Post by Kafou »

Bon, pour la projection on en reparle demain si tu y tiens (moi pas plus que ça). En fait l'idée c'est d'associer (en 2D pour simplifier) à 1/2 (par exemple) la projection du point de la surface de la sphère (enfin du cercle en l'occurence) correspondant à un angle de pi/8 (pi/2 * 1/2). Ce afin de discrétiser de façon régulière le plan de projection en conservant un échantillonnage également régulier de la surface de la sphère (il ne le sera pas vraiment en 3D mais en 3D c'est pas possible).

Pour ma part, mon prochain prog à la con sera probablement une tentative de convertisseur tga->dds perso, pour voir si je suis capable de faire aussi bien que les outils actuels ^^ (mon stage de M2 ayant porté sur la compression de textures, j'ai déjà pas mal de code réutilisable)
Gamall wrote:sous opéra, je tape "g X Y" dans la barre d'adresse, et ça m'envoie sur la recherche google de X et Y
Ben disons que ça permet de faire des recherches dans ce que tu veux en cliquant sur le bon bouton (wikipédia, base d'images google, site actuel...) et que finalement c'est bien pratique.

Bonne nuit, dodo aussi.
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway Sequence Explorer

Post by Gamall »

Bon c'est gagné, je n'arrive pas à dormir :zzz
Kafou wrote:En fait l'idée c'est d'associer (en 2D pour simplifier) à 1/2 (par exemple) la projection du point de la surface de la sphère (enfin du cercle en l'occurence) correspondant à un angle de pi/8 (pi/2 * 1/2).
[pi/2 * 1/2 = pi / 4. Je suppose que c'était une typo et qu'il fallait lire 4 et non pas 8. (sinon on est mal biffés :gni)]

Bon, ben alors ta formule c'est trivialement x = tan (pi/2 * x). Et non, il n'y a pas moyen de l'exprimer exactement sans formule trigo ou exponentielle complexe. (dommage que ce ne soit pas une vraie transfo gnomonique que tu veuilles, parce qu'avec une vraie transfo la réponse serait x / racine (1-x^2) ; pas de formule trigo :P Si ça t'intéresse je peux te le démontrer.)

En revanche, il y a moyen de l'exprimer avec précision aussi grande qu'on veut avec un développement limité. Je ne sais pas si j'enfonce une porte ouverte ou pas, mais
tanx.png
tanx.png (1.58 KiB) Viewed 32381 times
Si tu veux calculer du tan dans un environnement où tu n'as pas accès aux fonctions trigo, genre asm, tu peux toujours utiliser ça. Sachant que la précision est mauvaise quand on se rapproche de pi/2, mais bonne au dela de pi/3 (en prenant le dev d'ordre 9, à l'ordre 5 faut attendre pi/4. Pour moi "bonne" ça veut dire erreur de l'ordre d'un centième.).

Tu peux aussi essayer directement avec les devs de sin et cos (tan = sin/cos), pour voir si la précision est meilleure.

Ou encore, tu peux utiliser une table de valeurs, si pour toi "discret" veut bien dire la même chose que pour moi, rien ne t'en empêche.

Yop. Bon dodooooooooooooooo.
{<§ 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 Sequence Explorer

Post by Kafou »

*message très largement édité, et ça continue*
Gamall wrote:Hé ben alors c'est bien une projection gnomonique directe, et non pas inverse
Oui, oui, j'aurais pas dû éditer, j'étais fatigué.
Gamall wrote:Bon c'est gagné, je n'arrive pas à dormir
Ah ben merde, si c'est ma faute désolé... :huh: Je te demandais juste au cas où, t'as aucun service à me rendre ! :P (suffit de me donner ton prénom et je te laisse tranquille :love )
Gamall wrote:[pi/2 * 1/2 = pi / 4. Je suppose que c'était une typo et qu'il fallait lire 4 et non pas 8. (sinon on est mal biffés )]
Je voulais dire pi/4 * 1/2 = pi/8.
Gamall wrote:x = tan (pi/2 * x).
X = tan( pi/4 * x ), oui c'est ce que j'ai écrit plus haut :P
Gamall wrote:dommage que ce ne soit pas une vraie transfo gnomonique que tu veuilles, parce qu'avec une vraie transfo la réponse serait x / racine (1-x^2)
Ca m'intéresse, je vais regarder ça (les "vraies" proj gnomoniques) aujourd'hui. Merci. Tu peux dormir maintenant hein...

Edit : je viens de regarder, mais je pige absolument pas d'où tu sors ton arccos. tan(arccos) ça revient à projeter un point du plan sur la sphère (plus précisément une projection orthographique inverse) puis de le reprojeter sur le plan d'une autre façon (plus précisément une projection gnomonique)...

Pas de développement limité (utiliser la fonction trigo de la lib standard est plus efficace et précis en l'occurence, bien que je suppose qu'elle utilise quelque chose comme ça en pratique :lol), je veux être maître du temps passé sur la fonction et autant de précision que possible.
Gamall wrote:Ou encore, tu peux utiliser une table de valeurs, si pour toi "discret" veut bien dire la même chose que pour moi, rien ne t'en empêche.
Voui mais non. Du moins je vois pas comment appliquer ça à mon bordel (la discrétisation doit pouvoir se faire à n'importe quel pas, alors bon si t'as une solution pour exprimer les valeurs à un pas plus précis en fonction d'un pas plus large je suis bien entendu preneur, mais je me penche pas trop là dessus pour le moment).
Kafou
Poulidor Gnomonique
Posts: 1526
Joined: Sun Aug 19, 2007 7:17 pm
Location: dans son labo
Contact:

Re: Conway Sequence Explorer

Post by Kafou »

Jeté un oeil à ton code,
Gamall wrote:C++;
:D
Gamall wrote:// rnb = real number of bytes
Non, rnb = Rythm and Blues

Sinon :
- je sais plus trop comment je faisais dans mon ancienne version (avec ton algo) niveau allocation de lignes mais ça devait être quelque chose dans le style 1.4 fois la taille de la précédente ouais. Ptet qu'on (avec mon pote) avait envisagé une version en liste chaînée pour avoir l'équivalent d'une seule ligne en mémoire à la fois, je me souviens plus, mais intuitivement je pense que ça serait plus lent et qu'on y gagnerait en fait rien en mémoire à cause des pointeurs, sauf à faire une liste chaînée de tableaux de taille définie mais là ça m'étonnerait qu'on ait fait ça.
- tu n'utilises pas du tout le même genre d'opérateurs que moi pour ton stockage binaire, m'enfin diviser par 4 et faire un décalage de 2 bits à droite c'est du pareil au même par exemple, je suppose qu'au final si les compilos sont bien fichus ça revient au même
- tes entiers font 64 bits ? si tu utilises un processeur 32bits il y a de grandes chances que ça aille plus vite avec des entiers de 32 bits (même si tu stockes deux fois moins d'infos dessus)

Ce qui est marrant c'est notre approche différente de la lecture des chiffres sur un entier.
Pour les lire successivement tu utilises un masque que tu décales progressivement à gauche et tu passes à l'entier suivant quand ton masque déborde, alors que moi je décalais les entiers eux-même à droite (macro REMOVE) et je passais à l'entier suivant quand le courant était à 0.
Ceci n'est plus vraiment vrai avec mon algo puisque je ne décale que quand je suis sûr de pouvoir dériver, et j'utilise effectivement des masques (construits à la compilation avec mes macros VAL et MORE) pour lire les chiffres lorsque je teste si je peux dériver ou pas.

Pour écrire de nouveaux chiffres ils sont décalés à gauche en fonction du nombre de chiffres déjà présents. Au passage j'ai remarqué que c'était plus rapide de tester de façon brutale avec des masques que de conserver comme toi des variables qui indiquent où on en est dans l'entier - bien sûr c'est valable que dans le cas où on a un maximum réduit de chiffres par ligne, dans mon cas 2 (4 en pratique mais dès qu'on a 3 ou 4 chiffres dans une ligne c'est forcément dérivé donc on ne rajoute rien sur cette ligne avant d'enlever) ce qui limite à 2 tests, dont un qui est une simple comparaison avec 0 (voir macro ADD).
Last edited by Kafou on Thu Aug 30, 2007 2:57 pm, edited 1 time in total.
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway Sequence Explorer

Post by Gamall »

Kafou wrote:Ah ben merde, si c'est ma faute désolé... s:huh: s:huh: Je te demandais juste au cas où, t'as aucun service à me rendre ! :P (suffit de me donner ton prénom et je te laisse tranquille :love )
T'en fais pas, je n'ai pas besoin de toi pour avoir des insomnies.
Kafou wrote:utiliser la fonction trigo de la lib standard
Comme ta question au départ c'était d'exprimer ta transfo sans fonction trigo, je pensais que tu ne pouvais pas les utiliser, pour une raison x ou y.
Kafou wrote:Edit : je viens de regarder, mais je pige absolument pas d'où tu sors ton arccos. tan(arccos) ça revient à projeter un point du plan sur la sphère (plus précisément une projection orthographique inverse) puis de le reprojeter sur le plan d'une autre façon (plus précisément une projection gnomonique)...
::gne
On va y aller étape par étape ; si je me trompte ou si on ne parle pas de la même chose, tu tapes fort avec le marteau rouge marqué "arrêt d'urgence", là, derrière la vitre.

Image
Pour moi, on a la sphère unité (rayon 1, centrée en 000), c'est à dire l'ensemble des points à distance 1 du centre. (shpère != boule).

Et quand on projette P_1, élément de notre sphère (sur sa surface, donc), sur le plan tangent d'équation Z = 1 (sur la figure, Z=-1, peu importe) on obtient P.

C'est ça que j'appelle projection gnomonique (directe).

Bon, maintenant, je fais une figure en dimension 2 avec paint, que ça va pas être triste. 8|

(rha il a posté autre chose entre temps, le sacripant ! Regarderai ça plus tard :P )
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Gamall
Hic sunt dracones
Posts: 4174
Joined: Fri May 26, 2006 11:09 pm
Contact:

Re: Conway Sequence Explorer

Post by Gamall »

En dim 2, on a cette config là :
fig1.PNG
tu as x, tu veux calculer xP.

On est toujours d'accord ?
{<§ Gamall Wednesday Ida §>}
{ Mods and Programs - Mods TES-IV Oblivion }
Post Reply

Who is online

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