Binary splitting method (math sup++)

[invitedebe236f]

http://numbers.computation.free.fr/C...splitting.html

je comprend pas comment il calcule une factorielle rapidement
si quelqu un pouvais m expliquer avec un exemple fact(10) par exemple
-----

[inviteeecca5b6]

tu devrais deja regarder une autre page parce que celle-ci déconne un peu (enfin chez moi...)
Du coup les formules sont incomprehensibles...

[inviteea0d596d]

les formules sont "presque" bonnes.
En fait il faut considérer la partie entière de (a+b)/2 et non pas (a+b)/2

La formule marche, je l'ai testée sous Visual Basic.

voici l'algorithme pour calculer P(a,b) :

si a+1=b alors renvoyer b
sinon
m=E[(a+b) /2]
renvoyer P(a,m)*P(m,b)



ensuite pour calculer n! il suffit d'appeler P(0,n)

[invitedebe236f]

ok merci
mais je vois pas ou est l avantage

[A voir en vidéo sur Futura]

[inviteea0d596d]

bah la démonstration qu'ils font prouve que la méthode classique se fait en

alors que la méthode proposée demande seulement opérations

si tu étudies ces 2 fonctions tu veras que la première croit beaucoup plus vite que la seconde.

[inviteeecca5b6]

bah la démonstration qu'ils font prouve que la méthode classique se fait en

alors que la méthode proposée demande seulement opérations

si tu étudies ces 2 fonctions tu veras que la première croit beaucoup plus vite que la seconde.

Salut,
la méthode proposée est récursive, non ?
En générale c'est moins rapide...
Le plus rapide des algorithmes pour calculer le factoriel est le suivant (je sais, c'est pas beau mais très éfficace) :
switch n:
case 0:
return 1;
break;
case 1:
return 1;
break;
case 2:
return 2;
break;
case 3:
return 6;
break;
case 4:
return 12;
break;
etc etc... jusqu'a la valeur désirée... Avec cet algo, aucun problème de vitesse

[invitedebe236f]

j ai oublier de preciser peut etre que c est pour calculer dans le genre de fact(354455) avec tous ces chiffres
si j ai bien comprit il prend par 2 les chiffres et les multiplie il lui en reste la moitie
il recommence et quand les resultat sont trop gros il passe a la FFT pour multiplie

[inviteea0d596d]

Salut,
la méthode proposée est récursive, non ?
En générale c'est moins rapide...
Le plus rapide des algorithmes pour calculer le factoriel est le suivant (je sais, c'est pas beau mais très éfficace) :
switch n:
case 0:
return 1;
break;
case 1:
return 1;
break;
case 2:
return 2;
break;
case 3:
return 6;
break;
case 4:
return 12;
break;
etc etc... jusqu'a la valeur désirée... Avec cet algo, aucun problème de vitesse