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

[C.Ret]

OK, merci.

Je n'avais pas compris >(X,0) qui veut dire X>0

Il y a trop longtemps que je n'ai plus pratiqué de PROLOG (et jamais le dialecte particulier de ce pocket !).

[Paul Tergeist]

Allez plus loin avec le logarithme décimal !!!
Ne loupez pas cette occasion fabuleuse d'utiliser les touche LOG et 10^x de votre calculette...
en effet, LOG(a*b)=LOG(a)+LOG(b)
donc pour calculer le logarithme naturel de la factorielle de 10 on fera :
LOG(1)+LOG(2)+LOG(3)+LOG(4)+LOG(5)+LOG(6)+LOG(7)+LOG(8)+LOG(9)+LOG(10)
ce qui fait 6.559763032
très beau nombre !
la partie décimale exposée à 10 nous donne : 10^0.559763032 = 3.628799993
la partie entière exposée à 10 nous donne : 10^6=1 000 000
le produit des deux (arrondi a l'unité) : 3 628 800
on aura tous reconnu la factorielle de 10
Voila de quoi aller beaucoup plus loin...

[doum-doum]

J'en reste sans voix ! Ce qu'il y a de bien, c'est qu'avec ces MPO, on révise nos Maths, c'est comme lire Tangente, mais en application directe

[Gilles59]

Allez plus loin avec le logarithme décimal !!!
.

Bien vu Paul !...

Ma Casio 602P sait maintenant que 200! = 7.88658E374
et que
400! = 6.40345E868
1000! =4.02391E2567 (en fait 4.023872 ... )

nombres plus qu'astronomiques qui ne représentent rien de concevable. L'univers "ne contient que" 10^80 atomes

Code : Tout sélectionner

Min00 "#!= " 0 Min1F
LBL0
 MR00 log M+1F
DSZ GOTO0

MR1F FRAC 10^x FIX5 ";#E" M1F INT ";#"

39GII

Code : Tout sélectionner

EXPORT BIGFACT(n)
BEGIN
 S:=Σ(LOG(X),X,1,n);
 MSGBOX(n+"!="+10^FRAC(S)+"E"+FLOOR(S)));
END;

[currybleu]

Allez plus loin avec le logarithme décimal !!!

