coeficiente binomial

Question

'simple' pregunta, ¿cuál es la manera más rápida de calcular el coeficiente binomial? - Algunos roscado algoritmo

Busco consejos :) - no implementaciones:)

Answer 1

De acuerdo con la ecuación siguiente (de Wikipedia ) la manera más rápida sería dividir el variar i = 1, k al número de hilos, dar a cada hilo de un segmento de gama, y ??cada hilo actualiza el resultado final en una cerradura. "Forma académica" sería dividir el rango en tareas, siendo para el cálculo de cada tarea (n - k + i) / i, y entonces no importa cuántos hilos que tiene, todos corren en un bucle pidiendo siguiente tarea. En primer lugar es más rápida, la segunda es ... académica.

EDIT: una explicación adicional - en ambos sentidos que tenemos un número arbitrario de hilos. Por lo general, el número de hilos es igual al número de núcleos de procesador, porque no hay ningún beneficio en la adición de más hilos. La diferencia entre dos formas es lo que los hilos están haciendo.

En primera forma en que cada hilo se da N, K, I1 y I2, donde I1 e I2 son el segmento en el 1..K gama. Cada hilo tiene entonces todos los datos que Neads, por lo que calcula su parte del resultado, y al final se actualiza el resultado final.

En segundo forma de administración de cada hilo N, K, y el acceso a algunos contador sincronizado que cuenta de 1 a K. Cada hilo entonces aquires un valor de este contador compartido, calcula una fracción del resultado, actualiza el resultado final, y lazos en esto hasta que informa de contador del hilo que no hay más elementos. Si sucede que algunos núcleos de procesadores son más rápidos que otros, entonces esta segunda manera pondrán todos los núcleos de máximo uso. Desventaja de segunda manera es demasiado sincronización que bloquea eficazmente, por ejemplo, 20% de hilos de todo el tiempo.

Answer 2

Bueno, la forma más rápida, supongo, sería leer desde una tabla en lugar de calcularlos.

Sus requisitos de precisión de número entero del uso de un doble medios de representación que C (60,30) es casi demasiado grande, estar cerca de 1E17, de modo que (suponiendo que desea tener C (m, n) para todo m hasta algún límite, y todo n <= m), su tabla sólo tendrían alrededor de 1800 entradas. Como para el llenado de la tabla de pienso triángulo de Pascal es el camino a seguir.

Answer 3

Sugerencia: desea hacer tan poco como sea posible multiplicaciones. La fórmula es n! / (k! * (n-k)!). Usted debe hacer menos de multiplicaciones 2m, donde m es el mínimo de k y n-k. Si desea trabajar con (bastante) grandes números, se debe utilizar una clase especial para la representación de números (Java tiene BigInteger por ejemplo).

Answer 4

Aquí está una manera que nunca se desborda si el resultado final se puede expresar de forma nativa en la máquina, no implica multiplicaciones / facturizaciones, se parallelized fácilmente, y se generaliza a BigInteger tipos:

Primero nota que los coeficientes binomiales satisfacen siguiente:

.

Esto produce una recursión sencillo para calcular el coeficiente de: los casos base son y , ambos de los cuales son 1.

Los resultados individuales de las subllamadas son números enteros y si \ Binom {n} {k} puede ser representado por un int, ellos también pueden; Por lo tanto, el desbordamiento no es una preocupación.

Ingenuamente implementado, los cables de la recursividad para subllamadas repetidas y tiempos de ejecución exponenciales.

Esto puede ser fijado por el almacenamiento en caché los resultados intermedios. Existen n ^ 2 subproblemas, que se pueden combinar en O (1) tiempo, produciendo un O (n ^ 2) límite de complejidad.