techInterview Discussion

A part of answers to technical interview questions.

Your host: Michael Pryor

N Factorial in Assembly


I just went to an interview and there is a question I don't know how to solve. They ask me to write a function to do


in assemble language. Does anyone know? thanks!
Raymond Send private email
Friday, June 16, 2006
.type factorial, @function


 pushl %ebp
 movl %esp, %ebp
 movl 8(%ebp), %eax
 cmpl $1, %eax
 je end_factorial
 decl %eax
 pushl %eax
 call factorial
 movl 8(%ebp), %ebx
 imull %ebx, %eax
  movl %ebp, %esp
  popl %ebp
Sajid Send private email
Sunday, June 18, 2006
I _hate_ the recursive solution for this. It is totally unnecessary and a stilted and contrived example of recursion.

nfact: ;call w/ eax=n, returns edx:eax w/ n!
 mov ecx, eax
 mov edx, 0
 mov eax, 1
 mul ecx
 loop nfactloop
Lou Zher Send private email
Saturday, July 01, 2006
If you are ever asked the question "How would you code factorial?" you are really being asked "How would you code factorial faster than doing a recursive loop?"  Iteration is one way, but the right answer (because there are only going to be ~13 possible inputs, depending on your architecture, before you blow up the register you need to save the answer in) is "implement it via a lookup table".

Here's one way

; Factorial code using lookup table
; Inputs: n in AX, valid for 0<=n<=12.  Input unchanged
; Outputs: n! in BX
; Checking n valid responsibility of calling code.
; Table: contains precalculated lookup table for 0! through 12!

Jmp Start;  Skip past the lookup table
Db 1; 0! = 1
Db 1; 1! = 1
Db 2; Continuing lookup table of precalculated values
Db 6;
Db 24;
Db 120;
Db 720;
Db 5040;
Db 40320;
Db 362880;
Db 3628800;
Db 39916800;
Db 479001600; 12! = 479001600.  We'll stop here, 13! and higher overflow the register on the target chip

MOV BX, Start; point BX to start of table
ADD BX, AX, BX; index into proper place in table
MOV BX, [BX]; BX now contains n!

Alright, we're done.  Its been ~6 years since I had to touch MASM so my syntax might be a weee bit on the rusty side.  A quick variation to make on this to make points with the interviewer is to bounds-test AX before you do any work with it.
Patrick McKenzie Send private email
Monday, July 31, 2006

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz