web analytics

Spotlight: Looping through Fibonacci with DoWhile

The purpose of this Spotlight is to demonstrate the use of the DoWhile module to loop within a Composable DataFlow.

Our scenario:

The Fibonacci sequence is one of the best-known series in Mathematics.  The series is composed of Fibonacci numbers, where the sum of each consecutive pair of numbers becomes the next number in the series (a + b = c).  Since the addition of a new term yields a fresh consecutive pair to sum (b + c = d), this series is infinite (c + d = e, …).

More than a mere mathematical parlor trick, Fibonacci appears in designs both natural and man-made.  Patterns described (or approximated) by Fibonacci are found in mathematics, computer algorithms, spiral structures from organisms to galaxies, architecture and design, the growth of plants and populations… even city planners can use Fibonacci in planning expansion of a power grid.  I actually worked with a team that used Fibonacci numbers as a non-linear ranking of tasks in Scrum meetings.

Since Fibonacci is so useful in so many situations, how could we use a Composable DataFlow to generate this limitless list – and how do we constrain it so it doesn’t run forever?

Our solution:

At any given point in building out the Fibonacci series, we really only need access to three numbers: the two most recent, and the new number in the series that they create.  Of course, we also need to be able to store the results as the series grows.

This is an iterative process, so we need a way to repetitively grab the two numbers to add, add them, add a new number to the series, and then start over again with the next “most recent pair”.

Lastly, since series this is theoretically infinite, we need to decide how to practically terminate a loop of otherwise undefined length.

Functionally, that means we need a minimum of six items:  The start and endpoint of the loop, the three relevant values of the current iteration, and a way to identify the next pair. 

In a Composable DataFlow, that means we need six modules and some thoughtful ways to link them together.  If we wanted to expand the functionality, like inserting a value threshold, that would add another module (and we will do such things in a future exercise).

Let’s create a new DataFlow and think our way through the modules we want.

Starting the Loop:

Starting at the top, we need a way to iterate indefinitely.  

As we saw in a prior Spotlight post, Spotlight: Looping with ForEach, For loops are great for iterating, but each loop has the number of iterations defined by the input list.  Six items in the list means six trips through the loop.

For our task, the stopping point will be defined by conditions within the loop, not by list length.  We need an iterator that will continue until conditions change.

That’s a textbook use case for a DoWhile module.

The DoWhile module
Module Details for the DoWhile module

Like the ForEach module in the previously-mentioned blog post, we have InitialPassedOutputs and MaxIterations as inputs, but we do not have a List input.

For our use case, this is all we need. 

The Fibonacci series commonly starts with 0 and 1 (i.e., [0, 1]) as the seed values, although there are those who use the next pair (0+1=1, so the next pair is [1, 1]).  I have read that Fibonacci himself actually used the pair after that (1+1=2, so [1, 2] is the next pair) as his starting point.

We will choose [0,1] as our seed values.  We will explore adding some user-driven flexibility, and the implications on F(n) (the Fibonacci series index) in a future post on Nested DataFlows.

We will also set MaxIterations to… 6 to start with, so that we can get some cycles in for testing.

The DoWhile module, with our chosen starter values

Getting the Three Values:

The outputs passed from the DoWhile will contain a pair of values in a list/array structure.  To parse those out individually, we can use the Array Indexer module.

The Array Indexer module
Module Details for the Array Indexer module

We can connect the PassedOutputs output of the DoWhile to the Array input of an Array Indexer.  We haven’t set up the endpoint of the loop yet, so I’m not concerned with iterations at this point.

Index 0 means that we will get the first value in the passed array.     

When we run this, we can see that [0,1] is indeed the expected output and 0 the parsed value.

Starting to parse the Fibonacci seed pair

Note: If your line doesn’t look like mine and you want to change it, take a look at our DYK blog post on Changing Wire Type.

To get the second value in the pair, we can add a second Array Indexer, set its Index to 1, and connect the same output from the DoWhile to the new Array Indexer’s Array input.

Finished parsing the Fibonacci seed pair

Just as a double-check that we aren’t simply grabbing the index numbers, or some other defaults, we can set test values to something else, like … 7 and 5.  We’ll replace the [0,1] later.

Checking seed pair parsing with different values

We can see [7,5] as the passed output and the 7 and 5 being parsed correctly, respectively.

To get our third value, we need to derive it by adding the other two together.

Here we can use the Calculator module.

