I decided to write a program that calculates the factorial of a given number.
The code works fine up until anything larger than 12!, after that I get incorrect results.
I suspect It is due to the result being larger than 32 bits. Correct?
To correct this I tried to rcl the edx register.
15! should be 1307674368000 but, it returns 27701857280.
.386
.model flat, stdcall
option casemap :none
includelib \masm32\lib\msvcrt.lib
sprintf proto C :vararg
includelib \masm32\lib\user32.lib
MessageBoxA proto :ptr,:ptr,:ptr,:DWORD
includelib \masm32\lib\kernel32.lib
ExitProcess proto :dword
.data
format db "%lld", 13, 10, 0
_title db "Result",13,10,0
.code
main PROC
LOCAL szBuf[9]:byte
xor edx,edx
rcl edx ,1
xor ebx,ebx
mov eax, 15 ; start of 15!
mov ebx,eax ; Prepares # of loop counter cycle
factoral:
dec ebx ;loop counter
jz ready ;when ebx = 0 jump to ready step
imul eax, ebx ; Multiply for intermeddiate result.
rcl edx, 1 ; Shift carry flag to edx to handle > 32 bit results.
jnz factoral ; Continue loop counter when ebx > 0
ready:
invoke sprintf, addr szBuf, offset format, eax, edx
invoke MessageBoxA, 0, addr szBuf, offset _title, 0
invoke ExitProcess, 0
main ENDP
END main
Extra: Would using shl eax, 1 to calculate the 2nd degree portion (n*2) for the intermediate be better than using imul for each and every degree.
Example: 5!
1) (5*4 =20)
2) (20*3 = 60)
3) (60 left bit shift 1 time = 120)
4) (120 * 1 = 120)
You will reach the limits very soon anyway:
include \masm32\MasmBasic\MasmBasic.inc ; download (http://masm32.com/board/index.php?topic=94.0)
Init
fld1 ; put 1 into the fpu
Let esi="1" ; start descriptive string
For_ ecx=1 To 22
push ecx ; put counter into stack
fild stack ; load value into fpu
fmul ; multiply with previous value
PrintLine Str$(ecx), Tb$, Str$("%u \t", ST(0)), esi ; print value of counter, FPU, string esi
pop eax ; balance the stack
Let esi=esi+Str$("*%i", ecx+1) ; construct the descriptive string
Next
Inkey "ok?" ; wait for a keypress
EndOfCode
Result:1 1 1
2 2 1*2
3 6 1*2*3
4 24 1*2*3*4
5 120 1*2*3*4*5
6 720 1*2*3*4*5*6
7 5040 1*2*3*4*5*6*7
8 40320 1*2*3*4*5*6*7*8
9 362880 1*2*3*4*5*6*7*8*9
10 3628800 1*2*3*4*5*6*7*8*9*10
11 39916800 1*2*3*4*5*6*7*8*9*10*11
12 479001600 1*2*3*4*5*6*7*8*9*10*11*12
13 6227020800 1*2*3*4*5*6*7*8*9*10*11*12*13
14 87178291200 1*2*3*4*5*6*7*8*9*10*11*12*13*14
15 1307674368000 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15
16 20922789888000 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16
17 355687428096000 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17
18 6402373705728000 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18
19 121645100408832000 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19
20 2432902008176640000 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20
21 10082365496054775808 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21
22 10082365496054775808 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22
#20 is still valid, the rest is not. You can check it with Wolfram Alpha (https://www.wolframalpha.com/input/?i=20!).
The Calculator results (it uses FPU):
++++++++++++++++++++++++++++++++
Monday, 17-07-2017 11:04:27
input box=> 20!
solution box1=> 2.43290200817664e+18
+++++++++++++++++++++++++++++++++
Monday, 17-07-2017 11:04:37
input box=> 21!
solution box1=> 5.109094217170944e+19
+++++++++++++++++++++++++++++++++++++++++++
Monday, 17-07-2017 11:04:46
input box=> 22!
solution box1=> 1.12400072777760768e+21
+++++++++++++++++++++++++++++++++++++++++++++
Monday, 17-07-2017 11:04:54
input box=> 23!
solution box1=> 2.5852016738884977e+22
++++++++++++++++++++++++++++++++++++++++++++++++++++
Monday, 17-07-2017 11:05:01
input box=> 24!
solution box1=> 6.2044840173323944e+23
++++++++++++++++++++++++++++++++++++++++++++++++++++
Monday, 17-07-2017 11:05:09
input box=> 45!
solution box1=> 1.19622220865480195e+56
+++++++++++++++++++++++++++++++++++++++++++++++++++++
Monday, 17-07-2017 11:05:21
input box=> 100!
solution box1=> 9.3326215443944153e+0157
+++++++++++++++++++++++++++++++++++++++++++++++++++++
input box=> 500!
solution box1=> 1.22013682599111005e+1134
++++++++++++++++++++++++++++++++++++++++++++++++++
input box=> 1000!
solution box1=> 4.0238726007709371e+2567
All factorials up to 20!
.386
.model flat, stdcall
option casemap :none
includelib \masm32\lib\msvcrt.lib
printf proto C :vararg
includelib \masm32\lib\kernel32.lib
ExitProcess proto :dword
.data
format db "%lld", 13, 10, 0
.code
main proc
mov ebx, 1
.while ebx<21
xor edi, edi
mov esi, 1
mov ecx, 1
.while esi<=ebx
mov eax, esi
cdq
push ebx
push esi
push edx
mov esi, eax
mov eax, edx
mov edx, ecx
or ecx, eax
mov ecx, edx
.if ZERO?
mov eax, esi
pop edx
mul ecx
.else
mul ecx
mov ebx, eax
mov eax, esi
pop edx
mul edi
add ebx, eax
mov eax, esi
mul ecx
add edx, ebx
.endif
pop esi
pop ebx
inc esi
mov ecx, eax
mov edi, edx
.endw
invoke printf, addr format, ecx, edi
inc ebx
.endw
invoke ExitProcess, 0
main endp
end main
If you don't care about precision, the example above can be extended by switching to scientific notation:
.if ecx>20 ; print value of counter, FPU, string esi
PrintLine Str$(ecx), Str$("\t%Ge \t .. ", ST(0)), Right$(esi, 46)
.else
PrintLine Str$(ecx), Str$("\t%i \t", ST(0)), esi
.endif
20 2432902008176640000 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20
21 5.109094217170944000e+19 .. *5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21
...
39 2.039788208119744336e+46 .. 4*25*26*27*28*29*30*31*32*33*34*35*36*37*38*39
40 8.159152832478977343e+47 .. 5*26*27*28*29*30*31*32*33*34*35*36*37*38*39*40
W.A.: 8.15915283247897734345611269596115894272 × 10^47
The last line is the Wolfram Alpha value, for comparison (they use a bignum algo). There is no factual limit for the counter, but the number of valid digits is limited, of course, as rounding errors creep in. Here is the result for 99!:99 9.332621544394415264e+155 .. 4*85*86*87*88*89*90*91*92*93*94*95*96*97*98*99
W.A.: 9.332621544394415268169923885626670049071596826438162... × 10^155
As you can see, the last digit is no longer valid. Source & exe attached.
As has been noted, 20! is the maximum factorial which can be computed "easily" with full accuracy using the FPU or even 64-bit integer registers. Anything higher needs 'big number' computation.
One possible way to compute those big numbers with full accuracy is to use BCD (Binary Coded Decimal) math, which has the advantage of not requiring conversion from binary to ascii if you wish to display the result. Typical code to compute 30! using such a procedure is given at http://www.ray.masmcode.com/BCDaam.html
That code could be easily modified to compute any factorial.
Hello raymond, i'm studying the fpu tutorials page that i found in the old masm forum (simple fpu). Thanks a lot for that! And i'm also going to see your new pages. :greensml: