[Défi math] Calculer rapidement une factorielle

[SPH]

Salut,

je lance un défi mathématique.
Je demande que vous produisiez un code plus rapide que mon code pour calculer une factorielle.
Ex : Factoriel 7 = 1*2*3*4*5*6*7
Comme le nombre est tres vite enorme, vous pourrez le stocker dans une banque d'octet. Ce nombre sera donc en base 256.

Pour etre bien certain de la bonne marche de votre code, voici la factorielle de 200 (du moins, ce que ma routine donne; a verifier donc) :


Le but de votre programme sera de calculer dans un minimum de temps la factorielle de 200 000 !!!
Pas la peine d'afficher le resultat mais verifiez quand meme qu'elle commence par (les 5 octets de poids fort) : D3,E2,84,C6,77
Bien sur, les nombreux octets de poids faibles sont des zero.

DONC, pour ma part, je sais calculer la factorielle de 200000 en 75672 ms (avec mon programme compilé). Mon ordi datant de 6 ans environ, votre programme sur VOTRE ordi mettra un temps different.
Le concours est lancé et je vous devoilerais mon moteur mais pas tout de suite. Je laisse votre geni creatif tourner.

Voici quand meme le squelette de mon programme :

Code : Tout sélectionner

OpenConsole()
;cmb=500000

PrintN("SPH(2009) - Calcul la factorielle d'un nombre")
PrintN("Exemple : Factorielle de 7 = 1*2*3*4*5*6*7")
re:
PrintN(" ")
Print("Factorielle de : ")
a$=Input()
cmb=Val(a$)
If cmb<1
Goto re
EndIf


;Goooooooooooo 
temps = GetTickCount_() 

;========================================
Dim noeud.w(cmb*3)
noeud(0)=1
ici.l=1
reste.l=0
reste2.l=0
For np=1 To cmb
      If np%10000=0
      af.f=ici/np
      PrintN("Factorielle de : "+Str(np)+" -- Produit en "+Str((GetTickCount_()-temps)/1000)+"s  -- "+StrF(af))
      EndIf

;;;;;;;;;
;========================================
;;; MON MOTEUR
;========================================

temps = GetTickCount_() - temps 
;temps /1000
;MessageRequester("Millisecondes : ",Str(temps))
PrintN("Millisecondes : "+Str(temps))
;STOOOOOOOOOOP 

;;;;
If CreateFile(0, "d:\Factorielle "+Str(cmb)+"_"+Str(temps)+"ms.bank")
Else
MessageRequester("Erreur", "Fichier impossible à créer...")
End
EndIf

For octet=0 To ici
WriteWord(0,noeud(octet)) 
Next

CloseFile(0)

;;;;
PrintN(" ")
PrintN("--FIN--")

For i=0 To 5
Beep_(i*100,60)
Next
Repeat
  Delay(1000)
ForEver

Comme vous pouvez le voir, j'ecris le resultat sur disque dur (sur D). Changez l'emplacement si vous voulez.

Allez, le concours est lancéééééééé

[G-Rom]

je comprend rien , ca tiens pas dans un integer ou quad... ?
ton code contient trop de truc inutile pour comprendre ( les beep_() windows par ex... )
Explique moi déjà une factorielle en clair
j'ai compris n7 = n*n*n*n*n*n*n
mais après , mes n c'est quoi ?

[TazNormand]

@G-Rom : une factorielle, c'est le fait de multiplier les nombres d'une suite numériques par eux-mêmes ; ces suites commençant à 1.

Par exemple, pour calculer la factorielle de 10 (10!), il faut calculer : 10x9x8x7x6x5x4x3x2x1.

@ SPH : Ton code ne marche pas chez moi !!!

sinon, fonction récursive :

Code : Tout sélectionner

Procedure factorielle(n)
	If n = 1
		ProcedureReturn 1
	EndIf
	ProcedureReturn n * factorielle(n - 1)
EndProcedure

[SPH]

@TazNormand : mon code ne marche pas car c'est le squelette de mon programme; donc sans l'algorhitme (donc, il ne marche pas)
@G-Rom : Un quad, c'est 8 octets (8 hein ?? j'espere ne pas me planter) tandis que factorielle de 200, c'est plus de 150 octets ! Alors imagine factorielle de 200000 !!! (plus de 388000 octets)
Non Grom, factorielle de x, c'est multiplier ensemble tous les nombres de 1 a x.
Ex :
10! = 1*2*3*4*5*6*7*8*9*10
3! = 1*2*3
21! = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21

[Mindphazer]

Code : Tout sélectionner

Procedure factorielle(n)
	If n = 1
		ProcedureReturn 1
	EndIf
	ProcedureReturn n * factorielle(n - 1)
EndProcedure

La procédure récursive fonctionne.... lorsque n n'est pas un entier trop grand....... sinon, on dépasse la capacité de calcul "standard" de Purebasic

L'idée de SPH, je crois, c'est de trouver un algorithme permettant de calculer n! pour des entiers comme 200 par exemple (dans ce cas présent, le résultat est 788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000, soit un nombre à 375 chiffres !!!)

[SPH]

