coefficient binomial

Question

'simple' question, ce qui est le meilleur moyen de calculer le coefficient binomial? - Certains fileté algorithme

Je cherche des conseils :) - pas mises en œuvre:)

Answer 1

Selon l'équation ci-dessous (à partir de wikipedia ) le moyen le plus rapide serait de diviser la varier i = 1, k le nombre de fils, chaque fil donner un segment de gamme, et chaque fil met à jour le résultat final dans une serrure. « Voie académique » serait de diviser la plage en tâches, chaque tâche étant de calculer (n - k + i) / i, et peu importe le nombre de threads que vous avez, ils fonctionnent tous dans une boucle demande pour la tâche suivante. Tout d'abord est plus rapide, le second est ... universitaire.

EDIT: des explications plus - dans les deux sens que nous avons un certain nombre arbitraire de threads. Habituellement, le nombre de fils est égal au nombre de coeurs de processeur, parce qu'il n'y a pas d'avantage à ajouter plusieurs threads. La différence entre les deux façons est ce que ces fils sont en train de faire.

En premier moyen de chaque fil est donnée N, K, I1 et I2, où I1 et I2 sont le segment dans la plage 1..K. Chaque thread a alors toutes les données qu'il NEADS, il calcule sa part du résultat, et à la fin met à jour le résultat final.

En deuxième façon, chaque fil est donnée N, K, et l'accès à un certain compteur synchronisé qui compte de 1 à K. Chaque thread acquiert alors une valeur de ce compteur partagé, calcule une fraction du résultat, met à jour le résultat final, et boucles jusqu'à ce que contre informe le fil qu'il n'y a pas d'autres articles. S'il arrive que certains cœurs de processeur sont plus rapides que d'autres, alors ce deuxième façon mettra tous les cœurs à utiliser au maximum. Inconvénient de seconde voie est trop synchronisation qui bloque efficacement, disons, 20% de fils tout le temps.

Answer 2

Eh bien, le plus rapide, je pense, serait de les lire à partir d'une table plutôt que les compute.

Vos exigences sur la précision du nombre entier d'utiliser un moyen de double représentation que C (60,30) est tout sauf trop grand, être autour 1e17, de sorte que (en admettant que vous voulez avoir C (m, n) pour tout m jusqu'à une certaine limite, et tout n <= m), votre table aurait seulement environ 1800 entrées. En ce qui concerne le remplissage de la table, je pense que le triangle de Pascal est le chemin à parcourir.

Answer 3

Astuce: Vous voulez faire aussi peu que possible multiplications. La formule est n! / (k! * (n-k)!). Vous devriez faire moins de 2m multiplications, où m est le minimum de k et n-k. Si vous voulez travailler avec (assez) grand nombre, vous devez utiliser une classe spéciale pour la représentation numérique (Java a BigInteger par exemple).

Answer 4

Voici une manière qui ne déborde jamais si le résultat final est exprimable nativement dans la machine, ne comporte aucun multiplications / factorisation, est facilement parallélisés et se généralise à BigInteger-types:

Notons d'abord que les coefficients binomiaux satisfont suivants:

.

Cela donne une récursivité simple pour le calcul du coefficient: les affaires de base sont et , qui sont tous deux 1.

Les résultats individuels des sous-appels sont des nombres entiers et si \ binom {n} {k} peut être représenté par un entier, ils peuvent aussi; donc, le débordement n'est pas une préoccupation.

Naïvement mis en œuvre, les fils de récursion à plusieurs reprises et sous-appels runtimes exponentielle.

Cela peut être corrigé par la mise en cache des résultats intermédiaires. Il y a n ^ 2, sous-problèmes qui peuvent être combinés en O (1) heure, donnant une complexité en O (n ^ 2) liés.