Divisão longa - Long division

Em aritmética , a divisão longa é um algoritmo de divisão padrão adequado para dividir numerais arábicos de vários dígitos ( notação posicional ) que é simples o suficiente para ser executado à mão. Ele divide um problema de divisão em uma série de etapas mais fáceis.

Como em todos os problemas de divisão, um número, denominado dividendo , é dividido por outro, denominado divisor , produzindo um resultado denominado quociente . Ele permite que cálculos envolvendo números arbitrariamente grandes sejam executados seguindo uma série de etapas simples. A forma abreviada de divisão longa é chamada de divisão curta , que quase sempre é usada em vez da divisão longa quando o divisor tem apenas um dígito. Chunking (também conhecido como método de quocientes parciais ou método da forca) é uma forma menos mecânica de divisão longa proeminente no Reino Unido, que contribui para um entendimento mais holístico sobre o processo de divisão.

Embora algoritmos relacionados existam desde o século 12 DC, o algoritmo específico em uso moderno foi introduzido por Henry Briggs c. 1600 DC.

Educação

Calculadoras e computadores baratos tornaram-se a maneira mais comum de resolver problemas de divisão, eliminando um exercício matemático tradicional e diminuindo a oportunidade educacional de mostrar como fazê-lo por meio de técnicas de papel e lápis. (Internamente, esses dispositivos usam um de uma variedade de algoritmos de divisão , os mais rápidos entre os quais contam com aproximações e multiplicações para realizar as tarefas). Nos Estados Unidos, a divisão longa tem sido especialmente direcionada para a redução, ou mesmo eliminação do currículo escolar, pela reforma da matemática , embora tradicionalmente introduzida na 4ª ou 5ª série.

Método

Em países de língua inglesa, a divisão longa não usa a barra de divisão ⟨ ∕ ⟩ ou os símbolos de sinal de divisão ⟨÷⟩, mas, em vez disso, constrói um quadro . O divisor é separado do dividendo por um parêntese direito ⟨ ) ⟩ ou barra vertical ⟨ | ⟩; o dividendo é separado do quociente por um vínculo (ou seja, uma barra superior ). A combinação desses dois símbolos às vezes é conhecida como símbolo de divisão longa ou colchete de divisão . Ele se desenvolveu no século 18 a partir de uma notação anterior de linha única separando o dividendo do quociente por um parêntese esquerdo .

O processo é iniciado dividindo o dígito mais à esquerda do dividendo pelo divisor. O quociente (arredondado para um inteiro) torna-se o primeiro dígito do resultado e o restante é calculado (esta etapa é notada como uma subtração). Este resto é transportado para a frente quando o processo é repetido no dígito seguinte do dividendo (notado como 'baixando' o próximo dígito para o resto). Quando todos os dígitos tiverem sido processados ​​e nenhum resto for deixado, o processo estará concluído.

Um exemplo é mostrado abaixo, representando a divisão de 500 por 4 (com um resultado de 125).

     125      (Explanations)
   4)500
     4        ( 4 ×  1 =  4)
     10       ( 5 -  4 =  1)
      8       ( 4 ×  2 =  8)
      20      (10 -  8 =  2)
      20      ( 4 ×  5 = 20)
       0      (20 - 20 =  0)

Um exemplo de divisão longa realizada sem calculadora.

Uma análise mais detalhada das etapas é a seguinte:

1. Encontre a menor sequência de dígitos começando da extremidade esquerda do dividendo, 500, em que o divisor 4 entra pelo menos uma vez. Neste caso, este é simplesmente o primeiro dígito, 5. O maior número pelo qual o divisor 4 pode ser multiplicado sem exceder 5 é 1, então o dígito 1 é colocado acima de 5 para começar a construir o quociente.
2. A seguir, o 1 é multiplicado pelo divisor 4, para obter o maior número inteiro que é um múltiplo do divisor 4 sem exceder o 5 (4 neste caso). Este 4 é então colocado sob e subtraído do 5 para obter o restante, 1, que é colocado sob o 4 sob o 5.
3. Posteriormente, o primeiro dígito ainda não utilizado no dividendo, neste caso o primeiro dígito 0 após o 5, é copiado diretamente abaixo de si mesmo e ao lado do restante 1, para formar o número 10.
4. Neste ponto, o processo é repetido o suficiente para chegar a um ponto de parada: O maior número pelo qual o divisor 4 pode ser multiplicado sem exceder 10 é 2, então 2 é escrito acima como o segundo dígito quociente mais à esquerda. Este 2 é então multiplicado pelo divisor 4 para obter 8, que é o maior múltiplo de 4 que não excede 10; portanto, 8 é escrito abaixo de 10, e a subtração 10 menos 8 é realizada para obter o restante 2, que é colocado abaixo de 8.
5. O próximo dígito do dividendo (o último 0 em 500) é copiado diretamente abaixo de si mesmo e próximo ao restante 2 para formar 20. Em seguida, o maior número pelo qual o divisor 4 pode ser multiplicado sem exceder 20, que é 5, é colocado acima como o terceiro dígito quociente mais à esquerda. Este 5 é multiplicado pelo divisor 4 para obter 20, que é escrito abaixo e subtraído dos 20 existentes para render o restante 0, que é então escrito abaixo do segundo 20.
6. Neste ponto, como não há mais dígitos para diminuir do dividendo e o resultado da última subtração foi 0, podemos ter certeza de que o processo terminou.

Se o último resto quando ficamos sem dígitos dos dividendos fosse algo diferente de 0, teria havido dois cursos de ação possíveis:

1. Poderíamos simplesmente parar por aí e dizer que o dividendo dividido pelo divisor é o quociente escrito no topo com o resto escrito na parte inferior, e escrever a resposta como o quociente seguido por uma fração que é o resto dividido pelo divisor.
2. Poderíamos estender o dividendo escrevendo-o como, digamos, 500.000 ... e continuar o processo (usando um ponto decimal no quociente diretamente acima do ponto decimal no dividendo), a fim de obter uma resposta decimal, como a seguir exemplo.

      31.75     
   4)127.00
     12         (12 ÷ 4 = 3)
      07        (0 remainder, bring down next figure)
       4        (7 ÷ 4 = 1 r 3)                                             
       3.0      (bring down 0 and the decimal point)
       2.8      (7 × 4 = 28, 30 ÷ 4 = 7 r 2)
         20     (an additional zero is brought down)
         20     (5 × 4 = 20)
          0

Neste exemplo, a parte decimal do resultado é calculada continuando o processo além do dígito das unidades, "diminuindo" os zeros como sendo a parte decimal do dividendo.

Este exemplo também ilustra que, no início do processo, uma etapa que produz um zero pode ser omitida. Como o primeiro dígito 1 é menor que o divisor 4, a primeira etapa é executada nos primeiros dois dígitos 12. Da mesma forma, se o divisor fosse 13, seria realizada a primeira etapa em 127 em vez de 12 ou 1.

Procedimento básico para divisão longa de n ÷ m

1. Encontre a localização de todas as casas decimais no dividendo ne divisor m .
2. Se necessário, simplifique o problema da divisão longa movendo os decimais do divisor e do dividendo pelo mesmo número de casas decimais, para a direita (ou para a esquerda), de modo que o decimal do divisor fique à direita do último dígito .
3. Ao fazer uma divisão longa, mantenha os números alinhados de cima para baixo sob o quadro.
4. Após cada etapa, certifique-se de que o restante dessa etapa seja menor que o divisor. Se não for, há três problemas possíveis: a multiplicação está errada, a subtração está errada ou é necessário um quociente maior.
5. No final, o restante, r , é adicionado ao quociente de crescimento como uma fração ,  r / m .

Propriedade invariável e correção

A apresentação básica das etapas do processo (acima) enfoca quais etapas devem ser realizadas, ao invés das propriedades dessas etapas que garantem que o resultado será correto (especificamente, que q × m + r = n , onde q é o quociente final er o resto final). Uma ligeira variação de apresentação requer mais escrita e requer que alteremos, em vez de apenas atualizar, os dígitos do quociente, mas podemos esclarecer por que essas etapas realmente produzem a resposta certa, permitindo a avaliação de q × m + r no intermediário pontos no processo. Isso ilustra a propriedade chave usada na derivação do algoritmo (abaixo) .

Especificamente, alteramos o procedimento básico acima para preencher o espaço após os dígitos do quociente em construção com 0's, pelo menos até a casa dos 1s, e incluir esses 0s nos números que escrevemos abaixo do colchete de divisão.

Isso nos permite manter uma relação invariante a cada passo: q × m + r = n , onde q é o quociente parcialmente construído (acima do colchete de divisão) er o resto parcialmente construído (número inferior abaixo do colchete de divisão). Observe que, inicialmente q = 0 e r = n , portanto, essa propriedade é válida inicialmente; o processo reduz r e aumenta q a cada passo, eventualmente parando quando r <m se buscarmos a resposta na forma de quociente + resto inteiro.

Revisitando o exemplo 500 ÷ 4 acima, encontramos

     125      (q, changes from 000 to 100 to 120 to 125 as per notes below)
   4)500
     400      (  4 × 100 = 400)
     100      (500 - 400 = 100; now q=100, r=100; note q×4+r = 500.)
      80      (  4 ×  20 =  80)
      20      (100 -  80 =  20; now q=120, r= 20; note q×4+r = 500.)
      20      (  4 ×   5 =  20)
       0      ( 20 -  20 =   0; now q=125, r=  0; note q×4+r = 500.)

