Вычисление биномиальных коэффициентов… всё-таки программно

[a_batyr]

Астрологи объявили неделю биномиальных коэффициентов. Количество математиков выросло.
Вангую вычисление БК на ардуино за 5 долларов.

[PavelSandovin]

Дело облегчается тем, что в данном случае, и числитель и знаменатель являются произведениями небольших чисел

Хорошо, давайте посчитаем этим методом, например,

С(394959569696694800489675432,2340540340005932332490003325025398054778666543).

Просто любопытно, сколько времени займет факторизация всех входящих в числитель и знаменатель множителей?

[a_batyr]

С(394959569696694800489675432,2340540340005932332490003325025398054778666543).

У вас k > n, как вы собираетесь считать факториал отрицательного числа?

[PavelSandovin]

В данном случае — никак. По определению, С(n, k) = 0 при k > n.

И что-то я такую проверку в коде в статье не увидел :)

[a_batyr]

Да, действительно, не проверяет :)
Но и длинной арифметики он не реализовывал, тогда достаточно запустить C(2147483647, 1073741824)
Меня вот больше беспокоит, что в функции main() переменная k не используется. А ещё при n==k неправильно тоже.

[cranium256]

Да, корректность аргументов функция не проверяет. И длинную арифметику не реализовывал. И для факторизации был взят самый примитивный алгоритм. Цель другая была: формализовать алгоритм, описанный в статье V2008n.

Тем не менее, для целой 64-разрядной арифметики всё работает быстро, точно и без переполнения (естественно, в пределах разумного).

Кстати, при n == k работает правильно. Циклы факторизации числителя и знаменателя не выполняются, поскольку условия продолжения циклов ложны. В итоге функция возвращает 1, как и ожидается.

Переменная k не используется — да, грешен. Проглядел. Осталась от предыдущей версии функции main(). Вся надежда на оптимизирующий компилятор ;)

Если же рассматривать вопрос вычисления биномиальных коэффициентов с применением длинной арифметики, то проблема переполнения, с которой, собственно, и началась эта серия статей, отпадает сразу. Останутся традиционные вопросы: скорость работы и занимаемая память. Но это как бы уже далеко за рамками данной статьи.

PS. Переменную k из кода убрал.

[a_batyr]

На самом деле вот этот комментарий уже раскрывал вопрос разложения на множители.
Ваш код тоже можно было б оставить в виде комментария под спойлером, не будь вы read-only.
Добро пожаловать.

[PavelSandovin]

Попробуйте реализовать еще одну версию, вычисляющую биномиальный коээффициент «в лоб», без факторизации и сравнить производительность обоих версий.

Делаю ставку на то, что даже при вычислениях в пределах диапазона типа INT без факторизации будет быстрее.

А за его пределами, как в моем примере — только если поменять местами аргументы — факторизацией пользоваться вообще нереально.

[dcc0]

Что означает «самый примитивный»? Т.е. какой именно алгоритм?
Метод Ферма тоже довольно прозрачен, и операций в нем немного, я даже на php с ним игрался.
Код C# понимаю очень слабо, поэтому спросил.
Дело в том, что у Вас реализация алгоритма, формализация на языке, конкретном, а хотелось бы
на естественном… или по шагам.

[cranium256]

Наверное этот алгоритм называется «перебор делителей». Хотя я над этим не задумывался.
«Самый примитивный» — потому что вообще без оптимизаций.

Вообще-то код у меня на кондовом C++ ;)

Примерно так будет выглядеть эта функция на PHP (сохранение простых делителей заменено просто на вывод):

function factorize($num) {
	$j = 2;
	while ($num / 2 >= $j) {
		if ($num % $j == 0) {
			echo $j;
			$num /= $j;
			$j = 2;
		} else {
			++$j;
		}
	}
	echo $num;
}

Переменная j — это проверяемый делитель. В самом плохом случае, если num постое, в цикле while она пробежит все значения от 2 до num / 2 (условие продолжения цикла). Если же num — не простое, то при каком-то значении j остаток от деления станет равным 0, следовательно текущее значение является делителем num. В это случае выводим найденное значение, num делим на это значение и j сбрасываем на начальное значение (2). Таким образом находим все делители, кроме последнего, в порядке возрастания. Последний делитель — значение num после завершения цикла.