The Calculator module
Module Details for the Calculator module

We add the Calculator module and simply connect the Value outputs of our Array Indexers to the Param1 and Param2 inputs of the Calculator.  Since we are summing, we can leave the Operator as “+”.  I am also going to set the default input values in the Calculator to 0.  That way, if there were an error, we have a known, expected value to test for that we wouldn’t get if the process was working (there is no 0 + 0 = 0 in Fibonacci).  Not that I expect an error, but old programmer habits die hard.

Leaving our test values of [7,5] in place and running again, we can see the 7, 5, and 12 as the correct outputs from their respective modules.

Creating the third value

To keep track of the pieces in our DataFlow so far, let’s rename the modules of the three values as Val1, Val2, and Val3, as appropriate.

Renaming modules to Val1, Val2, Val3

Setting the “Next Pair”:

Now that we have our three values identified, it’s a simple step to set up the “next pair”

Let’s add an Array Builder module.

The Array Builder module
Module Details for the Array Builder module

Now we connect the Value outputs from our data sources.

Many people would do this from the top down (Val3, then Val2), so I will do that to show the ramifications and how we can correct it without rewiring.

Showing connection order of multiple inputs

If we hover over the Array Builder’s InputCollection input, we see that the connection to Val3 has a 0, and Val2 shows a 1.  If we were just adding two terms, it wouldn’t matter (a + b = b + a).  But, in our case, we’re not dealing with the commutative property of addition.  We need an array where the terms are in a specific order.

No need to worry.  If you ever attach in a different order than you intended, or need, you can simply shift+right-click on the relevant input port.  That pops up a list of the attachments, in the order that they will be handled.  Better still, the list items are movable.  Here, you can see that I have started to click-and-drag the lower list item (Val2) and move it up.

Rearranging the order of multiple inputs

When rearranged, a click on the input shows that the index numbers have flipped to 1 and 0.

Showing rearranged connection order of multiple inputs

Let’s rename the Array Builder to Next Pair and run the DataFlow.

Setting all values with our test seed pair

Here we can see that our test values [7,5] get parsed into 7 and 5, summed to 12, and our second term and new term (Val2, Val3) are correctly ordered [5, 12] as our Next Pair.

Restoring to our actual Fibonacci seed values of [0,1], we see we can finish the first round of processing as expected.

Setting all values with our Fibonacci seed pair

Now, [0,1] becomes 0 and 1, summed to 1, and [1,1] is the Next Pair.

Making the Loop Endpoint:

At this point, we have five of the six functions that we need in place.

What’s left?  We need to make the loop, loop.

In the ForEach post, we discussed two types of endpoints, Loop Terminator and Accumulator.

Loop Terminator has Trigger and Break inputs and LoopComplete output to control and signal the end of the loop.

Accumulator adds an Input input and Result output, to allow for storing values on completed iterations and passing them out upon completion.

We, however also need to be able to pass values back into the next iteration of the loop.

For that, we need a Passing Accumulator module.

The Passing Accumulator module
Module Details for the Passing Accumulator module

Here, we see the addition of a PassedLoopValues input (what will be passed back), as well as FinalLoopValues (what the next passing value would be when the loop terminated).

Let’s add a Passing Accumulator and some thoughtful wiring to tie this all together.

For any loop, we tie the iterator module’s LoopComplete output to the endpoint module’s Trigger input, so let’s start there.

Connecting the start and end of the loop

The whole purpose of the Next Pair is to pass it back to the next iteration, so let’s connect that ArrayOutput output to the Passing Accumulator’s PassedLoopValues input.

Connecting the Next Pair to be passed in the loop

Hmmm…what should our input be?

Well, as we loop, we will want to do the same operation each time, so we should add one value per iteration.  I’m not in favor of seeding our otherwise initially-empty Result list, as it breaks the simplicity of the loop.  We also don’t need to.

If we simply make Val1 our input, and pass [Val2, Val3] to the next iteration, we will end up with one value in our Result list for every iteration of the loop.

So, let’s do that.  That gives us:

Connecting the Val1 as Input to our Result list

As a reminder, our goal stated at the outset was to be able to construct a Fibonacci series.

If we’ve done this all correctly, we’re done building.  But any process needs testing, so we’ll do that next.

Testing:

I always like to Save before running anything, so I’ll do that here.

I’m going to call my DataFlow “Fibonacci Loop” and add a Description.  The easily memorable name will come in handy in a later blog post…