Exemplo com divisor de vários dígitos

Exemplo animado de divisão longa com vários dígitos

Um divisor de qualquer número de dígitos pode ser usado. Neste exemplo, 1260257 deve ser dividido por 37. Primeiro, o problema é configurado da seguinte forma:

              
    37)1260257

Os dígitos do número 1260257 são obtidos até que um número maior ou igual a 37 ocorra. Portanto, 1 e 12 são menores que 37, mas 126 é maior. Em seguida, o maior múltiplo de 37 menor ou igual a 126 é calculado. Portanto, 3 × 37 = 111 <126, mas 4 × 37> 126. O múltiplo 111 está escrito abaixo do 126 e o ​​3 está escrito no topo onde a solução aparecerá:

         3    
    37)1260257
       111

Observe cuidadosamente em qual coluna de valor local esses dígitos estão escritos. O 3 no quociente vai para a mesma coluna (casa de dez mil) que o 6 no dividendo 1260257, que é a mesma coluna do último dígito de 111.

O 111 é então subtraído da linha acima, ignorando todos os dígitos à direita:

         3    
    37)1260257
       111
        15

Agora, o dígito do próximo valor de casa menor do dividendo é copiado e anexado ao resultado 15:

         3    
    37)1260257
       111
        150

O processo se repete: o maior múltiplo de 37 menor ou igual a 150 é subtraído. Isso é 148 = 4 × 37, então um 4 é adicionado ao topo como o próximo dígito quociente. Em seguida, o resultado da subtração é estendido por outro dígito retirado do dividendo:

         34   
    37)1260257
       111
        150
        148
          22

O maior múltiplo de 37 menor ou igual a 22 é 0 × 37 = 0. Subtraindo 0 de 22 resulta em 22, muitas vezes não escrevemos a etapa de subtração. Em vez disso, simplesmente pegamos outro dígito do dividendo:

         340  
    37)1260257
       111
        150
        148
          225

O processo é repetido até que 37 divida a última linha exatamente:

         34061
    37)1260257
       111
        150
        148
          225
          222
            37

Modo misto de divisão longa

Para moedas não decimais (como o sistema sd britânico antes de 1971) e medidas (como avoirdupois ) , a divisão de modo misto deve ser usada. Considere dividir 50 milhas com 600 jardas em 37 peças:

          mi -     yd -   ft -   in
           1 -    634      1      9 r. 15"
    37)   50 -    600 -    0 -    0
          37    22880     66    348
          13    23480     66    348
        1760    222       37    333
       22880     128      29     15
       =====     111     348     ==
                  170    ===
                  148
                   22
                   66
                   ==

Cada uma das quatro colunas é trabalhada separadamente. Começando com as milhas: 50/37 = 1 resto 13. Nenhuma divisão adicional é possível, então faça uma longa multiplicação por 1.760 para converter milhas em jardas, o resultado é 22.880 jardas. Leve isso para o topo da coluna de jardas e adicione-as aos 600 jardas no dividendo, resultando em 23.480. A divisão longa de 23.480 / 37 agora procede normalmente, rendendo 634 com o restante 22. O restante é multiplicado por 3 para obter os pés e carregado até a coluna dos pés. A divisão longa dos pés dá 1 resto 29, que é então multiplicado por doze para obter 348 polegadas. A divisão longa continua com o resto final de 15 polegadas sendo mostrado na linha de resultado.

Interpretação de resultados decimais

Quando o quociente não é um número inteiro e o processo de divisão é estendido além da vírgula decimal, uma de duas coisas pode acontecer:

1. O processo pode terminar, o que significa que um resto de 0 é alcançado; ou
2. Um resto pode ser alcançado que é idêntico a um resto anterior que ocorreu depois que as casas decimais foram escritas. No último caso, continuar o processo seria inútil, porque daquele ponto em diante a mesma sequência de dígitos apareceria no quociente continuamente. Assim, uma barra é desenhada sobre a sequência de repetição para indicar que ela se repete para sempre (ou seja, todo número racional é um decimal final ou repetitivo ).

Notação em países de língua não inglesa

China, Japão e Coréia usam a mesma notação que as nações de língua inglesa, incluindo a Índia. Em outros lugares, os mesmos princípios gerais são usados, mas as figuras costumam ser organizadas de maneira diferente.

América latina

Na América Latina (exceto Argentina , Bolívia , México , Colômbia , Paraguai , Venezuela , Uruguai e Brasil ), o cálculo é quase exatamente o mesmo, mas é escrito de forma diferente conforme mostrado abaixo com os mesmos dois exemplos usados ​​acima. Normalmente, o quociente é escrito sob uma barra desenhada sob o divisor. Uma longa linha vertical às vezes é desenhada à direita dos cálculos.

     500 ÷ 4 =  125   (Explanations) 
     4                ( 4 ×  1 =  4)
     10               ( 5 -  4 =  1)
      8               ( 4 ×  2 =  8)
      20              (10 -  8 =  2)
      20              ( 4 ×  5 = 20)
       0              (20 - 20 =  0)

