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

Господа программисты!
Вновь возвращаюсь к этой теме. В #30 Nouzui запостил листинг на Си. Я слегка изменил его:

Код (Text):

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

Спасибо Nouzui - код великолепно работает
Затем я дизассемблировал полученную программу и исходя из дизассемблерного листинга "дословно" переписал её на FASM:

Код (Text):

1. format PE console
2. include 'win32axp.inc'
3. .data
4. massiv dw 1
5.        dw 999999 dup 0
6.  
7. len dd 1
8. N dd ?
9. ten dd 10
10. inp db 'Input N:',0Dh,0Ah,0;10
11. d db '%d',0
12. d04 db '%04d',0
13. stroka db 1000000 dup 0
14. hout dd ?
15. ns dd ?
16. vvod db 11 dup 0
17. faiil db 'Program fails',0;13
18. dllka db 'msvcrt.dll',0
19. name1 db 'atoi',0
20. name2 db 'printf',0
21. atoi dd ?
22. printf dd ?
23. .code
24. fuck:
25. invoke LoadLibrary,dllka
26. push eax
27. invoke GetProcAddress,eax,name1
28. mov [atoi],eax
29. pop eax
30. invoke GetProcAddress,eax,name1
31. mov [printf],eax
32. invoke GetStdHandle,STD_OUTPUT_HANDLE
33. mov [hout],eax
34. invoke WriteConsole,eax,inp,10,ns,0
35. invoke GetStdHandle,STD_INPUT_HANDLE
36. invoke ReadConsole,eax,vvod,10,ns,0
37. cinvoke atoi,vvod
38. mov [N],eax
39.  
40. xor esi,esi
41. xor edi,edi
42. xor ebx,ebx
43. inc esi
44.  
45. factorial:
46.  cmp esi,[N]
47.  ja nol
48.  xor edi,edi
49. cyclo:
50.  cmp edi,[len]
51.  jb testcn
52. xxx:
53.  movzx eax,[massiv+edi*2]
54.  imul eax,esi
55.  add eax,ebx
56.  xor edx,edx
57.  mov ecx,2710h
58.  div ecx
59.  mov [massiv+edi*2],dx
60.  mov eax,ebx
61.  xor edx,edx
62.  div ecx
63.  mov ebx,eax
64.  inc edi
65.  jmp cyclo
66.  
67. testcn:
68.  test ebx,ebx
69.  jnz xxx
70.  mov [len],edi
71.  inc esi
72.  jmp factorial
73.  
74. nol:
75.  mov eax,[len]
76.  dec eax
77.  mov edi,eax
78.  movzx ecx,[massiv+eax*2]
79.  cinvoke printf,d,ecx
80.  
81. cykl:
82.  dec edi
83.  test edi,edi
84.  jz quit
85.  movzx eax,[massiv+edi*2]
86.  cinvoke printf,d04,eax
87.  jmp cykl
88. jmp quit
89.  
90. retry:invoke WriteConsole,[hout],faiil,13,ns,0
91. quit:invoke ExitProcess,0
92. .end fuck

Разница только в том, что я некоторые переменные сразу распихнул по регистрам: i в edi, l в esi, cn в ebx
Всё компилится, но при работе вызывает исключение во время cn%10000
Подскажите, пожалуйста, что я делаю не так?

 

Спасибо Great!
Я косячил с сишными функциями

 

Уважаемые программисты! Прошу прощения, что вновь возвращаюсь к этой избитой теме, но возник ещё ряд вопросов:
Код, данный мне Nouzui, я переложил на ассемблер, получилось следующее (файл в аттаче) - всё работает, всё отлично

Теперь мне захотелось использовать функции gmp, тем более, что попался мне на глаза исходничек на ПХП, факториал вычисляющий:

Код (Text):

1. <?php
2.  
3. function fact ($x) {
4.  
5.     if ($x <= 1)
6.  
7.   return 1;
8.  
9.     else
10.  
11.   return gmp_mul ($x, fact ($x-1));
12.  
13. }
14.  
15.  
16.  
17. print gmp_strval (fact (1000)) . "\n";
18.  
19. ?>

Скачал я GMP, распаковал и к сишным инклудам закинул (а юзаю я MS VC++ 2003). Сочинил следующее:

Код (Text):

