Coeficiente binomial

Question

Pergunta 'simples', qual é a maneira mais rápida de calcular o coeficiente binomial? - Algum algoritmo rosqueado?

Estou procurando dicas :) - não implementações :)

Answer 1

De acordo com a equação abaixo (de Wikipedia) A maneira mais rápida seria dividir o intervalo i = 1, k no número de threads, fornecer a cada segmento de um intervalo de um thread e cada thread atualiza o resultado final em um bloqueio. "Way Academic" seria dividir o intervalo em tarefas, sendo cada tarefa calcular (n - k + i)/i e, não importa quantos threads você tenha, todos correm em um loop pedindo a próxima tarefa. O primeiro é mais rápido, o segundo é ... acadêmico.

EDIT: Explicação adicional - Nos dois sentidos, temos algum número arbitrário de threads. Geralmente, o número de encadeamentos é igual ao número de núcleos do processador, porque não há benefício em adicionar mais threads. A diferença entre duas maneiras é o que esses tópicos estão fazendo.

Na primeira maneira, cada thread é dado n, k, i1 e i2, onde i1 e i2 são o segmento no intervalo 1..k. Cada encadeamento possui todos os dados que ele não, por isso calcula sua parte do resultado e, após o final, atualiza o resultado final.

De segunda maneira, cada segmento é dado n, k e acesso a algum contador sincronizado que conta de 1 para K. Cada fio e depois faz um valor desse contador compartilhado, calcula uma fração do resultado, atualiza o resultado final e loops em Até que o contador informe o tópico que não há mais itens. Se acontecer que alguns núcleos de processador são mais rápidos que outros, essa segunda maneira colocará todos os núcleos em uso máximo. Desvantagem da segunda maneira é muita sincronização que bloqueia efetivamente, digamos, 20% dos threads o tempo todo.

Answer 2

Bem, a maneira mais rápida, eu acho, seria lê -los de uma mesa em vez de computá -los.

Seus requisitos sobre precisão inteira de usar uma representação dupla significa que C (60,30) é praticamente grande demais, em torno de 1E17, de modo que (supondo que você queira ter C (m, n) para todos os limites, e todos n <= m), sua tabela teria apenas cerca de 1800 entradas. Quanto a encher a mesa, acho que o triângulo de Pascal é o caminho a percorrer.

Answer 3

Dica: você deseja fazer o mínimo de multiplicações possível. A fórmula é n! / (k! * (n-k)!). Você deveria fazer menos do que 2m Multiplicações, onde m é o mínimo de k e n-k. Se você deseja trabalhar com (razoavelmente) grandes números, use uma classe especial para a representação numérica (o Java tem Biginteger, por exemplo).

Answer 4

Aqui está uma maneira que nunca transborda se o resultado final for expressável nativamente na máquina, não envolve multiplicações/fatorizações, for facilmente paralelo e generaliza para os tipos BigInteger:

Primeiro, observe que os coeficientes binomiais satisfazem seguidores:

.

Isso produz uma recursão direta para calcular o coeficiente: os casos base são e , ambos são 1.

Os resultados individuais dos subcursos são inteiros e se binom {n} {k} podem ser representados por um int, eles também podem; Portanto, o transbordamento não é uma preocupação.

Implementado ingenuamente, a recursão leva a subcalas repetidas e tempos de execução exponenciais.

Isso pode ser corrigido por resultados intermediários. Existem n^2 subproblemas, que podem ser combinados em O (1) tempo, produzindo uma complexidade O (n^2) ligada.