Misez p'tit, Optimisez ! n°63-64 : L'échiquier de Sissa

[Marge]

Bonsoir, Alain,
J'ai bien raté une marche : je ne connaissais pas la formule, et du coup j'ai découvert (après bien du monde) que 2^64-1 équivaut à la somme de toutes les puissances précédentes de deux.

Du coup mon programme est faux (modifier 64 en 63), je vais en porter le carcan pendant toute une semaine, cela me permettra de méditer cette leçon de modestie. Merci !

(mais je ne m'avoue pas vaincu pour le MPO 64 !)

Edition : ça sent les études de binaire tout ça...

[zpalm]

Marge, dans ton programme je ne vois pas où tu initialises Z pour ton STO + . Z, il manque peut être un CLST au début.

Dans le même style en 11 pas et 15 octets (sans compter le LBL de début):

Code : Tout sélectionner

01 LBL S
02 63        en partant de la première case il faut ajouter le contenu des 63 cases suivantes
03 1         valeur de la première case
04 x²        initialise LAST x  à 1 pour la somme des cases (on gagne 1 octet par rapport à STO L)
05 LBL 00
06 STO+ X    double x (sans modifier LASTx)
07 STO+ L    ajoute à la somme des cases précédente   
08 DSE Y     passe à la case suivante
09 GTO 00    boucle si on n'a pas fini  
10 LASTx     rappelle la somme des cases
11 RTN

sinon toujours pour les blancs (on n'est pas à une unité près):

Code : Tout sélectionner

01 LBL S
02 2
03 64
04 y^x
05 RTN

[alain1261]

Bonsoir, Alain,
J'ai bien raté une marche : je ne connaissais pas la formule, et du coup j'ai découvert (après bien du monde) que 2^64-1 équivaut à la somme de toutes les puissances précédentes de deux.

Du coup mon programme est faux (modifier 64 en 63), je vais en porter le carcan pendant toute une semaine, cela me permettra de méditer cette leçon de modestie. Merci !

(mais je ne m'avoue pas vaincu pour le MPO 64 !)

Edition : ça sent les études de binaire tout ça...

Bonjour,

je dois avouer que lors de mes premiers essais, j'avais fait la somme de 2^x pour x de 1 à 64 (au lieu de 0 à 63)

merci pour ce défi, qui m'a permis d'apprendre (ou réapprendre) à utiliser les suites et ∑ sur ti92 (et classpad, c'est exactement la même syntaxe).

je vais essayer de réfléchir au MPO64 sur une machine plus intéressante que les TI92 ou classpad, qui travaillent nativement sur les entiers jusqu'a environ 600 chiffres...

[Tipoucet]

En même temps, se servir d'une formule, c'est moins sportif. J'aime bien l'idée (laborieuse mais puisque c'est la machine qui calcule ...) de cascades de multiplications s'ajoutant les unes aux autres jusqu'à la limite fixée (pas de formule, pas de puissances). Par exemple le programme demande dans un premier temps le nombre de cases (on ne se limite pas à l'échiquier), le nom de notre céréale favorite (pas forcément du riz) et hop c'est parti pour les multiplications en boucles. J'ai une grosse flemme mais j'aurais bien sorti la TI-57.
Bonne journée

[C.Ret]

Bon, je me lance c'est enfin les vacances.

Mon SHARP PC-1211 joue les noirs :

Code : Tout sélectionner

1:A=0,B=0,C=1,E=€7,D=1/E,F=2,K=64
2:FOR I=1 TO K:C=FC,R=INT CD,C=C-RE,B=R+FB,R=INT BD,B=B-RE,A=R+FA:NEXT I
3:C=C-1:USING "########":PRINT A;B;C: END

et affiche après environ 1min17s le résultat suivant :

Code : Tout sélectionner

┌────────────────────────┐
│  184467 4407370 9551615│
└────────────────────────┘

il faut lire 18 446 744 073 709 551 615.
Mais mettre un espace tous les 3 chiffres nécessite un affichage de plus de 24 caractères, ce que ne permet pas mon équipement.

Les paramètres sont :
- nombre de cases de l'échiquier K = 64
- facteur multiplicatif entre chaque case F=2
- nombre de grains de riz sur la première case C=1

Le résulat est formé par la juxtaposition des trois registres A, B et C
Le registre E contient 10^7 et D l'inverse de E afin de profiter au maximum des multiplications implicites de ce SHARP.
Le registre R est utilisé pour les retenues. En réalité il ne prend que les valeurs 0 ou 1.

[gege]

Bonjour,
Un peu sur le même principe sur PC1500 :

Code : Tout sélectionner

100 A=1:B=0:FOR I=1 TO 64
110 IF A<5000000000 LET A=A+A:B=B+B:GOTO 130
120 A=A-5000000000:A=A+A:B=B+B+1
130 NEXT I:PRINT A;B-1

Ca affiche1844674407 3709551615 en 4 secondes (9 sur le PB-700).
G.E.

[zpalm]

Sur HP-16C, pour connaitre la somme des grains jusqu'à une case donnée:

Code : Tout sélectionner

001-43.22. A   g LBL A
002-  42  44   f WSIZE
003-  42   3   f UNSIGN
004-  43  35   g CLx
005-  42  30   f NOT
006-  43  21   g RTN

Utilisation: appuyer sur DEC puis entrer le numéro de la case suivi de GSB A.

Par exemple: 4 GSB A donne 15, et 64 GSB A donne 18446744073709551615 en 1 seconde ... le tout en 6 octets, pas trop mal pour une machine de 1982.

Ça marche aussi sur WP-34S en remplaçant WSIZE par WSIZE->X. La touche DEC de la 16C (base 10) est remplacée par f 10 (touche EEX), l'affichage des digits masqués à gauche ou à droite se fait avec f / g x<>y, la sortie du mode entier par f H.d (touche RCL).

[zpalm]

Bonjour,
Un peu sur le même principe sur PC1500 :

Code : Tout sélectionner

100 A=1:B=0:FOR I=1 TO 64
110 IF A<5000000000 LET A=A+A:B=B+B:GOTO 130
120 A=A-5000000000:A=A+A:B=B+B+1
130 NEXT I:PRINT A;B-1

Ca affiche1844674407 3709551615 en 4 secondes (9 sur le PB-700).
G.E.

Testé sur PC-1262: le PRINT final est erroné, il faut à la place PRINT B;A-1

La même chose en 28 pas sur HP-29C:

Code : Tout sélectionner

01 LBL 0
02 STO 0
03 1
04 STO 1
05 0
06 STO 2
07 LBL 1
08 RCL 2
09 STO + 2
10 RCL 1
11 5
12 EEX
13 9
14 x>y
15 GTO 2
16 STO - 1
17 1
18 STO + 2
19 LBL 2
20 RCL 1
21 STO + 1
22 DSZ
23 GTO 1
24 1
25 STO - 1
26 RCL 2
27 RCL 1
28 RTN

On entre le nombre de cases puis GSB 0. Le programme retourne les 10 chiffres de poids faible dans le registre X et les 10 chiffres de poids fort dans le registre Y, accessibles par x<>y.

64 GSB 0 donne 1844674407 3709551615 en 32 secondes.

[babaorhum]

Bonjour,

C.Ret, toujours aussi incroyables tes solutions avec le PC-1211 - Gege, algorithme étonnant, simple et efficace bravo ! - Zpalm, je découvre les fonctions WSISE et UNSIGN sur ma 16C ...

De mon côté, j'étais parti avec mon 75C pour essayer de me rapprocher des années 80 de l'énoncé initial ... et j'ai écris un code bizarre, pas terrible pour un MPO mais qui fonctionne :

Code : Tout sélectionner

1 REM SISSA POUR HP75C
10 R$="1" @ FOR K=1 TO 64 @ C=0 @ FOR I=LEN(R$) TO 1 STEP -1 @ S=VAL(R$[I,I])*2
20 IF S>=10 THEN S=S+C-10 @ C=1 ELSE S=S+C @ C=0
30 R$[I,I] = STR$(S) @ NEXT I @ IF C=1 THEN R$="1" & R$ 
40 NEXT K @ I = LEN(R$)
50 S = VAL(R$[I,I])-1 @ IF S<0 THEN R$[I,I]="9" @ I=I-1 @ GOTO 50
60 R$[I,I]=STR$(S) @ DISP R$

J'obtiens bien 18446744073709551615 à l'affichage en un peu moins de 30 secondes ...

Tout ca n'est pas dans l'esprit du MPO mais je crois que je peux calculer jusqu'à 99 cases avec ce code ! (qui trouve pourquoi ?)

J'avais une question complémentaire ... combien pèsent 18446744073709551615 grains de riz ??? (c'est pour me rendre compte)

Merci marge pour ce MPO

[babaorhum]

En fait j'ai trouvé que 1000 grains de riz pèsent environ 30 g .... (merveilleux internet quand même)
donc donc donc:

Code : Tout sélectionner

18446744073709551615
----------------------------------- = poids en tonnes
         30000000

et ca fait ... 614891469123.6517 tonnes de riz sauf erreur

la production mondiale est de 480 000 000 tonnes par an (toujours internet ...)

ce qui nous fait environ 1280 ans de production mondiale ...

Dingue cet échiquier de Sissa ...

[bernouilli92]

J'avais une question complémentaire ... combien pèsent 18446744073709551615 grains de riz ??? (c'est pour me rendre compte)

Merci marge pour ce MPO

Si on compte 25 à 50 grains par gramme, on arrive à environ 370-740 milliard de tonnes, soit environ 500 à 1000 fois la production annuelle mondiale de riz.

[babaorhum]

yes bernouilli, ca colle bien, merci !

[bernouilli92]

En tout cas, cela fait plus que beaucoup. Je pense même que Sissa n'avait pas tout à fait idée de combien cela faisait. Car sinon il n'aurait pas fait une récompense impossible à satisfaire.

[tyann]

Bonjour

Je vous propose une extension: sachant que dans 2 litres
d'eau on peut cuire 500g de riz, combien faudra-t-il à Sissa
Non je rigole

[Gilles59]

Pour l'anecdote, en utilisant la même formule que donnée au dessus pour la TI92 ( ∑ ...), on obtient (mode exact) sur la HP49 :

e^(64*LN(2))-1
EXP2POW donne alors 2^64-1
EVAL donne alors tous les chiffres du nombre

Le CAS retarde l'évaluation numérique et il à mon avis raison car par exemple 2^64-1 est plus pratique à manipuler qu'un nombre exact de 20 chiffres