VPF::Подсчет биноминального коэффециента

Dzo

Дата 7.10.2010, 23:42 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 88
Регистрация: 22.4.2008

Репутация: нет
Всего: 1

В общем, стандартный биноминальный коэффициент:

http://en.wikipedia.org/wiki/Binomial_coefficient

Хочется его посчитать, но основная задача сделать это не быстро, а чтобы вводимое n было как можно бОльшим и соответсвенно k ему не уступало. То есть хочется считать что-то вроде countBinomialCoefficient(1000000,84564).

Что я имею сейчас:

Код



public class IntroductoryUnderstanding {

    public static void main(String args[]) {
        System.out.println(countBinomialCoefficient(10000,2000));
    }
    
    public static BigInteger countBinomialCoefficient(int n, int k) {
        
        // in order not to count crazy large numbers
        
        int tmpN = n;
        
        ArrayList<Integer> topFactors = new ArrayList<Integer>();
        topFactors.add(n);
        
        boolean factorLeft;
        int factor;
        
        if (k < Math.ceil(n/2)) {
            factorLeft = true;
            factor = n - k;
        } else {
            factorLeft = false;
            factor = k;
        }
        
        while (tmpN > factor + 1) {
            
            topFactors.add(tmpN - 1);
            tmpN = tmpN - 1;
            
        }
        
        BigInteger topFactor = BigInteger.valueOf(0);
        
        for (int i = 0; i < topFactors.size(); i++) {
            
            if (i == 0) {
                topFactor = BigInteger.valueOf(topFactors.get(0));
            } else {
                topFactor = topFactor.multiply( BigInteger.valueOf(topFactors.get(i)) );
            }
            
        }
        
        if (factorLeft) {
            
            BigInteger kFactorial = factorial(k);
            return topFactor.divide(kFactorial);
            
        } else {
            
            BigInteger knFactorial = factorial(n-k);
            return topFactor.divide(knFactorial);
        }
        
    }
    

    public static BigInteger factorial( int n ) {
        
     if( n <= 1 ) {
            return BigInteger.valueOf(1);
     } else {
            return BigInteger.valueOf(n).multiply( factorial( n - 1 ) );
     }
     
    }
    
}

Там я использую принцип симметрии и пытаюсь сокращать числа по максимуму прежде, чем считать сам факториал. То есть в случаях если k < 0.25n (примерно), то я могу считать очень большие числа ибо сокращение решает, но вот если k ~ 0.5n, то тут уже начинается StackOverflow.

Да и вообще, покритикуйте код и общий подход, если не трудно.

Код предполагается использовать для построения биноминальных распределений для всевозможных манипуляций в области теории информаций. То есть, грубо говоря, есть миллион бит, сколькими разными способами могу выбрать 100 из них, которые с вероятностью в 0.1 заваляться. Ну как-то так...

Спасибо!

P.S. Некоторые вещи там делаются для визуализации. Например ArrayList с факторами используется чисто для визуализации в определенных случаях.

P.P.S. И да, всякие аппроксиматизации не катят... Наверное...

maxim1000

Дата 8.10.2010, 00:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

в принципе, можно считать через треугольник Паскаля
но тогда придётся платить памятью (нужно будет одновременно хранить несколько чисел)

--------------------

qqq

esperanto

Дата 8.10.2010, 01:12 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 31.5.2003

Репутация: 2
Всего: 4

Очень просто и достаточно очевидно
(n,cn) для с меньших 0.5 например

очень быстро стремиться к выражению

1 делить на ( корень из ( 2*пи*n*c*(1-c)) и результат умножить на 2 в степени( n*Entropy©)

Вот и все. Считаеться просто.

пс: предложение с треугольником паскаля для миллиона потребует много времени.

Это сообщение отредактировал(а) esperanto - 8.10.2010, 01:15

--------------------

B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »