La fonction factorielle

a marqué ce sujet comme résolu.

Dans le cadre de mes études, j'ai un TP d'info toutes les semaines. Ce coup ci, le TP est sur le multithreading. Je pense avoir assez bien compris le concept et comment m'en servir. Ici je viens vous demander un coup de main sur un exo en particulier.

On doit simplement écrire la fonction factorielle, mais voilà, il y a un scoreboard pour montrer qui a les meilleurs perfs dans la promo. Ayant une réputation de hardcore teckie à tenir dans cette école, je prends ce genre de défis à la con très au sérieux. Le calcul doit obligatoirement être multithreadé. J'ai pensé à écrire une fonction qui multiplie les nombres de n à m. Ça permet de découper le calcul en petits fragments parallélisables. J'aurais donc pour factorielle 100 ce calcul :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
thread 1 : fact(2, 10) = 3628800
thread 2 : fact(11, 20) = 670442572800
thread 1 : fact(21, 30) = 109027350432000
thread 2 : fact(31, 40) = 3075990524006400
thread 1 : fact(41, 50) = 37276043023296000
thread 2 : fact(51, 60) = 273589847231500800
thread 1 : fact(61, 70) = 1439561377475020800
thread 2 : fact(71, 80) = 5974790569203456000
thread 1 : fact(81, 90) = 20759078324729606400
thread 2 : fact(91, 100) = 62815650955529472000

pendant ce temps là le thread 0 fait un join sur les deux autres (il les attend) puis il multiplie les dix résultats entre eux.

Là j'ai déjà deux problèmes. Premièrement, cette solution est sûrement très naïve, je suis sûr qu'il y a de bien meilleurs manières de faire. Je suis tombé là dessus : http://www.luschny.de/math/factorial/conclusions.html Je planche encore dessus. Deuxièmement, ce TP est à faire en C. Les tests effectués par nos profs seront faits avec n compris entre 500 et 700. Evidemment, 500! dépasse déjà de loin la taille de tous les types d'entiers standard que je connais. Du coup je vais devoir bidouiller.

Ceci m'amène à mes questions :

  • Est-ce que vous auriez des idées d'optimisations de la fonction factorielle ?

  • Qu'est-ce que vous suggérez comme manière de faire pour gérer des grands nombres en C sans perte de perfs.

Toutes les idées sont les bienvenues. Je suis ouvert aux solutions les plus originales. Le seul objectif est la vitesse d'exécution. Je suis en train de vérifier si j'ai le droit de charger un tableau de 200 chaînes de caractères écrites à la main (résultats précalculés et mis en dur dans le code source héhé) et surtout si ça vaut le coup d'un point de vue perfs. Je préfère éviter les instructions directement en assembleur tant que je ne connais pas la machine de tests.

Au fur et à mesure des idées proposées, je vais essayer de les implémenter, et je vous dirais quel est le temps pris par telle ou telle solution histoire qu'on parle pas juste dans le vide.

Merci pour votre lecture les agrumes !

+0 -0

Oui gmp est pas mal et toujours plus efficace que du code a la main.

Au lieu de toutes les valeurs en dur tu peux toujours mettre un database. Pour gagner du temps, vu ton énoncé, tu peux dans tous les cas fixer en dur $500!$ : ca t'economisera 498 multiplications pour chaque valeur testée

+2 -0

Une idée comme ça en passant.

Pour calculer $n!$ tu fais la décomposition en facteurs premiers des nombres de 1 à n.
Ainsi plutôt de calculer le produit de 500 nombres, tu calcules le produits de ces nombres premiers, chacun avec leur multiplicité respective.
Tu utilises karatsuba pour le produit de grands nombres, et l'exponentiation rapide pour les puissances de chaque nombre premier.
Exemple avec 15! :

$15! = 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10\times 11\times 12\times 13\times 14\times 15$

