ThinkGeek - Cool Stuff for Geeks and Technophiles

Monday, September 8, 2008

PIR factorials - a simple algorithm comparison

Here are a couple algorithms to calculate factorials in PIR.

The first is a straightforward procedural algorithm:


.sub factor
.param int n
.local int total

total = n
if n == 1 goto done

loop1:
dec n
total = total * n
if n > 1 goto loop1

done:
.return (total)
.end


The second is recursive:


.sub factor
.param int n
.local int total
.local int subfact
.local int subval

total = n
if n == 1 goto done

loop1:
subval = n - 1
subfact = factor (subval)
total = n * subfact

done:
.return (total)
.end


I've tried to keep them as close to identical as possible, with the only difference being the instructions between the loop1 and done labels (plus the extra variables needed by the recursion).

This allows for a simple comparison of the two algorithms. Just drop each into this program:


.sub main :main
.local int n
.local int fact
.local num start
.local num stop
.local num ellapsed_time

n = 1
print "Factorial: Recursive\n"
start = time
loop0:
fact = factor (n)
printout (n, fact)
inc n
if n <= 12 goto loop0
stop = time
ellapsed_time = stop - start
print ellapsed_time
print " seconds\n\n"
.end

.sub printout
.param int n
.param int fact

print n
print "! = "
print fact
print "\n"
.end


In twelve trials on my AMD 3100+ machine, the procedural code averaged 1.816 milliseconds, and the recursive code averaged 13.178 milliseconds. This included outliers of 142.376 for the recursive and 7.430 for the procedural. I'm guessing they were interrupted by other processes. Ignoring these outliers, the procedural code averaged 1.305 and the recursive 1.433 milliseconds. Not a huge difference, but I only did 12 calculations per trial.

Labels: , , ,