URGENT: Programming factorials

[1veedo]

I need help how do I create a program that calculates factorials?

[timo]

What exactly is your problem?

[bascule]

See the other thread for my Erlang implementation

[bascule]

Here's a Ebonicode implementation:

 

sup
{
 gimme fibo bitch
 a be 1 bitch
 b be 1 bitch
 putou a bitch
 putou b bitch
 fibo be fibo widout 2 bitch
 slongas (fibo bepimpin 0)
   c be a an b bitch
   a be b bitch
   b be c bitch
   putou b bitch
   dissin fibo bitch
 nomo
}

[Ndi]

Em, I'm not sure what you need,

 

if you need to calculate a factorial, the Windows Calc.exe has that function, just go scientific on his behind.

 

If you need a program that does that en-masse, say so and one will be sent to you.

 

If you want to calculate a factorial, the cleanest implementation is as-is:

 

function Factorial(Number: Integer): Integer;

var

i, Factor: integer;

begin

Factor := 1; // otherwise it's zero and you get 0

for i := 2 to Number do // no point in starting at 1 is there?

Factor := Factor * i; // factorial.

Result := Factor; // return.

end;

 

There are stinkier ways, but this is OK up to a decent 70-100. Huge numbers usually get precalculated by huge number manipulation routines, typically large memory machines that do recursion. They take more than a post.

 

-- Edit:

 

I noticed the challenge (now), but I'll pass the rare opportunity to do math with Java Call when total war is on.

[Rocket Man]

just run a loop. i'll assume you know what factorial means and basic how to program. there's no simple short cut to factorials.

btw, what's it for?

[Dak]

This seems suspiciously like a homework assignment

[1veedo]

function Factorial(Number: Integer): Integer;

var

i, Factor: integer;

begin

Factor := 1; // otherwise it's zero and you get 0

for i := 2 to Number do // no point in starting at 1 is there?

Factor := Factor * i; // factorial.

Result := Factor; // return.

end;

What language is this? It looks so... funny. Like a mix between C++ and one of the kiddy languages.

This seems suspiciously like a homework assignment

Yep. You caught me.

[Rocket Man]

do you need to take the factorials over a certain limit? if not, it's three lines of code.

[Aeternus]

What language is this? It looks so... funny. Like a mix between C++ and one of the kiddy languages.

 

It looks like Pascal but the comments aren't right so I'm going to assume Delphi.

[1veedo]

Ok well this thread was meant to be a joke from Atheist's factorial thread (homework help!) but I just recently started trying to learn assembly, 32bit [for now] on Linux (gcc/gas = At&t style, though this is arbitrary because if there's anything I've learned so far it's how to convert between intel and At&t).

 

There really aren't very many quality articles online for assembly, except introductory and hello world tutorials. I'd rather have a list of commands and what they do. I assume you should pick up a book or something which I plan to do next time I'm out but for now I've been learning by compiling dummy programs in C++ to see what the commands do.

 

So I have this program in C++

int main() {
   int number = 11;

   int xx = 0;
   int answer = 1;
   for(xx = number; xx > 1; xx -= 1)
   {
       answer *= xx;
   }
}

And in assembly it looks like this

	.file	"factorial.cpp"
.text
.align 2
.globl main
.type	main, @function
main:
.LFB2:
leal	4(%esp), %ecx
.LCFI0:
andl	$-16, %esp
pushl	-4(%ecx)
.LCFI1:
pushl	%ebp
.LCFI2:
movl	%esp, %ebp
.LCFI3:
pushl	%ecx
.LCFI4:
subl	$16, %esp
.LCFI5:
movl	$11, -16(%ebp)
movl	$0, -12(%ebp)
movl	$1, -8(%ebp)
movl	-16(%ebp), %eax
movl	%eax, -12(%ebp)
jmp	.L2
.L3:
movl	-8(%ebp), %eax
imull	-12(%ebp), %eax
movl	%eax, -8(%ebp)
subl	$1, -12(%ebp)
.L2:
cmpl	$1, -12(%ebp)
jg	.L3
movl	$0, %eax
addl	$16, %esp
popl	%ecx
popl	%ebp
leal	-4(%ecx), %esp
ret
.LFE2:
.size	main, .-main
.globl __gxx_personality_v0
.ident	"GCC: (GNU) 4.1.2 (Ubuntu 4.1.2-0ubuntu4)"
.section	.note.GNU-stack,"",@progbits

But what I cant do from here is assemble it. I don't know why -- as and then ld but it says "ld: warning: cannot find entry symbol _start; defaulting to 0000000008048074" and then "Segmentation fault (core dumped)." Presumably g++ didn't think it was necessary to give it _start and would have done something a little different then as/ld from here. But seeing as how I don't want all this compiled stuff -- just basic assembly, I've truncated it and added _start.