$2 = 2$
$3 = 3$
$4 = 2\times 2$
$5 = 5$
$6 = 2\times 3$
$7 = 7$
$8 = 2\times 2\times 2$
$9 = 3\times 3$
$10 = 2\times5$
$11 = 11$
$12 = 2\times 2\times 3$
$13 = 13$
$14 = 2\times7$
$15 = 3\times 5$

$15! = 2^{11}\times 3^6\times 5^3\times 7^2\times 11\times 13$

Pour des nombres de petites taille comme celui-là c'est assez peu criant. Mais quand les nombres deviennent grands je pense que ça devient intéressant.
En effet le nombre de nombres premiers inférieurs à $n$ tend vers $\frac{n}{\ln{n}}$
Tu peux les pré-calculer, il y en a tout juste une centaine inférieurs à 500.
Dans ta factorielle, la puissance à laquelle il faudra porter chacun d'eux est donné par la formule de Legendre :

$v_p(n!) = \sum_{k=1}^\infty \lfloor \frac{n}{p^k}\rfloor$

Cette somme est rapide à calculer, dans la pratique, puisque très vite, pour k = 3 ou k = 4, tu vas dépasser n. Mis à part pour 2, où k devra monter jusque 9, et 3, où k devra monter jusque 6.
La puissance de chaque nombre premier, tu la calcules grâce à l'exponentiation rapide (qui a une complexité en temps logarithmique). Sauf pour 2 (qui aura la puissance la plus élevée) : là tu triches et tu utilises un décalage bit à bit. Si la puissance de 2 vaut 200, bah tu décales simplement le 1 de 200 bits, ça va être très rapide.
Et c'est là que le parallélisme interviens ! Tu lances un thread pour calculer les puissances de chaque nombre premier. En réalité, ce n'est rentable que pour les premiers nombres premiers, de 2 à 29 maxi, et encore ! En effet, les puissances de chaque nombres premiers vont devenir très vite très petites. Le temps que les premiers threads calculent des puissances élevée, le dernier aura eu le temps de calculer les produits de tout les autres nombres premiers de grande valeur et de puissances peu élevée.

Pour les produits de grands nombres tu utilises karatsuba qui a une bonne complexité, surtout pour des nombres comme $500!$. Karatsuba n'est rentable que pour des nombres de plusieurs centaines de chiffres, mais là, on peut déjà minorer $500!$ par $100^{400} = 10^{800} \simeq 2^{2660}$ qui possède déjà pas mal de chiffres en base 10 comme en base 2.
Tu peux éventuellement paralléliser le produit des différentes puissances de nombres premiers, en mettant chaque terme dans un tableau, et en faisant un diviser pour régner.

J'aurais bien du mal à évaluer la complexité de l'algo, et n'ayant jamais testé, je ne saurais pas dire si c'est efficace en pratique, ou juste séduisant.

PS :
J'ai fait quelques calculs et il se trouve que le nombre de multiplications à réaliser sera très inférieur à 500 même pour calculer $700!$ (c'est une majoration très haute). Dans la pratique je pense que ce sera entre 200 et 300, pour $700!$.

+4 -0

Woah merci beaucoup :D Pour la petite histoire, les solutions malhonnêtes sont autorisées. J'ai reçu cette réponse d'un de mes profs :

1
2
3
Dans l'ordre :
Vous n'avez pas le droit d'avoir autre chose que du code C
Vous n'avez pas le droit d'écrire sur le disque

Et la règle est que tout ce qui n'est pas interdit est autorisé.

J'avais pensé à cette décomposition en facteurs premiers. Je ne savais juste pas comment faire la décomposition rapidement :)

Je vais maintenant me remettre à mon code et faire plein de tests chronométrés. Je dois tester le temps que met une multiplication en fonction de sa base, de la technique utilisée, enfin un peu tout quoi. Je vous tiens au courant ! N'hésitez pas à continuer à proposer des choses en attendant si vous avez des idées !

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte