Factorial calculation

[skinnyg]

Ok writing a prog to check factorial then display message if does not fit in 32bit space.. cant fig that part out.. i know i gotta check for over flow then display when it cant fit in 32bit..any assistance would be great..here is the code.. i def will continue to try..(head is pounding..  :redface:  )

INCLUDE Irvine32.inc

.data

factormsg BYTE "Enter the value of n to calculate the factorial (-1 to quit): ",0
factordisplay BYTE "The factorial is: ",0
factorError BYTE "Error: Result does not fit in 32 bits.",0


.code

main PROC
L1:
   mov edx, OffSet factormsg
   Call WriteString
   Call Readint
   mov edx, Offset factordisplay
   Call WriteString

   .if eax== -1
   exit
   .endif
   
   ;Call Crlf

   push eax ; push user entered interger on stack

call Factorial ; calculate factorial (EAX)
call WriteDec ; display it
call Crlf

loop L1

exit
main ENDP
;----------------------------------------------------
Factorial PROC
; Calculates a factorial.
; Receives: [ebp+8] = n, the number to calculate
; Returns: eax = the factorial of n
;----------------------------------------------------
push ebp
mov ebp,esp
mov eax,[ebp+8] ; get n

cmp eax,0 ; n  0?
   ja L1 ; yes: continue
mov eax,1 ; no: return 1 as the value of 0!

   jmp L2 ; and return to the caller

L1: dec eax

push eax ; Factorial(n1)

call Factorial
; Instructions from this point on execute when each
; recursive call returns.

ReturnFact:

mov ebx,[ebp+8] ; get n
   mul ebx ; EDX:EAX = EAX * EBX
   L2: pop ebp ; return EAX
   ret 4 ; clean up stack
Factorial ENDP
END main

[dedndave]

there are some sieve type algorithms for this
probably one of the simplest is the sieve of Eratosthenes

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

you could create a 512 Mb file, with 1 bit for each value from 0 to 4294967295
one little program to create the file
and another program to open and read the file, and test values

[qWord]

the overflow can be detected by testing EDX after the multiplications:

Code Select Expand

mul ebx
test edx,edx
jnz @largerThan32Bit
Because you are using a recursive algorithm, you must find a way to notify the "upper level" that an overflow occurs. This could be done by using a register (e.g. ECX) or adding a second parameter to the function, which is a pointer to a Boolean variable (e.g. Factorial  proto n:DWORD,pOverflow: ptr BOOL). An other solution is to use the carry flag (instructions: set/clear carry: stc/clc).

[Mikl__]

Code Select Expand

.586p
.model flat, stdcall
option casemap:none
.code
include \masm32\include\windows.inc
includelib \masm32\lib\user32.lib
extrn _imp__MessageBoxA@16:dword
n equ 73
;19!=121645100408832000
;20!=2432902008176640000
;21!=51090942171709440000
;22!=1124000727777607680000
;23!=25852016738884976640000
;24!=620448401733239439360000
;25!=15511210043330985984000000
;26!=403291461126605635584000000
;27!=10888869450418352160768000000
;28!=304888344611713860501504000000
;29!=8841761993739701954543616000000
;30!=2,6525285981219105863630848e+32
;31!=8,22283865417792281772556288e+33
;32!=2,6313083693369353016721801216e+35
;33!=8,68331761881188649551819440128e+36
;34!=2,9523279903960414084761860964352e+38
;35!=1,0333147966386144929666651337523e+40
;36!=3,7199332678990121746799944815084e+41
;37!=1,3763753091226345046315979581581e+43
;38!=5,2302261746660111176000722410007e+44
;39!=2,0397882081197443358640281739903e+46
;40!=8,1591528324789773434561126959612e+47
;41!=3,3452526613163807108170062053441e+49
;42!=1,4050061177528798985431426062445e+51
;43!=6,0415263063373835637355132068514e+52
;44!=2,6582715747884487680436258110146e+54
;45!=1,1962222086548019456196316149566e+56
;46!=5,5026221598120889498503054288003e+57
;47!=2,5862324151116818064296435515361e+59
;48!=1,2413915592536072670862289047373e+61
;49!=6,082818640342675608722521633213e+62
;50!=3,0414093201713378043612608166065e+64
;51!=1,5511187532873822802242430164693e+66
;52!=8,0658175170943878571660636856404e+67
;53!=4,2748832840600255642980137533894e+69
;54!=2,3084369733924138047209274268303e+71
;55!=1,2696403353658275925965100847567e+73
;56!=7,1099858780486345185404564746372e+74
;57!=4,0526919504877216755680601905432e+76
;58!=2,3505613312828785718294749105151e+78
;59!=1,3868311854568983573793901972039e+80
;60!=8,3209871127413901442763411832234e+81
;61!=5,0758021387722479880085681217663e+83
;62!=3,1469973260387937525653122354951e+85
;63!=1,9826083154044400641161467083619e+87
;64!=1,2688693218588416410343338933516e+89
;65!=8,2476505920824706667231703067855e+90
;66!=5,4434493907744306400372924024784e+92
;67!=3,6471110918188685288249859096605e+94
;68!=2,4800355424368305996009904185692e+96
;69!=1,7112245242814131137246833888127e+98
;70!=1,1978571669969891796072783721689e+100
;71!=8,5047858856786231752116764423993e+101
;72!=6,1234458376886086861524070385275e+103
;73!=4,4701154615126843408912571381251e+105
start:  mov edi,offset result+len;edi - pointer to the last byte of the result
    mov esi,n
    mov dword ptr [edi-4],esi
    sub edi,8
    mov ebp,1
    dec esi