.text

   .global _start

_start:

leal	4(%esp), %ecx
andl	$-16, %esp
pushl	-4(%ecx)
pushl	%ebp
movl	%esp, %ebp
pushl	%ecx
subl	$16, %esp
movl	$11, -16(%ebp) #11=factorial, for now.  I'll figure out input latter
movl	$0, -12(%ebp)
movl	$1, -8(%ebp)
movl	-16(%ebp), %eax
movl	%eax, -12(%ebp)
jmp	.L2
.L3:
movl	-8(%ebp), %eax
imull	-12(%ebp), %eax
movl	%eax, -8(%ebp)
subl	$1, -12(%ebp)
.L2:
cmpl	$1, -12(%ebp)
jg	.L3
movl	$0, %eax
addl	$16, %esp
popl	%ecx
popl	%ebp
leal	-4(%ecx), %esp
#here we need output eg

#	movl	$???,%edx	# somehow get message length
#	movl	$ebp,%ecx	
#	movl	$1,%ebx		
#	movl	$4,%eax		
#	int	$0x80

#exit -- equivalent platform-specific exit message here, er [b]ret[/b] which for some reason segfaults, but this works fine.
movl	$0,%ebx
movl	$1,%eax	
int	$0x80

No seg faults or anything. I'm assuming at this point the program works just fine, I just need to generate output. When I add printf into the C++ program the assembly gets incredibly more complicated so I'm hopping I can just follow the hello world template. I don't really get memory operands though. And pop from what I remember extracts the last byte of data in a variable and I don't understand why that's there, either, so this program isn't really making sense (though I see how the for loop got compiled).

 

I'm about to try inline assembly -- copy + paste this in asm() and then call printf and see if it's working.

 

--edit. I uncommented the output section and replaced ??? w/ 8 because that's how long 11! is. But on ld it says

 

"factorial2.o: In function `_start':

