Como a matemática fundamental é avaliada com eficiência pelas linguagens de programação?

22

À medida que me envolvo cada vez mais com a teoria por trás da programação, sinto-me fascinado e aturdido por coisas aparentemente simples. Percebo que minha compreensão da maioria dos processos fundamentais é justificada através da lógica circular

P : Como isso funciona?

A : Porque sim!

Eu odeio essa realização! Adoro o conhecimento e, além disso, adoro aprender, o que me leva à minha pergunta (embora seja ampla).

Questão:

Como os operadores matemáticos fundamentais são avaliados com linguagens de programação?

Como os métodos atuais foram aprimorados?

Exemplo

var = 5 * 5; 

Minha interpretação:

$num1 = 5; $num2 = 5; $num3 = 0;
while ($num2 > 0) {
    $num3 = $num3 + $num1;
    $num2 = $num2 - 1;
}
echo $num3;

Isso parece ser altamente ineficiente. Com fatores mais altos, esse método é muito lento, enquanto o método incorporado padrão é instantâneo. Como você simularia a multiplicação sem adicionar iterações?

var = 5 / 5;

Como isso é feito? Não consigo pensar em uma maneira de literalmente dividir 5 em 5 partes iguais.

var = 5 ^ 5; 

Iterações de iterações de adição? Minha interpretação:

$base = 5;
$mod = 5;
$num1 = $base;
while ($mod > 1) {

    $num2 = 5; $num3 = 0;
    while ($num2 > 0) {
        $num3 = $num3 + $num1;
        $num2 = $num2 - 1;
    }
    $num1 = $num3;
    $mod -=1;
}
echo $num3;

Novamente, isso é EXTREMAMENTE ineficiente, mas não consigo pensar em outra maneira de fazer isso. Essa mesma pergunta se estende a todas as funções matemáticas relacionadas que são tratadas automagicamente.

Korvin Szanto
fonte
1
Um pouco de história de fundo para mim, estou indo para a faculdade de ciências da computação e, mais tarde, na vida, para a teoria matemática, bem como possivelmente para a filosofia e a física teórica. Muitas aspirações, pouco tempo.
Korvin Szanto 26/09
10
É seguro presumir que você consultou todos os links de en.wikipedia.org/wiki/Category:Computer_arithmetic ?
JB King
2
Fundamentalmente, é semelhante a como você foi ensinado a fazer multiplicação de vários dígitos e divisão longa no ensino fundamental. Pegue um dígito de A, multiplique por B. Desloque por dez. Pegue o próximo dígito de A, multiplique por B. Repita para todos os dígitos, adicione todos juntos. Por ser binário, a multiplicação de um dígito é mais simples (é x0 ou x1) e, em vez de mudar por dez, você dobra. Divisão é semelhante.
Pergunte sobre Monica

Respostas:

35

Para realmente entender como a aritmética funciona dentro de um computador, você precisa ter programado em linguagem assembly. De preferência um com tamanho de palavra pequeno e sem instruções de multiplicação e divisão. Algo como o 6502.

No 6502, praticamente toda aritmética é feita em um registro chamado Accumulator. (Um registro é um local de memória especial dentro do processador que pode ser acessado rapidamente.) Portanto, para adicionar dois números, você carrega o primeiro número no Acumulador e depois o segundo número.

Mas isso é simplista demais. Como o 6502 é um processador de 8 bits, ele pode manipular números apenas de 0 a 255. Na maioria das vezes, você desejará poder trabalhar com números maiores. Você deve adicioná-los em pedaços, 8 bits por vez. O processador possui um sinalizador Carry que é definido quando o resultado da adição de dois números excede o acumulador. O processador adiciona isso ao fazer uma adição, para que possa ser usado para "carregar o 1", supondo que você comece com o byte de ordem mais baixa de um número. Uma adição de vários bytes no 6502 se parece com isso:

  1. Limpar bandeira de transporte (CLC)
  2. Carregar o byte de menor ordem do primeiro número (LDA, acumulador de carga)
  3. Adicione o byte de menor ordem do segundo número (ADC, adicione com carry)
  4. Armazene o byte de resultado de ordem mais baixa (STA, acumulador de loja)
  5. Repita as etapas 2 a 4 com bytes de ordem superior sucessivamente
  6. Se no final, o transporte estiver definido, você transbordou; tome as medidas apropriadas, como gerar uma mensagem de erro (BCS / BCC, ramificação se transportar definido / limpo)