e

     127 ÷ 4 = 31.75
     124                             
       30      (bring down 0; decimal to quotient)
       28      (7 × 4 = 28)
        20     (an additional zero is added)
        20     (5 × 4 = 20)
          0

No México , a notação mundial anglófona é usada, exceto que apenas o resultado da subtração é anotado e o cálculo é feito mentalmente, conforme mostrado abaixo:

     125     (Explanations)
   4)500
     10      ( 5 -  4 = 1)
      20     (10 -  8 = 2)
       0     (20 - 20 = 0)

Na Bolívia , Brasil , Paraguai , Venezuela , Canadá de língua francesa , Colômbia e Peru , a notação europeia (veja abaixo) é usada, exceto que o quociente não é separado por uma linha vertical, conforme mostrado abaixo:

    127|4    
   −124 31,75
      30
     −28
       20
      −20
        0

O mesmo procedimento se aplica no México , Uruguai e Argentina , apenas o resultado da subtração é anotado e o cálculo é feito mentalmente.

Eurásia

Na Espanha, Itália, França, Portugal, Lituânia, Romênia, Turquia, Grécia, Bélgica, Bielo-Rússia, Ucrânia e Rússia, o divisor está à direita do dividendo e separado por uma barra vertical. A divisão também ocorre na coluna, mas o quociente (resultado) é escrito abaixo do divisor e separado pela linha horizontal. O mesmo método é usado no Irã, Vietnã e Mongólia.

    127|4    
   −124|31,75
      30
     −28
       20
      −20
        0

Em Chipre, assim como na França, uma longa barra vertical separa o dividendo e subtrações subsequentes do quociente e divisor, como no exemplo abaixo de 6359 dividido por 17, que é 374 com um resto de 1.

6

3

5

17

1

374

6

Os números decimais não são divididos diretamente, o dividendo e o divisor são multiplicados por uma potência de dez, de modo que a divisão envolve dois números inteiros. Portanto, se alguém estivesse dividindo 12,7 por 0,4 (vírgulas sendo usadas em vez de casas decimais), o dividendo e o divisor seriam primeiro alterados para 127 e 4 e, em seguida, a divisão continuaria como acima.

Na Áustria , Alemanha e Suíça , a forma de notação de uma equação normal é usada. <dividendo>: <divisor> = <quociente>, com os dois pontos ":" denotando um símbolo de infixo binário para o operador de divisão (análogo a "/" ou "÷"). Nessas regiões, o separador decimal é escrito como uma vírgula. (cf. a primeira seção dos países latino-americanos acima, onde é feito praticamente da mesma maneira):

    127 : 4 = 31,75
   −12
     07
     −4
      30
     −28
       20
      −20
        0

A mesma notação é adotada na Dinamarca , Noruega , Bulgária , Macedônia do Norte , Polônia , Croácia , Eslovênia , Hungria , República Tcheca , Eslováquia , Vietnã e na Sérvia .

Na Holanda , a seguinte notação é usada:

   12 / 135 \ 11,25
        12
         15
         12
          30
          24
           60
           60
            0

Algoritmo para base arbitrária

Cada número natural pode ser representado exclusivamente em uma base de número arbitrário como uma sequência de dígitos onde para todos , onde é o número de dígitos em . O valor de em termos de seus dígitos e a base é ${\ displaystyle n}$ ${\ displaystyle b> 1}$ ${\ displaystyle n = \ alpha _ {0} \ alpha _ {1} \ alpha _ {2} ... \ alpha _ {k-1}}$${\ displaystyle 0 \ leq \ alpha _ {i} <b}$${\ displaystyle 0 \ leq i <k}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle n}$

${\ displaystyle n = \ sum _ {i = 0} ^ {k-1} \ alpha _ {i} b ^ {ki-1}}$

Let ser o dividendo e ser o divisor, onde é o número de dígitos em . Se , então e . Caso contrário, iteramos de , antes de parar. ${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle l}$${\ displaystyle m}$${\ displaystyle k <l}$${\ displaystyle q = 0}$${\ displaystyle r = n}$${\ displaystyle 0 \ leq i \ leq kl}$

Para cada iteração , seja o quociente extraído até agora, seja o dividendo intermediário, seja o resto intermediário, seja o próximo dígito do dividendo original e seja o próximo dígito do quociente. Por definição de dígitos de base , . Por definição de resto ,. Todos os valores são números naturais. Nós iniciamos ${\ displaystyle i}$${\ displaystyle q_ {i}}$${\ displaystyle d_ {i}}$${\ displaystyle r_ {i}}$${\ displaystyle \ alpha _ {i}}$${\ displaystyle \ beta _ {i}}$${\ displaystyle b}$${\ displaystyle 0 \ leq \ beta _ {i} <b}$${\ displaystyle 0 \ leq r_ {i} <m}$

