Large inputs give weird results

[Yutxz]

I'm developing a program based on the Tower of Hanoi. It accepts the number of discs and returns the amount of turns it takes for those discs to complete the conundrum. All of my inputs work fine, until the input (d) is greater than 31. Is the result too large to return?

package numTurns;

/**
 *
 * @author Josh
 */
public class Main {
    public static int numTurns (int d) {
int turns = 1;
if (d == 0) {
return 0;
} if ( d == 1) {
    return 1;
    // returns 1 if d == 1
        }

for (int i = 1; i < d; i++) {
turns = turns * 2 + 1;
}
return turns;
// returns number of turns only if d is greater than 1
}

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // Tests
        System.out.println (numTurns (3));
        System.out.println (numTurns(4));
        System.out.println (numTurns(32));
    }
}

[jon.kiparsky]

Try running this little program and see if it answers your question:

public class intLoop
{
	public static void main(String[] args)
	{
		short i = 0;
		while (true)
			System.out.println( i++);
	}
}

(I used a short out of mercy... it takes a few minutes to see the looping on an int, but 2^16 isn't that big)

Anyway, what you're seeing is a product of two's complement representation, which Java uses for integers. There are ways of representing bigger numbers, but I think once you've got up to 31 disks, there's not a lot more to be learned from the Towers.

(better read up on that two's complement, by the way - the next time there's a question about integer representation, I expect you to be Johnny on the spot... :) )

[Yutxz]

Thank you! This explanation helped me out a lot.
Are there any simple means by which I can find the integer for discs greater than 31? Can I use long?

[jon.kiparsky]

Long should work - that's an 8-byte, so it'll get you a bit further. 9,223,372,036,854,775,807 if you want to be precise.
Or if you want to a bit larger than that, you could look at java.math.BigInteger

Or you could look into Scheme, which is well-suited to this sort of problem, and calculates arbitrarily large numbers without complaining.

1 ]=> (pow 2 10000)

;Value: 19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376