techInterview Discussion

Answers to technical interview questions. A part of TechInterview.org

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

N Factorial in Assembly

Hello

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

N!

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

factorial:

 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
 
 end_factorial:
  movl %ebp, %esp
  popl %ebp
  ret
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
nfactloop:
 mul ecx
 loop nfactloop
 ret
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
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

Start:
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