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 du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

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

Message par C.Ret »

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 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
bkg2018
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 359
Enregistré le : 30 mai 2012 16:57

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

Message par bkg2018 »

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 : 1602
Enregistré le : 27 oct. 2010 20:46

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

Message par Gilles59 »

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+ CM14 et MM12 / Alice 32
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

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

Message par Gilles59 »

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+ CM14 et MM12 / Alice 32
Avatar du membre
Marcus von Cube
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 914
Enregistré le : 20 avr. 2006 13:48
Localisation : Wehrheim, Allemagne
Contact :

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

Message par Marcus von Cube »

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 du membre
bkg2018
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 359
Enregistré le : 30 mai 2012 16:57

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

Message par bkg2018 »

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 du membre
Marcus von Cube
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 914
Enregistré le : 20 avr. 2006 13:48
Localisation : Wehrheim, Allemagne
Contact :

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

Message par Marcus von Cube »

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 du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

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

Message par C.Ret »

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 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
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5632
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

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

Message par ledudu »

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.
Modifié en dernier par ledudu le 12 mars 2017 17:27, modifié 2 fois.
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°32 (factorielle)

Message par dprtl »

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
Modifié en dernier par dprtl le 31 janv. 2021 23:41, modifié 1 fois.
Avatar du membre
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3626
Enregistré le : 06 sept. 2011 14:57
Localisation : Normandie

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

Message par Hobiecat »

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 du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

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

Message par C.Ret »

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 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
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5632
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

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

Message par ledudu »

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.
Modifié en dernier par ledudu le 10 févr. 2013 08:17, modifié 1 fois.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

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

Message par C.Ret »

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."
Modifié en dernier par C.Ret le 10 févr. 2013 08:33, modifié 1 fois.
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
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5632
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

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

Message par ledudu »

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

Retourner vers « Tous les Pockets »