Loops, Part 1

6/21/2007 12:48:40 PM

Loops, Part 1

I was hoping to post at a rate of once a day highlighting some area of NStatic, but I have found myself busy eliminating bugs. This is my first post on loops, but I will likely be expanding on it on the future.

One feature that is possibly unique to NStatic is the exact treatment of loops. Other products tend to examine loops a fixed number of iterations (usually just once) or simply punt on the issue.

Variables that are changed within loops are converted into expressions containing functions or closed forms of specially recognized functions. In this example, I will use the Fibonacci function. The Fibonacci function returns the nth element of the sequence

1,1,3,5,8,13,21,34,55,...

It's alternatively expressed as a recurrence relation:

Fib(0) = 1
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)

Below are two alternate implementations of the Fibonacci function, one which is recursive and another which is implemented imperatively via for loops.

I have also included below a goto version of the for loop to show that loops are handled in a general way and that I offer no special treatment for the for loop operator.

Below is the actual result at the breakpoint in the FibGoto function.

The values of both prev and sum are expressible in closed forms. The closed form of the Fibonacci function is well-known and is expressed as the sums of the powers of the golden ratio (and its difference from one), all divided by the square root of five. However, I did not hardcode the formula, since the Fibonacci function falls into a general class of second-order homogenous recurrence formulas.

The function FibTest computes the results of the earlier three implementations of the Fibonacci function. Note that I pass in a double to the recursive function, so it doesn't produce a closed form. (The closed form can probably be generated by taking the ceiling of the floating-point value before applying the function.)

The output for FibTest is shown below.

Comments

 

Navigation

Categories

About

Net Undocumented is a blog about the internals of .NET including Xamarin implementations. Other topics include managed and web languages (C#, C++, Javascript), computer science theory, software engineering and software entrepreneurship.

Social Media