Fibonacci numbers (PIR)

From LiteratePrograms

Other implementations: ALGOL 68 | Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell | Hume | Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml | occam | Oz | Pascal | PIR | PostScript | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | T-SQL | Visual Basic .NET

In this article we show two ways of calculating fibonacci numbers in PIR.

<<fib.pir>>=
fib
fastfib
test

Recursive

This is a very simple recursive implementation. This will become slow on big numbers, because the numbers are recalculated for each recursion.

The PIR language gives us some help not available in regular assembly languages. The .param and .local macros creates named local registers, so that we don't need to care about register allocation, lifetime and other such details.

<<fib>>=
.sub fib
	.param int n
	.local int f1
	.local int f2
	if n <= 1 goto END
	n = n - 1
	f1 = fib(n)
	n = n - 1
	f2 = fib(n)
	n = f1 + f2
END:
	.return (n)
.end

Iterative

This is a faster, but also somewhat more complicated way to calculate fibonacci numbers. To avoid recalculation, the numbers are stored in local registers, for later reuse.

<<fastfib>>=
.sub ffib
	.param int n
	.local int f1
	.local int f2
	.local int tmp
	if n <= 1 goto END
	f1 = 0
	f2 = 1
	n = n - 1
LOOP:
	tmp = f2
	f2 = f1 + f2
	f1 = tmp
	n = n - 1
	if n > 0 goto LOOP
	n = f1
	if f1 > f2 goto END
	n = f2
END:
	.return (n)
.end

Test

If we run this test code, we can see that the iterative method is significantly faster then the recursive.

<<test>>=
.sub main :main
	.local int f
	.local int n
	n = 0
FIBLOOP:
	f = fib(n)
	print n
	print ": "
	print f
	print "\n"
	n = n + 1
	if n > 30 goto FIBEND
	goto FIBLOOP
FIBEND:
	n = 0
FFIBLOOP:
	f = ffib(n)
	print n
	print ": "
	print f
	print "\n"
	n = n + 1
	if n > 30 goto END
	goto FFIBLOOP
END:
.end

Download code