${\ displaystyle q _ {- 1} = 0}$

${\ displaystyle r _ {- 1} = \ sum _ {i = 0} ^ {l-2} \ alpha _ {i} b ^ {l-2-i}}$

os primeiros dígitos de . ${\ displaystyle l-1}$${\ displaystyle n}$

A cada iteração, as três equações são verdadeiras:

${\ displaystyle d_ {i} = br_ {i-1} + \ alpha _ {i + l-1}}$

${\ displaystyle r_ {i} = d_ {i} -m \ beta _ {i} = br_ {i-1} + \ alpha _ {i + l-1} -m \ beta _ {i}}$

${\ displaystyle q_ {i} = bq_ {i-1} + \ beta _ {i}}$

Só existe um tal que . ${\ displaystyle \ beta _ {i}}$${\ displaystyle 0 \ leq r_ {i} <m}$

Prova de existência e singularidade de${\ displaystyle \ beta _ {i}}$  -

De acordo com a definição do restante , ${\ displaystyle r_ {i}}$

${\ displaystyle 0 \ leq r_ {i} <m}$

${\ displaystyle 0 \ leq br_ {i-1} + \ alpha _ {i + l-1} -m \ beta _ {i} <m}$

${\ displaystyle m \ beta _ {i} \ leq br_ {i-1} + \ alpha _ {i + l-1} <m (\ beta _ {i} +1)}$

Para o lado esquerdo da desigualdade, selecionamos o maior, de modo que ${\ displaystyle \ beta _ {i}}$

${\ displaystyle m \ beta _ {i} \ leq br_ {i-1} + \ alpha _ {i + l-1}}$

Sempre há um maior , porque e se , então ${\ displaystyle \ beta _ {i}}$${\ displaystyle 0 \ leq \ beta _ {i} <b}$${\ displaystyle \ beta _ {i} = 0}$

${\ displaystyle 0 \ leq br_ {i-1} + \ alpha _ {i + l-1}}$

mas porque , , , isso é sempre verdade. Para o lado direito da desigualdade, assumimos que existe um menor, tal que ${\ displaystyle b> 1}$${\ displaystyle r_ {i-1} \ geq 0}$${\ displaystyle \ alpha _ {i + l-1} \ geq 0}$${\ displaystyle \ beta _ {i} ^ {\ prime}}$

${\ displaystyle br_ {i-1} + \ alpha _ {i + l-1} <m (\ beta _ {i} ^ {\ prime} +1)}$

Uma vez que este é o menor que a desigualdade é verdadeira, isso deve significar que para${\ displaystyle \ beta _ {i} ^ {\ prime}}$${\ displaystyle \ beta _ {i} ^ {\ prime} -1}$

${\ displaystyle br_ {i-1} + \ alpha _ {i + l-1} \ geq m \ beta _ {i} ^ {\ prime}}$

que é exatamente igual ao lado esquerdo da desigualdade. Assim ,. Como sempre existirá, assim será igual a , e só há um único que é válido para a desigualdade. Assim, provamos a existência e a singularidade de . ${\ displaystyle \ beta _ {i} = \ beta _ {i} ^ {\ prime}}$${\ displaystyle \ beta _ {i}}$${\ displaystyle \ beta _ {i} ^ {\ prime}}$${\ displaystyle \ beta _ {i}}$${\ displaystyle \ beta _ {i}}$${\ displaystyle \ beta _ {i}}$

O quociente final é e o resto final é${\ displaystyle q = q_ {kl}}$${\ displaystyle r = r_ {kl}}$

Exemplos

Na base 10 , usando o exemplo acima com e , os valores iniciais e . ${\ displaystyle n = 1260257}$${\ displaystyle m = 37}$${\ displaystyle q _ {- 1} = 0}$${\ displaystyle r _ {- 1} = 1}$

