 |
General Programming »
Algorithms & Recipes »
Math
Intermediate
License: The Code Project Open License (CPOL)
CPP Math and FunBy Zeeshan AmjadFun with Maths |
C++, Windows, Visual Studio, Dev
|
|
Advanced Search |
|
|
|
||||||||||||||||
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.
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.
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.
#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; }
#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; }
#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; }
#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; }
#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; }
#includeusing 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; }
| You must Sign In to use this message board. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
General 
News 
Question 
Answer 
Joke 
Rant 
Admin
|
PermaLink |
Privacy |
Terms of Use
Last Updated: 3 Aug 2004 Editor: Nishant Sivakumar |
Copyright 2004 by Zeeshan Amjad Everything else Copyright © CodeProject, 1999-2009 Web10 | Advertise on the Code Project |
) of those like meta programming. 