1. #include <stdio.h>
2. #include <gmp\gmpxx.h>
3. int N;
4. int fact(int x)
5. {
6. if (x <= 1)
7. return 1;
8. else return gmp_mul(x, fact(x-1));
9. }
10.  
11. void main()
12. {
13. scanf("%d",&N);
14. printf("%s\n",gmp_strval(fact(N)));
15. }

Не компилится даже, зараза! Я попробовал найти gmp_mul в тамошних хедерах - нету там такой!
Подскажите, как использовать gmp'шные функции в сишном коде?

 

ECk

Можно для совсем чайников как сделать так, чтобы можно было вызвывать функции GMP из Delphi

 

У меня есть программа вместе с исходниками, у меня за 3 минуту факториал 50000 вычислила, более 200000 десятичных знаков и все точно. Толька там с управлением нужно разобраться. Нужно будет сначала и систему исчисления и разрядность указать. http://www.asm1a.narod.ru/calc.rar

Функция вычисления факториала основана на алгоритме короткого умножения т. е. будь у вас хоть террабайт памяти на супер компе факториал более 2^32 вычисляться не будет

Код (Text):

1. Factorial proc uses edi esi ebx n:DWORD
2.     mov ecx,RegSize    ;в ecx - количество DWORD`ов в числе
3.     mov edi,R1            ;edi - указатель на число
4.     xor eax,eax
5.     rep stosd
6.     mov esi,n
7.     mov dword ptr [edi-4],esi
8.     sub edi,8
9.     mov ebp,1
10.     dec esi
11.     .repeat
12.         mov ecx,ebp
13.         xor ebx,ebx
14.         .repeat
15.             mov eax,dword ptr [edi+4*ecx]
16.             mul esi
17.             add eax,ebx
18.             adc edx,0
19.             mov ebx,edx
20.             mov dword ptr [edi+4*ecx],eax
21.         .untilcxz
22.         .if !ZERO?
23.             mov dword ptr [edi],edx
24.             .if dword ptr [edi+4*ebp]
25.                 inc ebp
26.             .endif
27.             sub edi,4
28.         .endif
29.         dec esi
30.     .until ZERO?
31.     pop ebx
32.     pop edi
33.     pop esi
34.     pop ebp
35.     retn 4
36. Factorial endp

 

Быстрее будет записать факториал всех 20000 чисел в массив и читать уже готовые значение. Нужно взять любой исходник, записать результаты факториалов в файл (в понятном программе формате). Это лучше, чем сидеть и мучаться "как же это быстрее посчитать" и потом писать совершенно нечитаемые программы.

 

я как-то давно написал такую программу на fortrane

попробуй представить себе 96-и битное число записанное в регистрах eax, ebx, ecx ну или где-то в памяти
и умножь его на 3.
Чтоб понять алгоритм, на бумажке перемножь 12 34 56 на 3, считая группу регистром, обрати внимание на
переносы. Этой логикой можно считать любые факториалы, и единственным ограничением будет доступная
память компьютера

 

Имхо фигней стадаете, господа.
1000000! вычисляется за пол секунды и требует 8 мешков рама,
ну а 10000000! соответственно за 5 сек и требует 80 мешков рама.

Алгоритм слияния по степеням двойки. Полезно предварительно развести массив нулями в двое. Пример для 9 факториал.

2030405060708090
6000020024002700
0210000042030000
0882630000000000

 

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

Вощщем та, я бы мог это зарелизить, но какой прок иметь например 90 или 900 мешков случайных цыфирь? Зато такой огроменный факториал нужен например для кодов РидаСоломона, и там я его сделал.

 

Малешка недооценил я вычислительные сложности и требования по памяти и времени. =(((
Вообщем, ближе к делу оказалось, что

1000000! вычисляется за 30 секунд,
10000000! вычисляется за 10 минут на c2d.

А памяти жрет 1.6G =)))

Но это сусщества дела не меняет! 1000000 секунд это 11 дней однако если в лоб.
Реально быстро можно получить и мешок цифр, и целый гараж.

Посколько такие факториалы это вовсе не бегинерс, а скорее крутос, то брать мою прогу можно в проджектс.

 

persicum
ну, а где функция подсчета (или хотя бы приблизительно) количества нулей в конце каждого факториала? .