Strange issue with my factorial program

[Chris.]

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.

Code Select Expand

.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)

[jj2007]

You will reach the limits very soon anyway:

include \masm32\MasmBasic\MasmBasic.inc         ; download
  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:

Code Select Expand

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.

[RuiLoureiro]

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

[aw27]

All factorials up to 20!

Code Select Expand


.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


[jj2007]

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

Code Select Expand

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!:

Code Select Expand

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.

[raymond]

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.

[felipe]

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.