Trabalhar com números GIGANTES

Use BigDecimal, deve funcionar.

Vortex,

Você já tentou armazenar esse valor em um double?
De acordo com Kathy Sierra (Sun Certified Java Programmer) não é necessário um intervalo para o tipo double.
Testa com esse tipo!

Abraço.

Olá

Seu número não é grande. Se fosse grande de verdade (mais de 100 dígitos), lhe recomendaria computação quântica. Mas para este porte nem precisa usar long. Pode usar int mesmo que vai até 214 milhões.

Fatorar != fatorial

Bland, se fosse um problema de números reais, nem precisaria de double porque como tem apenas 7 dígitos significativos, bastaria usar float. Mas fatoração fala de números inteiros.

[]s
Luca

Pergunta: você quer fatorar o número 1500000! (fatorial de 1500000) ou o número 1500000?

No segundo caso a fatoração é simples e não requer quase esforço.

No primeiro caso, você não precisa de BigDecimal ou de uma máquina poderosa. Basta ter um pouco de miolo.

Vou dar um exemplo com um fatorial menor (10!).

Você sabe que 10! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10

Fatore cada uma das parcelas:
(1) x (2) x (3) x (2 x 2) x (5) x (2 x 3) x 7 x (2 x 2 x 2) x (3 x 3) x (2 x 5)

ou, reordenando tudo ( estou usando ^ para representar a exponenciação):

( 2 ^ 8 ) x (3 ^ 4) x (5 ^2) x 7

No seu caso você pode repetir esse processo para os números de 1 até 1500000, o que vai ser realmente rápido.

Concordo com o tingol, use esse método, porque BigInteger é muito lendo para fins de processar numeros muito grandes.

O número 1.500.000! tem aproximadamente 27902869 bits (uma estimativa). Hoje fatorar um número de 1024 bits custa 20 mips ano. Ou seja, o número que você quer é 27mil vezes maior. Usando o melhor algorítmo disponível você vai precisar de 250milhões de mips ano.

Para obter 250 milhões de mips ano, basta você ter acesso a 100mil máquinas P4 2.5Ghz, se forem quad core feito o MacPro, corta pra 25mil. Porém o trabalho deve ser pra segunda, então vc precisa fatorar no final de semana, então aumente esse número para 4.5milhões desses.

Isso para a etapa de crivagem, claro. Para fazer a redução do sistema linear, sei lá usando block-wiedermann por exemplo, vc vai ter uma matriz quadrada de tamanho superior a 2^24, então serão necessários apenas
256 teras de memória principal para executar o algorítmo.

Até aqui tudo bem, um MacPro custa $2.500 dolares. Para comprar eles e todo equipamento de rede necessários você vai gastar coisa de 25bilhões de reais.

Moral da história, ou você pensa e entende direito o problema, ou então fique de DP.

Olá

A pergunta foi sobre que variável para armazenar fatoração de 1500000 ou estou comendo mosca?

Como um número fatorado de 1500000 pode ser maior do que 1500000?

Acho que ando viajando…

[]s
Luca

Luca:

Olá

A pergunta foi sobre que variável para armazenar fatoração de 1500000 ou estou comendo mosca?

Como um número fatorado de 1500000 pode ser maior do que 1500000?

Acho que ando viajando…

[]s
Luca

Todos comeram mosca, porque o vortex não soube explicar o problema dele. Ele precisa calcular fatorial e ele achou que ‘fatorar’ é o verbo a ser utilizado.

Galera quem comeu mosca foi eu!!

sorry,

eu quero mesmo é o FATORIAL de 1.500.000…sera que dá?

obrigado a todos!!

Pelo resumo do pessoal, vai demorar, e bastante… talvez ja esteja calculado, faça uma pesquisa no google, alguem deve ter isso em DVD… mas acho dificil.

vc precisa do numero exato ou aproximado? não deve ser dificil fazer uma aproximação… ou será? :twisted:

Olá

Trabalhei muitos anos como engenheiro em uma das maiores se não a maior empresa de montagens industriais do Brasil. Lá as pressões e os prazos eram MUITO maiores do que alguém de TI pode imaginar porque a grana envolvida geralmente era MUITO maior. Na empresa corria o seguinte ditado:

“O impossível a gente faz na hora, milagre demora mais um pouquinho!”

Todo este preâmbulo foi para perguntar: para que quer isto?

É para saber o quanto a gente pode cobrar

[]s
Luca

Uma vez o Daniel tinha proposto exatamente esse problema - quem conseguia calcular mais rápido o fatorial de um número muito grande. Havia aquela solução óbvia - usar BigInteger e efetuar milhões de multiplicações - mas depois apareceram várias soluções que não envolviam tantas contas assim. É só procurar aqui no forum.

Isso é um trabalho de probabilidade…eu preciso fazer um cálculo para saber qual a probabilidade de erro em cada peça de um lote de 1.500.000 de peças…tenho que utilizar a fórmula do cálculo binomial

n = número de peças no lote
x = representa cada peça analizada

n!                                1.500.000!

---------- = -------------------------------------------------
(n-x)! x! (1.500.000 - 0…1.500.000)! 0…1.500.000!

se alguém não entender (acho que da pra entender) eu simplifico mais!

vlw galera []'s

pense em matematica…

n = número de peças no lote
x = representa cada peça analizada

onde n = 1.500.000

formula: n! / (n-x)! x!

vamos analisar: (1.500.000 - x)!

(x=0) 1.500.000!
(x=1) 1.500.000 - 1! = 1.499.999! = 1.499.999! * 1.500.000/1.500.000 = 1.500.000! /1.500.000
(x=2) 1.500.000 - 2! = 1.499.998! = 1.500.000!/(1.500.000 * 1.499.999)
(x=3) 1.500.000 - 3! = 1.499.997! = 1.500.000!/(1.500.000 * 1.499.999 * 1.499.998)
(x=4) 1.500.000 - 4! = 1.499.996! = 1.500.000!/(1.500.000 * 1.499.999 * 1.499.998 * 1.499.997)

(n-x)! = n!/(n * (n-1) * (n-2) * … *(n-x+1))

n!

x!n!/(n * (n-1) * (n-2) * … *(n-x+1))

equivale à

(n * (n-1) * (n-2) * … * (n-(x-1)))/x!

que é muito mais facil de calcular

1/x! * produtorio (n-x) onde x=[0…x-1]

acho que tem alguma mancada por ai… dê uma revisada

UPDATE:

Pq tu nao usa stirling?

N! ~ N^Nexp(N)sqrt(2PiN)

Ou “stirling plus”

N! ~~ N^Nexp(N)sqrt(2PiN)(1+1/(12N))

Galera OBRIGADO por enquanto…deu pra ter algumas idéias com o que vcs me passaram…deu pra aprender algumas coisas! VLW Mesmo!

vou testar em casa alguma dessas dicas…dando certo ou não eu aviso!

até mais!!!

peczenyj:

pense em matematica…

n = número de peças no lote
x = representa cada peça analizada

onde n = 1.500.000

formula: n! / (n-x)! x!

colega, posso resaltar que existe outra formula

a = n! / (n-x)!
onde essa formula seria a formula do arranjo

e

c = n! / (n-x)! x!
onde essa formula seria a formula da combinação

dai nesse caso você teria que saber em qual formula usar…
abraços…

oi gente…to com um trabalho de ADM para fezer …mais ta foda naum encontei na net vc naum sebe onde posso encontra ?
e do Peter Brucker … :arrow: