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 (iTemp % 2 == 0)
{
iTemp /= 2;
}
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 (iNo % 2 == 0)
{
iNo /= 2;
}
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 (p_iNo % 2 == 0)
{
p_iNo /= 2;
}
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 (p_iNo % 2 == 0)
{
p_iNo /= 2;
}
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
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;
}
| You must Sign In to use this message board. |
|
|
 |
 | useful 
dronology | 0:15 4 Oct '07 |
|
|
Very useful information source for programmers. I prefer my friends to read this article for the purpose of learning how can programming can be handled.
I asked my master "Why don't you publish free tutorials or free source in any web site?"
He said me "I tried but it has no return..."
And I said "You may be retired but I'll try my best to reach people who needs knowledge.."
www.dronology.com
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
| Thanks
Pure Amatuer | 7:16 2 Jun '06 |
|
|
This is a great article for an amatuer like myself. I have written a simple program that derives the function for a user input solution set of whole numbers. For example, in seconds it can derive [n(3n-1)]/2 for user input n=0,1,2,5,7,12,15,22,26... (pentagonal numbers). It can handle more complicated relationships. My work is completely amatuer - but I suspect it has commercial/experimental applications. Anyway, I have no idea what I'm doing - but I know using programming to conduct number theory "experiments" is cool.
nick schmelzer
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
it was helpful in explaining me the different styles of programming. I was not familiar with few (1 in fact  ) of those like meta programming.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
You started off talking about number theory and then the rest of the article is about style, and the different ways to implement the algorithm. I still enjoyed it and will give you high marks.
What I would really like to see is a good article on set theory in plain english. I spent a lot of time at the end of last year working with sets and most of the related articles I read where heavy on set theory notation. I finally understand it well enough to produce the required code, but do not ask me to explane it. I can explane the code, but I can not explane it in terms of set theory notation. A good article would take some examples of set theory notation and break it down symbol by symbol.
I think I will go and make a request for articles on this and some other advanced subjects.
Thanks!
INTP
Every thing is relative...
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
enum { count = CalculateCycle&;t N % 2 ?
(N * 3 + 1) : (N / 2) >::count + 1 };
Sorry,
I don't understand..
Please explain it more clearly.
Thank you...
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Thanks to point out this. This was HTML formating error. Correct code should be something like
enum { count = CalculateCycle< N % 2 ?
(N * 3 + 1) : (N / 2) >::count + 1 };
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
If you care at all about performance, you should cut the middle man and not rely on the compiler for optimizing math operations. Here are the operations followed by their faster equivalent :
N / 2 : N >> 1
N % 2 : N & 1
N * 3 : N + N + N
C++ compiler does it implicitly, but in compilers that support it, you should use integer division operator when possible. It is usually '\' instead of '/'.
The recursion example is there for completeness sake, but you should state that it's a big no-no
In the OOP example, why not return the result of the operation at once, instead of storing it into a property ?
In the generic example, I think the following :
template
int Collatz::NextTerm(T p_iNo)
should read
template
T Collatz::NextTerm(T p_iNo)
Sébastien
Intelligence shared is intelligence squared.
Homepage : http://sebastienlorion.com
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
|
|
|
Some of these comments are not correct.
N * 3 : N + N + N
Not a good idea. On a 386 or higher machine, multiplication of an integer by 3 can be done in a single instruction (you use the LEA instruction). It's better not to reduce code clarity unless you have evidence that there's an important performance benefit. Frankly, if a compiler can't optimize multiplucation by a constant, you should change compilers. I've never encountered a compiler that couldn't do it.
> C++ compiler does it implicitly, but in compilers that support it, you should use integer division operator when possible. It is usually '\' instead of '/'.
What compilers support that? I've never seen it. It doesn't work on MSVC, for example. Normally backslash indicates an escape sequence.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Remember that on a CISC cpu, one OP can take a *long* time. A simple DIV 2 in x86 assembly is way longer than a SHR instruction, even if both do the same. That said, you are right about this one and I've never wrote N+N+N in my own code.
As for the '\' division, simply search "integer division operator" on Google. That particular symbol is used in VB and its ilk, but it is also an open debate to have that kind of operator for other languages like Ruby or Python. The argument is about whether to let the compiler decides which operator overload to use based on the operands and/or let the programmer decides. In C++, it's up to the compiler.
Sébastien
Intelligence shared is intelligence squared.
Homepage : http://sebastienlorion.com
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Sébastien Lorion wrote: C++ compiler does it implicitly, but in compilers that support it, you should use integer division operator when possible. It is usually '\' instead of '/'.
If both sides of the / operand are integers, integer division is used. \ is the line concatenation operator in the preprocessor, so it's definately not a C++ operator.
Sébastien Lorion wrote: The recursion example is there for completeness sake, but you should state that it's a big no-no
Just make it tail recursive, and have the intelligent compiler optimize it into a loop.
--
Pictures[^] from my Japan trip.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Maybe it is not clear from my comment, but I explicitely said "in compilers that support it". Obviously, C++ does not, but for example, VB6 does.
About recursion, no matter how smart your compiler is, it will not find a better algorithm for you, tail recursion or not. For example, in terms of memory usage, there is an O(1) iterative solution to the problem of Tower of Hanoi, while the recursive solution is O(log n). See http://blogs.msdn.com/ericlippert/archive/2004/05/19/135392.aspx.
Sébastien
Intelligence shared is intelligence squared.
Homepage : http://sebastienlorion.com
-- modified at 23:46 Thursday 5th January, 2006
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
