flat assembler
Message board for the users of flat assembler.

Index > High Level Languages > factorial implementation

Goto page 1, 2  Next
Author
Thread Post new topic Reply to topic
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.
Post 03 Nov 2011, 20:35
View user's profile Send private message Reply with quote
typedef



Joined: 25 Jul 2010
Posts: 2913
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
Post 03 Nov 2011, 20:50
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17250
Location: In your JS exploiting you and your system
revolution
factorial(-1) gives the wrong answer.
Post 03 Nov 2011, 20:56
View user's profile Send private message Visit poster's website Reply with quote
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).
Post 03 Nov 2011, 22:07
View user's profile Send private message Reply with quote
Matrix



Joined: 04 Sep 2004
Posts: 1171
Location: Overflow
Matrix
revolution wrote:
factorial(-1) gives the wrong answer.

that's zero Wink

btw:
http://en.wikipedia.org/wiki/Factorial
Post 03 Nov 2011, 22:26
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17250
Location: In your JS exploiting you and your system
revolution
Matrix wrote:
revolution wrote:
factorial(-1) gives the wrong answer.

that's zero Wink

btw:
http://en.wikipedia.org/wiki/Factorial
Maybe you should read your link again! Wink
Post 04 Nov 2011, 02:35
View user's profile Send private message Visit poster's website Reply with quote
Tyler



Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
Matrix wrote:
revolution wrote:
factorial(-1) gives the wrong answer.

that's zero Wink

btw:
http://en.wikipedia.org/wiki/Factorial
It's undefined, because the domain of the factorial function is only 0 and the natural numbers.
Post 04 Nov 2011, 07:53
View user's profile Send private message Reply with quote
Matrix



Joined: 04 Sep 2004
Posts: 1171
Location: Overflow
Matrix
revolution wrote:
Matrix wrote:
revolution wrote:
factorial(-1) gives the wrong answer.

that's zero Wink

btw:
http://en.wikipedia.org/wiki/Factorial
Maybe you should read your link again! Wink


been there, done that...
Post 04 Nov 2011, 16:19
View user's profile Send private message Visit poster's website Reply with quote
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.
Post 05 Nov 2011, 16:18
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17250
Location: In your JS exploiting you and your system
revolution
Andy: Any input above 12 give the wrong answer. Wink
Post 05 Nov 2011, 16:25
View user's profile Send private message Visit poster's website Reply with quote
emc



Joined: 20 Aug 2011
Posts: 90
Location: France
emc
You have to be careful with limitations of your CPU: 13! > (2^32)-1
Post 05 Nov 2011, 16:42
View user's profile Send private message Reply with quote
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. Rolling Eyes
Post 05 Nov 2011, 17:28
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17250
Location: In your JS exploiting you and your system
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. Rolling Eyes
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.
Post 05 Nov 2011, 18:07
View user's profile Send private message Visit poster's website Reply with quote
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.
Post 05 Nov 2011, 18:09
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17250
Location: In your JS exploiting you and your system
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.
Post 05 Nov 2011, 18:13
View user's profile Send private message Visit poster's website Reply with quote
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. Shocked

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. Wink
Post 05 Nov 2011, 19:50
View user's profile Send private message Reply with quote
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'.
Post 05 Nov 2011, 20:00
View user's profile Send private message Reply with quote
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;
}    
Post 05 Nov 2011, 20:05
View user's profile Send private message Reply with quote
emc



Joined: 20 Aug 2011
Posts: 90
Location: France
emc
what happens if you work with 'double' instead 'float'?
Post 05 Nov 2011, 21:25
View user's profile Send private message Reply with quote
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     
Post 05 Nov 2011, 21:41
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2  Next

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.