Et ma HP28s m'a également confirmé en 15 secondes que 1000! faisait 4.02387267E2567 (fonction SPEED activée) et 8 secondes sur HP50G
!! Attention la fonction RND entre la 28S et la HP50G a changé (je ne sais pas trop pour les séries 48 et 49..
Sur HP28S, pour arrondir à 4 chiffres après la virgule, on fait:

Code : Tout sélectionner

4 FIX RND STD

Sur HP50G, on fait

Code : Tout sélectionner

4 RND

HP28S

Code : Tout sélectionner

<< 0 1 ROT FOR X X LOG + NEXT DUP FP ALOG 8 FIX RND STD ->STR "E" + SWAP FLOOR ->STR + >>

/ HP48? / HP49? / HP50

Code : Tout sélectionner

0 1 ROT FOR X X LOG + NEXT DUP FP ALOG 8 RND ->STR "E" + SWAP FLOOR ->STR +

[C.Ret]

Bonjour curryblue,
.. est bienvenue sur le forum.

Chouette, je trouve enfin un homologue qui utilise encore une HP-28S !!

De plus le code proposé est très très bien.
Comme nous sommes dans un MPO, et juste pour crâner un peu, je le MPO-ise
Et comme cela je me l'approprie.

Code : Tout sélectionner

«                            // Allez plus loin avec le logarithme décimal !!!
   0                         // Ne loupez pas cette occasion fabuleuse d'utiliser les touches LOG et 10^x
                             // de votre calculette... en effet, LOG(a*b)=LOG(a)+LOG(b)
   1 ROT FOR x               // pour calculer le logarithme naturel de la factorielle de n on fera :
          x LOG +            // LOG(1)+LOG(2)+LOG(3)+LOG(4)+...+LOG(n)
   NEXT
   IP                        // la partie entière exposée nous donne l'exposant de 10.
   LAST FP ALOG              // la partie décimale exposée à 10 nous donne [la mantisse]. 
   'EE' ROT ^ *              // [petite astuce de représentation des grands grand nombres
»

Le gain est minime. J'ai juste changé le format final du résultat qui sera affiché comme une expression algébrique ce qui permet d'éventuellement enchainer des calculs. Et aussi , je n'ai pas arrondi la mantisse, il faut donc utiliser ce programme avec son format habituel pour avoir un résultat propre.

Remercions aussi au passage l'intervention de Paul pour les explications de l'algorithme.

[currybleu]

Hello,

L'arrondi me semble nécessaire car par exemple, avec 10! la conversion LOG/ALOG donne un resultat tres approximatif:
3.62879999994E6 au lieu de 3.6288E6
Pariel pour 11, 12, etc...
Maintenant, au vu de la précision de la 28S ou 50G, 9 RND semble plus judicieux.

PS: je débarque sur ce forum.. que veut dire mpo?

[Pocket]

Salut,

PS: je débarque sur ce forum.. que veut dire mpo?

Relis le titre du sujet

A+

[Paul Tergeist]

Allez je lève toute ambiguïté, mpo est une abréviation de
Misez P'tit Optimisez

(et non pas un acronyme pour les connaisseurs)

[gege]

Bonjour,
Retrouvé bout de code, qui attend ses papas ci-dessous :

Code : Tout sélectionner

00; "A"
01; 1=>X
02; IF Z>5,GTO 6
03; X*Z=>X
04; Z+1=>Z
05; GTO 2
06; Z*LN Z-Z+LN (2*π/Z)/2+((((1/99/Z/Z-1/140)/Z/Z+1/105)/Z/Z-1/30)/Z/Z+1)/Z/12-LN X
07; END

(pompé sur le site de Victor Toth)
Cet algorithme est **plus précis** que de longues additions de logs...
A bon entendeur
G.E.

[C.Ret]

Et oui.

Mais attention, si précision veut dire donner plus de chiffres justes, il ne faut pas oublier que certaines machines RPL sont capables de calculer tous les chiffres de 250! ou 1000! et alors, dans ce cas, le résultat est "extrêmement" précis.

Code : Tout sélectionner

« -> n
     « 
       [1]                     //  0! = 1
       1 n FOR i            
          i *                  //  n! = n*(n-1)!
          ARRY-> 1E7 ACarry    //  Reporte les retenues et agrandit si nécessaire le vecteur résultat 
       NEXT
     »
»
'AFACT' STO


250! =                                                        3 232856 260909
        107732 320814 552024 368470 994843 717673 780666 747942 427112 823747
        555111 209488 817915 371028 199450 928507 353189 432926 730931 712808
        990822 791030 279071 281921 676527 240189 264733 218041 186261 006832
        925365 133678 939089 569935 713530 175040 513178 760077 247933 065402
        339006 164825 552248 819436 572586 057399 222641 254832 982204 849137
        721776 650641 276858 807153 128978 777672 951913 990844 377478 702589
        172973 255150 283241 787320 658188 482062 478582 659808 848825 548800
        000000 000000 000000 000000 000000 000000 000000 000000 000000 000000

1000! =               402387 260077 093773 543702 433923 003985 719374 864210
        714632 543799 910429 938512 398629 020592 044208 486969 404800 479988
        610197 196058 631666 872994 808558 901323 829669 944590 997424 504087
        073759 918823 627727 188732 519779 505950 995276 120874 975462 497043
        601418 278094 646496 291056 393887 437886 487337 119181 045825 783647
        849977 012476 632889 835955 735432 513185 323958 463075 557409 114262
        417474 349347 553428 646576 611667 797396 668820 291207 379143 853719
        588249 808126 867838 374559 731746 136085 379534 524221 586593 201928
        090878 297308 431392 844403 281231 558611 036976 801357 304216 168747
        609675 871348 312025 478589 320767 169132 448426 236131 412508 780208
        000261 683151 027341 827977 704784 635868 170164 365024 153691 398281
        264810 213092 761244 896359 928705 114964 975419 909342 221566 832572
        080821 333186 116811 553615 836546 984046 708975 602900 950537 616475
        847728 421889 679646 244945 160765 353408 198901 385442 487984 959953
        319101 723355 556602 139450 399736 280750 137837 615307 127761 926849
        034352 625200 015888 535147 331611 702103 968175 921510 907788 019393
        178114 194545 257223 865541 461062 892187 960223 838971 476088 506276
        862967 146674 697562 911234 082439 208160 153780 889893 964518 263243
        671616 762179 168909 779911 903754 031274 622289 988005 195444 414282
        012187 361745 992642 956581 746628 302955 570299 024324 153181 617210
        465832 036786 906117 260158 783520 751516 284225 540265 170483 304226
        143974 286933 061690 897968 482590 125458 327168 226458 066526 769958
        652682 272807 075781 391858 178889 652208 164348 344825 993266 043367
        660176 999612 831860 788386 150279 465955 131156 552036 093988 180612
        138558 600301 435694 527224 206344 631797 460594 682573 103790 084024
        432438 465657 245014 402821 885252 470935 190620 929023 136493 273497
        565513 958720 559654 228749 774011 413346 962715 422845 862377 387538
        230483 865688 976461 927383 814900 140767 310446 640259 899490 222221
        765904 339901 886018 566526 485061 799702 356193 897017 860040 811889
        729918 311021 171229 845901 641921 068884 387121 855646 124960 798722
        908519 296819 372388 642614 839657 382291 123125 024186 649353 143970
        137428 531926 649875 337218 940694 281434 118520 158014 123344 828015
        051399 694290 153483 077644 569099 073152 433278 288269 864602 789864
        321139 083506 217095 002597 389863 554277 196742 822248 757586 765752
        344220 207573 630569 498825 087968 928162 753848 863396 909959 826280
        956121 450994 871701 244516 461260 379029 309120 889086 942028 510640
        182154 399457 156805 941872 748998 094254 742173 582401 063677 404595
        741785 160829 230135 358081 840096 996372 524230 560855 903700 624271
        243416 909004 153690 105933 983835 777939 410970 027753 472000 000000
        000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
        000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
        000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
        000000 000000 000000 000000 000000 000000 000000 000000 000000 000000

[gege]

Certes, et joli travail, mais en tapant 250! [Enter] sur une banale TI89, on a le résultat en 3 secondes...
Oui c'est déprimant... encore
G.E.

[currybleu]

ARRY-> 1E7 ACarry // Reporte les retenues et agrandit si nécessaire le vecteur résultat

hello,
A quoi correspond cette fonction ACarry? (autre programme RPL ou library?)

[C.Ret]

Salut,

Désolé, j'ai oublié de préciser.
Oui ACarry est un autre programme dont voici la version qui correspond au code ci-dessus. Comme beaucoup de mes code, il a été composé il y a bien longtemps et il en existe différentes version en fonction des autres programmes utilitaire que j'utilisais à l'époque et surtout de mes convention de présentation des objets.

Code : Tout sélectionner

« SWAP 1 GET 1 + -> p n      //  input max precision p and array size (plus one)
   « 
     0                       //  Init carry
     IF
        2 n START            //  for each element of the original array
           +                 //  Add carry
           p MOD             //  round element to max precision p
           LAST / IP         //  compute eventual carry
           SWAP n ROLLD      //  roll down to next array element
        NEXT
                             //  if carray after last element
     THEN
        LAST n ROLLD         //  add carry in stack
        n                    //  n is array's size + 1
     ELSE
        n 1 -                //  readjust array size when no carry at end
     END
     ->ARRY                  //  rebuilt array from stack
   »
»

Dans la version en question, les entiers longs sont en fait des vecteurs ligne (row array) ce qui permet d'effectuer directement une partie des calculs (comme la multiplication par exemple - d'où le code simple et compréhensible pour la fonction AFACT. Mais, il y a d'autres façons de faire bien évidemment.

Par ailleurs, il y a actuellement dans mon HP-28S une version différente qui prend en argument directement le vecteur et la précision. C'est plus lisible et mieux organisé, mais pas nécessairement plus rapide. De plus cette dernière version utilise pas mal d'utilitaires personnels, ce qui rend sa publication un peu compliquée.

Mais quoi qu'il en est, toutes ces versions font la même chose, elles parcourent le vecteur de droite à gauche en reportant les éventuelles retenues d'un élément à l'autre. Après on peut utiliser un vecteur à taille fixe ou variable selon les cas. Dans le cas des factorielles, un vecteur à taille variable est bien adapté et optimise le temps de calcul en n'utilisant que le nombre d'élément nécessaires.

[Gilles59]

Certes, et joli travail, mais en tapant 250! [Enter] sur une banale TI89, on a le résultat en 3 secondes...
Oui c'est déprimant... encore
G.E.

Ce qui importe je trouve, c'est de tirer le maximum du machine donnée, de contourner ses limitations, comme ici calculer des entiers tres long alors que la machine n'est pas conçue à priori pour çà.