Misez P'tit, Optimisez - N°32 (factorielle)

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 de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1983
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par C.Ret » 15 janv. 2013 21:51

babaorhum a écrit : Mais 69! est calculé en ... 13,5s (car le test est désormais dans la boucle) mais c'est hors cahier des charges !
C'est toujours de l'ordre de quelques secondes, j'ai sur mon bureau un pocket BASIC qui, pour calculer 69! utilise un temps de l'ordre de quelques minutes.

Mais, ce mêm pocket se débrouille bien pour calculer avec précision :

Code : Tout sélectionner

10: "F" AREAD N:H=0,G=0,F=1
20:FOR I=1 TO N:F=FI:G=GI:H=HI
30:  IF F>|E8 LET R=INT |E-8F,G=G+R,F=F-|E8R
40:  IF G>[E8 LET R=INT |E-8G,H=H+R,G=G-|E8R
50:NEXT I
60:PRINT USING "####";N;"!=";USING "#########";H;G;F:END

  17!=            3556874 28096000.
  18!=           64023737 05728000.
  19!=        12 16451004 08832000.
  20!=       243 29020081 76640000.
  21!=      5109 94211717 09440000.
  22!=    112400 07277776 07680000.
  23!=   2585201 67388849 76640000.
  24!=  62044840 17332394 39360000.
  25!=1551121004 33309859 84000000.  (34.2s)

  69!= 171 12245242 81413113 72468338 88127283 90922705 44893520 36939364 80409232 57279754 14064742 40000000 00000000 (~10.1min)
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator |HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
bkg2018
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 359
Inscription : 30 mai 2012 16:57

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par bkg2018 » 16 janv. 2013 01:14

zpalm a écrit :
bkg2018 a écrit :Sur TI57 avec la contrainte 0!=1 et une utilisation sans préstockage dans les registres je n'ai pas grand chose de dément...

00 Sto 0
01 1
02 Sto 1
03 Lbl 0
04 Inv Dsz
05 Gto 1
06 Rcl 0
07 Prd 1
08 Gto 0
09 Lbl 1
10 Rcl 1
11 R/S

On ne peut plus ruser avec RST à cause de l'initialisation de R0 et R1. Et on ne peut pas trop éviter deux labels : un pour boucler, un pour sortir de la boucle.
... 10 pas avec RST, sans label et avec 0!=1

Code : Tout sélectionner

00 2nd C.t
01 x=t?
02 1
03 STO 0
04 =
05 INV 2nd DSZ (Decrement & Skip if not Zero)
06 INV SBR     (RTN)
08 *
08 RCL 0
09 RST         (Reset program counter to first step = GTO 00)
WOW :-) Encore une fois zpalm tu nous sors un diamant :-)

Il faut dire que nous sommes dans deux paradigmes très opposés de programmation : moi je suis déformé par 30 années de boulot où on doit programmer des trucs toujours dans le but d'une intégration facile au coeur d'autres programmes, ce qui est exactement incompatible avec une optimisation au ras du métal. Et pour tout dire, j'ai toujours préféré la propreté et le but à atteindre, plutôt que le côté 'mécano de formule 1'

Mais même sans çà je ne crois pas que j'aurais su faire ce que tu nous as pondu !

Chapeau bas !
HP : 67 25 34C 15C 41CX 48S* 48SX 48GX 35S* WP34S* 39gII*
TI : SR52 57 58C* 59 Programmer 66 74S 65
Sharp : PC 1245 1251* 1262 G-850S G-850V
Canon : X-07* F-800P*
Casio : CG-8 SF5300E*
*: persos d'époque

Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1290
Inscription : 27 oct. 2010 20:46

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par Gilles59 » 16 janv. 2013 12:54

bkg2018 a écrit :
Gilles59 a écrit :J'ai pas la 602 (ou 502), sous la main mais :

Code : Tout sélectionner

Min00 ISZ
LBL0
MR00 
*
DSZ
GOTO0
=
en 8 pas devrait le faire avec 0! -> 1
Doit y avoir mieux

pas mieux que les solution précédente en RPL
MMmmm si ISZ fait ce que je pense, tu ne serais pas en train de calculer factorielle de N+1 ?
Oups oui !
x=0 1 Min00
LBL0
MR00
*
DSZ
GOTO0
=
Ce qui est très proche de la solution de Zpalm pour TI57. Je me rends compte que la TI57 et très proche des 502/602P, plus que de la TI58 par beaucoup d'aspects
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49G+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+

Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1290
Inscription : 27 oct. 2010 20:46

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par Gilles59 » 16 janv. 2013 18:20

Une solution récursive sur 50G qui montre la souplesse de ce calculateur et façon de mélanger du RPN et de l'algébrique (mais aussi sa 'complexité' puisqu'il y a de multiples façon de résoudre un problème) :

Code : Tout sélectionner

