Misez p'tit, Optimisez - N°74

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Misez p'tit, Optimisez - N°74

Message par gege »

Bonjour,
Profitant des 64Ko du MSX Sanyo PHC28 et des deux jours de VM, Ledudu s'est attaqué à la recherche des nombres "taxicab", c'est à dire ceux qui peuvent s'exprimer comme la somme de deux cubes d'au moins deux façons.
Après quelques heures de calcul il en a obtenu trois, le premier étant inférieur à 2000.
Ferez-vous aussi bien ?????
G.E.

P.S. : interdiction de regarder les photos du VM !

-->Sommaire des MPO
Modifié en dernier par gege le 16 oct. 2016 10:08, modifié 3 fois.
Avatar du membre
rogeroge
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4227
Enregistré le : 14 mai 2010 21:41
Localisation : Entre Nancy et Bercy : à Torcy

Re: Misez p'tit, Optimisez - N°74

Message par rogeroge »

Bonjour.
Pas mieux ! Je suis en possession du fichier de Ledudu. :mrgreen:
Il faut être fou pour venir sur ce site mais encore plus fou pour ne pas y revenir !
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2918
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit, Optimisez - N°74

Message par zpalm »

Une version en BASIC Sharp testée sur mon PC-1262:

Code : Tout sélectionner

10 FOR J=1 TO 100:FOR K=J+1 TO 100:A=J^3+K^3
20 FOR N=J+2 TO K-1:FOR M=J+1 TO N
30 IF A=M^3+N^3 THEN PRINT A:PRINT J,K,M,N
40 NEXT M:NEXT N:NEXT K:NEXT J
Je l'ai écrite après quelques essais sur HP Prime.
Tout d'abord une version rapide avec des listes :

Code : Tout sélectionner

EXPORT MPO74()
BEGIN
  LOCAL a,j,k,l:={},m:={},n;
  PRINT();
  FOR j FROM 1 TO 100 DO
    FOR k FROM j TO 100 DO
      a:=j^3+k^3;
      n:=POS(l,a);
      IF n THEN PRINT({a,m(n),{j,k}});
      ELSE l(0):=a;m(0):={j,k};
      END; 
    END;
  END;
END;
Puis une version sans liste, facilement portable, beaucoup plus économe en mémoire mais aussi beaucoup plus lente :

Code : Tout sélectionner

EXPORT MPO74()
BEGIN
  LOCAL a,j,k,m,n;
  PRINT();
  FOR j FROM 1 TO 100 DO
    FOR k FROM j+1 TO 100 DO
      a:=j^3+k^3;
      FOR n FROM j+2 TO k-1 DO
        FOR m FROM j+1 TO n DO
          IF a==m^3+n^3 THEN PRINT({a,{j,k},{m,n}}); END;
        END; 
      END;
    END;
  END;
END;
Cela donne 46 nombres "taxicab". Le PC-1262 trouve assez rapidement le premier nombre, j'attends toujours le second…
Les résultats sont présentés avec le nombre "taxicab" suivi de deux paires de nombres dont il est la somme des cubes :

Code : Tout sélectionner

{1729, {1, 12}, {9, 10}}
{4104, {2, 16}, {9, 15}}
{13832, {2, 24}, {18, 20}}
{39312, {2, 34}, {15, 33}}
{704977, {2, 89}, {41, 86}}
{46683, {3, 36}, {27, 30}}
{216027, {3, 60}, {22, 59}}
{32832, {4, 32}, {18, 30}}
{110656, {4, 48}, {36, 40}}
{314496, {4, 68}, {30, 66}}
{216125, {5, 60}, {45, 50}}
{439101, {5, 76}, {48, 69}}
{110808, {6, 48}, {27, 45}}
{373464, {6, 72}, {54, 60}}
{593047, {7, 84}, {63, 70}}
{149389, {8, 53}, {29, 50}}
{262656, {8, 64}, {36, 60}}
{885248, {8, 96}, {72, 80}}
{40033, {9, 34}, {16, 33}}
{195841, {9, 58}, {22, 57}}
{20683, {10, 27}, {19, 24}}
{513000, {10, 80}, {45, 75}}
{805688, {11, 93}, {30, 92}}
{65728, {12, 40}, {31, 33}}
{134379, {12, 51}, {38, 43}}
{886464, {12, 96}, {54, 90}}
{515375, {15, 80}, {54, 71}}
{64232, {17, 39}, {26, 36}}
{171288, {17, 55}, {24, 54}}
{443889, {17, 76}, {38, 73}}
{320264, {18, 68}, {32, 66}}
{165464, {20, 54}, {38, 48}}
{920673, {20, 97}, {33, 96}}
{842751, {23, 94}, {63, 84}}
{525824, {24, 80}, {62, 66}}
{955016, {24, 98}, {63, 89}}
{994688, {29, 99}, {60, 92}}
{327763, {30, 67}, {51, 58}}
{558441, {30, 81}, {57, 72}}
{513856, {34, 78}, {52, 72}}
{984067, {35, 98}, {59, 92}}
{402597, {42, 69}, {56, 61}}
{1016496, {47, 97}, {66, 90}}
{1009736, {50, 96}, {59, 93}}
{684019, {51, 82}, {64, 75}}
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°74

