Parte decimal e inteira de numeros proximos de 62 bits

17 de outubro de 2006 6 respostas

Gustavo_Zeferino 17 de outubro de 2006

Tenho qe implementar um teste de primalidade, a fatoração por Fermat.

O problema é que para números grandes, os valores saem errados.

public static boolean fatoracaoFermat (long num){

	//false representa que num eh composto e true que eh primo
	boolean resultado = false;
	
	//Os comandos do metodo so serao executados caso o numero seja impar
	if (num%2 != 0){ 
		long x = (long)Math.floor(Math.sqrt(num));
		double y = 0;
		System.out.println("x inicial = "+x+". E y inicial = "+y);
	
		//Esse if modica as variaveis x e y. Mas so e executado se x nao for um quadrado perfeito
		if (x*x != num){
			while(true){
				x++; y = Math.sqrt(x*x - num);
				if (x == (long)((num + 1)/2)) {resultado = true; break;}			
				if (y == Math.floor(y)) break;
			}
		}
		
		long y2 = (long)(Math.round(y));
		System.out.println("x final = "+x+". E y final = "+y2);
		long fator1 = x - y2;
		long fator2 = x + y2;
		
		//Impressao do resultado da fatoracao por Fermat
		System.out.println("Resultado da fatoracao por Fermat");
	
		if (resultado)
			System.out.println(num + " e primo");
		else
			System.out.println(num + " e composto: "+num+" = "+fator1+" x "+fator2);
	}
	else System.out.println(num + " e par e portanto composto");
	
	return resultado;
}

Para o número 1759003855257, o resultado sai errado.... ela sai:

Z:\aa>java fermat 1759003855257
x inicial = 1326274. E y inicial = 0.0
x final = 75125595. E y final = 75113887
Resultado da fatoracao por Fermat
1759003855257 e composto: 1759003855257 = 11708 x 150239482

Mas 11708 x 150239482 = 1759003855256.

Alguém sabe como comparar se um número do tipo double possui um valor inteiro quando o número é grande?

6 Respostas

Proteu_Alcebidiano 18 de out. de 2006

Se os numeros estão ultrapassando no limite do tipo do dado, usa as Classes BigInteger e BigDecimal para não se preocupar mais com isso

http://javaalmanac.com/egs/java.math/AddBigInt.html?l=rel

http://javaalmanac.com/egs/java.math/AddBigDec.html?l=rel

http://javaalmanac.com/egs/java.math/Bits.html?l=rel

T+

thingol 18 de out. de 2006

Aí você só vai ter um problema, que é calcular uma raiz quadrada de um BigInteger.
Mas isso você também acha na Internet.

Gustavo_Zeferino 18 de out. de 2006

Não tem nuenhum problema com relação ao limite do tipo long. Nenhum valor passa de 62 bits. Tem uma parte no meu programa que foi preciso usar o BigInteger. Mas aqui não foi o caso. A fatoração é para números de no máximo 62 bits mesmo.

Penso que o problema talvez esteja quando quero verificar se y é um número inteiro… não tenho muita certeza se
y == Math.floor(y) é um bom método.

Também já tentei

y == (long)y

y == Math.ceil(y)

Math.ceil(y) == Math.floor(y)

e sempre apareceu o mesmo resultado.

thingol 18 de out. de 2006

O seu problema é que a precisão do double, em bits, é de 56 bits se não me engano, não 64. Portanto o cálculo da raiz quadrada, do jeito que você fez, pode não dar o valor exato quando convertido para um long.

thingol 18 de out. de 2006

Como de costume, enxergando o problema ao contrário tem-se a solução para determinar se um long (com até 63 bits!) é quadrado ou não.

class ChecaQuadradoPerfeito {
    
    public static boolean checa (long n) {
        // Note que a precisão de um double, em bits significativos, é inferior a de um double porque
        // é necessário reservar vários bits para a mantissa.
        // Entretanto, mesmo com problemas de precisão, ainda é possível determinar se um
        // long é um quadrado perfeito. Deixo a prova como exercício.
        long raiz = (long) Math.sqrt(n);
        return raiz * raiz == n;
    }
    
    public static void main(String[] args) {
        // Atenção - não passe longs "negativos".
        System.out.println (checa (0x7FFFFFFFFFFFFFFFL)); // não é quadrado; raiz = 0xB504F333L
        System.out.println (checa (0x7FFFFFFE9EA1DC29L)); // é quadrado; raiz = 0xB504F333L
    }
}

thingol 18 de out. de 2006

Pelo que imagino, a fatoração de Fermat só vale se o número for um composto de dois fatores. Mas

1759003855257 = 3 x 11 x 31 x [telefone removido]

(pelo que o comando “factor” do Unix/Linux me disse).

Peguei seu programa e dei uma adaptada, ele volta o seguinte resultado:

1759003855257 e composto: 1759003855257 = 1322436 x 1330124

que não parece estar certo.

Criado 17 de outubro de 2006

Ultima resposta 18 de out. de 2006

Respostas 6

Participantes 3

6 Respostas

Topicos relacionados