Как вычислить факториал большого числа?

Дамссс, хорошие бегиннеры сейчас пошли!

 

Помню разок патался влезть в "серьезный" раздел так меня быстро оттуда нагнали вот и не парюсь. ))

 

Всем огромное спасибо!

2 murtix
Пытаюсь разобраться с гамма-функцией. Спасибо за код.
2 nitrotoluol
Спасибо за исходник. Разбираюсь...

Ну а в целом, господа программисты, есть ли какие-нибудь общепринятые эффективные алгоритмы работы с большими числами (умножение, возведение в степень и т.д.) с реализацией на ассемблере? Возможно, готовые библиотеки (желательно к FASM)?

 

В GMP есть сорцы - там оптимизация под кучу различных процессоров (от ARM до Cray).
Для IA32 там реализация умножения методом Карацубы на асме есть.

 

а еще есть формула Стирлинга:
n!~= (2*pi*n)^0.5 * (n/e)^n
здесь ^ обозначает возведение в степень

формула довольно таки точная, причем ее относительная погрешность убывает с ростом n
уже для n=5 формула дает 118 вместо 120, то есть расхождение меньше 2%

 

2 ECk
Скачал GMP, немного растерялся... В каком из многочисленных файлов искать пример умножения больших чисел на ассемблере x86-32?

 

в каталоге mpn\ если не путаю - а там, смотря какой процессор тебя интересует (generic - там портабельный, а в других - каталогах заточенные под разные процы файлы)

 

2 ECk
Большое спасибо!

 

Nouzui
Есть еще более точные аппроксимирующие приближения (уточняющие формулу Стирлинга).

 

crypto
все равно с их помощью быстрее не получится, со Стирлингом, по крайней мере, выигрыша точно никакого

ну хез что там за алгоритм.. я попробовал тупо в лоб, и для факториала 50000 у меня получилось быстрее (калькулятор ~ 20 сек, у меня ~ 8). Вот код:

Код (Text):

1. unsigned short array[1000000] = {1};
2. unsigned int len= 1;
3.  
4. #define FACTOR  50000
5.  
6. int main()
7. {
8.     // TODO: Place code here.
9.     unsigned int i;
10.     unsigned long l;
11.     unsigned long cn;
12.  
13.     cn= 0;
14.     for(l= 1; l<=FACTOR; l++)
15.     {
16.         for(i= 0; i<len || cn; i++)
17.         {
18.             cn+= array[i]*l;
19.             array[i]= (unsigned short)(cn%10000);
20.             cn/= 10000;
21.         }
22.         len= i;
23.     }
24.  
25.     printf("%d", array[len-1]);
26.     for(i= len-1; i--;)
27.     {
28.         printf("%04d", array[i]);
29.     }
30.  
31.     printf("\n");
32.    
33.     return 0;
34. }

ps: может ты просто тестил Debug конфигурацию?

 

Nouzui
А ты не пробовал факториал через логарифмы считать?

 

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

 

Nouzui
Есть же у сопроцессора функция exp(x)

 

ну есть.. да ну, стоит ли это того?

 

Nouzui
Для больших чисел через логарифмы будет быстрее...

 

а сами логарифмы считаются не дольше?

 

Nouzui
Поставь эксперимент, результатом его должна быть таблица, сопоставляющая результаты расчетов в лоб и с помощью логарифмов

 

crypto
оч надо ))
это Adrax загоняется, а не я.. гы

 

Nouzui
Офтоп
Знаешь, что здесь с ленивыми делают?
Их помещают в качестве экспонатов в раздел Вирология

 

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