Message par C.Ret »

Comme j'arrive relativement tard sur ce fils, je me suis dit, qu'au lieu de rechercher séquentiellement tous ces nombres TaxiCab, je vais faire un p'tit code qui permet de vérifier vos calculs pour un entier N donné.

Comme mon p'tit SHARP n'a que 10 chiffres significatifs, je ne m'attends qu'à pourvoir déterminer des nombres TaxiCab de niveau 0,1 ou 2.

C'est à dire des nombres N qui au mieux s'exprimeront de trois manières : N = a³ + f³ = b³ + e³ = c³ + d³ avec a < b < c < L < d < e < f.
Où L est le cas limite (non acceptable) pour lequel le terme de gauche rattrape le terme de droite dans chaque somme.
C'est à dire N = a³ + a³ = b³ + b³ = c³ + c³ = 2.L³ de ce cas limite, on en déduit l'expression de L : L = ³√(N/2)

Le calcul de L, réduit bien plus le domaine de recherche que le simple fait de se limiter à 10 chiffres significatifs. Notons cependant, que cette dernière limitation entraine les intervalles suivants :
1 < a < 1708 , L < f < 1712 et L <= 1710 (le plus grand N que traite mon p'tit code est en fait non pas 1E+10 mais 1.0000422E+10

Une fois que l'on a bien délimité la zone de recherche, il me suffit de la parcourir avec, par exemple, a et pour chaque valeur de a, vérifier si le f correspondant existe et qu'il est bien un entier.
Si c'est le cas, alors j'affiche une des possibilités N = a³ + f³ et je continue en cherchant les éventuels autres couples d'entiers.

Comme a<f, plus a est grand, plus f diminue (en fait a tend vers L par valeur croissante et f tend vers le même L par valeur décroissantes.
Ce qui veut dire que si, au point a, la valeur de f n'est pas un entier, la partie entière de f est plus petite que f, et donc il existe une valeur z, plus grande que a qui permet d'obtenir l'éventuel entier f suivant (rappelons-nous que les valeurs f diminuent vers L !).

On peut donc gagner un temps considérable, car toutes les valeurs pour a ne sont pas bonnes à tester. On peut bondir de a en z afin de s'approcher au mieux des valeurs entières pour f. Mais attention dans certains cas on risque de ne pas passer au f suivant, mais de rester sur le même. Il faut donc veiller à ce que ce point soit effectivement diffèrent, c'est à dire que z soit strictement supérieur à et a.

Dans le code ci-dessous produit pour SHARP PC-1360 (mais qu'il est facile d'appliquer à un autre Pocket), les variables sont les suivantes :
N - Nombre testé N
L - Limite L
X et Y - Successivement les couples (a,f) (b,e) (c,d) s'ils existent.
Z - valeur de X pour l'éventuelle prochaine valeur entière de Y

Code : Tout sélectionner

10:"N" AREAD N : WAIT 0 : L=(N/2)^(1/3) , X=0 : IF L>1710 STOP
20:Y=(N-X^3)^(1/3) : IF Y= INT Y PRINT STR$ N;"= "; STR$ X:"^3 + "; STR$ Y;"^3"
30:Z=(N- INT Y^3)^(1/3) : IF INT Z>X LET X= INT Z-1
40:X=X+1 : LINE (0,0)-(128*X/L,0) : IF X<= INT L GOTO 20
50:BEEP 1 : END
Le calcul de la racine cubique est plus précis avec l'astuce du calcul du ratio 1/3 explicite qui permet de profiter des 13 chiffres significatifs internes du calculateur. Je perds quelques octets, par rapport à une version utilisant une variable (i.e. P=1/3 , L=(N/2)^P ) mais dans ce cas des erreurs d'arrondi surgissent car P ne contient qu'une représentation approchée de 1/3 à 10 chiffres.

L'instruction LINE sert à afficher une barre de progression, qui fait patienter le cas échant, mais surtout permet de voir les "sauts" lors de la recherche.

L'affectation biscornue X=INT(Z)-1 est une astuce qui anticipe sur le X=X+1 de la ligne 40: pour profiter du test X<L qu'à un seul endroit et évite ainsi les sauts au-delà du domaine autorisé.

La ligne 50 est facultative, elle sert qu'à faire sonner le Pocket à la fin de la vérification afin de faciliter les chronométrages.


Exemple d'exécutions :

Code : Tout sélectionner

RUN MODE
2  [def][ N ]
2= 1^3 + 1^3
>                          2"92 
[CLS]
27  [def][ N ]
27= 0^3 + 3^3
>                          4"24
1729  [def][ N ]
1729= 1^3 + 12^3
1729= 9^3 + 10^3
>                          9"03 
[CLS]
314156 [def][ N ]
>                          35"25
[CLS]
955016  [def][ N ]
955016= 24^3 + 98^3
955016= 63^3 + 89^3
>                          53"62 
[CLS]
87539319 [def][ N ]
87539319= 167^3 + 436^3
87539319= 228^3 + 423^3
87539319= 255^3 + 414^3
>                          3'57"07
Notons que les temps sont ceux correspondant au retentissement du bip de fin de recherche (sur 10 chiffres significatifs), mais que les résultats sont affichés bien avant.
Pour le dernier exemple, les trois couples de valeurs sont affichés en moins de 2min.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2918
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit, Optimisez - N°74

Message par zpalm »

zpalm a écrit :Une version en BASIC Sharp testée sur mon PC-1262:

Code : Tout sélectionner

10 FOR J=1 TO 100:FOR K=J+1 TO 100:A=J^3+K^3
20 FOR N=J+2 TO K-1:FOR M=J+1 TO N
30 IF A=M^3+N^3 THEN PRINT A:PRINT J,K,M,N
40 NEXT M:NEXT N:NEXT K:NEXT J
Les piles de mon PC-1262 ont rendu l’âme avant de trouver le deuxième nombre "taxicab".
Du coup voici une version beaucoup plus rapide:

Code : Tout sélectionner

10 FOR J=1 TO 50:FOR K=J+1 TO 50:A=J^3+K^3
20 FOR M=J+1 TO K-1:X=(A-M^3)^(1/3):N=INT(X)
30 IF N=X AND N>M THEN PRINT A:PRINT J,K,M,N
40 NEXT M:NEXT K:NEXT J
Avec de nouvelles piles, le premier nombre est trouvé en 35s, le deuxième en 13mn15s et le troisième en 14mn47s.

Utiliser le PC-1262 pour ce MPO m’a permis de me replonger dans le BASIC Sharp et les particularités de son instruction PRINT.
L’affichage des résultats se fait avec deux PRINT, un premier pour le nombre "taxicab" : PRINT A
Image

Et un deuxième pour afficher deux couples de nombres dont la somme des cubes est égale au premier nombre : PRINT J,K,M,N
Image

Par contre sur un Sharp qui n’a qu’une ligne d’affichage comme le PC-1403 par exemple on est limité à deux paramètres pour le PRINT, il faut donc deux instructions PRINT au lieu d’une seule pour les couples de nombres: PRINT J,K:PRINT M,N

Et merci à Rémi pour Pockemul qui m'a permis les captures d'écran ci-dessus.
Modifié en dernier par zpalm le 23 nov. 2018 18:14, modifié 1 fois.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°74

Message par C.Ret »

C'est en relisant mon explication psotée hier soir, que je me sui rendu compte que je pouvais faire mieux.

Dans N= a³ + b³

Au lieu de n'utiliser qu'un seul saut pour parcourir b par valeurs entières décroissantes, je peux en utiliser un second pour faire de même avec les valeurs croissantes entière de a.
Le code est plus court et la convergence plus rapide :

Code : Tout sélectionner


PROGRAM MODE

1:"N" AREAD N : WAIT 0 : A=1, L=(N/2)^(1/3) : IF L>1710 STOP
2:B=(N-A^3)^(1/3) , A=(N- INT B^3)^(1/3): IF A= INT A PRINT STR$ N;"= "; STR$ A;"^3 + "; STR$ INT B;"^3"
3:LINE (0,0)-(128*A/L,0) : A=1+ INT A : IF A<L GOTO 2
4:BEEP 1 : END

RUN MODE
2  [def][ N ]
2= 1^3 + 1^3
>                          1"96
27  [def][ N ]
>                          2"37
1729  [def][ N ]
1729= 1^3 + 12^3
1729= 9^3 + 10^3
>                          4"85
314156 [def][ N ]
>                          21"29
955016  [def][ N ]
955016= 24^3 + 98^3
955016= 63^3 + 89^3
>                          32"23
87539319 [def][ N ]
87539319= 167^3 + 436^3
87539319= 228^3 + 423^3
87539319= 255^3 + 414^3       (46"02)
>                          2'18"91
Bref, faire deux sauts divise presque par deux les temps et simplifie grandement l'algorithme.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°74

Message par C.Ret »

zpalm a écrit :[...]Avec de nouvelles piles, le premier nombre est trouvé en 35s, le deuxième en 13mn15s et le troisième en 14mn47s.[...]
Voilà qui m'a donné du fil à retordre avec mon SHARP PC-1360 et son BASIC bien plus lent.

Mais le challenge a été suffisamment fort pour que je m'acharne.
Finalement, et après quelques nuits blanches, j'arrive moi aussi à trouver quelques valeurs TAXICAB dans environ 1/4 d'heure :

Code : Tout sélectionner

RUN
Max43000                      0'00"0
1729= 1.12 9.10               4'21"3  bip
4104= 2.16 9.15               4'25"7  bip
39312= 2.34 15.33             8'59"9  bip
40033= 9.34 16.33             9'40"7  bip
13832= 2.24 18.20            10'27"6  bip
32832= 4.32 18.30            10'52"3  bip
20683= 10.27 19.24           11'17"5  bip
>                            14'46"1  bip bip bip

RUN
Max1729                       0'00"0
1729= 1.12 9.10                        
>                             0'59"4  bip bip bip bip



Ce ne fût pas simple. Il m'a fallu ruser un peu. Voici le code qui résulte de mes cogitations pathologiques, présenté ci-dessous façon listing des années '80 :

Code : Tout sélectionner

1:CLEAR : WAIT 0:M=255:      3:J=I(0): IF N(J)<=2*C       5:P=I,I=I(I) : GOTO 6+      8:NEXT B: NEXT A: BEEP 3
  DIM N(M),A(M),B(M),I(M       LET K=K-1,J(K)=J,I(0)=       SGN (N(I)-N)                : END
  ),J(M): INPUT "Max";M:       I(J): GOTO 3               6:PRINT STR$ N;"=";A(I);
  L=(M/2)^(1/3),N(0)=1E9     4:FOR B=1+A TO (M-C)^(1/       STR$ B(I);" ";A; STR$   
  ,K=1                         3):N=C+B^3,J=J(K): IF      7:N(J)=N,A(J)=A,B(J)=B,I   
2:FOR A=1 TO L:C=A^3,I=0       J=0 LET J=K                  (J)=I,I(P)=J,K=K+1
Comme j'ai pitié des lecteurs de ce forum, je donne ci-dessous un listing éclaté et largement commenté.

L'efficacité des codes de zpalm et les performances de son PC-1262 m'oblige à optimiser. Je dois, sur mon pauvre PC-1360 me limiter à uniquement deux boucles.
Une pour a et une pour b afin de calculer les n = a³ + b³ . Une utilisation astucieuse des tableaux va me permettre de "gagner du temps" en mémorisant ces valeurs.
Ce sera aussi la limite de cette méthode, car ces tableaux sont d'une taille limitée.

Pour permettre une recherche vers les plus hautes valeurs, il faut donc "économiser" la mémoire, en "recyclant" son espace. c'est à dire qu'il est préférable d'effacer les valeurs obsolètes au fur e à mesure de la recherche.
En effet, je construit mon tableau de données N() = A³ + B³ avec des valeurs croissantes de A et B. Il doit donc être possible de maintenir une liste triée de ces valeurs sans trop de complication.
De plus A < B, ce qui fait qu'au fur et à mesure de l'accroissement de A, les valeurs trop faibles vont pouvoir être retirées et l'espace mémoire ainsi recyclé.

Par ailleurs, comme les valeurs de B sont également croissantes, il doit y avoir une astuce qui permette à la fois de rechercher si la nouvelle valeur N existe déjà dans le tableau et d'accroitre celui-ci à moindre coût.
L'astuce étant ici de maintenir les valeurs N()en ordre croissant.

J'utilise donc une liste triée chainée. ce qui permet de l'accroître facilement tout en la maintenant triée et de trouver instantanément sa valeur minimale.

Pour illustrer mon propos, voici une présentation de ce qui se passe : limitant pour cette illustration ma recherche aux nombres inférieurs ou égaux à 1729 :

Code : Tout sélectionner

RUN
Max1729                       0'00"0
1729= 1.12 9.10                        
>                             0'59"4  bip bip bip bip
A ma grande surprise, il faut moins d'une minute pour débusquer les nombres TaxiCab jusqu'à 1729.

Code : Tout sélectionner

a:    a3  2a3    b: 2    3    4    5    6    7    8    9   10   11   12                  VALEUR EN MEMOIRE :
1      1    2       9   28   65  126  217  344  513  730 1001 1332 1729   #11       9   28   65  126  217  344  513  730 1001 1332 1729      
2      8   16           35   72  133  224  351  520  737 1008 1339        #19      28   35   65   72  126  133  217  224  344  351  513  520  730  737 1001 1008 1332 1339 1729 
3     27   54                91  152  243  370  539  756 1027 1358        #25      65   72   91  126  133  152  217  224  243  344  351  370  513  520  539  730  737  756 1001 1008 1027 1332 1339 1358 1729
4     64  128                    189  280  407  576  793 1064 1395        #28     133  152  189  217  224  243  280  344  351  370  407  513  520  539  576  730  737  756  793 1001 1008 1027 1064 1332 1339 1358 1395 1729  
5    125  250                         341  468  637  854 1125 1456        #28     280  341  344  351  370  407  468  513  520  539  576  637  730  737  756  793  854 1001 1008 1027 1064 1125 1332 1339 1358 1395 1456 1729 
6    216  432                              559  728  945 1216 1547        #27     468  513  520  539  559  576  637  728  730  737  756  793  854  945 1001 1008 1027 1064 1125 1216 1332 1339 1358 1395 1456 1547 1729
7    343  686                                   855 1072 1343 1674        #24     728  730  737  756  793  854  855  945 1001 1008 1027 1064 1072 1125 1216 1332 1339 1343 1358 1395 1456 1547 1674 1729 
8    512 1024                                       1241 1512             #16    1027 1064 1072 1125 1216 1241 1332 1339 1343 1358 1395 1456 1512 1547 1674 1729 
9    729 1458                                            1729             # 4    1512 1547 1674 1729
Comme on peut le voir, les valeurs N sont de moins en moins nombreuses au fur et à mesure que l'on avance. L'effacement rattrape car 2*C avance plus vite que A et B (et de façon cubique). Il ne faut donc mémoriser plus de 28 valeurs pour scanner jusqu'à 1729.

Par contre, la liste triée évolue à chaque boucle et sa maintenance peut être la source de ralentissement, sans compter que rechercher une valeur déjà rencontrée contenue dans la mémoire peut devenir de plus en plus lent.

La réussite du code provient du fait que les valeurs mémorisées ne sont pas remplacées, mais uniquement retirée du chainage, ce qui permet de recycler les emplacements mémoire. Pour ne pas perdre de temps à retrouver ces emplacements, ceux ci sont mémorisés dans une pile au fur et à mesure.

Voici un aperçu de la gestion mémoire correspondant au même exemple de recherche jusqu'à 1729 :

Code : Tout sélectionner

RUN
Max1729
L: 9.526                                                                   
a: 2a3:  b:                                                                         1:   2:   3:   4:   5:   6:   7:   8:   9:  10:  11:  12:  13:  14:  15:  16:  17:  18:  19:  20:  21:  22:  23:  24:  25:  26:  27:  28:        
1    2                                                                    # 0
1      2-12         9   28   65  126  217  344  513  730 1001 1332 1729   #11       9°  28   65  126  217  344  513  730 1001 1332 1729
2   16                                                                    #10           28°  65  126  217  344  513  730 1001 1332 1729
2      3-11             35   72  133  224  351  520  737 1008 1339        #19      35   28°  65  126  217  344  513  730 1001 1332 1729   72  133  224  351  520  737 1008 1339
3   54                                                                    #17                65° 126  217  344  513  730 1001 1332 1729   72  133  224  351  520  737 1008 1339
3      4-11                  91  152  243  370  539  756 1027 1358        #25      91  152   65° 126  217  344  513  730 1001 1332 1729   72  133  224  351  520  737 1008 1339  243  370  539  756 1027 1358 
4  128                                                                    #21          152            217  344  513  730 1001 1332 1729       133° 224  351  520  737 1008 1339  243  370  539  756 1027 1358
4      5-11                      189  280  407  576  793 1064 1395        #28     280  152  576  189  217  344  513  730 1001 1332 1729  407  133° 224  351  520  737 1008 1339  243  370  539  756 1027 1358  796 1064 1395
5  250                                                                    #21     280°      576            344  513  730 1001 1332 1729  407            351  520  737 1008 1339       370  539  756 1027 1358  796 1064 1395
5      6-11                           341  468  637  854 1125 1456        #28     280°1125  576  854  637  344  513  730 1001 1332 1729  407 1456  468  351  520  737 1008 1339  341  370  539  756 1027 1358  796 1064 1395
6  432                                                                    #16         1125  576  854  637       513  730 1001 1332 1729      1456  468°      520  737 1008 1339            539  756 1027 1358  796 1064 1395   
6      7-11                                559  728  945 1216 1547        #27         1125  576  854  637 1216  513  730 1001 1332 1729  559 1456  468° 945  520  737 1008 1339 1547  728  539  756 1027 1358  796 1064 1395
7  686                                                                    #21         1125       854      1216       730 1001 1332 1729      1456       945       737 1008 1339 1547  728°      756 1027 1358  796 1064 1395
7      8-11                                     855 1072 1343 1674        #24         1125 1072  854  855 1216       730 1001 1332 1729 1343 1456       945       737 1008 1339 1547  728°1674  756 1027 1358  796 1064 1395
8 1024                                                                    #14         1125 1072           1216                1332 1729 1343 1456                          1339 1547      1674      1027°1358      1064 1395 
8      9-10                                         1241 1512             #16         1125 1072           1216           1512 1332 1729 1343 1456                     1241 1339 1547      1674      1027°1358      1064 1395
9 1458                                                                    #4                                             1512°     1729                                         1547      1674                                
9        10                                              1729             #4                                             1512°    *1729*                                        1547      1674                 
Au début de chaque boucle externe (variable A), la liste mémorise est débarrassée des valeurs obsolètes.

Dans la boucle interne (variable B), les nouvelles valeur N sont ajoutées dans les places recyclée ou à la fin du tableau.

L'efficacité est due au fait que cette opération se fait sans boucle supplémentaire et en même temps que le maintient de l'ordre croissant ou la détection d'un valeur préexistante (c'est à dire d'un nombre TaxiCab !).

Voici la liste des variables et quelques explication sur la stratégie mise en ouvre:

Code : Tout sélectionner

VARIABLES:
 
Données de Base :
   M      Limite maximale du domaine de recherche. Scanner un domaine plus petit permet d'aller plus vite. M ne peut dépasser guère plus de 43000 du fait de la limite des 256 éléments des tableau (un scan fait alors environ 1/4 d'heure)
   
 A B N    Variables pour calcul de n = a³ + b³ 
   C      Pré-calcul de a³ 
   L      Borne supérieure de la boucle sur A
   
Indices :
   I      Indice de parcours  de la liste chainée mémorisée triée.
          Comme la liste est triée, I pointe en général sur l'élément immédiatement supérieur à N (ou égal à 0 s'il n'existe pas d'élément supérieur).
          Dans la boucle interne, I pointe au bon endroit pour rechercher l'élément N suivant, car les N soit toujours générés dans l'ordre croissant (puisque B est parcouru également dans cet ordre).
          La liste mémorisée n'est donc parcourue qu'une seule fois dans chaque boucle interne. La recherche ne reprend au début I=0 qu'au début des itérations sur A (boucle externe).

   J      Indice du prochain élément à ajouter dans la liste mémorisée.
          Les valeurs des positons disponibles sont données par la pile J() indicée par le nombre d'éléments mémorisés K.
          Une valeur nulle indique qu'il n'y a plus de position "récupérée", J prends alors la valeur K afin de placer le prochain élément en fin du tableau. 

   K      Nombre d'éléments mémorisés, augmenté d'une unité car l'élément N(0) est volontairement initialisée à +oo (1E9) afin de simplifier le parcours du chainage I().
          En effet, une valeur I(i)=0 indique la fin de la liste chainée (et triée). Le test N(i)<N permet de sortir de la boucle (ligne 5) sans tester la valeur nulle de I.    
          Simultanément, K est l'indice de la pile des positions libres J() car il indique la prochaine position libre dans J() ce qui permet de trouver instantanément une place libre
          sans parcourir ou déplacer les éléments dans la structure mémorisée. Une valeur nulle dans J() indique qu'il faut ajouter à la fin du tableau, c'est à dire à la positon K.
          Pour ne pas utiliser la positon réservée N(0), K est initialisé à 1 au début du programme. On ne peut donc mémoriser que 255 éléments sur un PC-1360.

Structure de donnée:
  N()  A()  B()    Valeurs des cubes et arguments  n = a³ + b³ déjà calculés.
                   Comme A est parcouru en ordre croissant, la boucle externe se charge d'éliminer les valeurs N() trop faible c'est à dire inférieures à 2.a³ car b>a implique N>(a³+a³)
                   Comme B est parcouru en ordre croissant, la structure de donnée n'est parcouru qu'une seule fois pour toute la boucle, l'indice I progressant conjointement à B.

  I()              Pointeurs de chainage des données. C'est ce tableau d'indices qui permet de maintenir les valeurs N() en ordre croissant.
                   Pour chaque valeur de la structure, I() pointe vers la valeur immédiatement supérieure. 
                   Pour le dernier élément, I() pointe vers l'indice zéro (0) ce qui indique la fin de la liste tout en pointant vers la valeur infinie N(0)== +oo.
  
  J()              Pile des positions libérées ou disponibles pour insertion d'un nouvel élément dans la structure.
                   Cette pile est indicé par le nombre d'éléments K. Initialisée à zéro 0, une valeur nulle dans cette pile indique qu'il faut ajouter le prochain élément en fin de tableau à la position K.

Affichage et signaux sonores:
 1729=1.12 9.10   signifie que 17289 = 1³+12³ = 9³+10³

Un bip retenti à chaque nombre TaxiCab trouvé et 3 bips indiquent la fin du scan afin de faciliter les chronométrages.
 
Voici le listing éclaté et largement commenté du code:

Code : Tout sélectionner

1 CLEAR : WAIT 0 :                                                         REM   Efface la mémoire et règle le temps d'arrêt aux affichages
  M=255 : DIM N(M),A(M),B(M),I(M),J(M) :                                   REM   La taille des tableaux est limitée à 256 éléments sur un PC-1360
  INPUT "Max";M : L=(M/2)^(1/3) , N(0)=1E9 , K=1                           REM   Saisie du domaine de recherche et initialisation des variables

2 FOR A=1 TO L : C=A^3 , I=0                                               REM   Boucle externe pour A de 1 à L. Le carré C est pré-calculé. L'indice de recherche est remis à zéro

3      J=I(0) :                                                            REM   Boucle d'effacement des valeurs trop faibles.
       IF N(J)<=2*C LET                                                    REM        On efface toutes les valeurs N(j) ≤ a³ + a³ c'est à dire à 2*C
                       K=K-1 ,                                             REM        Décrémente le nombre K de valeurs mémorisées 
                       J(K)=J ,                                            REM        Mémorise dans la pile d'indices J() la position ainsi libérée
                       I(0)=I(J) : GOTO 3                                  REM        I(0) doit toujours pointer sur l'élément mémorisé le plus petit, ici l'élément immédiatement supérieur indiqué par I()

4   FOR B=1+A TO (M-C)^(1/3) :                                             REM   Boucle interne pour B dans l'intervalle [ 1+a , ³√(M-a³) ] afin de ne jamais dépasser la limite M du domaine
       N=C+B^3 ,                                                           REM        La somme N = a³ + b³ est calculée à l'aide de la valeur C pré-calculée
       J=J(K) : IF J=0 LET J=K                                             REM        La position J du prochain élément est trouvée dans la pile d'indices J(),
                                                                                      le cas échéant l'élément est ajouté en fin de liste (position K).

                                                                           REM        Branchement triple : la comparaison de N et N(i) donne l'une des trois directions suivantes:
5      P=I,I=I(I) : GOTO 6+SGN (N(I)-N)                                    REM            -ligne 5- N(i)<N - L'indice de recherche I parcourt la liste mémorisée triée en suivant le chainage donné par les I()
6      PRINT STR$ N;"=";A(I); STR$ B(I);" ";A; STR$ B : BEEP 1 : GOTO 8    REM            -ligne 6- N(i)=N - Egalité ! On a trouvé un nombre TaxiCab, on l'affiche et on sonne l'utilisateur.
7      N(J)=N , A(J)=A , B(J)=B , I(J)=I , I(P)=J , K=K+1                  REM            -ligne 7- N(i)>N - La nouvelle somme N et ses argument A et B sont insérés à la position J dans la liste triée mémorisée. 
                                                                                                                Les chainages I() sont mis à jour à la position J nouvelle et à la position P du prédécesseur.
                                                                                                                Le nombre K d'éléments de la liste chainée triée mémorisée est augmenté d'une unité. 

8 NEXT B : NEXT A : BEEP 3 : END                                           REM  Fin des deux boucles et du programme

Voilà, il doit être possible de faire mieux ou d'augmenter la limite haute de recherche. Mais pour cela il faut complexifier le code afin d'utiliser plusieurs tableaux et de ne pas être limité à 255 valeurs.
Mais, le plus efficace est peut-être utiliser un autre Pocket, plus rapide, car déjà 15 min c'est long.

Pour finir, le code proprement présenté pour facilité la saisie (certaines lignes nécessitent de s'y prendre à deux fois )

Code : Tout sélectionner

1 CLEAR : WAIT 0 : M=255 : DIM N(M),A(M),B(M),I(M),J(M) : INPUT "Max";M : L=(M/2)^(1/3) , N(0)=1E9 , K=1
2 FOR A=1 TO L : C=A^3 , I=0
3   J=I(0) : IF N(J)<=2*C LET K=K-1 , J(K)=J ,  I(0)=I(J) : GOTO 3
4   FOR B=1+A TO (M-C)^(1/3) : N=C+B^3 , J=J(K) : IF J=0 LET J=K
5      P=I,I=I(I) : GOTO 6+SGN (N(I)-N)
6      PRINT STR$ N;"=";A(I); STR$ B(I);" ";A; STR$ B : BEEP 1 : GOTO 8
7      N(J)=N , A(J)=A , B(J)=B , I(J)=I , I(P)=J , K=K+1
8 NEXT B : NEXT A : BEEP 3 : END

Et je pense que très vite l'un des talentueux lecteur de ce forum trouvera le moyen de nous démontrer que c'est bien trop long déjà...
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2918
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit, Optimisez - N°74

Message par zpalm »

C.Ret a écrit : Voilà qui m'a donné du fil à retordre avec mon SHARP PC-1360 et son BASIC bien plus lent.
Je n'imaginais pas que le 1360 était beaucoup plus lent que le 1262!

Pour le reste, il va me falloir un peu de temps pour assimiler ce que tu proposes pour le 1360.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°74

Message par C.Ret »

Je voulais faire quelques captures d'écran ou d'impression à l'aide de l'excellent pockemul de remy.

Je me rends compte que les cinq tableaux de 256 éléments n'entrent pas sur une configuration qui n'est pas propulsée par au moins 32 ko de RAM !

Voici donc une version qui utilise moins d'octets car ne mémorise pas A() et B(), N() est utilisé seul pour mémoriser N et A, le B correspondant est déduit (cf. ligne 6)

Code : Tout sélectionner

1:CLEAR : WAIT 0:M=255: DIM N(M),I(M),J(M): INPUT "Max ";M:L=(M/2)^(1/3),N(0)=1E9,K=1
2:F0R A=1 T0 L:C=A^3,I=0
3:J=I(0): IF N(J)<2*C LET K=K-1,J(K)=J,I(0)=I(J): G0T0 3
4:F0R B=1+A T0 (M-C)^(1/3):N=C+B^3,J=J(K): IF J=0 LET J=K
5:P=I,I=I(I): G0T0 6+ SGN ( INT N(I)-N)
6:X=(N(I)-N)*1E3,Y=(N-X^3)^(1/3): PRINT STR$ N;"="; INT X; STR$ INT Y;" ";A; STR$ B: BEEP 1: G0T0 8
7:N(J)=N+A/1E3,I(J)=I,I(P)=J,K=K+1,I=J
8:NEXT B: NEXT A: BEEP 3: END
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Misez p'tit, Optimisez - N°74

Message par dprtl »

La recherche des nombres taxicab constitue un problème très difficile, voire infaisable pour un pocket un peu ancien !

En toute rigueur, voici la définition exacte du nième nombre taxicab, noté Ta(n) : c'est le plus petit nombre qui peut être exprimé comme une somme de deux cubes positifs non nuls de n façons distinctes à l'ordre des opérandes près. Donc, par exemple, 1729 est un nombre taxicab, mais pas 4104.

Cela dit, cette définition ne change pas grand chose à l'abominable complexité logarithmique du problème.

Sur mes vieilles machines, comme je n'arrivais pas à trouver Ta(3), qui a pourtant été découvert en 1957 (sur quel ordinateur ?!), je suis parti sur un programme Python naïf en 20 lignes et 388 octets pour smartphone. C'est ma meilleure calculette en 2016 :

Code : Tout sélectionner

#!/usr/bin/python3
print("Calcul en cours...")
L=[]
for A in range(1,1000):
  for B in range(1,1000):
    if A<=B:
      L.append([A*A*A+B*B*B,A,B])
L.sort()
print("Resultat :")
N=1
C=0
for I in range(1,len(L)):
  if L[I][0]-L[I-1][0]==0:
    C+=1
  else:
    C=0
  if C==N:
    N+=1
    for J in range(I-N+1,I+1):
      print("Ta({}) = {} = {}^3+{}^3".format(N,L[J][0],L[J][1],L[J][2]))
Après l'appel à la fonction "sort" interne de Python, la liste L contient toutes les combinaisons des sommes des cubes triées. Ceci n'est pas affiché par le programme ci-dessus :

Code : Tout sélectionner

[2, 1, 1]
[9, 1, 2]
[16, 2, 2]
[28, 1, 3]
[35, 2, 3]
[54, 3, 3]
[65, 1, 4]
[72, 2, 4]
[91, 3, 4]
[126, 1, 5]
[128, 4, 4]
[133, 2, 5]
[152, 3, 5]
...
[1991014991, 998, 999]
[1994005998, 999, 999]
Le résultat final s'affiche en quelques secondes :

Image
Modifié en dernier par dprtl le 02 sept. 2018 14:07, modifié 1 fois.
Avatar du membre
Miskatonic91
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 477
Enregistré le : 27 août 2016 17:28
Localisation : Valdemarnie

Re: Misez p'tit, Optimisez - N°74

Message par Miskatonic91 »

C'est rigolo de pouvoir programmer en python sur son smartphone.
Je vais essayer, tiens... :wink:
Un peu de tout, mais toujours de bon goût :wink:
Répondre

Retourner vers « Tous les Pockets »