Expert: Ralph McArdell - 10/23/2008

Question
hi
can you help me about this program,it doesn't workwhen n is mor than 30
what should i do for solving this problem?

#include<stdio.h>
int hanoi(int n);
void main(){
   int n;
   printf("Enter your number:\n");
   scanf("%d",&n);
   hanoi(n);
   printf("%d\n",hanoi(n));
}
int hanoi(int n){
   if(n!=1)
       return (1+2*hanoi(n-1));
   return 1;
}



thanx
bita


Answer
You have not appreciated the fact that numbers - either integer or floating point - held by computers are _not_ infinite. Yes you can use big number libraries, but in this case you are using a plain int to hold values which you multiply by 2.

The int built in type is of a bit-length that is natural for the processor the compiled code is targeted to run on. In this case I would guess that it is a 32-bit value. As int is signed the useful range of positive values is one less than 2 to the 31st power (or 31 one bits). Hence I think your program will not work with n > 31 (or n < 1 for that matter - you might try passing 0 for n to your hanio function - I'd start by doing it in your head using paper and pen or pencil to keep track of the values at first if I were you).

Each time you multiply a value by two you add one to the number of binary digits required to hold it. Thus 1 requires 1 bit to represent, 1*2 (==2) requires 2 bits, 2*2 (==4) requires 3 bits and so on. Hence by the time you have done this 31 times you are running out of bits in your int. In fact you run out when n=32. But for a twos complement signed values of 32 bits in length when the top (32nd) bit is set the value is negative, with -1 represented by all 1 bits. If you are unfamiliar with twos complement representation and arithmetic then you might like to read up on it (e.g. see http://en.wikipedia.org/wiki/Two%27s_complement). I suggested signed integers are held in twos complement as this is the norm for most (if not all) popular modern desktop computer systems, as is 32-bits for the size of C and C++ int types.

[Note:

C and C++ do not mandate the bit length of the supported built in integer types, only that sizeof(char)==1 - which does not mean char is 8-bits long necessarily - and that sizeof(char) <= sizeof(short) <= sizeof(int) <= sizeof(long) and the bit length of the unsigned equivalent for each integer type is the same as its signed counterpart.

However, most compilers for 32-bit code for byte addressed machines, which covers a majority of current desktop and server platforms have the following sizes for the integer types:

       sizeof(char ) == 1 (by definition) and is 8-bits in length
       sizeof(short) == 2 and is 16-bits in length
       sizeof(int  ) == 4 and is 32-bits in length
       sizeof(long ) == 4 and is 32-bits in length
       
For the newer 64-bit architectures there are various schemes. The one used by Microsoft, called LLP64, keeps all C89/C++98 standard integer types the same as the 32-bit model above, but allows an int64 or long long type and pointers to be 64 bits in size (hence LLP64 - Long Long and Pointers 64 bits). Un*x like systems however tend to use the LP64 (long and pointers 64 bits). See for example http://www.unix.org/whitepapers/64bit.html for more in this issue. The long long int type was added to the ISO C99 standard and will probably also be part of the next version of the ISO C++ standard.

-- end note]

Your code returns a value having n one bits set. When this reaches 32 you have the 2s complement -1 value. When you try 33 or greater the additional bits "fall off" the end when multiplied by 2, you then add 1 to restore the lower bit thus keeping the returned value at 32 1 bits - or -1. To test this I wrapped your hanio function up in some code to see what value it returned for various values of n using MS VC++ 2008 - which has 32-bit twos complement signed ints. Here are the results:

       For n=29 the hanio function returns: 536870911
       For n=30 the hanio function returns: 1073741823
       For n=31 the hanio function returns: 2147483647
       For n=32 the hanio function returns: -1
       For n=33 the hanio function returns: -1
       For n=34 the hanio function returns: -1

You can get 1 more bit (i.e. n=32 should return the correct result) by using unsigned int rather than int as then all 32-bits are for positive values. Doing this in my test program returned the following results:

       For n=29 the hanio function returns: 536870911
       For n=30 the hanio function returns: 1073741823
       For n=31 the hanio function returns: 2147483647
       For n=32 the hanio function returns: 4294967295
       For n=33 the hanio function returns: 4294967295
       For n=34 the hanio function returns: 4294967295

To make use of even greater values you would need to use a larger integer - e.g. a 64-bit integer if supported by your compiler (this may be long long, int64, __int64, or for some compilers for 64-bit processors long or even int, and their unsigned counter parts - you will have to check out your compiler's specification to see what it supports). For even greater precision you could use an arbitrary precision arithmetic library that supported large integer types - see http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic for some information on arbitrary precision arithmetic and examples of libraries.

Of course if you continue to use C you will have to use custom I/O procedures to use these values (I think some libraries may allow values to be converted to and from string values however) as printf / scanf etc. will not know about these types. If using C++ some such C++ libraries provide custom IOStream insertion and extraction operators (operator<< and operator>>).

Of course if using an integer is only a convenience and you do not need to do arithmetic on the result you could re-write your function to work with strings. In this case each time you call hanio you would append '1' (the character one, not the value 1) to a string. Remember, if using C that C style strings are just arrays and _you_ are responsible for making sure you do not cause your code to exceed the limits of the available space - and remember that C strings are arrays of char with a terminating zero character and storage space is required for this terminator.

In C++ I would also consider using a std::vector<bool> or a std::bitset or even a boost::dynamic_bitset (see http://www.boost.org/doc/libs/1_36_0/libs/dynamic_bitset/dynamic_bitset.html one of the Boost libraries for C++, see http://www.boost.org/).

Hope this helps.