flat assembler
Message board for the users of flat assembler.

 Index > High Level Languages > factorial implementation Goto page 1, 2  Next
Author
Andy

Joined: 17 Oct 2011
Posts: 26
Andy
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
typedef

Joined: 25 Jul 2010
Posts: 2908
Location: 0x77760000
typedef
Factorial in C, JAVA, C++

Code:
```int factorial( int n )
{
if ( n <= 1 )
return 1;
else
return  n * factorial( n-1 );
}
```

In java, it's best to use Long for large numbers
03 Nov 2011, 20:50
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 18070
revolution
03 Nov 2011, 20:56
emc

Joined: 20 Aug 2011
Posts: 90
Location: France
emc
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

Joined: 04 Sep 2004
Posts: 1166
Location: Overflow
Matrix
revolution wrote:

that's zero

btw:
http://en.wikipedia.org/wiki/Factorial
03 Nov 2011, 22:26
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 18070
revolution
Matrix wrote:
revolution wrote:

that's zero

btw:
http://en.wikipedia.org/wiki/Factorial
04 Nov 2011, 02:35
Tyler

Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
Matrix wrote:
revolution wrote:

that's zero

btw:
http://en.wikipedia.org/wiki/Factorial
It's undefined, because the domain of the factorial function is only 0 and the natural numbers.
04 Nov 2011, 07:53
Matrix

Joined: 04 Sep 2004
Posts: 1166
Location: Overflow
Matrix
revolution wrote:
Matrix wrote:
revolution wrote:

that's zero

btw:
http://en.wikipedia.org/wiki/Factorial

been there, done that...
04 Nov 2011, 16:19
Andy

Joined: 17 Oct 2011
Posts: 26
Andy
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
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 18070
revolution
Andy: Any input above 12 give the wrong answer.
05 Nov 2011, 16:25
emc

Joined: 20 Aug 2011
Posts: 90
Location: France
emc
You have to be careful with limitations of your CPU: 13! > (2^32)-1
05 Nov 2011, 16:42
Andy

Joined: 17 Oct 2011
Posts: 26
Andy
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
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 18070
revolution
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.
Factorials get large very quickly. This is not primarily an assembly problem, it is more of a data definition problem. You will need to decide how large of a result you want to support, and how to represent that result. You can use registers to hold each part of the result or you can use memory. But no matter which you choose you still need an algorithm for doing the multiplication. This problem also arises if you use any HLL so don't think of it as just an assembly difficulty. For a hint search for 'bigint'. There are a lot of implementations already around.
05 Nov 2011, 18:07
emc

Joined: 20 Aug 2011
Posts: 90
Location: France
emc
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
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 18070
revolution
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

Joined: 17 Oct 2011
Posts: 26
Andy
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

Joined: 20 Aug 2011
Posts: 90
Location: France
emc
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

Joined: 17 Oct 2011
Posts: 26
Andy
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

Joined: 20 Aug 2011
Posts: 90
Location: France
emc
what happens if you work with 'double' instead 'float'?
05 Nov 2011, 21:25
Andy

Joined: 17 Oct 2011
Posts: 26
Andy
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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area
Goto page 1, 2  Next

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum