## News:

Message to All Guests
NB: Posting URL's See here: Posted URL Change

## Factorial calculation

Started by skinnyg, May 15, 2013, 10:17:20 AM

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

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:
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).
MREAL macros - when you need floating point arithmetic while assembling!

#### Mikl__

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