A subtração é semelhante, exceto se você definir o transporte primeiro, use a instrução SBC em vez do ADC e, no final, o transporte ficará limpo se houver fluxo insuficiente.

Mas espere! E os números negativos? Bem, com o 6502, eles são armazenados em um formato chamado complemento de dois. Supondo que um número de 8 bits, -1 seja armazenado como 255, porque quando você adiciona 255 a algo, você recebe um a menos no Acumulador (mais um carry). -2 é armazenado como 254 e assim por diante, até -128, que é armazenado como 128. Portanto, para números inteiros assinados, metade do intervalo de 0 a 255 de um byte é usada para números positivos e metade para números negativos. (Essa convenção permite verificar o número alto de um número para ver se é negativo.)

Pense nisso como um relógio de 24 horas: adicionar 23 à hora resultará em uma hora uma hora antes (no dia seguinte). Então 23 é o equivalente modular do relógio a -1.

Quando você estiver usando mais de 1 byte, precisará usar números maiores para negativos. Por exemplo, números inteiros de 16 bits têm um intervalo de 0 a 65536. Portanto, 65535 é usado para representar -1, e assim por diante, porque adicionar 65535 a qualquer número resulta em um a menos (mais um carry).

No 6502, existem apenas quatro operações aritméticas: somar, subtrair, multiplicar por dois (deslocar para a esquerda) e dividir por dois (deslocar para a direita). A multiplicação e a divisão podem ser feitas usando apenas essas operações ao lidar em binário. Por exemplo, considere multiplicar 5 (binário 101) e 3 (binário 11). Como na multiplicação decimal longa, começamos com o dígito direito do multiplicador e multiplicamos 101 por 1, resultando em 101. Em seguida, deslocamos o multiplicando para a esquerda e multiplicamos 1010 por 1, resultando em 1010. Em seguida, adicionamos esses resultados, fornecendo 1111 ou 15. Como sempre multiplicamos por 1 ou 0, na verdade não multiplicamos; cada bit do multiplicador simplesmente serve como uma bandeira que indica se devemos adicionar ou não o multiplicando (deslocado).

Divisão é análoga à divisão longa manual usando divisores de teste, exceto em binário. Se você estiver dividindo por uma constante, é possível fazer isso de maneira análoga à subtração: em vez de dividir por X, você multiplica por uma representação pré-calculada de 1 / X que produz o resultado desejado mais um estouro. Ainda hoje, isso é mais rápido que a divisão.

Agora tente fazer matemática de ponto flutuante na montagem ou converter números de ponto flutuante em bons formatos de saída na montagem. E lembre-se, é 1979 e a velocidade do relógio é de 1 MHz, então você deve fazê-lo da maneira mais eficiente possível.

As coisas ainda funcionam praticamente assim hoje, exceto com tamanhos maiores de palavras e mais registros, e é claro que a maior parte da matemática é feita por hardware agora. Mas ainda é feito da mesma maneira fundamental. Se você adicionar o número de turnos e os acréscimos necessários para uma multiplicação, por exemplo, ele se correlacionará bastante bem com o número de ciclos necessários para uma instrução de multiplicação de hardware nos primeiros processadores com uma instrução como a 6809, onde foi executada no microcódigo da mesma maneira que você faria manualmente. (Se você tiver um orçamento maior de transistor, existem maneiras mais rápidas de fazer as trocas e as adições, para que os processadores modernos não executem essas operações sequencialmente e possam realizar multiplicações em apenas um ciclo.)

kindall
fonte
3
Ei, obrigado por sua explicação muito detalhada! É exatamente o que eu queria! Por estar no meu nível, muitas vezes você esquece que o que está apoiando você geralmente é mais complexo do que qualquer coisa que esteja fazendo. Essa é a razão exata pela qual eu quero estudar ciência da computação. Odeio o fato de que, se eu voltasse no tempo, não saberia nada do mundo mudar, apenas como formular uma instrução SQL adequada;) De qualquer forma, muito obrigado por dedicar seu tempo a escrever essa resposta, você me deu um testador de sabor sobre o que estou prestes a me aprofundar.
Korvin Szanto
7
discordo, a montagem ainda é muito alta; se você quiser saber como os computadores são aritméticos, é necessário analisar o hardware ou pelo menos os algoritmos de hardware
jk.
Eh. Depois que você souber que existem somadores e shifters, é tão fácil imaginá-los controlados por hardware quanto por software, e é mais fácil jogar com software.
kindall
4
-1. A multiplicação de hardware não é feita com mudanças e aumenta há quase três décadas, e muitas CPUs podem fazer uma multiplicação em um ciclo. Verifique o artigo da Wikipedia Binary Multiplierpara obter detalhes.
Mason Wheeler
24