(.text+0x55): undefined reference to `ebp'"

 

So I made it %ebp but here I just get no output at all.

 

So I don't really know how to get 11! out of this.

	#here we need output eg

movl	$8,%edx	# somehow get message length
movl	%ebp,%ecx	
movl	$1,%ebx		
movl	$4,%eax		
int	$0x80

I probably need Linux-specific advice here but of more immediate (and cross-platform) concern is where 11! is actually stored!

 

--Answered. Presumable it's in -8(%ebp). If you follow the algorithm it does one superfluous loop then starts multiplying. -12(%ebp) is XX and when it reaches one it doesn't go to L3 anymore. I don't know how the value is stored though -- the memory operands are negative!

[Aeternus]

Since you are only printing positive integers, you can quite easily convert that integer result to a base 10 string by having a large array/block predeclared (this is easier as you know you won't be able to do very large factorials, so there's a limit on the space you'll need to print it) and then using the following concept -

 

result = ?
temp = 0
string = ""
while result > 0 do
   temp = result % 10
   string = (char)(temp + 48) ++ string
   result = result / 10 // integer division
od

 

That's just some pseudocode but you can see the idea, take the last digit put it in the string (think ascii), then chop it off by division until you've got all the digits. Clearly it's more complicated than that in assembly, but you can easily declare a block of memory in the .data pr .bss section or whatever and an integer length field and do the same thing.

 

Then you can use the write syscall to print it out - http://docs.cs.up.ac.za/programming/asm/derick_tut/syscalls.html (useful list of syscalls) .

 

It's early in the morning so I can't really offer more than this atm but I might knock together a simple example later on.

[cosine]

I need help how do I create a program that calculates factorials?

Step 1. Write a research proposal that requires the calculation of factorials.

Step 2. Budget for a program that already calculates factorials.

Step 3. Get research grant.

Step 4. Purchase and install program.

 

4 lines of code, easy!

[Aeternus]

factorial.asm

.section .data
   answerText: .ascii "The answer = "
   answerTextLen: .byte 13

.section .bss
   .comm input 25 
   .comm answer 25 

.section .text
   .globl _start

_start:

   /* Read in */
   movl $0,%ebx
   movl $input,%ecx
   movl $25,%edx
   movl $3,%eax 
   int $0x80 /* Length comes back on eax */

   /* Convert to Integer - %eax = accum, %ecx = input+length, %ebx = input, %edx = digit  */
   movl $input, %ebx 
   movl %ebx, %ecx
   addl %eax, %ecx /* Move length into ecx */
   subl $2, %ecx

   movl $0, %eax
cl :
   cmp %ebx, %ecx
   jb cend /* Finished reading input? */
   movl $10, %edx
   mul %edx
   movb (%ebx), %dl
   subl $48, %edx
   addl %edx, %eax
   addl $1, %ebx
   jmp cl
cend :
   pushl %eax /* Push input onto stack */

   /* Write (syscall 4) answerText to stdout (fd 1) */
   movl $1,%ebx
   movl $answerText,%ecx
   movl $0, %edx
   movb (answerTextLen),%dl
   movl $4,%eax
   int $0x80

   /* Calculates 10 factorial */
   popl %eax /* Get Input back again */
   movl %eax, %ebx
   movl $1, %eax
   movl $0, %ecx
fl :
   cmp %ecx, %ebx
   jbe end /* Finish if neccessary */
   mul %ebx
   subl $1, %ebx
   jmp fl
end :

   /* Convert number to string - val = eax, 10 = ebx, temp = edx, answer = ecx  */
   movl $10, %ebx
   movl $answer, %ecx
   addl $25, %ecx
   /* Add New Line */
   subl $1, %ecx
   movb $10, (%ecx)
   cdq

loop :
   idiv %ebx /* eax = eax / ebx ; edx = eax % ebx */
   addl $48, %edx
   subl $1, %ecx
   movb %dl, (%ecx) 
   movl $0, %edx
   cmpl %eax, %edx
   jb loop


   /* Print Result */
   movl $answer,%edx
   addl $25, %edx
   subl %ecx, %edx
   movl $1,%ebx
   movl $4,%eax
   int $0x80

   /* Exit */
   movl $1,%eax
   movl $0,%ebx
   int $0x80

 

Makefile

factorial : factorial.o
ld -s -o factorial factorial.o

factorial.o : factorial.asm
as factorial.asm -o factorial.o

 

Something like that is what I was suggesting. You can see in the input and output sections, the conversions from and to integers and strings.

[1veedo]

Lol your program makes no sense. I do see the add/subl $48 lines for conversion which is what I was trying to do (0x30 = 48 in decimal -- ascii 1 is 0x30).

 

I made a temporary hack sense echo $? prints the exit status -- just make the exit status the answer. -8(%ebp) was just 0 though . But that's ok cause I wrote a new program. I've also figured out how stack works through trial and error.

 

pop 1 -- num args

pop 2 -- program name for some odd reason??? It's counted as an argument -- if no arguments are passed then pop the first time returns 1, not 0.

pop 3 -- first argument

pop 4 -- second argument

etc

 

My program couldn't do anything above 5 (error codes don't go up to 6!) nor could it take input, although I could input indirectly from the top stack (eg num of arguments if I pass 2 arguments then it calculates 3!).

 

But thanks to your code I added the input and output functions, leaving everything else alone.

.section .data
   answerText: .ascii "The answer = "
   answerTextLen: .byte 13

.section .bss
   .comm input 25
   .comm answer 25 

.text

   .global _start
   .global multiply

_start:
   /* Read in */
   movl $0,%ebx
   movl $input,%ecx
   movl $25,%edx
   movl $3,%eax 
   int $0x80 /* Length comes back on eax */

   /* Convert to Integer - %eax = accum, %ecx = input+length, %ebx = input, %edx = digit  */
   movl $input, %ebx 
   movl %ebx, %ecx
   addl %eax, %ecx /* Move length into ecx */
   subl $2, %ecx

   movl $0, %eax
cl :
   cmp %ebx, %ecx
   jb cend /* Finished reading input? */
   movl $10, %edx
   mul %edx
   movb (%ebx), %dl
   subl $48, %edx
   addl %edx, %eax
   addl $1, %ebx
   jmp cl
cend :
pushl	%eax

/* Write (syscall 4) answerText to stdout (fd 1) */
   movl $1,%ebx
   movl $answerText,%ecx
   movl $0, %edx
   movb (answerTextLen),%dl
   movl $4,%eax
   int $0x80

call	multiply

   movl $10, %ebx
   movl $answer, %ecx
   pushl %eax
   addl $25, %ecx
   /* Add New Line */
   subl $1, %ecx
   movb $10, (%ecx)
   cdq



loop :
   idiv %ebx /* eax = eax / ebx ; edx = eax % ebx */
   addl $48, %edx
   subl $1, %ecx
   movb %dl, (%ecx) 
   movl $0, %edx
   cmpl %eax, %edx
   jb loop


   /* Print Result */
   movl $answer,%edx
   addl $25, %edx
   subl %ecx, %edx
   movl $1,%ebx
   movl $4,%eax
   int $0x80

movl	$0, %ebx
movl	$1, %eax
int	$0x80

   .type multiply,@function
multiply: #does up to 12 factorial

pushl	%ebp	#place holder so %eax is always stored 8(%esp)
movl	%esp, %ebp
movl	8(%ebp), %eax

cmpl	$1, %eax
je	done

decl	%eax
pushl	%eax
call	multiply
movl	8(%ebp), %ebx
imull	%ebx, %eax

done:
movl	%ebp, %esp
popl	%ebp
ret

Btw can java do inline assembly like C++? I'm about to make an entry into Atheist's contest with this . Just stick it in Math.java right?

[Aeternus]

Lol your program makes no sense. I do see the add/subl $48 lines for conversion which is what I was trying to do (0x30 = 48 in decimal -- ascii 1 is 0x30).

 

I made a temporary hack sense echo $? prints the exit status -- just make the exit status the answer. -8(%ebp) was just 0 though . But that's ok cause I wrote a new program. I've also figured out how stack works through trial and error.

 

pop 1 -- num args

pop 2 -- program name for some odd reason??? It's counted as an argument -- if no arguments are passed then pop the first time returns 1, not 0.

pop 3 -- first argument

pop 4 -- second argument

etc

 

My program couldn't do anything above 5 (error codes don't go up to 6!) nor could it take input, although I could input indirectly from the top stack (eg num of arguments if I pass 2 arguments then it calculates 3!).

 

But thanks to your code I added the input and output functions, leaving everything else alone.

.section .data
   answerText: .ascii "The answer = "
   answerTextLen: .byte 13

.section .bss
   .comm input 25
   .comm answer 25 

.text

   .global _start
   .global multiply

_start:
   /* Read in */
   movl $0,%ebx
   movl $input,%ecx
   movl $25,%edx
   movl $3,%eax 
   int $0x80 /* Length comes back on eax */

   /* Convert to Integer - %eax = accum, %ecx = input+length, %ebx = input, %edx = digit  */
   movl $input, %ebx 
   movl %ebx, %ecx
   addl %eax, %ecx /* Move length into ecx */
   subl $2, %ecx

   movl $0, %eax
cl :
   cmp %ebx, %ecx
   jb cend /* Finished reading input? */
   movl $10, %edx
   mul %edx
   movb (%ebx), %dl
   subl $48, %edx
   addl %edx, %eax
   addl $1, %ebx
   jmp cl
cend :
pushl	%eax

/* Write (syscall 4) answerText to stdout (fd 1) */
   movl $1,%ebx
   movl $answerText,%ecx
   movl $0, %edx
   movb (answerTextLen),%dl
   movl $4,%eax
   int $0x80

call	multiply

   movl $10, %ebx
   movl $answer, %ecx
   pushl %eax
   addl $25, %ecx
   /* Add New Line */
   subl $1, %ecx
   movb $10, (%ecx)
   cdq



loop :
   idiv %ebx /* eax = eax / ebx ; edx = eax % ebx */
   addl $48, %edx
   subl $1, %ecx
   movb %dl, (%ecx) 
   movl $0, %edx
   cmpl %eax, %edx
   jb loop


   /* Print Result */
   movl $answer,%edx
   addl $25, %edx
   subl %ecx, %edx
   movl $1,%ebx
   movl $4,%eax
   int $0x80

movl	$0, %ebx
movl	$1, %eax
int	$0x80

   .type multiply,@function
multiply: #does up to 12 factorial

pushl	%ebp	#place holder so %eax is always stored 8(%esp)
movl	%esp, %ebp
movl	8(%ebp), %eax

cmpl	$1, %eax
je	done

decl	%eax
pushl	%eax
call	multiply
movl	8(%ebp), %ebx
imull	%ebx, %eax

done:
movl	%ebp, %esp
popl	%ebp
ret

Btw can java do inline assembly like C++? I'm about to make an entry into Atheist's contest with this . Just stick it in Math.java right?

 

Heh, makes no sense? It should work as advertised, although the lack of registers in x86 assembly becomes a pain :\ It just does what I suggested above for output and for input it just takes what's been read in and converts each character from input to an integer and adds it to the input integer, making sure to times the input by 10 at each stage so it is of the right order (ie 567 goes 5 -> 50 + 6 -> 560 + 7 etc). The reason for this is so that it can do more than 9! (multiple digits). It could have been commented better I admit but I didn't spend that long on it

 

Sure, you can take the argument in from the command line as well, I just chose to read it in from stdin (although I didn't bother to do any checks so random data will probably kill it).

 

If you have a question about something in particular, feel free to ask.

 

Java doesn't accept inline assembly afaik since it compiles to byte code so it can run on any machine. Also I think the idea behind Atheists challenge (as I think he suggested in the thread) was to be able to calculate factorials larger than would fit in a single integer or long although that is only the impression I got.

[bascule]

I thought this was hilarious:

 

http://www.willamette.edu/~fruehr/haskell/evolution.html

 

Also note my previous Erlang solution was suboptimal as it didn't use a proper tail call.

 

Here's an improved one:

 

fact(N) -> fact(N, 1). fact(1, Acc) -> Acc; fact(N, Acc) -> fact(N - 1, N * Acc).