L'idée de SPH, je crois, c'est de trouver un algorithme permettant de calculer n! pour des entiers comme 200 par exemple (dans ce cas présent, le résultat est 788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000, soit un nombre à 375 chiffres !!!)

200! dans une base 256 est ce que j'ai posté (si je n'ai pas fait d'erreurs).
Ton nombre a ete calculé comment ?
Correspond t'il a mon nombre "en banque d'octets" ??

[Mindphazer]

J'avoue : je ne me suis pas fatigué !!

Je l'ai calculé ici :
http://www.dcode.fr/calcul-factorielle

[SPH]

J'avoue : je ne me suis pas fatigué !!

Je l'ai calculé ici :
http://www.dcode.fr/calcul-factorielle

Tiens tiens, EXTREMEMENT INTERESSANT (en tout cas pour moi qui aiiiime les maths) :

0! = 1, 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720, 7! = 5040, 8! = 40320, 9! = 362880, 10! = 3628800
Somme des factorielle des chiffres d'un nombre
NOMBRE :
145 => 1!+4!+5! = 1 + 24 + 120 = 145
Formule de Stirling
La formule de Striling permet une approximation rapide de la valeur de n! pour de très grand nombres :
n! = sqrt(2*pi*n) * (n/e)^n

Cette toute derniere formule est extremement interessante. Et si elle fonctionne, elle va booster mon algo (mais ne trichons pas, je reste avec mon ancien algo)

[Mindphazer]

Elle fonctionne à priori, je l'ai vue sur pas mal de sites traitant du sujet.

Après, j'avoue humblement avoir la flemme de me creuser la cervelle, même si le sujet m'intéresse..
D'autant que ça faisait une paire de dizaine d'années que je n'avais pas revu les factorielles !
Je me souviens de vieux Jeux&Stratégie dans lesquels des casses-tête à base de factorielles étaient publiés, ainsi qu'à base de sommielles (n!! = 1+2+3+..+n, par ex 5!! = 1+2+3+4+5 = 15)

Ah là là, que de vieux souvenirs !...

[SPH]

... ainsi qu'à base de sommielles (n!! = 1+2+3+..+n, par ex 5!! = 1+2+3+4+5 = 15)

Tiens, jamais entendu parlé de ce terme.
Mais j'ai deja developpé des algho tres rapide sur la forme n+n+1+n+2+.....n+x

EDIT : la formule "n! = sqrt(2*pi*n) * (n/e)^n" est loin d'etre facile a coder... A cause de "pi" et de "e"

[G-Rom]

C'est du brainfuck ce truc , codable , mais casse couilles à faire ...
surtout à cause de la limitation des entiers....
en tout cas , c'est pas pour moi cette fois , chui trop crevé pour ca !

[Backup]

est loin d'etre facile a coder... A cause de "pi" et de "e"

e c'est La constane d'euler non ? soit 2.7182818

[SPH]

est loin d'etre facile a coder... A cause de "pi" et de "e"

e c'est La constane d'euler non ? soit 2.7182818

Oui, mais je ne sais pas quel degre de precision il lui faut ! De meme que pour PI

[Ollivier]

@SPH

Salut Spiche,

Je me permets de te donner une petite image de comment je digère ton sujet.
J'imagine qu'on est deux potes de galère qui se font ch... en plein milieu de Paris. Soudain l'un dit à l'autre « Vas-y viens quoi, ouèche! On a qu'à aller à Dam fumer des spulicensurés! ça nous détendra... »
Et Dam (diminutif de Amsterdam), en fait c'est, comme le titre du sujet l'indique la ville du calcul rapide de la factorielle.

300 bornes plus tard sur la E19, le même gars dit à l'autre « C'est génial! d'ailleurs, en même temps, on ira voir le nouvel appart de Yolande... Celui qui est à Marseille... »

Et Marseille c'est la formule de Stirling.

Alors, je suis d'accord: le voyage de Marseille à Amsterdam, en bateau, c'est possible. Aussi possible que la formule de Stirling corrigée par un érudit génial que l'on ne découvre que tous les 200 ans permettrait une ultra-haute performance du calcul des factorielles.

Mais, en attendant, là, avec le 4x4 emprunté à Papa, on est les 4 roues embourbées dans le trou du censuré du monde paumé à mi-chemin entre la Belgique et la PACA. Et on n'est même pas défoncé... (traduction: on n'a pas encore pondu un seul code digne de ce nom)

Donc le co-pilote de galère que je suis soudainement, te demande: performance et précision ou... honneur à la formule de Stirling?

Si tu ne choisis pas, c'est évident, on ne va pas bouger du champ de boue dans lequel le sujet est, et tu vas ressentir la déception de l'inachevé, comme tu l'indiques dans un autre sujet.

Loin de te blesser...

Ollivier

[Backup]

mise en applicationde en Purebasic de la formule de STIRLING

Code : Tout sélectionner

e.f=2.7182818
pi.f=3.1415926536

n=4 ; <<<<<<<<< ceci est le chiffredont on calcul la factoriel

debug  Round(sqr(2*pi*n) * Pow((n/e),n),#PB_Round_Nearest)

c'est étonnant ... ça marche