No final, operações aritméticas básicas são feitas em hardware. Mais especificamente, na CPU (ou na verdade, uma subparte dela)

Em outras palavras, são circuitos eletrônicos. Defina os bits apropriados como entrada e você obterá os bits apropriados como saída. É uma combinação de portas lógicas básicas.

http://en.wikipedia.org/wiki/Adder_%28electronics%29

http://en.wikipedia.org/wiki/Binary_multiplier

dagnelies
fonte
3
Os algoritmos para o hardware são cuidadosamente especificados e podem ser estudados separadamente do hardware.
S.Lott
@ S.Lott: Acho o seu comentário confuso. Para mim, os algoritmos envolvem uma série de etapas que você segue, um procedimento, algo que você pode programar. Aqui, estamos falando de circuitos eletrônicos executando as operações aritméticas básicas. Em outras palavras, apenas uma sequência de portas onde a corrente flui. Portanto, é mais "lógico" do que "algorítmico", na melhor das hipóteses. ... meus 2 centavos.
Dagnelies
6
Um algoritmo é "finito, definido e eficaz". Pode ser em circuitos, ou feito com papel e lápis, ou com Tinkertoys ou moléculas em um prato ou DNA. Algoritmo pode ser qualquer coisa. Um circuito eletrônico deve seguir um algoritmo definido. Magicamente, não passa pela necessidade de algoritmos.
S.Lott 27/09
1
Um processo que consistisse em apenas uma etapa seria considerado um "algoritmo"? Em geral, os circuitos eletrônicos seguem uma tabela de verdade - um processamento em uma única etapa. O fato de a tabela da verdade acabar sendo "compilada" em portões de várias camadas não nega o fato de que é um processo de etapa única.
Slebetman
2
@ S.Lott: Um primeiro comentário mais apropriado seria: a "lógica" do hardware é cuidadosamente especificada e pode ser estudada separadamente do hardware. E de fato é. O estudo da lógica binária é chamado Álgebra Booleana.
Slebetman
6

Tudo isso é coberto com paciência em The Art of Computer Programming, de Don Knuth.

Algoritmos eficientes para adicionar, subtrair, multiplicar e dividir são todos descritos em detalhes completos.

Você pode ler coisas como esta que cobrem bem a divisão.

http://research.microsoft.com/pubs/151917/divmodnote.pdf

S.Lott
fonte
5

É feito em picossegundos por circuitos eletrônicos. Google 'multiplicador de hardware' etc. para obter detalhes. As CPUs modernas são o resultado extremamente complexo de décadas de melhoria contínua.

BTW, Como você não se multiplica por adição repetida, por que você imaginaria que um computador faria?

Kevin Cline
fonte
Minha pergunta é sobre o raciocínio por trás das funções, e não as próprias funções, eu entendo que é interpretado pelo processador, estou curioso em saber como. Especificamente, a teoria por trás dela e como ela pode ser replicada em pseudo-código.
Korvin Szanto 26/09
1
A multiplicação que faço na minha cabeça é memória. Também a multiplicação longa requer iteração da maneira que eu fiz isso. Eu vou em frente e jogar juntos uma função por muito tempo multiplicação
Korvin Szanto
2
@Korvin, o livro que recomendei será útil se esse for o seu interesse. Eu também recomendo "Estrutura e Interpretação de Programas de Computador", de Harold Abelson e Gerald Jay Sussman. Ele lida com essas questões em profundidade.
Jonathan Henson
Vários computadores antigos eram compatíveis apenas com adição e subtração. Alguns apenas subtração suportada! Portanto, a operação x = y * z foi implementada da mesma forma que (z vezes) {x + y} da mesma forma a divisão x = y / z foi implementada como enquanto (y> z) {x + 1; y = y - z}
James Anderson
@ James: eles apoiaram turno? Eu esperaria que a multiplicação fosse feita por turno e adição, enquanto a divisão era turno, comparação, subtração.
kevin Cline
4

