L'uso di numeri interi e doppi danno risposte diverse quando non dovrebbero

Question

Sto risolvendo un Eulero di progetto Problem 14 usando java. NON sto chiedendo aiuto per risolvere il problema. L'ho già risolto, ma mi sono imbattuto in qualcosa che non riesco a capire.

Il problema è come questo:

viene definita la seguente sequenza iterativa per il set di positivi interi:

n = n/2, se n è pari
n = 3n + 1, se n è dispari

Utilizzando la regola di cui sopra e partendo da 13, generiamo la seguente sequenza di :

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1. Qui, la lunghezza della catena è di 10 numeri.

Trova il numero iniziale inferiore a 1.000.000 che produce la catena più lunga.

Così ho scritto questo codice:

public class Euler014 { 
    public static void main(String[] args){ 
     int maxChainCount = 0; 
     int answer = 0; 
     int n; 
     int chainCount = 1; 

     for(int i = 0; i < 1000000; i++){ 
      n = i; 
      while(n > 1){ 
       if(n%2 == 0){  //check if even 
        n /= 2; 
       }else{    //else: odd 
        n = 3*n + 1; 
       } 
       chainCount++; 
      } 
      if(chainCount > maxChainCount){ //check if it's the longest chain so far 
       maxChainCount = chainCount; 
       answer = i; 
      } 
      chainCount = 1; 
     }  
     System.out.println("\n\nLongest chain: i = " + answer);  
    } 
} 

Questo mi dà la risposta 910.107, che è sbagliato.

TUTTAVIA, se cambio il tipo di mia variabile n in double n viene eseguito e mi dà la risposta 837799, che è giusto!

Questo mi confonde, perché non riesco a vedere quale sarebbe la differenza. Capisco che se usiamo int e facciamo divisioni possiamo finire su numeri di arrotondamento quando non abbiamo intenzione di farlo. Ma in questo caso, controlliamo sempre per vedere se lo n è divisibile per 2, PRIMA di dividere per 2. Quindi ho pensato che sarebbe stato totalmente sicuro usare gli interi. Cosa non vedo?

Questo è il codice nella sua interezza, copia, incolla ed eseguilo se desideri vedere di persona. Funziona in un paio di secondi nonostante molta iterazione. =)

Answer 1

Il tuo problema è overflow. Se cambia long n, otterrai la risposta giusta.

Ricorda: I numeri nella sequenza può essere davvero grande. Così grandi che superano la gamma di int. Ma non (in questo caso) double o long.

In un punto della catena, n è 827,370,449 e si segue il ramo 3n + 1. Tale valore deve essere 2,482,111,348, ma trabocca la capacità di int (che è 2,147,483,647 nel dominio positivo) e porta a -1,812,855,948. E le cose vanno a sud da lì. :-)

Quindi la tua teoria secondo cui staresti bene con numeri interi (dovrei dire ) è corretta. Ma devono avere la capacità per il compito.