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

[Anthony Cowley]

Wes, do you think you're going to publish something more detailed on your symbolic manipulation techniques? On the one hand, it's a bit hard to appreciate your software's full capabilities given only specific examples of what it can do, and on the other hand, it sounds like the work you've done would make for a very interesting read! Of course, you are doing this in a commercial rather than an academic setting, but I still hope you can share a more detailed treatment of your work with the public at some point.

[Wesner Moise]

There's probably a bug in my implementation. I initially had prev = 0, and replaced it with prev = 1, but it appears that the problem was due to a bad simplification.

[Denis]

Missing "2"...

[Wesner Moise]

I'll post more information in my blog over the next few weeks. I'll try to get something written every few days, if not every day.

A more detail paper may be some time off.