${\ displaystyle 0 \ leq i \ leq kl}$	${\ displaystyle \ alpha _ {i + l-1}}$	${\ displaystyle d_ {i} = br_ {i-1} + \ alpha _ {i + l-1}}$	${\ displaystyle \ beta _ {i}}$	${\ displaystyle r_ {i} = d_ {i} -m \ beta _ {i}}$	${\ displaystyle q_ {i} = bq_ {i-1} + \ beta _ {i}}$
0	2	${\ displaystyle 10 \ cdot 1 + 2 = 12}$	0	${\ displaystyle 12-37 \ cdot 0 = 12}$	${\ displaystyle 10 \ cdot 0 + 0 = 0}$
1	6	${\ displaystyle 10 \ cdot 12 + 6 = 126}$	3	${\ displaystyle 126-37 \ cdot 3 = 15}$	${\ displaystyle 10 \ cdot 0 + 3 = 3}$
2	0	${\ displaystyle 10 \ cdot 15 + 0 = 150}$	4	${\ displaystyle 150-37 \ cdot 4 = 2}$	${\ displaystyle 10 \ cdot 3 + 4 = 34}$
3	2	${\ displaystyle 10 \ cdot 2 + 2 = 22}$	0	${\ displaystyle 22-37 \ cdot 0 = 22}$	${\ displaystyle 10 \ cdot 34 + 0 = 340}$
4	5	${\ displaystyle 10 \ cdot 22 + 5 = 225}$	6	${\ displaystyle 225-37 \ cdot 6 = 3}$	${\ displaystyle 10 \ cdot 340 + 6 = 3406}$
5	7	${\ displaystyle 10 \ cdot 3 + 7 = 37}$	1	${\ displaystyle 37-37 \ cdot 1 = 0}$	${\ displaystyle 10 \ cdot 3406 + 1 = 34061}$

Assim, e . ${\ displaystyle q = 34061}$${\ displaystyle r = 0}$

Na base 16 , com e , os valores iniciais são e . ${\ displaystyle n = {\ text {f412df}}}$${\ displaystyle m = 12}$${\ displaystyle q _ {- 1} = 0}$${\ displaystyle r _ {- 1} = {\ text {f}}}$

${\ displaystyle 0 \ leq i \ leq kl}$	${\ displaystyle \ alpha _ {i + l-1}}$	${\ displaystyle d_ {i} = br_ {i-1} + \ alpha _ {i + l-1}}$	${\ displaystyle \ beta _ {i}}$	${\ displaystyle r_ {i} = d_ {i} -m \ beta _ {i}}$	${\ displaystyle q_ {i} = bq_ {i-1} + \ beta _ {i}}$
0	4	${\ displaystyle 10 \ cdot {\ text {f}} + 4 = {\ text {f4}}}$	${\ displaystyle {\ text {d}}}$	${\ displaystyle {\ text {f4}} - 12 \ cdot {\ text {d}} = {\ text {a}}}$	${\ displaystyle 10 \ cdot 0 + {\ text {d}} = {\ text {d}}}$
1	1	${\ displaystyle 10 \ cdot {\ text {a}} + 1 = {\ text {a1}}}$	8	${\ displaystyle {\ text {a1}} - 12 \ cdot 8 = 11}$	${\ displaystyle 10 \ cdot {\ text {d}} + 8 = {\ text {d8}}}$
2	2	${\ displaystyle 10 \ cdot 11 + 2 = 112}$	${\ displaystyle {\ text {f}}}$	${\ displaystyle 112-12 \ cdot {\ text {f}} = 4}$	${\ displaystyle 10 \ cdot {\ text {d8}} + {\ text {f}} = {\ text {d8f}}}$
3	${\ displaystyle {\ text {d}} = 13}$	${\ displaystyle 10 \ cdot 4 + {\ text {d}} = {\ text {4d}}}$	4	${\ displaystyle {\ text {4d}} - 12 \ cdot 4 = 5}$	${\ displaystyle 10 \ cdot {\ text {d8f}} + 4 = {\ text {d8f4}}}$
4	${\ displaystyle {\ text {f}} = 15}$	${\ displaystyle 10 \ cdot 5 + {\ text {f}} = {\ text {5f}}}$	5	${\ displaystyle {\ text {5f}} - 12 \ cdot 5 = 5}$	${\ displaystyle 10 \ cdot {\ text {d8f4}} + 5 = {\ text {d8f45}}}$

Assim, e . ${\ displaystyle q = {\ text {d8f45}}}$${\ displaystyle r = {\ text {5}}}$

Se não houver tabelas de adição , subtração ou multiplicação para a base b memorizadas, este algoritmo ainda funcionará se os números forem convertidos para decimais e no final forem convertidos de volta para a base b . Por exemplo, com o exemplo acima,

${\ displaystyle n = {\ text {f412df}} _ {16} = 15 \ cdot 16 ^ {5} +4 \ cdot 16 ^ {4} +1 \ cdot 16 ^ {3} +2 \ cdot 16 ^ { 2} +13 \ cdot 16 ^ {1} +15 \ cdot 16 ^ {0}}$

e

${\ displaystyle m = {\ text {12}} _ {16} = 1 \ cdot 16 ^ {1} +2 \ cdot 16 ^ {0} = 18}$

com . Os valores iniciais são e . ${\ displaystyle b = 16}$${\ displaystyle q _ {- 1} = 0}$${\ displaystyle r _ {- 1} = 15}$

