A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor
.type factorial, @function
movl %esp, %ebp
movl 8(%ebp), %eax
cmpl $1, %eax
movl 8(%ebp), %ebx
imull %ebx, %eax
movl %ebp, %esp
Sunday, June 18, 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 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.
Monday, July 31, 2006
This topic is archived. No further replies will be accepted.Other recent topics
Powered by FogBugz