Por que eu escolhi o método da potência de 10? #23

New issue

Open

opened 2025-07-27 09:23:31 -03:00 by blau_araujo · 1 comment

blau_araujo commented

2025-07-27 09:23:31 -03:00

Owner

Essa tabela mostra como o método de contagem pelas potências de 10 é mais eficiente do que o método das divisões sucessivas:

Operação	OpCode	Latência	Eficiência
Potência de 10	`imul r64, r64, imm`	~3–4 ciclos	Alta
Divisões por 10	`div r64`	~32–96 ciclos	Baixa

Eu estimei as latências com base neste PDF, muito utilizado na engenharia, para o modelo da minha CPU (Haswell), considerando possíveis variações em CPUs modernas.

Essa tabela mostra como o método de contagem pelas potências de 10 é mais eficiente do que o método das divisões sucessivas: | Operação | OpCode | Latência | Eficiência | |----------|---------|----------|------------| | **Potência de 10** | `imul r64, r64, imm` | ~3–4 ciclos | Alta | | **Divisões por 10** | `div r64` | ~32–96 ciclos | Baixa | Eu **estimei** as latências com base [neste PDF](https://www.agner.org/optimize/instruction_tables.pdf), muito utilizado na engenharia, para o modelo da minha CPU (Haswell), considerando possíveis variações em CPUs modernas.

👍 1

blau_araujo commented

2025-07-27 10:02:30 -03:00

Author

Owner

Uma preocupação com a potência de 10 poderia ser a possibilidade de overflow, mas estamos trabalhando com inteiros de 64 bits sem sinal, o que estabelece um limite de 2^64 - 1:

: 2^64 - 1
18446744073709551615

Este número tem 20 dígitos, o que significa que os expoentes da base 10 irão de 0 a 19, portanto:

: 10^19
10000000000000000000

Que é menor que 18446744073709551615:

: (10^19) < (2^64 - 1)
1 <-- verdadeiro

Nota: eu usei a minha calculadora em Bash e AWK, cawk, para obter esses resultados.

Uma preocupação com a potência de 10 poderia ser a possibilidade de *overflow*, mas estamos trabalhando com inteiros de 64 bits sem sinal, o que estabelece um limite de `2^64 - 1`: ``` : 2^64 - 1 18446744073709551615 ``` Este número tem 20 dígitos, o que significa que os expoentes da base 10 irão de `0` a `19`, portanto: ``` : 10^19 10000000000000000000 ``` Que é menor que `18446744073709551615`: ``` : (10^19) < (2^64 - 1) 1 <-- verdadeiro ``` **Nota:** eu usei a minha calculadora em Bash e AWK, cawk, para obter esses resultados.

No labels

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference: blau_araujo/pbn#23

No description provided.

Rows
Columns