Index
> High Level Languages > factorial implementationGoto page 1, 2 Next |
| Author |
|
|
Andy 03 Nov 2011, 20:35
I tried to find on forum an implementation of factorial function but I can't find any short and clear code. I'm interesed in generating machine code from FASM code, something like in my other thread example. I would really appreciate if anyone can help me with this.
|
|||
03 Nov 2011, 20:35 |
|
|
revolution 03 Nov 2011, 20:56
factorial(-1) gives the wrong answer.
|
|||
|
03 Nov 2011, 20:56 |
|
|
emc 03 Nov 2011, 22:07
Formally, the factorial function is defined as a sequence as follow (defined on naturals numbers):
0! = 1 n! = n * (n-1)! This is the simplest form to implement in any language (with a recursive function like typedfef shown). |
|||
|
03 Nov 2011, 22:07 |
|
|
Matrix 03 Nov 2011, 22:26
revolution wrote: factorial(-1) gives the wrong answer. that's zero 
btw: http://en.wikipedia.org/wiki/Factorial |
|||
|
03 Nov 2011, 22:26 |
|
|
revolution 04 Nov 2011, 02:35
Matrix wrote:
|
|||
|
04 Nov 2011, 02:35 |
|
|
Tyler 04 Nov 2011, 07:53
Matrix wrote:
|
|||
|
04 Nov 2011, 07:53 |
|
|
Matrix 04 Nov 2011, 16:19
revolution wrote:
been there, done that... |
|||
|
04 Nov 2011, 16:19 |
|
|
Andy 05 Nov 2011, 16:18
Thanks guys, after some work I wrote this:
Code: use32
push ebp
mov ebp, esp
mov eax, [ebp + 08]
cmp eax,0
jl Error
cmp eax,1
jle Set1
mov ecx,eax
Again:
dec ecx
mul ecx
cmp ecx,1
ja Again
Result:
pop ebp
ret 4
Set1:
mov eax,1
jmp Result
Error:
or eax,0FFFFFFFFh
jmp Result
Maybe is not the best way but seems to work good for me. |
|||
|
05 Nov 2011, 16:18 |
|
|
revolution 05 Nov 2011, 16:25
Andy: Any input above 12 give the wrong answer.
|
|||
|
05 Nov 2011, 16:25 |
|
|
emc 05 Nov 2011, 16:42
You have to be careful with limitations of your CPU: 13! > (2^32)-1
|
|||
|
05 Nov 2011, 16:42 |
|
|
Andy 05 Nov 2011, 17:28
I know, the limitation is caused by int data type range, right? If you know how can I extend that I listen, as I said I`m new in assembly.
 |
|||
|
05 Nov 2011, 17:28 |
|
|
revolution 05 Nov 2011, 18:07
Andy wrote: I know, the limitation is caused by int data type range, right? If you know how can I extend that I listen, as I said I`m new in assembly. |
|||
|
05 Nov 2011, 18:07 |
|
|
emc 05 Nov 2011, 18:09
yes (unsigned int, exactly), Maybe you can use an other 'type': IEEE single precision ( http://en.wikipedia.org/wiki/Single_precision_floating-point_format#IEEE_754_single_precision_binary_floating-point_format:_binary32 ) working with SSE extension and xmm registers.
|
|||
|
05 Nov 2011, 18:09 |
|
|
revolution 05 Nov 2011, 18:13
Single precision will give you a reasonable dynamic range but you lose of lot of precision (also applies to double precision). If your application can accept the precision loss then floating point might also be a suitable option.
|
|||
|
05 Nov 2011, 18:13 |
|
|
Andy 05 Nov 2011, 19:50
It's a little over my knowledge to work with floating point numbers. I tried an example wrote in VC++ 2010 and I checked the disassembled code, there are some strange instructions that I never saw or used them.
Code: float Factorial(int n) { 00411380 55 push ebp 00411381 8B EC mov ebp,esp 00411383 81 EC D8 00 00 00 sub esp,0D8h 00411389 53 push ebx 0041138A 56 push esi 0041138B 57 push edi 0041138C 8D BD 28 FF FF FF lea edi,[ebp-0D8h] 00411392 B9 36 00 00 00 mov ecx,36h 00411397 B8 CC CC CC CC mov eax,0CCCCCCCCh 0041139C F3 AB rep stos dword ptr es:[edi] if (n<0) return -1; 0041139E 83 7D 08 00 cmp dword ptr [n],0 004113A2 7D 08 jge Factorial+2Ch (4113ACh) 004113A4 D9 05 60 57 41 00 fld dword ptr [__real@bf800000 (415760h)] 004113AA EB 44 jmp Factorial+70h (4113F0h) if (n<=1) return 1; 004113AC 83 7D 08 01 cmp dword ptr [n],1 004113B0 7F 04 jg Factorial+36h (4113B6h) 004113B2 D9 E8 fld1 004113B4 EB 3A jmp Factorial+70h (4113F0h) float result = 1; 004113B6 D9 E8 fld1 004113B8 D9 5D F8 fstp dword ptr [result] for (float index=1;index=n;index++) 004113BB D9 E8 fld1 004113BD D9 5D EC fstp dword ptr [index] 004113C0 EB 0C jmp Factorial+4Eh (4113CEh) 004113C2 D9 45 EC fld dword ptr [index] 004113C5 DC 05 50 57 41 00 fadd qword ptr [__real@3ff0000000000000 (415750h)] 004113CB D9 5D EC fstp dword ptr [index] 004113CE DB 45 08 fild dword ptr [n] 004113D1 D9 5D EC fstp dword ptr [index] 004113D4 D9 45 EC fld dword ptr [index] 004113D7 D9 EE fldz 004113D9 DA E9 fucompp 004113DB DF E0 fnstsw ax 004113DD F6 C4 44 test ah,44h 004113E0 7B 0B jnp Factorial+6Dh (4113EDh) { result *= index; 004113E2 D9 45 F8 fld dword ptr [result] 004113E5 D8 4D EC fmul dword ptr [index] 004113E8 D9 5D F8 fstp dword ptr [result] } 004113EB EB D5 jmp Factorial+42h (4113C2h) return result; 004113ED D9 45 F8 fld dword ptr [result] } 004113F0 5F pop edi 004113F1 5E pop esi 004113F2 5B pop ebx 004113F3 8B E5 mov esp,ebp 004113F5 5D pop ebp 004113F6 C3 ret Would be a challenge for me to understand this code at every line even looking at C code. |
|||
|
05 Nov 2011, 19:50 |
|
|
emc 05 Nov 2011, 20:00
Can we see the C or C++ source? This code uses some x87 FPU (the floating point unit) instructions often prefixed with 'f'.
|
|||
|
05 Nov 2011, 20:00 |
|
|
Andy 05 Nov 2011, 20:05
Code: float Factorial(int n) { if (n<0) return -1; if (n<=1) return 1; float result = 1; for (float index=1;index=n;index++) { result *= index; } return result; } |
|||
|
05 Nov 2011, 20:05 |
|
|
emc 05 Nov 2011, 21:25
what happens if you work with 'double' instead 'float'?
|
|||
|
05 Nov 2011, 21:25 |
|
|
Andy 05 Nov 2011, 21:41
Seems just data type go from dword->qword
Code: double Factorial(int n) { 00411390 55 push ebp 00411391 8B EC mov ebp,esp 00411393 81 EC E0 00 00 00 sub esp,0E0h 00411399 53 push ebx 0041139A 56 push esi 0041139B 57 push edi 0041139C 8D BD 20 FF FF FF lea edi,[ebp-0E0h] 004113A2 B9 38 00 00 00 mov ecx,38h 004113A7 B8 CC CC CC CC mov eax,0CCCCCCCCh 004113AC F3 AB rep stos dword ptr es:[edi] if (n<0) return -1; 004113AE 83 7D 08 00 cmp dword ptr [n],0 004113B2 7D 08 jge Factorial+2Ch (4113BCh) 004113B4 DD 05 50 58 41 00 fld qword ptr [__real@bff0000000000000 (415850h)] 004113BA EB 44 jmp Factorial+70h (411400h) if (n<=1) return 1; 004113BC 83 7D 08 01 cmp dword ptr [n],1 004113C0 7F 04 jg Factorial+36h (4113C6h) 004113C2 D9 E8 fld1 004113C4 EB 3A jmp Factorial+70h (411400h) double result = 1; 004113C6 D9 E8 fld1 004113C8 DD 5D F4 fstp qword ptr [result] for (double index=1;index=n;index++) 004113CB D9 E8 fld1 004113CD DD 5D E4 fstp qword ptr [index] 004113D0 EB 0C jmp Factorial+4Eh (4113DEh) 004113D2 DD 45 E4 fld qword ptr [index] 004113D5 DC 05 40 58 41 00 fadd qword ptr [__real@3ff0000000000000 (415840h)] 004113DB DD 5D E4 fstp qword ptr [index] 004113DE DB 45 08 fild dword ptr [n] 004113E1 DD 5D E4 fstp qword ptr [index] 004113E4 DD 45 E4 fld qword ptr [index] 004113E7 D9 EE fldz 004113E9 DA E9 fucompp 004113EB DF E0 fnstsw ax 004113ED F6 C4 44 test ah,44h 004113F0 7B 0B jnp Factorial+6Dh (4113FDh) { result *= index; 004113F2 DD 45 F4 fld qword ptr [result] 004113F5 DC 4D E4 fmul qword ptr [index] 004113F8 DD 5D F4 fstp qword ptr [result] } 004113FB EB D5 jmp Factorial+42h (4113D2h) return result; 004113FD DD 45 F4 fld qword ptr [result] } 00411400 5F pop edi 00411401 5E pop esi 00411402 5B pop ebx 00411403 8B E5 mov esp,ebp 00411405 5D pop ebp 00411406 C3 ret |
|||
|
05 Nov 2011, 21:41 |
|
| Goto page 1, 2 Next < Last Thread | Next Thread > |
Forum Rules:
|