${\ displaystyle 0 \ leq i \ leq kl}$	${\ displaystyle \ alpha _ {i + l-1}}$	${\ displaystyle d_ {i} = br_ {i-1} + \ alpha _ {i + l-1}}$	${\ displaystyle \ beta _ {i}}$	${\ displaystyle r_ {i} = d_ {i} -m \ beta _ {i}}$	${\ displaystyle q_ {i} = bq_ {i-1} + \ beta _ {i}}$
0	4	${\ displaystyle 16 \ cdot 15 + 4 = 244}$	${\ displaystyle 13 = {\ text {d}}}$	${\ displaystyle 244-18 \ cdot 13 = 10}$	${\ displaystyle 16 \ cdot 0 + 13 = 13}$
1	1	${\ displaystyle 16 \ cdot 10 + 1 = 161}$	8	${\ displaystyle 161-18 \ cdot 8 = 17}$	${\ displaystyle 16 \ cdot 13 + 8}$
2	2	${\ displaystyle 16 \ cdot 17 + 2 = 274}$	${\ displaystyle 15 = {\ text {f}}}$	${\ displaystyle 274-18 \ cdot 15 = 4}$	${\ displaystyle 16 \ cdot (16 \ cdot 13 + 8) + 15 = 16 ^ {2} \ cdot 13 + 16 \ cdot 8 + 15}$
3	${\ displaystyle {\ text {d}} = 13}$	${\ displaystyle 16 \ cdot 4 + 13 = 77}$	4	${\ displaystyle 77-18 \ cdot 4 = 5}$	${\ displaystyle 16 \ cdot (16 ^ {2} \ cdot 13 + 16 \ cdot 8 + 15) + 4 = 16 ^ {3} \ cdot 13 + 16 ^ {2} \ cdot 8 + 16 \ cdot 15 + 4 }$
4	${\ displaystyle {\ text {f}} = 15}$	${\ displaystyle 16 \ cdot 5 + 15 = 95}$	5	${\ displaystyle 95-18 \ cdot 5 = 5}$	${\ displaystyle 16 \ cdot (16 ^ {3} \ cdot 13 + 16 ^ {2} \ cdot 8 + 16 \ cdot 15 + 4 = 16 ^ {4} \ cdot 13 + 16 ^ {3} \ cdot 8+ 16 ^ {2} \ cdot 15 + 16 ^ {1} \ cdot 4 + 5}$

Assim, e . ${\ displaystyle q = 16 ^ {4} \ cdot 13 + 16 ^ {3} \ cdot 8 + 16 ^ {2} \ cdot 15 + 16 ^ {1} \ cdot 4 + 5 = {\ text {d8f45}} _ {16}}$${\ displaystyle r = 5 = {\ text {5}} _ {16}}$

Esse algoritmo pode ser feito usando o mesmo tipo de notações feitas em lápis e papel, conforme mostrado nas seções acima.

          d8f45 r. 5
    12 ) f412df
         ea
          a1
          90
          112
          10e
            4d
            48
             5f
             5a
              5

Quocientes racionais

Se o quociente não for restrito a um número inteiro, o algoritmo não termina por . Em vez disso, se então por definição. Se o resto for igual a zero em qualquer iteração, então o quociente é uma fração -adic e é representado como uma expansão decimal finita na notação posicional de base . Caso contrário, ainda é um número racional, mas não um racional -adic e, em vez disso, é representado como uma expansão decimal repetida infinita na notação posicional de base . ${\ displaystyle i> kl}$${\ displaystyle i> kl}$${\ displaystyle \ alpha _ {i} = 0}$${\ displaystyle r_ {i}}$${\ displaystyle b}$${\ displaystyle b}$${\ displaystyle b}$${\ displaystyle b}$

Divisão binária

O cálculo dentro do sistema numérico binário é mais simples, porque cada dígito no curso só pode ser 1 ou 0 - nenhuma multiplicação é necessária, pois a multiplicação por ambos resulta no mesmo número ou zero .

Se isso fosse em um computador, a multiplicação por 10 pode ser representada por um deslocamento de bits de 1 para a esquerda, e a descoberta se reduz à operação lógica , onde verdadeiro = 1 e falso = 0. Com cada iteração , as seguintes operações são feitas : ${\ displaystyle \ beta _ {i}}$ ${\ displaystyle d_ {i} \ geq m}$${\ displaystyle 0 \ leq i \ leq kl}$

${\ displaystyle {\ begin {alinhados} \ alpha _ {i + l-1} \ & {\ mathtt {=}} \ n \ {\ mathtt {\ &}} \ (1 \ {\ mathtt {<<} } \ (k + 1-il)) \\ d_ {i} \ & {\ mathtt {=}} \ r_ {i-1} \ {\ mathtt {<<}} \ 1+ \ alpha _ {i + l-1} \\\ beta _ {i} \ & {\ mathtt {=}} \ {\ mathtt {!}} (d_ {i} <m) \\ r_ {i} \ & {\ mathtt {= }} \ d_ {i} -m \ {\ mathtt {\ &}} \ \ beta _ {I} \\ q_ {i} \ & {\ mathtt {=}} \ q_ {i-1} \ {\ mathtt {<<}} \ 1+ \ beta _ {I} \ end {alinhado}}}$

