[closed][c#] функция нахождения факториала

Lizabeth

есть такая? или в цикл загнать? хотелось бы внутреннюю ф-ию какую-нибудь, чтобы работала быстрее цикла

Dasar

встроенной - нет.
если факториал много считается для одних и тех же значениях, то можно предвычислить массив результатов факториала, и уже по этому массиву результат получать

Lizabeth

а, ну типа контрольных точек ставить. тоже нормально.

sylar

В каких диапазонах значений и какая требуется точность ?
Просто имхо для малых значений тупо циклом вычислять, для больших - по формуле Стирлинга. Граница между "малыми" и "большими" определяется точностью которая вам требуется.

Lizabeth

требуется вычислить числа типа факториал 300* рандом(0.9-1.1) [ну т.е. небольшая флуктуация, диапазон 240-330]. и так, примерно, 300 раз вычислять...
прога тормозит при лобовом вычислении
по поводу точности: блин... в общем, надо смоделировать распределение пуассона
300 - матожидание, лямбда, - столько страховых случаев произошло.

AlexV769

диапазон 240-330
один раз вычислить, записать в хеш результаты и пользоваться.

Lizabeth

только не хеш, а кэш, имхо.... хеш-функции в шифровании используются...
ну да, так и сделаю. только не сразу же один раз все, а по мере надобности.

Lizabeth

спасибо большое, оплатил инет и посмотрел в вики эту формулу. думаю, этой точности будет достаточно. спасибо большое! а то я уже начал придумывать оптимизацию алгоритма контрольных точек

AlexV769

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

Helga87

Нафига тут хеш, если заведомо устроит массив на 1000 элементов? Работать будет в 10 раз быстрее

AlexV769

Логично, но зачем на 1000, когда надо на ~100?

Lizabeth

хм... странно. в шифровании так назывались функции, которые делают "отпечатки" шифруемого текста. отпечатки - типа отпечатки пальцев.

AlexV769

Ничего странного, обычный "ассоциированный" массив, если так можно сказать.
Хотя прав, array[value-base] будет работать куда быстрее :)

Lizabeth

но самое лучшее(и просто и быстро) - формула стирлинга!

Bibi

вот, как раз, тут-то ты и неправ. и непроще и небыстрее =)

AlexV769

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

Lizabeth

не знаю, я уже написал =)

pitrik2

только не сразу же один раз все, а по мере надобности.
если точно известно что нужно то нах это каждый раз вычислять?
пишешь отдельно прогу которая запишет все значения факториалов через запятую в файл - несколько строчек кода
в свою прогу добавляешь считывание из этого файла при старте в массив

sylar