'f(n)=IFTE(n==0,1,n*f(n-1))' DEFINE
On peut utiliser cette fonction en RPL ou algébrique 'pur'

5 f donne 120

ou

'f(5)' EVAL
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49G+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+

Avatar de l’utilisateur
Marcus von Cube
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 913
Inscription : 20 avr. 2006 13:48
Localisation : Wehrheim, Allemagne
Contact :

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par Marcus von Cube » 20 janv. 2013 15:33

Comme démonstration j'ai créé une version récursive pour la WP 34S:

Code : Tout sélectionner

LBL'FAC'
IP
x>1?
GTO 00
1
RTN
LBL 00
LocR 001
STO .00
DEC X
XEQ'FAC'
RCL× .00
RTN
C'est ni court ni efficace mais un bon exemple.

Avatar de l’utilisateur
bkg2018
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 359
Inscription : 30 mai 2012 16:57

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par bkg2018 » 20 janv. 2013 17:01

Marcus von Cube a écrit :Comme démonstration j'ai créé une version récursive pour la WP 34S:

Code : Tout sélectionner

LBL'FAC'
IP
x>1?
GTO 00
1
RTN
LBL 00
LocR 001
STO .00
DEC X
XEQ'FAC'
RCL× .00
RTN
C'est ni court ni efficace mais un bon exemple.
héhé si on fait çà sur la plupart de nos bébettes on va calculer 5! et çà plantera après !
HP : 67 25 34C 15C 41CX 48S* 48SX 48GX 35S* WP34S* 39gII*
TI : SR52 57 58C* 59 Programmer 66 74S 65
Sharp : PC 1245 1251* 1262 G-850S G-850V
Canon : X-07* F-800P*
Casio : CG-8 SF5300E*
*: persos d'époque

Avatar de l’utilisateur
Marcus von Cube
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 913
Inscription : 20 avr. 2006 13:48
Localisation : Wehrheim, Allemagne
Contact :

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par Marcus von Cube » 20 janv. 2013 17:26

bkg2018 a écrit : héhé si on fait çà sur la plupart de nos bébettes on va calculer 5! et çà plantera après !
On a besoin d'une pile "sans" limite ou des mémoires locales pour l’implémentation d'un algorithme récursive. Que les machines à RPL ou à C sont capable de ça. Peut-être l'Inspire et le 39gii sont des candidates aussi.

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1983
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par C.Ret » 20 janv. 2013 23:14

Un condidat inattendu pour l'appel récursif :

SHARP PC-1211:

Code : Tout sélectionner

1:"N" AREAD N:F=1:GOSUB "F":PRINT N;"!=";F:END

2:"F" IF F>1 LET F=FN,N=N-1:GOTO "F"
3:RETURN 
Ah! Zut, c'est pas récursif ! Juste presque...


En 1983, alors que je découvrais les factoriel au Lycée, j'utilisais le programme de calcul des factoriels suivant :

Les factorielles sont pré-calculées en mémoire en lançant l'iniitalisation (en général un dimanche après-midi afin que le pocket soit prêt pour le cours de math du lendemain). L'iniitalisation se termine soit en affichant 69!, soit sur un message d'erreur de dépassement de la mémoire 1: 4.................. quand ce petit programme partageait la mémoire du SHARP avec d'autres utilitaires que j'utilisé conjointement en math et en physique (et autres anti-sêches !).

Puis le PC-1211 calcule 'rapidement' toutes les factorielles N! (et mémorise la dernière factorielle calculée dans F)

Code : Tout sélectionner

1:A(27)=1:FOR N=1 TO 69:A(27+N)=NA(26+N):NEXT N
2 "F" AREAD N:F=A(27+N):PRINT N;"!=";F:END
Puis en 1985, j'ai eut mon interface CE-121. A cette occasion, le programme avait évolué en :

Code : Tout sélectionner

1:INPUT #"FACTO";A(27)
2:"F" AREAD N:PRINT N,A(27+N):END
Les factorielles précalculées étaient stockées sur une cassette (que j'ai égarée d'ailleurs + je ne sais plus si le nom du fichier était bien FACTO, ou FACTORI ??)
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator |HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
ledudu
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4514
Inscription : 26 mars 2009 14:07
Localisation : Ile de France
Contact :

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par ledudu » 02 févr. 2013 20:13

Machine : PRO FX-1
Langage : Fortran Casio

Code : Tout sélectionner

- Entrée de N
ST#0:ENT0:1=K1:
- Calcul de N!
ST#1:1=1x0:0=0-K1:If 0=K1:2:2:1:
- Affichage de N!
ST#2:ANS 1:GOTO 0:
69! en 34s.

Traduit sur HP-19c ( :D ) : 37 s

D'autres programmes pour PRO Fx-1.
Dernière édition par ledudu le 12 mars 2017 18:27, édité 2 fois.