Por exemplo, com e , os valores iniciais são e . ${\ displaystyle n = 10111001}$${\ displaystyle m = 1101}$${\ displaystyle q _ {- 1} = 0}$${\ displaystyle r _ {- 1} = 101}$

${\ displaystyle 0 \ leq i \ leq kl}$	${\ displaystyle \ alpha _ {i + l-1} \ {\ mathtt {=}} \ n \ {\ mathtt {\ &}} \ (1 \ {\ mathtt {<<}} \ (k + 1- il))}$	${\ displaystyle d_ {i} \ {\ mathtt {=}} \ r_ {i-1} \ {\ mathtt {<<}} \ 1+ \ alpha _ {i + l-1}}$	${\ displaystyle \ beta _ {i} \ {\ mathtt {=}} \! (d_ {i} <m)}$	${\ displaystyle r_ {i} \ {\ mathtt {=}} \ d_ {i} -m \ {\ mathtt {\ &}} \ \ beta _ {i}}$	${\ displaystyle q_ {i} \ {\ mathtt {=}} \ q_ {i-1} \ {\ mathtt {<<}} \ 1+ \ beta _ {i}}$
0	1	1011	0	1011 - 0 = 1011	0
1	1	10111	1	10111 - 1101 = 1010	1
10	0	10100	1	10100 - 1101 = 111	11
11	0	1110	1	1110 - 1101 = 1	111
100	1	11	0	11 - 0 = 11	1110

Assim, e . ${\ displaystyle q = 1110}$${\ displaystyle r = 11}$

atuação

Em cada iteração, a tarefa mais demorada é selecionar . Sabemos que existem valores possíveis, então podemos encontrar usando comparações . Cada comparação exigirá uma avaliação . Let Ser o número de dígitos no dividendo e ser o número de dígitos no divisor . O número de dígitos em . A multiplicação de é , portanto , e da mesma forma a subtração de . Portanto, é preciso selecionar . O restante do algoritmo são adição e da mudança de dígito e para o dígito à esquerda, e por isso leva tempo e da base , de modo que cada iteração leva , ou apenas . Para todos os dígitos, o algoritmo leva tempo , ou na base . ${\ displaystyle \ beta _ {i}}$${\ displaystyle b}$${\ displaystyle \ beta _ {i}}$ ${\ displaystyle O (\ log (b))}$${\ displaystyle d_ {i} -m \ beta _ {i}}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle l}$${\ displaystyle m}$${\ displaystyle d_ {i} \ leq l + 1}$${\ displaystyle m \ beta _ {i}}$${\ displaystyle O (l)}$${\ displaystyle d_ {i} -m \ beta _ {i}}$${\ displaystyle O (l \ log (b))}$${\ displaystyle \ beta _ {i}}$${\ displaystyle q_ {i}}$${\ displaystyle r_ {i}}$${\ displaystyle O (k)}$${\ displaystyle O (l)}$${\ displaystyle b}$${\ displaystyle O (l \ log (b) + k + l)}$${\ displaystyle O (l \ log (b) + k)}$${\ displaystyle k-l + 1}$${\ displaystyle O ((k-1) (l \ log (b) + k))}$${\ displaystyle O (kl \ log (b) + k ^ {2})}$${\ displaystyle b}$

Generalizações

Números racionais

A divisão longa de inteiros pode ser facilmente estendida para incluir dividendos não inteiros, desde que sejam racionais . Isso ocorre porque todo número racional tem uma expansão decimal recorrente . O procedimento também pode ser estendido para incluir divisores que têm uma expansão decimal finita ou final (isto é, frações decimais ). Nesse caso, o procedimento envolve a multiplicação do divisor e do dividendo pela potência de dez apropriada de modo que o novo divisor seja um inteiro - aproveitando o fato de que a  ÷  b = ( ca ) ÷ ( cb ) - e procedendo como acima.

Polinômios

Uma versão generalizada desse método chamada divisão longa polinomial também é usada para dividir polinômios (às vezes usando uma versão abreviada chamada divisão sintética ).

Veja também

• Algorismo
• Aritmética de precisão arbitrária
• Multiplicação e divisão egípcia
• Aritmética elementar
• Divisão de Fourier
• Divisão longa polinomial
• Mudança do algoritmo de raiz enésima - para encontrar a raiz quadrada ou qualquer enésima raiz de um número
• Divisão curta

Referências

links externos

• Algoritmo de Divisão Longa
• Divisão longa e lema de Euclides