Если настолько небольшая флуктуация то правильно умные люди говорят про хэштаблицу:)
Я бы сделал тупо файл - в который бы писал вычисленные значения факториалов после каждого прогона программы.
И на каждом старте программы потом этот файл считывал в словарь (Dictionary<int,long>) а в процессе работы пополнял.
Это на случай если диапазоны будут изменяться (станут например 420*random(0.8-1.2 потом еще какими то и т.д.)
Схема работы примитивная - не нашел в словаре -> вычислил Стирлингом, (округлил положил в словарь. Умными словами это называется "типовое решение IdentityMap".
После окончания работы словарь сериализуется в файл (добавленные значения).
Если диапазоны меняться не будут то имхо вполне подойдет массив. Хотя я бы все равно словарь использовал. Потому что так проще и тупее. А время доступа в обоих случаях есть O(1). Только в случае словаря думать не надо :)

Lizabeth



если точно известно что нужно то нах это каждый раз вычислять?
а вот этого условия нет. это я к примеру говорю, но могут быть и другие значения

Dasar

. А время доступа в обоих случаях есть O(1).
Да, и там, и там O(1 только у массива O(1 а у хэша C*O(1) - где C - в районе 10-ки.
бывает, что массив удачно инлайнится, тогда C может вообще до сотни доходить.

Sharp

Я понимаю, что автор уже все сделал и поздно что-либо советовать, но неужели у программы ограничение на память, что не получится завести массив из 400 элементов и заполнить его в самом начале?
400 умножений и столько же присваиваний, это будет работать очень быстро.
 

    i=0; fact[0] = 1.0;

    for(i=1;i<N;i++) {

        fact[i] = i*fact[i-1];

    }

lubanj

если че, 400! = 6,4034522846623895262347970319503e+868 //виндоус калькулятор

Dasar

если че, 400! = 6,4034522846623895262347970319503e+868 //виндоус калькулятор
значит массив будет double-ов, ну и все.

DEVIS2008

double это не выдержит

sylar

А за счет чего такие накладные расходы ?
Боксинг, анбоксинг, подсчет хэшфункции ?
(в словарях если в качестве ключа value type - Int32 например - по идее ведь этого не должно быть и хэш считать тоже не требуется ?)
Просто вопрос не исследовал -> как-то не было необходимости пока. Если просветите буду благодарен (тесты писать и индусский код в рефлекторе читать лень :) )

SPARTAK3959

Факториалы обычно умножают и делят - поэтому имеет смысл хранить их логарифмы, а не их самих.

DEVIS2008

потом всё равно надо будет брать экспоненту, так что капец всё равно настанет. Да, ещё, получается, топикстартер использует какой-то свой тип, не нативный?

agaaaa

Не думаю, что автор пользуется длинной арифметикой. А 10-битные флоаты потянут эти числа на ура.

pitrik2

Да, ещё, получается, топикстартер использует какой-то свой тип, не нативный?
а че, бигинтегер нету среди нативных?

Dasar

А за счет чего такие накладные расходы ?
if-ы, вызовы функций, сужающее преобразование хэша, проверки на равенство
псевдокод же хэша примерно следующий (это даже если конфликта хэша не было):
взять элемент
вызвать функцию получения хэша
по хэшу через сужающее преобразование получить индекс в массиве
проверить что ключ в массиве равен искомому
вернуть результат
вот лишний порядок тактов на этом коде и набегает

Dasar

double это не выдержит
да, не выдержит
кстати интересно в каком-типе топикстартер считает?

sylar

псевдокод работы хэштаблицы я знаю :)
понятно что массив заведомо быстрее работает потому что по сути хэштаблица это своего рода надстройка над массивом - и внутри себя содержит массив.
тут вопрос именно в количественной оценке -> про C = 10.
это эмпирические данные ?

Dasar

тут вопрос именно в количественной оценке -> про C = 10.
это эмпирические данные ?
на основе тестов для родного массива и dictionary для .net-а

Sharp

Зато long double вполне выдерживает.

sylar

вообще если вопрос с факториалом копать то вот: сайт
там куча всего доброго и светлого про факториал:
алгоритмы, исходники, анализ алгоритмов и т.п.
(в качестве демки онлайн калькулятор )
после чтения материалов сайта метод Стирлинга, кеширование и т.п. "хинты" кажутся детским лепетом :) по сравнению с этим
"And here is an algorithm which nobody needs, for the Simple-Minded only:
long factorial(long n) { return n <= 1 ? 1 : n * factorial(n-1); } Do not use it if n > 12. "

Lizabeth

через double, но это нифига не решает проблему, выдает что-то странное. long double вообще не берет, пишет Error 1 Identifier expected, 'double' is a keyword 
double KoefFluktuaciiLambda = (r.NextDouble * (1.2 - 0.8) + 0.8);        

double double chastota = (Math.Exp(-con_chastota 

* Math.Pow(con_chastota, con_chastota * KoefFluktuaciiLambda) 

/ (Math.Sqrt(2 * 2.14159265 * con_chastota * KoefFluktuaciiLambda) 

* Math.Powcon_chastota * KoefFluktuaciiLambda * Math.Exp(-1 con_chastota * KoefFluktuaciiLambda;

в общем, надо ставить msdn...

zya369

треш :shocked:

lubanj

2.14159265
бугага!

SPARTAK3959

Да, не все знают про константу Math.PI...
Оставить комментарий
Имя или ник:
Комментарий: