# C++ Math and Fun

**Zeeshan Amjad**on

**August 19th, 2004**

### Introduction

Some people think math is boring, and you have to have something extra in your brain to understand it. In fact, not all branches of mathematics are boring and very tough for a person who does not have a math background. Number theory is one such branch of math that may be very attractive to a normal person without learning lots of stuff.

Number theory is the study the properties of integers; in other words, whole numbers. This is perhaps the oldest branch of mathematics and is also called Queen of Mathematics by the Prince of Mathematics, Gauss, because lots of branches of mathematics are developed to solve the problems of number theory. In fact, there is no need to have lots of math background to start the study of it. To see the beauty of it, however, you have to be familiar with different branches of math. In fact, in the past, number theory was considered pure mathematics because there is no application of it outside the world of math. But, there are lots of applications of it available now, such as cryptography, random number generator, error detection, security, and so on. Still, a fascinating thing about number theory is that there are still lots of unsolveds problem in it. It might be possible that fewer branches of math will be evolved and a few more techniques will be developed to solve those problems.

The whole study of number theory is the beautiful proof of different problems, and solves more complex problems on the basis of existing proofs. It is interesting to note that if any conjecture or assumption is not proved in number theory, it still may have applications in real life. For example, the well-known cryptography algorithm RSA is based on the assumption that it is not easy to find the prime factor of a very large number if it is a multiple of two or more huge primes.

Here, we are trying to implement one very easy, but interesting problem, the Collatz problem, by using different programming techniques. The most interesting thing about this problem is that the algorithm of this problem is not classified for all possible input until now, although it is very simple to state it. This problem is also known as the hailstone problem, 3n+1 problem, Hasse's algorithm, Kakutani's algorithm, syracuse problem, or the Thwaites Conjecture or Ulam's problem. This problem was posed by L. Collatz in 1937.

In ther words, it is a very simple problem. Take any number as an input, and divide it by 2 if the number is even, or multiply by 3 and add 1 if the number is odd. The conjecture is that, no matter which no you take as an input, you will come to 1. However, this is still an open problem and no one can prove it until it is true for all values of n, although it has been checked for quite large numbers through a computer. This might be a challenging task for those who want to solve open problems and gain popularity.

Total the numbers of elements in the sequence until it reaches 1, including input number and 1; this is called the cycle of the sequence of that given input number. For example, if user input 5, the sequence will be something like this:

5 16 8 4 2 1

The cycle of this sequence is 6. This sequence is also called the hailstone sequence.

The algorithm to generate this sequence is very simple.

### Algorithm A (Algorithm for 3n+1 sequence)

A1. [Input n] A2. [Termination] If n = 1 then exit A3. [Check number] If n is even then n := n / 2 else n := n * 3 + 1 A4. [Next number] Go to A2.

Okay, now let's come to the implementation side of this algorithm. Here, I tried to do some fun with this simple algorithm and tried to implement it in different programming styles.

### No Structured Programming

This is perhaps the first technique of programming the computer, without any procedure or anything else. The most problematic thing about this style is its management and reusability because there is almost no abstraction layer in this style of programming. Therefore, it is quite difficult to handle a large-scale program using this technique.

#include <iostream> using std::cout; using std::endl; int main(int argc, char* argv[]) { int iCount = 1; int iNo = 22; int iTemp = iNo; while (iTemp != 1) { // if number is even if (iTemp % 2 == 0) { iTemp /= 2; } // if number is odd else { iTemp = iTemp * 3 + 1; } ++iCount; } cout << "Cycle length of " << iNo << " is " << iCount << endl; return 0; }

### Structured Programming

Break down the program into small modules (functions), so it will become more manageable and more reusable than the non-structured version. Logically, one function of the program should do the unit work of the algorithm, but it is quite subjective to describe the unit work. This programming style will increase the abstraction level by dividing the problem into small pieces and solving those pieces one by one.

#include <iostream> using std::cout; using std::endl; int NextTerm(int iNo) { // if number is even if (iNo % 2 == 0) { iNo /= 2; } // if number is odd else { iNo = iNo * 3 + 1; } return iNo; } int CalculateCycle(int iNo) { int iCount = 1; while (iNo != 1) { iNo = NextTerm(iNo); ++iCount; } return iCount; } int main(int argc, char* argv[]) { const int iNo = 22; cout << "Cycle length of " << iNo << " is " << CalculateCycle(iNo) << endl; return 0; }

### Recursive Programming

Do you know what the meaning of GNU is? GNU stands for "GNU's Not Unix." Doesn't that look strange? The name itself appears in the acronym, and when you try to expand it, GNU will again appear in acronym. This is a simple example of recursion. In other words, a more typical definition may be something like this: "Recursion is a way to specify a process by repeating a means of itself." In programming language context, recursion means a function that calls itself. Typical examples of recursion are factorial, Fibonacci number, Tower of Hanoi, and so forth.

