"logo.gif"  
Main
Read Online
Download PDF
Additional resources
Revision history
Known typos/bugs
Report a bug
License terms
About the author
"node515_1.gif" "node515_2.gif" "node515_3.gif"

5.4.2.6   Example:  the Collatz problem

Since the previous example may have left the reader with an impression that NestWhile is only good to produce inefficient solutions, we will now consider an example where it is perhaps the most appropriate command to use, both in the sense of elegance and efficiency.

The Collatz iteration is given by:    

"node515_4.gif"

It has been noticed that, regardless of the starting number <n>, the sequence of numbers that result from the repeated application of the function <c> will always eventually go to 1 (although this has not been rigorously proven). The most interesting  question is how the length of the Collatz sequence depends on the starting number.
      
We will be interested in implementing the Collatz sequence. First, consider the implementation from the "Computer science in
Mathematica" by Roman Maeder.

"node515_5.gif"

Look carefully at this implementation. The idea behind is beautiful: we recursively define the sequence by prepending a starting number to the sequence which starts with the transformed starting number. The separate base case guarantees a proper termination of the recursion.

For example:

"node515_6.gif"

"node515_7.gif"

Let us test the performance of this solution (I chose the powers of 2 since then the length of the Collatz sequence is known in advance and is equal to the power of 2)

"node515_8.gif"

"node515_9.gif"

We had to temporarily disable a limit on number of recursive calls (recursion depth) since  we will need the depth of recursion equal to the power of 2, in each case. The standard limit is 256. <Block> is used to make this modification local to its interior. We use <Block> when  we want some function or expression to temporarily "forget" the associated external (global) rules.

The inefficiency is (c.f. Wagner'96) due to modifications of large lists in place  at any iteration stage. This is necessary in this method, since the length of the sequence is not known an advance. The complexity of the program should be roughly proportional to N^3/2, where N is the length of the Collatz sequence.

Here is an alternative implementation using NestWhileList:    

"node515_10.gif"

Check:

"node515_11.gif"

"node515_12.gif"

We now test the performance :

"node515_13.gif"

"node515_14.gif"

This version does not communicate the idea and recursive nature of the Collatz sequence so clearly (which was probably the main motivation of Maeder. Besides, NestWhileList did not exist at the time), but the performance of this version is much better. This is because, the sequence (list) is created internally inside NestWhileList, and we don't have to modify large lists in place. The complexity of this program depends on details of internal implementation of NestWhileList, but could be even linear or log-linear, if c[x] is approximately constant-time (or log). We see that this problem is tailor-made for NestWhileList. It can be also seen by the conciseness of the code. Note that should we have only NestWhile at our disposal, this solution would not be possible - in this case we needed exactly NestWhileList.

Generally, many problems involving building large lists element by element and when the next element depends on the previous element(s), can be reformulated such that  they can be solved by NestWhileList. This is advantageous in
Mathematica programming, because one can think of NestWhileList as an efficient cousin of the standard procedural loops (which are usually inefficient in Mathematica). In the next case study of the Fibonacci numbers we will further dwell on this topic.

"node515_15.gif"

"node515_16.gif" "node515_17.gif" "node515_18.gif"

Created by Wolfram Mathematica 6.0  (05 February 2009) Valid XHTML 1.1!