@1: mov ecx,ebp
    xor ebx,ebx
@@: mov eax,dword ptr [edi+4*ecx]
    mul esi
    add eax,ebx
    adc edx,0
    mov ebx,edx
    mov dword ptr [edi+4*ecx],eax
    loop @b;.untilcxz
    je @2;  .if !ZERO?
    mov dword ptr [edi],edx
    cmp dword ptr [edi+4*ebp],0
    je @f
    inc ebp
@@: sub edi,4
@2: dec esi
    jne @1;.until ZERO?
; big-endian --> litle-endian
    mov edi,offset result
    mov cl,len/4;length of the result in the DWORD
@@: mov eax,[edi]
    bswap eax
    stosd
    loop @b
; translate hex->dec
    mov esi,offset terminator-1;
@3: mov cl,len;length in bytes of the value of the dividend
    mov edi,offset result
    xor eax,eax
@@: mov al,[edi];dividend
    div ten
    stosb
    loop @b
    or [esi],ah;remain
    dec esi
    cmp dword ptr [edi-4],0;cmp result+36,0
    jne @3
    cmp dword ptr [edi-8],0;cmp result+32,0
    jne @3
    cmp dword ptr [edi-12],0;cmp result+32,0
    jne @3
;screen output
    inc esi
    push MB_OK + MB_ICONASTERISK
    push offset mesbox_title   
    push esi;offset mesbox_text adjusted for leading zeros
    push 0
    call _imp__MessageBoxA@16
    ret;exit
.data
result  db 44 dup (0)
len = $-result
ten db 10
mesbox_text db 112 dup ('0')
terminator db 0
mesbox_title db 'Factorial calculation',0
end start

[dedndave]

i was thinking primes
DOH !   :redface:

[Mikl__]

Code Select Expand

.code
push N ;compute N factorial
call fact ;call procedure
push edi ;edi=N! the result is here
push offset format
push offset buffer
call _imp__wsprintfA
add esp,12 ;align the stack after wsprintfA
push 0
push offset caption
push offset buffer
push 0
call _imp__MessageBoxA@16 ;output the result on the screen
ret;exit the program
;structure of the stack frame
;[esp] saved return address of the procedure
;[esp+4] place for N
fact proc
mov ecx,[esp+4];ecx=N
jecxz done ;N equal 0?
dec ecx ;for the next call
push ecx ;included in the stack ecx=N-1
call fact
mov eax,edi ;in edi the value of the previous result
mul dword ptr [esp+4] ;eax=N*edi
jmp short rtrn
done: mov eax,1 ;eax=1
rtrn: mov edi,eax;return the new value of the result in edi
retn 4 ;remove unnecessary local variables
fact endp
.data
format db 'factorial=%lu',0
buffer db 50 dup (0)
caption db ' factorial',0

[RuiLoureiro]

 
1700! =  2.99835320555842E+4755

[skinnyg]

Thanks everyone... it was a great help.. :t