Прогнозирование переполнения при подсчете комбинаций - PullRequest
Новая
       19

Прогнозирование переполнения при подсчете комбинаций

2 голосов
/ 23 февраля 2012

У нас есть следующая формула для определения, сколько комбинаций C мы можем выбрать размером k из набора n:

Combinations Forumla

У меня естьнаписал алгоритм, который всегда будет давать ответ , если , конечно, ответ попадает в диапазон типа данных (* в моем случае ulong), разлагая и аннулируя термины в числителе и знаменателе во времяоценка.

Несмотря на то, что довольно быстро попытаться вычислить C и обнаружить переполнение, если результат слишком велик, было бы лучше, если бы я мог поместить n и k в предварительную функциюкоторый оценивает, будет ли ответ больше, чем то, что может удержать ulong.Это не должно быть точным.Если он оценивает, что данные n и k не будут переполнены, но это так, это нормально - но он никогда не должен говорить этого, он будет переполняться, если не будет.В идеале эта функция должна быть очень быстрой, иначе нет смысла ее иметь - я могу также попытаться вычислить непосредственно C и позволить ей переполниться.

Я строил кривую nCk для различных n как функциюиз k, чтобы увидеть, могу ли я найти кривую, которая растет, по крайней мере, так же быстро, как C (n, k), но не расходится слишком далеко в интересующем меня диапазоне (0..2 ^ 64-1) и являетсявычислительно легко оценить.

Мне не повезло.Есть идеи?

1 Ответ

0 голосов
/ 26 марта 2012

Не видя фактического кода для вашего алгоритма, я не могу дать вам 100% -ное решение, но вам лучше всего разработать эвристическую функцию. Просто найдя наименьшее значение r, для которого окончательный ответ на n C r переполняется для множества значений n, вы сможете проанализировать связь между чем-то как n и отношение между n и r ( n / r ), и найти функцию быстрого вычисления, которая позволит вам узнать, произойдет ли переполнение с помощью регрессии .

Я обнаружил, что для любого n < 68 вы никогда не должны переполнять окончательный ответ, так как 67 C 33 = 67 C 34 ~ 1,42x10 19 - самый большой из возможных ответов, а ulong содержит ~ 1,84x10 19 . Точно так же, когда n > 5000, любой r > 5 или n-r < n-5 обязательно переполнится. Вы можете настроить эти отсечки по своему вкусу, и для всех значений n между ними просто вычислите n / r и используйте формулу регрессии, чтобы решить, будет ли она переполнена или нет.

Это может быть слишком много работы, но это должно, по крайней мере, привести вас на правильный путь.

...