#include <iostream> using std::cout; using std::endl; int CalculateCycle(int iNo, int iCount) { ++iCount; if (iNo == 1) { return iCount; } else { if (iNo % 2 == 0) { iNo /= 2; iCount = CalculateCycle(iNo, iCount); } else { iNo = iNo * 3+ 1; iCount = CalculateCycle(iNo, iCount); } } return iCount; } int main(int argc, char* argv[]) { const int iNo = 22; cout << "Cycle length of " << iNo << " is = " << CalculateCycle(iNo, 0) << endl; return 0; }

### Object-Oriented Programming

Object-oriented programming is a programming style in which you make classes and create instances of those classes, called objects. Technically, a class is a prototype that defines the variables and methods of one kind. This problem is very small, so that you can not get the full advantage of object-oriented programming. This program is technically object based but not object oriented.

#include <iostream> using std::cout; using std::endl; class Collatz { private: int m_iCycle; int m_iNo; int NextTerm(int p_iNo); public: Collatz(int p_iNo = 0); void CalculateCycle(); int GetCycle() const; }; Collatz::Collatz(int p_iNo) : m_iNo(p_iNo), m_iCycle(1) { if (m_iNo < 1) throw std::out_of_range("Number should be greater than 0"); } int Collatz::NextTerm(int p_iNo) { // if number is even if (p_iNo % 2 == 0) { p_iNo /= 2; } // if number is odd else { p_iNo = p_iNo * 3 + 1; } return p_iNo; } void Collatz::CalculateCycle() { while (m_iNo != 1) { m_iNo = NextTerm(m_iNo); ++m_iCycle; } } int Collatz::GetCycle() const { return m_iCycle; } int main(int argc, char* argv[]) { const int iNo = 22; try { Collatz objCollatz(iNo); objCollatz.CalculateCycle(); cout << "Cycle length of " << iNo << " is " << objCollatz.GetCycle() << endl; } catch(std::out_of_range& ex) { cout << ex.what() << endl; } return 0; }

### Generic Programming

Generic means general or common. Technically, generic programming refers to a program written in such a way that it should work independent of data type. A generic program should work on all data types that satisfy the required concepts use in the program. In C++, a template is used for generic programming.

#include <iostream> using std::cout; using std::endl; template <typename T> class Collatz { private: T m_iCycle; T m_iNo; int NextTerm(T p_iNo); public: Collatz(T p_iNo = 0); void CalculateCycle(); T GetCycle() const; }; template <typename T> Collatz<T>::Collatz(T p_iNo) : m_iNo(p_iNo), m_iCycle(1) { if (m_iNo < 1) throw std::out_of_range("Number should be greater than 0"); } template <typename T> int Collatz<T>::NextTerm(T p_iNo) { // if number is even if (p_iNo % 2 == 0) { p_iNo /= 2; } // if number is odd else { p_iNo = p_iNo * 3 + 1; } return p_iNo; } template <typename T> void Collatz<T>::CalculateCycle() { while (m_iNo != 1) { m_iNo = NextTerm(m_iNo); ++m_iCycle; } } template <typename T> T Collatz<T>::GetCycle() const { return m_iCycle; } int main(int argc, char* argv[]) { const int iNo = 22; try { Collatz<int> objCollatz(iNo); objCollatz.CalculateCycle(); cout << "Cycle length of " << iNo << " is " << objCollatz.GetCycle() << endl; } catch(std::out_of_range& ex) { cout << ex.what() << endl; } return 0; }

### Template Metaprogramming

Template metaprogramming is the most beautiful programming technique of C++. In this programming style, you use your compiler to do the program's work for you. In other words, it is something like writing a program about a program. In template metaprogramming, you are a using C++ compiler as an interpreter; in other words, the compiler expands the template and generates the code, which can be executed at run time by the compiled code. Execution speed of this program is very fast because the compiler has already resolved it at compile time. Nothing comes without price, and here the price is compilation time. Compilation time of your program may increase drastically; the length of times depends on the nature of the algorithm implemented by using this technique.

#include <iostream> using std::cout; using std::endl; template<int N> class CalculateCycle { public: enum { count = CalculateCycle&< N % 2 ? (N * 3 + 1) : (N / 2) >::count + 1 }; }; template <> class CalculateCycle<1> { public: enum { count = 1 }; }; int main(int argc, char* argv[]) { const int iNo = 22; cout << "Cycle length of " << iNo << " is = " << CalculateCycle<iNo>::count << endl; return 0; }