Acima eu disse que o fato do seu programa ficar rodando por vários minutos indica um provável erro no programa. Isso não é verdade! Eu não levei em conta uma coisa: o enunciado do EP pede que a divisão de "inteiros grandes" seja efetuada por meio de subtrações sucessivas.
A vantagem do método de subtrações sucessivas é que ele muito fácil de implementar. Foi por esse motivo (faciltar as coisas) que o enunciado indica o caminho das subtrações sucessivas. A desvantagem é que esse método é muito lento. O número de subtrações necessário para se fazer uma divisão por subtrações sucessivas é igual ao valor absoluto do resultado da divisão. O método das subtrações sucessivas é basicamente um laço que faz três coisas (a descrição abaixo supõe que o dividendo e o divisor são positivos e que o quociente foi inicializado com zero):
- Compara o divisor com o dividendo. Sai do laço se o dividendo for menor que o divisor.
- Subtrai o divisor do dividendo. O resultado é o novo valor do dividendo.
- Soma 1 ao quociente
Agora vamos pensar na divisão do ítem 60, desconsiderando o sinal:
123456708912345678901234567890 / 12304567089123405 = 10033405321628
Quanto tempo levará essa divisão? Ela vai executar 10033405321628 voltas no laço que faz as subtrações sucessivas... Para estimar o tempo de cada volta no laço, temos que fazer algumas hipóteses sobre a velocidade do processador e sobre o número de instruções de máquina dentro do laço.
Vamos supor que nosso processador é de 20000 MIPS (1 MIPS = 1 milhão de instruções por segundo). Os microprocessadores de uso geral (Pentium, Athon, Core Duo, ...) fabricados por volta de 2006 estavam nessa faixa de velocidade.
Suponhamos também que cada volta no laço executa 400 instruções. Isso é um chute que tenta levar em conta as coisas que são feitas a cada volta no laço (três operações com "inteiros grandes": uma comparação, uma subtração e uma adição de um). Na verdade o número de instruções em cada volta não será constante e dependerá do comprimento dos "inteiros grandes" em questão... Mas vamos supor que em média sejam executadas 400 instruções por volta. (Sim, isso é um chute, mas não é um chute aleatório!)
Temos então que o tempo de 10033405321628 voltas no laço é
(10033405321628 voltas * 400 instruções/volta) / (20000 * 1000000 instruções/segundo) = 200668.11 segundos
Esse tempo, em horas, é
200668.11 segundos = 200668.11 / (60 * 60) horas = 55.74 horas
Ou seja, a divisão do ítem 60 levará mais de dois dias! Isso é uma consequência da nossa escolha de algoritmo de divisão. Não é resultado de algum erro no programa.
É claro que existem algoritmos de divisão mais eficientes. O algoritmo comum (aquele que aprendemos quando crianças e ainda hoje usamos sempre que precisamos fazer alguma divisão no papel) é MUITO melhor que o de subtrações sucessivas. Por simplicidade, neste EP optamos por ficar com o algoritmo de subtrações sucessivas mesmo.
O arquivo entrada.txt será atualizado de modo que todas as divisões nele contidas possam ser efetuadas em tempo razoável pelo método das subtrações sucessivas.
Reverbel