Isso não pretende ser uma resposta completa de forma alguma, mas deve lhe dar uma idéia de como as coisas são implementadas. Como você provavelmente sabe, os números são representados em binário. Por exemplo, um computador pode representar o número 5 como 00000101. Uma operação muito básica que um computador pode fazer é deslocar para a esquerda, o que daria 00001010 que é decimal 10. Se fosse o deslocador direito duas vezes, seria 00010100 (decimal 20). Toda vez que mudamos os dígitos para a esquerda 1 vez dobramos o número. Digamos que eu tenha um número x e que eu queira multiplicá-lo por 17. Eu poderia mudar x para a esquerda 4 vezes e depois adicionar x ao resultado (16x + x = 17x). Essa seria uma maneira eficiente de multiplicar um número por 17. Isso deve lhe dar algumas dicas sobre como um computador pode multiplicar números grandes sem usar apenas a adição repetida.

A divisão pode usar combinações de adição, subtração, deslocamento para a direita, deslocamento para a esquerda, etc. Existem também vários truques para aumentar o número de expoentes.

WuHoUnited
fonte
Só para esclarecer, geralmente você pode mudar mais de um bit por vez. Então, essas 4 operações de mudança são realmente apenas uma operação, como: shl r0, 4.
Caleb
4

Quando eu era criança, aprendi a multiplicar e dividir com uma caneta e um papel, sem perder tempo com muitas adições. Mais tarde, aprendi que as raízes quadradas também são computáveis ​​dessa maneira.

Na universidade, aprendi a calcular operações trigonométricas e logarítmicas com uma dúzia de multiplicações, divisões e adições. Eles chamaram de série Taylor.

Antes disso, meu pai me deu um livro onde essas operações complexas já eram computadas para centenas de valores e apresentadas em tabelas. Havia também algumas explicações para estimar o erro quando você desejava o seno de um valor entre dois valores calculados.

Unidades inteiras, unidades de ponto flutuante, GPU e DSP apenas implementam todas essas técnicas antigas em silício.

mouviciel
fonte
3

Tentarei dar uma idéia de como os circuitos digitais são projetados para resolver problemas de processamento digital usando os problemas que você apresenta: como as CPUs implementam adições e multiplicações.

Primeiro, vamos tirar a questão direta do caminho: como uma linguagem de programação avalia eficientemente multiplicações e acréscimos. A resposta é simples, eles os compilam para multiplicar e adicionar instruções. Por exemplo, o seguinte código:

a = 1 + 1;
b = a * 20;

é simplesmente compilado para algo como:

ADD 1 1  a
MUL a 20 b

(observe que o assembly acima é para uma CPU imaginária que não existe, por uma questão de simplicidade).

Nesse ponto, você percebe que a resposta acima simplesmente muda o problema e o resolve pela mágica do hardware. A pergunta seguinte é obviamente como essa mágica de hardware funciona?

Vamos analisar primeiro o problema mais simples: adição.

Primeiro, fazemos um problema familiar, adicionando regularmente números de base 10:

 17
+28

O primeiro passo seria adicionar 7 e 8. Mas isso resulta em 15, que é mais do que um único dígito. Então, carregamos o 1:

(1)
 17
+28
= 5

Agora adicionamos 1, 1 e 2 juntos:

 17
+28
=45

Então, a partir disso, obtemos as seguintes regras:

  1. quando o resultado da adição é superior a um dígito, mantemos o dígito menos significativo e avançamos com o dígito mais significativo

  2. se temos um dígito transportado para a nossa coluna, o adicionamos juntamente com os números que estamos adicionando

Agora é hora de interpretar as regras acima na base 2 - álgebra booleana.

Assim, na álgebra booleana, adicionando 0 e 1 juntos = 1. Adicionando 0 e 0 = 0. E adicionando 1 e 1 = 10, que é mais de um dígito, para que continuemos com o 1.

A partir disso, podemos construir uma tabela de verdade:

a b  |  sum  carry
-------------------
0 0  |   0     0
0 1  |   1     0
1 0  |   1     0
1 1  |   0     1

A partir disso, podemos construir dois circuitos / equações booleanas - uma para a saída da soma e outra para a saída do carry. A maneira mais ingênua é simplesmente listar todas as entradas. Qualquer tabela verdade, não importa quão grande e complexa possa ser reapresentada desta forma:

(AND inputs in first row) OR (AND of inputs in second row) OR ...

Esta é basicamente a soma da forma dos produtos. Nós olhamos apenas as saídas que resultam em 1 e ignoramos os 0s:

sum = (NOT a AND b) OR (a AND NOT b)

Vamos substituir AND e NOT por símbolos da linguagem de programação para facilitar a leitura:

sum = (!a & b) | (a & !b)

Basicamente, convertemos a tabela da seguinte maneira:

a b  |  sum  equation
-------------------
0 0  |   0   
0 1  |   1   (!a & b)
1 0  |   1   (a & !b)
1 1  |   0   

Isso pode ser implementado diretamente como um circuito:

                _____
 a ------------|     |
    \          | AND |-.     ____
     \  ,-NOT--|_____|  \   |    |
      \/                 `--| OR |----- sum
      /\        _____    ,--|____|
     /  `-NOT--|     |  /
    /          | AND |-`
 b ------------|_____|

Os leitores observadores nesse momento perceberiam que a lógica acima pode realmente ser implementada como uma única porta - uma porta XOR que possui convenientemente o comportamento exigido por nossa tabela de verdade:

                _____
 a ------------|     |
               | XOR |---- sum
 b ------------|_____|

Mas se o seu hardware não fornecer um portão XOR, as etapas acima são como definir e implementar em termos de portas AND, OR e NOT.

Como você converteria portas lógicas em hardware real depende do hardware que você possui. Eles podem ser implementados usando vários mecanismos físicos, desde que o mecanismo forneça algum tipo de comportamento de comutação. Os portões lógicos foram implementados com tudo, desde jatos de água ou sopros de ar (fluídicos) a transisitores (eletrônicos) a bolas de gude caindo. É um grande tópico por si só, então vou descrevê-lo e dizer que é possível implementar portas lógicas como dispositivos físicos.

Agora fazemos o mesmo para o sinal de transporte. Como existe apenas uma condição em que o sinal de transporte é verdadeiro, a equação é simplesmente:

carry = a & b

Portanto, carregar é simples:

                _____
 a ------------|     |
               | AND |---- carry
 b ------------|_____|

Combinando-os, obtemos o que é conhecido como meio adicionador:

                _____
 a ------;-----|     |
         |     | XOR |---- sum
 b --;---|-----|_____|
     |   |      _____
     |   '-----|     |
     |         | AND |---- carry
     '---------|_____|

As equações para o circuito acima, a propósito, são assim:

sum = a ^ b
carry = a & b

O meio adicionador está faltando alguma coisa. Implementamos a primeira regra - se o resultado for mais de um dígito do que transportar, mas não implementamos a segunda regra - se houver um transportador, adicione-o juntamente com os números.

Portanto, para implementar um somador completo, um circuito de adição que pode adicionar números com mais de um dígito, precisamos definir uma tabela verdade:

a b c  |  sum  carry
---------------------
0 0 0  |   0     0
0 0 1  |   1     0
0 1 0  |   1     0
0 1 1  |   0     1
1 0 0  |   1     0
1 0 1  |   0     1
1 1 0  |   0     1
1 1 1  |   1     1

A equação da soma é agora:

sum = (!a & !b & c) | (!a & b & !c) | (a & !b & !c) | (a & b & c)

Podemos passar pelo mesmo processo de fatorar e simplificar a equação e interpretá-la como um circuito etc., como fizemos acima, mas acho que essa resposta está ficando muito longa.

Agora você deve ter uma idéia de como a lógica digital é projetada. Existem outros truques que não mencionei, como mapas de Karnaugh (usados ​​para simplificar tabelas verdadeiras) e compiladores lógicos, como café expresso (para que você não precise fatorar equações booleanas à mão), mas o básico é basicamente o que eu tenho. descrito acima:

  1. Decomponha o problema até poder trabalhar no nível de bit único (dígito).

  2. Defina as saídas que você deseja usando uma tabela verdade.

  3. Converta a tabela em uma equação booleana e simplifique a equação.

  4. Interprete a equação como portas lógicas.

  5. Converta seu circuito lógico em circuitos reais de hardware implementando portas lógicas.

É assim que os problemas fundamentais (ou melhor, de baixo nível) são realmente resolvidos - muitas e muitas tabelas verdadeiras. O verdadeiro trabalho criativo está no detalhamento de uma tarefa complexa, como decodificação de MP3 no nível de bits, para que você possa trabalhar com tabelas verdadeiras.

Desculpe, não tenho tempo para explicar como implementar a multiplicação. Você pode tentar entender um pouco sobre isso, descobrindo regras de quanto tempo a multiplicação funciona e depois interpretando-a em binário, e tente dividi-la em tabelas verdadeiras. Ou você pode ler a Wikipedia: http://en.wikipedia.org/wiki/Binary_multiplier

slebetman
fonte
2

instruções aritméticas básicas são executadas com instruções de montagem que são altamente eficientes.

Instruções mais complexas (ou abstratas) são feitas em montagem com mecanismos de loop ou são tratadas em bibliotecas std.

Ao estudar matemática na faculdade, você começará a estudar coisas como o cálculo Lambda e a notação Big-O. Tudo isso, e muito mais, é usado pelos programadores para avaliar e criar algoritmos eficientes. De qualquer forma, o material básico geralmente é realizado em nível inferior, como na montagem ou em c com ponteiros.

Uma ótima introdução a esse tópico é "Code", de Charles Petzold.

Jonathan Henson
fonte
1
Ou tabelas de pesquisa. Muito mais rápido para precomputar valores e procurá-los. Exemplos Sin / Cos / Tan (divisão inteira, embora isso seja pré-calculado e armazenado no hardware).
Martin York
1

Obtenha um livro como Fundamentals of Digital Logic ... , que eu acho que ainda é bastante padrão para os alunos do Freshman / Sophomore EE, e trabalhe nele (ed: custa uma pequena fortuna, procure uma edição usada ou anterior de isto). Isso o guiará pelos somadores e multiplicadores e fornecerá um histórico suficiente para começar a entender alguns dos princípios por trás do que o hardware está fazendo.

Sua resposta, no curto prazo, se tornará "porque combina várias peças de lógica mais simples para evocar esse comportamento complexo" em vez de "porque o faz".

Se você quiser tentar entender todos os princípios de como os programas são compilados e executados, faça isso em conjunto, para que você possa ver como tudo se encontra no meio.

jonsca
fonte
1

Há muitas boas respostas aqui. Você também começou com a idéia certa: operações complexas como multiplicação são criadas a partir de operações mais simples. Como você adivinhou, existem maneiras mais rápidas de multiplicar sem uma instrução de multiplicação do que usar uma série de adições. Qualquer multiplicação pode ser implementada como a soma de multiplicações menores ou como uma combinação de turnos e adições. Exemplos:

a = 5 + 5 + 5 + 5 + 5;           // 5*5, but takes 5 operations
b = (5 << 2) + 5;                // 5*5 in only 2 operations
c = (41 << 4) + (41 << 2) + 41   // 41*21 in 4 operations

A divisão também pode ser dividida em operações menores. XOR (^) é uma instrução embutida em todos os processadores que eu já vi, mas mesmo assim ele pode ser implementado como uma combinação de AND, OR e NOT.

No entanto, sinto que respostas específicas serão menos satisfatórias para você do que uma idéia geral dos tipos de instruções que um processador fornece e como essas instruções podem ser combinadas em operações mais complexas. Não há nada melhor para esse tipo de curiosidade do que uma dose saudável de linguagem assembly. Aqui está uma introdução muito acessível à linguagem assembly MIPS.

Caleb
fonte
1

Veja como um processador moderno pode implementar a multiplicação de dois números inteiros de 64 bits:

Você sabe como fazer uma multiplicação de mão longa. Para multiplicar dois números de 10 dígitos, multiplique um número de 10 dígitos por cada um dos 10 dígitos do outro número, escreva o resultado de 11 dígitos um abaixo do outro e desloque-o e depois adicione todo o número.

Um processador moderno faz isso com todos os 64 por 64 bits. No entanto, uma multiplicação de dois números de bit único é muito simples: 1 x 1 = 1, todos os outros produtos são zero. Isso é implementado com uma lógica e. E, diferentemente do produto decimal, em que o resultado pode ter dois dígitos, um produto binário de números de bits únicos é sempre um bit.

Então agora você tem 64 linhas de 64 bits que precisam ser adicionadas. Mas 64 adições de números de 64 bits são slooooooow. Portanto, o processador usa um somador de 3/2 ou um somador de 7/3: se você adicionar três números de bit único, o resultado poderá ser 0, 1, 2 ou 3, o que se encaixa em dois bits. Se você adicionar 7 números de bit único, o resultado será um número de 0 a 7, que pode ser representado por 3 bits. A IBM afirma que eles podem criar um somador 7/3 com apenas 18 circuitos primitivos (documentação do PowerPC), aposto que a Intel e o ARM também podem fazer isso.

Você tem 4096 bits, agrupe-os em cerca de 600 grupos de 7 bits nas mesmas posições de bits e use cerca de 600 somadores 7/3 para reduzir o resultado de 4096 bits para menos de 2.000. Então você faz o mesmo novamente, e novamente, até acabar com pares de bits que podem ser alimentados em um somador completo comum.

gnasher729
fonte