Naming and Describing the DataFlow to save

Next, I want to be able to step through the early stages of the loop to see what is happening, so I’ll switch from Run mode to Debug mode.

Selecting Debug Mode
Debug Mode selected

Now, when I press Debug, I get the stepping controls at the top of the canvas and the blue color is drained out of the outputs and connectors until those tasks have been activated and completed.

Debug Mode initiated

Press the play button seven times. That will allow each of our six modules to run once (the first click initiates the debug run and sets the first module to be ready to run, plus one click to run each module from that point forward), so that we can examine the first cycle of the loop to completion.

Reviewing the first iteration through the loop

Now, let’s use View Results from the outputs shown.

DoWhile’s PassedOutputs, LoopComplete, and Current Iteration results show that the seed pair list ([0,1]) is being passed to Val1 and Val2, the Boolean false is being passed to the Passing Accumulator’s Trigger, and we are on CurrentIteration 1.

Val1, Val2, and Val3 are 0, 1, 1 as expected, and Next Pair’s ArrayOutput is set to [1,1].

For our Passing Accumulator, DoWhile’s LoopComplete false is passed into Trigger, Val1’s 0 is passed into Input to start our ResultList, and Next Pair’s [1,1] is passed into PassedLoopValues.

The Passing Accumulator’s Result is not yet available because the loop is not yet finished.  This is a safety measure so that no results are passed out of the module until the finished results are ready to go.

All good so far.

But here’s where the rubber meets the road.

Pressing the debugger’s play button six more times has us cycle the six-module loop one more time.

Reviewing the second iteration through the loop

We can see that this cycle’s starting pair is [1,1], successfully passed from last cycle’s Next Pair.

CurrentIteration 2 uses LoopComplete to tell the Trigger that we’re still not done, 1 + 1 = 2, and the Next Pair is [1,2].  Val1 adds 1 to our accumulating ResultList.

Six more clicks for the debugger and we complete the third cycle.

Reviewing the third iteration through the loop

CurrentIteration 3 starts with [1,2], we’re still not done, 1 + 2 = 3, 1 gets added to the ResultList, and [2,3] is the Next Pair.

This could go on, literally, forever.  How will it know when to stop?  Well, remember that DoWhile’s MaxIterations is set to 6.

We could step through each iteration, but let’s jump to the end by hitting the debugger’s Continue button (third of the three).

Now we can see all of the outputs at their final stage.

Reviewing the final iteration through the loop

We can see that our sixth and final iteration passed true to the Trigger, signalling that this is the last pass.

Our starting pair of [5,8] passed 5 in as the sixth and final term in our Result list. 5 + 8 = 13, and [8,13] is ready to go as our Next Pair.

Our Passing Accumulator now shows that the loop is complete (LoopComplete is true).  With the task finished, we can now see both the Result list of six items, [0,1,1,2,3,5], made from the six iterations, and also what the next two terms would be, [8,13], as the FinalLoopValues to passed to the next cycle, if there were one.

One final test.  Let’s set the MaxIterations to something larger, like… 12.

We don’t need to step through, as the first six steps will be exactly the same.  But let’s check out where we end up.  Switch back to Run mode and click Run.

Reviewing a 12-cycle loop

We can see that the 12th cycle starts with [89,144], and 89 + 144 = 233. 89 is at the end of our 12-item list, [0,1,1,2,3,5,8,13,21,34,55,89], and [144,233] would be next up.

The key takeaway: we have shown that this list will run until a stopping condition is met and we currently have the option to control the loop’s termination with a simple parameter of how many times we want it to run.

Success!

Wrap up:

We have built this DataFlow as a standalone, but to truly make use of the power of this functionality, we would want to be able to encapsulate this as a functional block in our library of modules, to be called upon whenever needed.  We would also want to expose control of inputs and outputs to the external user, without them needing to see how the sausage is made inside our loop.

Our next Spotlight post on Nested DataFlows will add another loop termination control method (using the Break input of Passing Accumulator), discuss how to handle a potential off-by-one error in assigning F(n) (hint: Fibonacci numbers with [0,1] start at F(0), but iterations start at 1), and show how to customize inputs and outputs when authoring your very own module!

Later, you’ll see how to utilize both DoWhile and ForEach looping techniques (and Nested DataFlows) in an upcoming Project Lab in our NASDAQ API series.  I will link here when that Lab is available.

Until next time…

Enjoy!