Avatar de l’utilisateur
dprtl
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 282
Inscription : 27 janv. 2013 01:26
Localisation : Strasbourg
Contact :

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par dprtl » 03 févr. 2013 01:19

bkg2018 a écrit :En BASIC:

1 INPUT N:F=1:FOR I=2 TO N:F=F*I:NEXT:PRINT F

Arf ... C'est chiant.
Trop simple en basic ? On peut complexifier un peu en intégrant la formule de Stirling. J'ai adapté mon vieux code, pas spécialement optimisé (du coup je suis un peu hors sujet ?) de la PB1000 pour le Z-1 (LGT à changer par LOG) :

Code : Tout sélectionner

10 INPUT"!",A
20 IFA>20THEN40
30 F=1:FORI=2TOA:F=F*I:NEXT:PRINTF:GOTO10
40 B=A*(LOGA-LOGEXP1)+LOG(2*PI*A)/2:E=INTB:D=10^(B-E):F=(1/12+1/288-1/373/A)/A)/A
50 N=D+D*F:PRINTN"E"E:GOTO10
Cela permet d'obtenir rapidement des approximations :

!253 = 5.17346099 E 499
!254 = 1.314059091 E 502
!255 = 3.350850687 E 504
!3000 = 4.149359587 E 9130

Avatar de l’utilisateur
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2912
Inscription : 06 sept. 2011 14:57
Localisation : Normandie / Antwerpen

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par Hobiecat » 03 févr. 2013 14:01

dprtl a écrit :du coup je suis un peu hors sujet ?
Oui, si l'on s'en tient à la définition des MPO d'il y a 30 ans... Non, si l'on se base sur les MPO de Sili qui sont plus un prétexte à s'amuser à programmer, à optimiser des programmes (quand même !), à partager des astuces de programmation et à faire tourner les machines qui dorment sur nos étagères ! A ce titre, ton programme est tout à fait recevable et intéressant.

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1983
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par C.Ret » 03 févr. 2013 21:18

dprtl a écrit :[...]!3000 = 4.149359587 E 9130
Eh! Pas mal, et quelque soit la définition du MPO.
C'est loin d'être hors sujet, c'est le plus court programme et le plus optimisé de tous ceux postés jusqu'ici qui permette de calculer (en un temps négligeable) la factorielle de 3000 !

j'suis pas prêt de donner tous les chiffres de 3000! Surtout avec mon PC-1211 :lol:
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator |HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
ledudu
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4514
Inscription : 26 mars 2009 14:07
Localisation : Ile de France
Contact :

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par ledudu » 09 févr. 2013 23:31

Machine : Casio PB-2000c
Langage : prolog

Comment ne pas faire une factorielle en prolog :

Code : Tout sélectionner

fact(0,1):-!.
fact(X,N):- >(X,0), Y is X-1,fact(Y,O),N is X*O.
?-fact(9,N).
N = 362880.
Dernière édition par ledudu le 10 févr. 2013 09:17, édité 1 fois.

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1983
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par C.Ret » 10 févr. 2013 08:36

Bonjour,

J'ai un peu de mal à cerner le fonctionnement de ce système.

La première clause est limpide, on apprend à PROLOG que 0!=1. Ca c'est ok

Code : Tout sélectionner

fact(0,1) :- !.
Incidieusement, on apprend aussi à l'opérateur que les factorielles sont codé par fact(N,F) où F=N!
Bien.

Mais avec la seconde clause, j'ai un peu de mal. Peut-être à cause d'une confusion entre 0 (zéro) et O (o comme Odile).

Je m'attendais à une définition par récurrence du style :

Code : Tout sélectionner

fact(N,F) :- M is N-1 , fact(M,E) , F is E * N.
où on apprend à PROLOG la relation de récurrence n! = n . (n-1)!

L'avantage de PROLOG, c'est qu'en définissant le calcul de F=9!, on obtiendrai aussi le calcul de N pour une factorielle donnée.
Donc, si je ne me trompe pas, on doit avoir ?- fact(9,F). qui donne F = 36280. et ?- fact(N,520). qui devrait retourner N = 5.

Malheureusement, en PROLOG M is N-1 n'est pas interprété symboliquement et dans la pluspart des implémentation on obtient ?- fact(N,520) renvoit alors "ERROR: Argument(s) are not sufficiently instantiated."
Dernière édition par C.Ret le 10 févr. 2013 09:33, édité 1 fois.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator |HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
ledudu
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4514
Inscription : 26 mars 2009 14:07
Localisation : Ile de France
Contact :

Re: Misez P'tit, Optimisez - N°32 (factorielle)

Message par ledudu » 10 févr. 2013 09:21

Bonjour C.ret,

A part que le choix de la lettre O n'était pas judicieux de mon côté (je ne me serais pas planté en saisissant le code) , on a la même formule.
J'ai juste ajouté la condition que le paramètre en entrée doit être positif.

Répondre

Revenir vers « Tous les Pockets »