Click here to Skip to main content
Click here to Skip to main content

CPP Math and Fun

, 3 Aug 2004
Rate this:
Please Sign up or sign in to vote.
Fun with Maths

Introduction

Some people think Math is boring stuff, 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 math background. Number theory is one such branch of math that may be very attractive to normal persons without learning lots of stuff.

Number theory is the study of the properties of integers; in other words whole numbers. This is perhaps the oldest branch of mathematics and also called Queen of Mathematics by the Prince of Mathematician 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. Although to see the beauty of it, you have to be familiar with different branches of math. In fact in past number theory is consider the pure mathematics, because there is no application of it outside the world of math. But there are lots of applications of it available now a day such as cryptography, random number generator, error detection, security etc. Still fascinating thing about number theory is that, there are still lots of unsolved problem in it waiting to be solved. It might be possible that there are few more branches of math will be evolved and few more technique will be developed to solve those problems.

The whole study of number theory is the proof of different problems beautifully, 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 then it still may have applications in real life. For example the well known cryptography algorithm RSA is based on this 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.

Details

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

In words, it is very simple problem. Take any number as an input, and divide it by 2 if no is even, or multiply by 3 then add one if no is odd. This is conjecture 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 till date that it is true for all values of n, although it has been checked for quite large numbers through computer. This might be a challenging task for those, who want to solve open problems and gain popularity.

Total numbers of elements in sequence until it reaches 1, including input number and 1, is called cycle of the sequence of that given input no. For example if user input 5 then 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 hailstone sequence.

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 no] If n is even then n := n / 2 else n := n * 3 + 1
A4. [Next number] Go to A2.
Ok now come to implementation side of this algorithm. Here I tired to do some fun with this simple algorithm and try to implement it in different programming style.

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 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 no is even
    if (iTemp % 2 == 0)
    {
      iTemp /= 2;
    }
    // if no 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 then 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 divide the problem into small pieces and solve those pieces one by one.

#include <iostream>
using std::cout;
using std::endl;

int NextTerm(int iNo)
{
  // if no is Even
  if (iNo % 2 == 0)
  {
    iNo /= 2;
  }
  // if no is even
  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". Isn't looks like strange? The name itself appears in the acronym, and when you try to expand it then GNU will again appear in acronym. This is simple example of recursion. In other words, more typical definition may be something like this "recursion is a way to specify a process by repeating means of itself". In programming language context, recursion means a function which calls itself. Typical examples of recursion are factorial, Fibonacci number, tower of Hanoi etc.

#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 made classes and create instances of those classes, called object. Technically class is a prototype that defines the variables and methods of one kind. This problem is very small, that you can not get full advantage of object oriented programming. This program is technically Object based 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("No should be greater than 0");
}

int Collatz::NextTerm(int p_iNo)
{
  // if no is Even
  if (p_iNo % 2 == 0)
  {
    p_iNo /= 2;
  }
  // if no is even
  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 means, program written in such a way that it should work independent of data type. Generic program should work on all data types which satisfy the required concepts use in the program. In C++ 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("No should be greater than 0");
}

template <typename T>
int Collatz<T>::NextTerm(T p_iNo)
{
  // if no is Even
  if (p_iNo % 2 == 0)
  {
    p_iNo /= 2;
  }
  // if no is even
  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 Meta-programming

Template Meta programming is the most beautiful programming technique of C++. In this programming style, you use your compiler to do work program for you. In other words, it is something like writing program about a program. In template Meta programming, you are using C++ compiler as an interpreter, i.e. compiler expand the template and generate the code, which can be executed at run time by compiled code. Execution speed of this program is very fast, because 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, 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&;t 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;
}

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Zeeshan Amjad
Software Developer (Senior) Bloomberg LP
United States United States
Working as a Sr C++ Developer at Bloomberg LP

Comments and Discussions

 
Generaluseful [modified] Pinmemberdronology3-Oct-07 23:15 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140709.1 | Last Updated 4 Aug 2004
Article Copyright 2004 by Zeeshan Amjad
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid