Lagarta Azul: Bem, você não vai nos derrubar. Sentamo-nos, sabemos: eles estão esperando nossa transformação. O que? Mas nada! Sentamos, fumamos, esperamos ...
Boneca Alice: O que?
Lagarta Azul: O quê, por quê! De transformações. A casa em fumaça, a fumaça em uma dama, e a dama em uma mãe. Lá vai você. Não interfira, não pule para a frente, caso contrário você mesmo se transformará prematuramente em algum tipo de borboleta.
Examinando o código em um dos fóruns dedicados ao Arduino, encontrei uma maneira divertida de trabalhar com um número de ponto flutuante (PT). O segundo nome comum para números nesse formato é ponto flutuante, mas a abreviação (PP) que surge nesse caso pessoalmente causa associações completamente diferentes para mim; portanto, usaremos essa opção. A primeira impressão (do código que vi) é que tipo de lixo está escrito aqui (devo dizer que o segundo é o mesmo, embora haja nuances, mas mais sobre isso depois), mas surge a pergunta - como é realmente necessário - a resposta dada em texto adicional.
Parte Um - Questionando
Formulamos o problema - precisamos imprimir no console (transformar em uma representação simbólica) um número de ponto flutuante, sem usar as opções de impressão destinadas a esse fim. Por que queremos fazer isso sozinhos -
- o uso do formato% f implica conectar a biblioteca para trabalhar com um ponto flutuante e uma versão estendida da função prntf (ou melhor, torna impossível o uso da versão truncada), o que leva a um aumento significativo no tamanho do módulo executável,
- uma solução padrão requer um tempo considerável (sempre funciona com um número de precisão duplo), o que pode ser inaceitável nessa situação específica,
- Bem (por último, mas não menos importante), é apenas interessante.
Para começar, considere a opção proposta no material acima, algo como:
for (float Power10=10000.0; Power10>0.1; Power10/=10.0; ) {char c=(int)(Fdata/Power10); Fdata -=Power10*c; };
e concordamos que ele resolve completamente o problema. Além disso, essa não é uma opção ruim, pois sua velocidade pode ser bastante aceitável. Vamos dar uma olhada mais de perto neste momento - vemos a divisão dos números PT, mas se aprofundarmos na essência da questão, acontece que é quase tão rápido quanto a divisão de números inteiros da profundidade de bits correspondente. De fato, antes de avaliar o desempenho do algoritmo, você deve avaliar o desempenho de várias operações elementares, o que faremos.
Parte Dois - Avaliação de Desempenho de Operações Elementares
A primeira operação interessante é a adição (subtração, no sentido de tempo gasto, eles são equivalentes) de números inteiros e podemos assumir que leva uma unidade de tempo (ciclo do relógio) com a seguinte ressalva - isso é verdade apenas para dados "nativos". Por exemplo, para a série MK AVR, é uma palavra de 8 bits, para MSP430 é uma palavra de 16 bits (e, é claro, menor em tamanho), para Cortex-M é uma palavra de 32 bits e assim por diante. Então, a operação de adicionar números com um comprimento de H vezes mais do que o nativo pode ser estimada como ciclos de H. Há exceções, por exemplo, AddW em controladores AVR, mas não cancela a regra.
A próxima operação é a multiplicação de números inteiros (mas não a divisão, difere em termos de velocidade) e, para ele, nem tudo é tão simples. Em primeiro lugar, a multiplicação pode ser implementada em hardware e, por exemplo, no AVR MEGA, são necessários 2 ciclos de clock e, nos 51 aprimorados, até 6 (para multiplicar números nativos).
Mas considere o caso em que não há implementação de hardware e precisamos implementar a multiplicação na forma de uma sub-rotina. Como ao multiplicar números de bits H, um produto de 2H é obtido, a estimativa da versão clássica com turnos pode ser encontrada da seguinte forma: precisamos de turnos H do fator com 1 ciclo de clock por turno, turnos H do segundo fator com um comprimento de 2 H com 2 ciclos de clock por turno, então H tomará decisões e , em média, N / 2 adições de números com duração de 2H, em conclusão, a organização de um ciclo de 2 medidas. Total de + 2 + + 2 / 2 + 2 = 7 ticks, e realmente executar operações aritméticas a partir deles leva apenas N ticks (uau eficiência, embora tenhamos conseguido contornar o motor).
Ou seja, para multiplicar dois números 8p por 8p MK, são necessários 56 ciclos e para multiplicar números 16p já existem 112 ciclos (um pouco menos, mas negligenciamos o valor exato) ciclos, o que é um pouco mais do que queríamos. Felizmente, a direção dos turnos pode ser modificada e existe uma maneira única de multiplicação, que exigirá apenas turnos H do número de dígitos 2H e adições H / 2 de números nativos, o que melhora o tempo de operação do algoritmo de multiplicação para 0 + 2 + 1 + 1/2 + 2 = 5,5 - é claro, não pode ser comparado com a implementação de hardware, mas pelo menos algum ganho sem perda de funcionalidade. Há melhorias nesse algoritmo, por exemplo, a análise de 2 bits por ciclo, mas eles não alteram drasticamente a situação - o tempo de multiplicação por ordens de grandeza excede o tempo de adição.
Mas com a divisão, a situação é pior - até a divisão implementada por hardware perde quase o dobro da multiplicação, e existem MKs com multiplicação de hardware, mas sem divisão de hardware. Sob certas condições, a divisão pode ser substituída pela multiplicação pela recíproca, mas essas condições são específicas e dão um resultado semelhante - são necessárias duas iterações de multiplicação seguidas da soma, portanto a perda é 2 vezes. Se implementarmos a divisão como um subprograma, H muda do divisor 2H de comprimento, H subtrações do divisível 2H de comprimento, H muda do resultado, é necessária a organização do ciclo 2H, mas tudo isso é precedido pelo alinhamento, que levará mais 5H ciclos, portanto, o número total é 2 + 2 + 1 + 2 + 5 = 12, que é cerca de 2 vezes pior que a multiplicação.
Bem, agora vamos considerar as operações de PT, e aqui a situação é um pouco paradoxal - a operação de multiplicação requer quase tanto tempo quanto os números inteiros (correspondendo à capacidade de bits, via de regra, 24 bits), pois precisamos multiplicar a mantissa e apenas adicionar as ordens, a normalização não necessário. Com a divisão também é boa, divida a mantissa e subtraia as ordens, a normalização novamente não é necessária. Portanto, para essas duas operações, a perda comparada aos números inteiros não é muito significativa, embora tenha um lugar.
Mas a operação de adição e subtração requer, antes de tudo, o alinhamento das ordens (e essas são mudanças e podem haver muitas, embora haja nuances), depois as próprias operações e (ao subtrair) a normalização (ao adicionar também, mas não é necessário mais do que 1 mudança) ), o que é um desperdício de tempo; portanto, as operações dessa classe para PT são muito mais lentas que para números inteiros, especialmente em termos relativos.
Vamos voltar às nossas ovelhas e concordar que, com base nas estimativas anteriores, o método proposto pode não ser muito longo, especialmente porque fornece o resultado imediatamente, mas tem uma limitação significativa - é aplicável a uma faixa muito limitada de valores de PT de entrada. Portanto, buscará uma solução universal (mais ou menos).
Imediatamente, faça uma reserva de que nossa solução não deve usar operações de ponto flutuante em geral (a partir da palavra) para enfatizar o mérito de nossa opção. E para a pergunta perplexa de como um número desse tipo aparecerá se as operações não estiverem disponíveis, respondemos - pode aparecer, por exemplo, ao ler informações de um sensor de luz (como no exemplo original), que produz dados no formato PT.
Como exatamente o número de PTs é organizado, você pode encontrar facilmente em vários sites, houve um artigo recente sobre Habré, não deve haver nenhum problema com isso. No entanto, várias questões são de interesse para o formato PT no estilo “se eu fosse o diretor” - por que isso é assim e não o contrário. Vou dar respostas a algumas delas, se alguém souber mais, por favor, comente.
A primeira pergunta é por que a mantissa é armazenada em código direto e não em código adicional? Minha resposta é porque é mais fácil trabalhar com uma mantissa normalizada com um bit oculto (opcional).
A segunda pergunta é por que o pedido é armazenado com um deslocamento, e não o contrário? Minha resposta é que, neste caso, é fácil comparar os módulos de dois PTs como números inteiros, com outros métodos é mais complicado.
A terceira pergunta é por que o sinal negativo é codificado por um em vez de zero, porque então seria possível simplesmente comparar os dois pontos como números inteiros? Minha resposta é que eu não sei, é apenas "é tão aceito aqui".
Parte Três - Explicações Exigidas
No parágrafo anterior, eu poderia fornecer termos incompreensíveis, um pouco sobre a representação de números. Claro, eles são diferentes, caso contrário não haveria necessidade de discuti-los. Imediatamente, observamos que na memória do MK (o mesmo se aplica aos computadores, embora eu não seja tão categórico quanto às arquiteturas mais modernas - elas são tão complicadas que tudo pode ser esperado), não há números, existem apenas unidades de armazenamento elementares - bits agrupados em bytes e mais em palavras. Quando falamos sobre a representação de um número, significa que interpretamos um conjunto de bits de um comprimento específico de uma maneira ou de outra, ou seja, estabelecemos uma lei pela qual podemos encontrar um determinado número correspondente a um determinado conjunto de bits e nada mais.
Inúmeras leis podem ser inventadas, mas algumas delas terão várias propriedades úteis em termos de realização de várias operações, de modo que serão aplicadas com mais frequência na prática. Uma dessas propriedades, implicitamente implícita, por exemplo, é o determinismo, e a outra é a independência do ambiente - propriedades que, à primeira vista, são óbvias, embora haja nuances. Outras propriedades do tipo de correspondência um-para-um já são objeto de discussão e nem sempre ocorrem em uma representação concreta. O tópico de representar números em si é extraordinariamente fascinante; para Knut (no Volume Dois), ele é totalmente divulgado, de modo que vai além das profundezas, e nós atravessamos a superfície.
Supondo que o conjunto de bits tenha um comprimento n (nós os numeramos em uma linha de 0 a n-1) e seja ponderado uniformemente com uma etapa de 2 e o bit menos significativo (com o número 0) tenha um peso de 1 (que, de um modo geral, não é necessário, apenas Nós nos acostumamos a essas coisas, e elas parecem óbvias para nós), obtemos uma representação binária do número, na qual a fórmula de redução é assim: o número exibido pelo conjunto de bits
(2) = (0)*2^0 + (1)*2^1 + ... + (-1)*2^(-1) ou em forma de cascata
2() = (0)+2*((1)+2*(...+2*((-1))..))) , a seguir, B (k) denota um pouco com o número k. Observe que em uma visão diferente não impõe restrições à localização do número de bytes na memória, mas seria mais lógico colocar o byte baixo nos endereços mais baixos (é assim que fácil e naturalmente eu resolvi o "argumento eterno dos eslavos entre si" sobre qual extremidade é mais conveniente para quebrar um ovo).
Com esta interpretação de um conjunto de bits de comprimento n (= 8), obtemos uma representação para números de 0 a (2 ^ n) -1 (= 255) (daqui em diante, entre parênteses, haverá um valor específico para um conjunto de 8 bits), que possui várias notáveis e propriedades úteis, razão pela qual se tornou generalizada. Infelizmente, ele também tem várias desvantagens, uma das quais é que não podemos representar números negativos em um registro como esse em princípio.
Você pode oferecer uma variedade de soluções para esse problema (a representação de números negativos), entre as quais também há importância prática, elas estão listadas abaixo.
Uma representação com um deslocamento é descrita pela fórmula H = N2 (n) - deslocamento (C), onde N2 é o número obtido em notação binária com n bits e C é um valor pré-selecionado. Em seguida, representamos números de 0-C a 2 ^ (n) -1-C, e se escolhermos C = 2 ^ (n-1) -1 (= 127) (isso é totalmente opcional, mas muito conveniente), então obtemos o intervalo de 0- (2 ^ (n-1) -1) (= - 127) a 2 ^ (n-1) (= 128). A principal vantagem dessa representação é a monotonia (além disso, aumento) ao longo de todo o intervalo, também existem desvantagens, dentre as quais destacamos a assimetria (existem outras relacionadas à complexidade de executar operações no número nessa representação), mas os desenvolvedores do padrão IEEE 457 (este é o padrão para O PT) transformou essa falha em virtude (usando um valor extra para codificar a situação nan), que mais uma vez enfatiza a fidelidade do ditado legal: “Se você é superior ao oponente, essa é sua vantagem. Se o adversário é mais alto que você, essa também é sua vantagem.
Observe que, como o número total de combinações possíveis de qualquer número de bits é par (se você não tiver combinações proibidas por razões religiosas), a simetria entre números representáveis positivos e negativos é fundamentalmente inatingível (ou melhor, alcançável, mas sob certas condições adicionais, sobre as quais ainda mais) .
Representação na forma de um código direto quando um dos bits (mais significativo) representa o sinal codificado do número H = (-1) ^ B (n-1) * P2 (n-1) tem um intervalo de 0- (2 ^ (n-1) -1) (= -127) a 2 ^ (n-1) -1 (= 127). É interessante notar que acabei de declarar a impossibilidade fundamental de simetria, e aqui está claramente: o número positivo máximo representável é igual ao módulo do número negativo mínimo representável. Esse resultado é alcançado tendo duas representações para zero (00 ... 00 e 10 ... 00), o que geralmente é considerado a principal desvantagem desse método. Isso é realmente uma desvantagem, mas não tão terrível quanto se acredita, já que existem outras mais significativas que limitaram seu uso.
A representação do código inverso, quando na representação direta invertemos todos os bits do valor para números negativos H = (1-B (n-1)) * P2 (n-1) + B (n-1) * (2 ^ (n -1) -CH2 (n-1)) - isto é da definição, você pode fazer uma fórmula muito mais compreensível H = Ch2 (n-1) -B (n-1) * (2 ^ (n-1) -1), o que nos permite representar números de 0-2 ^ (n-1) +1 (= - 127) a 2 ^ (n-1) -1 (= 127). Pode-se ver que essa representação é deslocada, mas o deslocamento muda gradualmente, o que torna essa representação não monotônica. Novamente, temos dois zeros, o que não é muito assustador, a ocorrência de transferência circular durante a adição é muito pior, o que cria certos problemas na implementação da ALU.
Para eliminar a última desvantagem da representação anterior, é extraordinariamente simples, basta alterar o deslocamento por um, obtemos = = 22 (n-1) -B (n-1) * 2 ^ (n-1) e podemos representar números de 0-2 ^ ( n-1) (= - 128) a 2 ^ (n-1) -1 (= 127). É fácil ver que a representação é assimétrica, mas zero é único. Significativamente mais interessante é a propriedade a seguir, “é completamente óbvio que” a transferência de anel não ocorre para uma operação do tipo adição, que é a razão (junto com outros recursos agradáveis) da distribuição universal desse método específico de codificação de números negativos.
Vamos elaborar uma tabela de valores interessantes para vários métodos de codificação de números, denotando por H o valor 2 ^ (n-1) (128)
| Bits | 00..00 | 11/01 | 10..00 | 11.11 |
|---|
| H (n) | 0 0 | H-1 (127) | H (128) | 2 * H-1 (255) |
| H (n-1) | 0 0 | H-1 (127) | 0 0 | H-1 (127) |
| Deslocamento. N | -H + 1 (-127) | 0 0 | 1 | H (128) |
| Direto | 0 0 | H-1 (127) | 0 0 | -H + 1 (-127) |
| Reverse | 0 0 | H-1 (127) | -H + 1 (-127) | 0 0 |
| Adição | 0 0 | H-1 (127) | -H (-128) | -1 |
Bem, para concluir o tópico, fornecemos gráficos para as representações listadas, a partir das quais suas vantagens e desvantagens são imediatamente visíveis (é claro, nem tudo o que faz lembrar o ditado interessante "A vantagem da apresentação gráfica da informação é visual, não tem outras vantagens").
Parte Quatro - Realmente resolvendo o problema original (antes tarde do que nunca).
Pequena digressão
Para começar, eu queria imprimir o PT em formato hexadecimal (e finalmente o fiz), mas de maneira inesperada / completamente inesperada (necessário substituir), me deparei com o seguinte resultado. O que você acha que será impresso como resultado da execução dos operadores:
printf("%f %x", 1.0,1.0); printf("%f %x",2.0,2.0); printf("%x %d",1.0,1.0); printf("%x %d",2.0,2.0);
, preste atenção também à seguinte construção e seu resultado:
printf("%x %x %f",1.0,1.0);
Não darei explicações para esse fenômeno "suficientemente inteligente".
No entanto, como imprimimos corretamente a representação hexadecimal de PT? A primeira solução é óbvia - união, mas a segunda é para os fãs de linha única printf ("% x", * ((int *) (& f))); (Peço desculpas se alguém se ofendeu com colchetes extras, mas eu nunca, e nunca pretendi, lembrar as prioridades das operações, principalmente considerando que os parênteses não geram código, então continuarei fazendo o mesmo). E aqui está, a solução da tarefa - vemos uma série de caracteres, 0x45678, que determinam exclusivamente o número desejado para nós, mas de forma que nós (eu não conheço você, definitivamente) não podemos dizer nada inteligível sobre esse número. Eu acho que o acadêmico Karnal, que poderia ter apontado um erro na fita perfurada com o código-fonte, teria lidado com essa tarefa, mas nem todos são tão avançados, então continuaremos.
Vamos tentar obter informações de uma forma mais compreensível.
Para fazer isso, retornamos ao formato do PT (daqui em diante, considero apenas float), que é um conjunto de bits dos quais você pode extrair (por certas regras) três conjuntos de bits para representar três números - sinal (es), mantissa (m) e ordem (p), e o número desejado codificado por esses números será determinado pela seguinte fórmula: Cs * Chm * Chn. Aqui, os símbolos designam os números representados pelo conjunto correspondente de bits; portanto, para encontrar o número desejado, precisamos conhecer as leis pelas quais extraímos esses três conjuntos do conjunto original de bits, bem como o tipo de codificação para cada um deles.
Para resolver esse problema, recorremos ao padrão IEEE e descobrimos que o sinal é um bit (sênior) do conjunto original e a fórmula para codificar Cs = (- 1) ^ B (0). A ordem ocupa os próximos 8 bits mais significativos, é escrita em código com um deslocamento de 127 e representa uma potência de dois, então Cn = 2 ^ (C2 (8) -127). Mantissa recebe a próxima ordem de 23 dígitos e representa o número Chm = 1 + Ch2 (23) / 2 ^ 23.
Agora temos todos os dados necessários e podemos resolver completamente a tarefa - criar uma string com caracteres, que com uma certa leitura representem um número igual ao codificado em PT. Para fazer isso, devemos, através de operações simples, extrair os números acima e imprimi-los, fornecendo os atributos necessários. Assumimos que somos capazes de converter um número inteiro com não mais de 32 bits em uma cadeia de caracteres; isso é completamente descomplicado.
Infelizmente, estamos apenas no início da jornada, uma vez que poucos leitores deste post no registro “+ 1.625 * 2 ^ 3” reconhecem o número azarado, codificado pelo decimal mais comum “13” e adivinham no registro “1.953125 * 2 ^ 9 ”o simples“ 1E3 ”ou“ 1 * 10 ^ 3 ”ou o muito familiar“ 1000 ”são capazes de unidades de pessoas em geral, eu definitivamente não pertenço a elas. É estranho como isso aconteceu, porque concluímos a tarefa inicial, que demonstra mais uma vez com que cuidado você deve tratar as formulações. E o ponto não é que a notação decimal seja melhor ou pior que o binário (neste caso, o deuce é baseado no grau), mas que estamos acostumados a decimais desde a infância e refazer as pessoas é muito mais difícil que o programa, portanto, daremos nosso entrada para o mais familiar.
Do ponto de vista da matemática, temos uma operação simples - existe um registro PT = (- 1) ^ s * m * 2 ^ n e precisamos convertê-lo para a forma PT = (-1) s '* m' * 10 ^ n '. Equacionamos, transformamos e obtemos (uma das opções possíveis) soluções s '= s', m '= m, n' = n * log (2). Se deixarmos de fora os colchetes, a necessidade de multiplicar por um número explicitamente irracional (isso pode ser feito se o número for racionalizado, mas falaremos sobre isso mais tarde), então o problema parece estar resolvido até que possamos ver a resposta, porque se o registro é como “+1.953125 * 2 ^ 9 "nos parece obscuro, o registro" + 1.953125 * 10 ^ 2.70927 "é ainda menos aceitável, embora parecesse que não havia lugar pior.
Continuamos a melhorar a solução e encontramos a seguinte solução - as equações de redução para o grau base 10 m '= m * 10 ^ {n * log (2)}, n' = [n * log (2)], onde os colchetes e os encaracolados indicam o fracionário e a parte inteira de um determinado número, respectivamente. Então, para o exemplo em questão, obtemos (1.953125 * 10 ^ 0.7 0927) * 10 ^ 2 = "10 * 10 ^ 2", que é muito mais aceitável, embora não seja perfeito, mas já pode ser implementado.A coisa é pequena, precisamos aprender:- multiplique o número inteiro (n) pelo irracional anteriormente conhecido (log (2)) (isso não é difícil com certas restrições na precisão do resultado);
- pegue a parte inteira e fracionária de um número de ponto fixo (isso é fácil);
- elevar um todo conhecido (10) a um grau irracional (hmm ...);
- multiplique o todo por um irracional arbitrário ("simplificaremos os cálculos, disseram eles ...").
No entanto, tentaremos avançar nessa direção e considerar o que não é difícil de fazer, ou seja, o ponto 1. Observamos imediatamente que esse problema é fundamentalmente insolúvel e não podemos calcular n * log (2), não podemos da palavra “completamente”, exceto o caso trivial n = 0 (bem, e o caso óbvio n = k / log (10)). Uma afirmação interessante, especialmente após a afirmação "não é difícil", mas a aparente contradição é removida pela frase "com certa precisão". Ou seja, ainda podemos calcular o produto de um número inteiro arbitrário com um irracional conhecido e isso não é difícil para o resultado com uma certa precisão. Por exemplo, se estivermos interessados no resultado com uma precisão de um por cento, apresentando o resultado desejado n '= n * log (2) na forma n * [log (2) * 256 + 1/2] / 256, obtemos o valor com a precisão necessária ,pois o possível erro relativo não pode exceder 1/2/77 = 1/144, o que é claramente melhor que o 1/100 necessário. Uma consideração importante deve ser levada em consideração - o pequeno valor do desvio relativo não diz absolutamente nada sobre o comportamento da função quando uma transformação não linear é aplicada a ela, e a operação de tirar a parte inteira é obviamente não linear. Damos um exemplo simples [4.501] = 5 e [4.499] = 4 e, apesar do desvio relativo nos dados de origem ser de 0,002 / 4,5 = 0,04%, o desvio do resultado será de 1/4 = 25%. Infelizmente, em geral, o problema não é resolvido, usando qualquer algoritmo de arredondamento. Você pode resolver apenas um caso especial quando os dados de entrada são limitados e, além disso, adotar um conjunto fixo de valores. Ao escolher o deslocamento inicial e o ângulo de inclinação, você pode obter uma precisão absoluta,no sentido de arredondamento, aproximação.Para o nosso caso, essa aproximação ideal será a função n '= n * 77/256.Antes de continuar com o design do algoritmo, devemos avaliar a precisão de que precisamos. Como a mantissa é de 24 bits, o número representado tem um erro relativo de 2 ^ -24 = 2 ^ -4 * 2 ^ -20 = 16 ^ -1 * (2 ^ 10) ^ - 2 ~ (10) ^ - 1 * (10 ^ 3) ^ - 2 = 10 ^ -7, o que significa 7 dígitos decimais exatos. Multiplicar dois números de 24 bits será suficiente para manter a precisão nesse intervalo (bem, quase o suficiente). Observe que a transição para números de 32 bits (ambos os fatores) reduz o erro relativo em mais de 100 (256) vezes, esse fato será útil mais tarde.A fórmula mais desagradável em termos de precisão calcula uma nova mantissa e se parece comm '= m * 10 ^ {n * log (2)}Por que é o mais desagradável - 1) contém uma cadeia de cálculos com relação a n e o erro se acumula; 2) possui uma operação extremamente ruim do ponto de vista da precisão, e isso não é a parte fracionária, porque se você fizer isso simultaneamente com a parte inteira, tudo não é tão ruim, mas um expoente. Se as operações restantes são multiplicações e os erros relativos são simplesmente somados, eles são previsíveis e dependem apenas do comprimento da grade de bits da representação do operando, então tudo é extremamente ruim para o expoente e é óbvio que o erro relativo será muito grande com grandes valores do argumento."Bem, sim, é óbvio que"q (10 ^ x) = Δ (10 ^ x) / 10 ^ x = (10 ^ (x + Δx) - 10 ^ x) / 10 ^ x = 10 ^ Δx -1 = 10 ^ (x * qx) -1,10 ^ (x * qx)> ~ 10 ^ (x * 0) + (10 ^ (x * 0)) '* qx = 1 + x * ln (10) * 10 ^ (0) * qx = 1 + x * ln (10) * qx,daqui temos
O que essa expressão significa é que, na extremidade do intervalo de valores, com n = 127, o erro relativo aumentará 292 vezes e, para manter a precisão do resultado no limite necessário, precisamos aumentar significativamente a precisão do argumento.Lembre-se de que a transição de 24 para 32 bits nos fornece o aumento necessário na precisão (não exatamente, mas muito próximo), entendemos que a primeira multiplicação (n * log (2)) deve ser realizada com operandos de 32 bits, ou seja, com tanta precisão o logaritmo de dois deve ser expresso, então será igual a 1'292'914'005 / 2 ^ 32. Observe que no código o numerador dessa constante deve ser escrito como (int) ((log (2) * float (2 ^ 32)) + 0,5), mas em nenhum caso como um misterioso 0x4d104d42, mesmo com um comentário sobre ele computação, porque o código bem escrito é auto-documentado.Em seguida, precisamos de toda a parte do resultado, isso não é difícil, pois sabemos exatamente a posição do ponto decimal nos dois fatores e, como resultado, como resultado.Mas então temos que calcular 10 com a potência de 0 a 1, e aqui usaremos um pequeno truque para obter a precisão necessária. Como, de acordo com a fórmula do erro, a precisão na borda direita do intervalo cai em mais de dois, se representarmos o valor do argumento como a soma do logaritmo dos dois decimais e algum restante, n '' = log (2) * i + (n '' - log ( 2) * i), então o primeiro membro da soma multiplicará por 2 no grau apropriado, o que é fácil de implementar com erro zero (até que ocorra um estouro), e o restante será limitado pelo valor do log (2) e não perderemos a precisão no cálculo 10 ^ n '' (sujeito a subtração adequada).No entanto, a função exponencial para o argumento limitado pelo valor lg (2) ainda terá que ser calculada e a única maneira que vejo é a expansão na série de Taylor. Infelizmente, ele não converge muito rapidamente em nosso intervalo e, por exemplo, para obter uma precisão de 10E-7, precisamos de 9 membros da soma, o que leva à necessidade de realizar multiplicações 1 + 9 * 2 = 19 de números inteiros de 32 bits, o que é um pouco excede o desempenho desejado. Ainda há vagas dúvidas sobre nossa capacidade de calcular n '= n * log (2) com tanta precisão que é suficiente para o valor máximo de n.No entanto, o algoritmo acabou sendo bastante funcional e precisamos apenas de multiplicação de 32 bits para obter o resultado na quantidade de 1 + 19 + 1 = 21 operações que determinam a complexidade computacional do algoritmoÉ possível reduzir a complexidade computacional de nossa transformação - parece que não, todos calculamos cuidadosamente -, mas de repente acontece que ainda é possível. Uma declaração um tanto inesperada, a chave para entender essa possibilidade está na natureza da ordem do PT - é preciso um conjunto fixo (e relativamente pequeno) de valores, e você e eu não levamos isso em consideração ao transformar fórmulas de conversão, mas trabalhamos implicitamente com um valor contínuo.A solução mais simples - altere a memória por um tempo - calcule antecipadamente todos os expoentes possíveis (2 ^ 8 = 256) nos valores correspondentes [n '] (o expoente mais adequado 10) e {n'} (o fator corretivo da mantissa), insira-os na tabela e em diante é fácil de usar no processo de cálculo. A fórmula acaba sendo bastante simples - PT = m * 2 ^ n = m * 10 ^ n '* (2 ^ n / 10 ^ n') = (m * (2 ^ n / 10 ^ n ')) * 10 ^ n '.No caso mais simples, precisamos de 256 * 3 (um fator de correção de 24 bits, não é mais necessário) + 256 * 1 (é garantido que a ordem na base 10 seja menor que a ordem na base 2) = constantes de 1 kbyte. Nesse caso, resta apenas fazer uma multiplicação de 24 * 24 bits (provavelmente será 32 * 32), o que acelera significativamente o trabalho em comparação com a versão deste cálculo.Vamos ver o que pode ser feito do ponto de vista da economia de memória (nesse caso, novamente temos que pagar tempo, portanto, estamos procurando um compromisso razoável). Primeiro, se levarmos em conta o sinal do pedido separadamente, poderemos gerenciar apenas metade da memória necessária (de 256 bytes para o pedido 10) e inverter o resultado, se necessário. Infelizmente, com o fator de correção, não será tão fácil, porque2 ^ -n / 10 ^ -n '= 1 / (2 ^ n / 10 ^ n')! = 2 ^ n / 10 ^ n ',uma pena.
Temos que deixar uma mesa longa ou, para indicadores negativos, dividir por uma constante para indicadores positivos. É claro que a divisão não é de 18 multiplicações, mas, mesmo assim, em velocidade, é exatamente equivalente a duas multiplicações; portanto, o tempo definitivamente dobrará para economizar memória duas vezes, até 512 bytes. Vale a pena - a questão não é simples, mas, felizmente, temos uma maneira muito mais bonita que nos permite livrar-nos do sofrimento da escolha.Esse método geralmente é chamado de aproximação linear por partes e consiste em definir constantes não para cada ponto do valor inicial, mas apenas para algumas e calcular os valores ausentes (com a precisão necessária) usando os valores fornecidos usando uma fórmula simples. Em relação ao nosso problema, verifica-se (sem considerar o sinal)PT = m * 2 ^ n = m * 2 ^ (n0 + n1) = m * 10 ^ n '* (2 ^ (n0 + n1) / 10 ^ n') = m * (2 ^ n0 / 10 ^ n ') * 2 ^ n1 * 10 ^ n',onde n0 é algum valor de referência e n1 = n-n0. Em seguida, a nova mantissa é calculada multiplicando dois números por um ponto fixo, seguido de uma mudança no resultado, o que não prejudica a precisão.Surge então uma pergunta legítima - por que precisamos de uma tabela, porque você pode pegar o indicador mínimo como n0 e conviver com apenas um valor do fator de correção? Infelizmente, essa abordagem é contraproducente devido a duas circunstâncias complementares - a necessidade de obter o expoente mais adequado de 10 e o aparecimento de turnos muito longos com essa abordagem. A última circunstância sugere os limites de aplicabilidade desse método - se realizarmos a multiplicação 32 * 32, e a mantissa inicial tiver 24 dígitos, um deslocamento de 8 dígitos não levará ao estouro e precisaremos de um ponto de referência por 8 valores binários.A quantidade total de memória necessária será 256/8 * 4 = 32 * 4 = 128 bytes - boa economia de memória ao custo do tempo de execução devido à necessidade de alterar todo o resultado do trabalho em no máximo 8 bits.Você pode reduzir um pouco mais a quantidade de constantes devido à simetria do expoente em relação a 0, que mencionei anteriormente, mas a economia será de 32/2 = 16 bytes, não tenho certeza de que isso justifique a complicação (e o aumento do tamanho do código) do próprio programa.Aliás, recentemente observei o código da biblioteca adafruit, amplamente conhecido em círculos estreitos, e fiquei um pouco surpreso com o seguinte fragmento de código const UINT8 Bits[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}; ... data = data | Bits[n];
com um comentário de que a operação 1 << n no AVR demora muito tempo. No meu post, eu já mostrei quais milagres o compilador faz com um parâmetro constante, mas esse não é o caso.Pareceu-me duvidoso que tirar uma máscara de bits de uma matriz fosse mais rápido do que realizar as operações de turno diretamente e subsequente análise de código (usando o site godbolt, embora seja extremamente improvável que seu criador lesse o Habr, no entanto, mais uma vez, trago-lhe meu sincero gratidão) mostrou que realmente é assim.O código gerado pelo compilador para as duas opções (aqui está a opção correta com turnos, levando em consideração os recursos da tarefa, porque precisamos apenas de 1 bit) ldi r18,lo8(4) sbrs r25,1 ldi r18,lo8(1) sbrc r25,0 lsl r18 sbrs r25,2 swap r18
ocupou exatamente o mesmo lugar na memória e, se tudo for feito com cuidado no assembler, a opção com o índice avança 8: 7 devido aos 8 bytes extras do programa (é claro, se não levarmos a sério uma solução realmente deliciosa com armazenamento separado da máscara invertida, o que custará 16 bytes - e a TI é usada em todos os lugares - “eu sabia que seria ruim, mas não sabia que seria tão cedo”). Bem, o pacote mencionado geralmente é uma música separada, descrita da melhor maneira possível pela seguinte citação de um livro maravilhoso: “Este castelo solicitou uma capa de fortificação com a legenda“ Como não construir castelos ou encontrar 12 erros ”(“ The Last Ringman ”, se quem não leu, eu recomendo.)Vamos voltar aos carneiros de ponto flutuante e criar a fórmula resultantePT = m * 2 ^ n = (m * pc [n / 8]) * 2 ^ (n% 8) * 10 ^ nn [n / 8],onde colchetes significam tomar um elemento de matrizes correção pc do indicador e nn- ordem do indicador. A complexidade computacional do algoritmo é imediatamente visível, que é determinada pela multiplicação de 32 * 32 (24 * 24) e turnos subsequentes. Além disso, você pode levar em conta a possibilidade de combinar um expoente de 10 e um fator de correção em uma palavra de 32 bits; isso é deixado para a parte de um leitor curioso (e paciente, afinal, ele leu até o final) deste post.A única observação no final é quando criaremos uma tabela de constantes. Em nenhum caso, podemos fazê-lo no seguinte estiloconst uint32_t Data [32] PROGMEM = {0xF82345, ...}e o ponto, é claro, não está nos atributos da descrição da matriz, mas nos próprios dados na forma de números mágicos. Como os autores observaram com razão, definitivamente não é mais burro do que eu, um código bem escrito é auto-documentado e, se escrevermos a constante acima (e o restante) na forma #define POWROUD(pow) ((uint8_t)((pow & 0x07)*log(2)+0.5)) #define MULT(pow) (2^pow / 10^POWROUND(pow)) #define MULTRAW(pow) (uint32_t((MULT(pow) << 24) +0.5)) #define BYTEMASK 0xFF #define POWDATA(pow) ((POWROUND(pow) & BYTEMASK)| (MULTRAW(pow) & (~BYTEMASK))) const uint32_t Data[(BYTEMASK/8)+1] = { POWDATA(0x00),POWDATA(0x08), ..POWDATA(0xF8)}
ninguém nos enviará perguntas perplexas e, se alguém nos enviar, definitivamente não podemos respondê-las, ainda será inútil.Podemos propor uma modificação desse método em que uma potência adequada de dez será calculada não para a borda direita do segmento, mas para a esquerda e, em seguida, o resultado não será desviado para a direita para levar em conta a potência de dois, mas para a esquerda. Do ponto de vista da matemática, os métodos são absolutamente equivalentes. Vejamos o resultado:1.953125 * 2 ^ 9 = 1.953125 * 2 ^ (8 + 1) = 1.953125 * 42949673/256/256/256 (2.56) * 2 * 10 ^ 2 = 10 * 10 ^ 2já é muito fácil encontrar 1000 aqui. Claro, também precisaríamos converter a mantissa obtida e a ordem em seqüências de caracteres, arredondar cuidadosamente, ajustar o resultado ao formato necessário, adicionar um personagem, levar em conta casos especiais e assim por diante, mas isso não é mais tão interessante, a parte principal transformações que realizamos.