Por que não é `int pow (int base, int exponent)` nas bibliotecas C ++ padrão?

https://stackoverflow.com/questions/2398442

25-09-2019
|

Pergunta

Sinto que devo apenas ser incapaz de encontrá -lo. Existe alguma razão para que o C ++ pow A função não implementa a função "Power" para qualquer coisa, exceto floatareia doubles?

Sei que a implementação é trivial, sinto que estou trabalhando que deve estar em uma biblioteca padrão. Uma função de poder robusta (ou seja, lida com o excesso de alguma maneira consistente e explícita) não é divertida de escrever.

Solução

De fato, sim.

Como C ++ 11 existe uma implementação modelada de pow(int, int) --- e ainda mais casos gerais, veja (7) emhttp://en.cppreference.com/w/cpp/numeric/math/pow

EDIT: Os puristas podem argumentar que isso não está correto, pois na verdade há a digitação "promovida" usada. De uma maneira ou de outra, um fica correto int resultado, ou um erro, em int parâmetros.

Outras dicas

AS C++11, casos especiais foram adicionados ao conjunto de funções de energia (e outras). C++11 [c.math] /11 estados, depois de listar todos os float/double/long double sobrecarga (minha ênfase e parafraseada):

Além disso, deve haver sobrecargas adicionais suficientes para garantir que, Se algum argumento correspondente a um double O parâmetro tem tipo double ou um tipo inteiro, então todos os argumentos correspondentes a double Os parâmetros são efetivamente lançados para double.

Portanto, basicamente, os parâmetros inteiros serão atualizados para dobrar para executar a operação.

Antes de C++11 (que foi quando sua pergunta foi feita), não existiam sobrecargas inteiras.

Desde que eu não estava intimamente associado aos criadores de C nem C++ nos dias de sua criação (embora eu sou bastante antigo), nem parte dos comitês da ANSI/ISO que criaram os padrões, isso é necessariamente opinião da minha parte. Eu gostaria de pensar que é informado Opinião, mas, como minha esposa lhe dirá (com frequência e sem muito incentivo necessário), já estive errado antes :-)

A suposição, pelo que vale a pena, segue.

EU suspeito que a razão pela qual o pré-Ansi original C Não tinha esse recurso é porque era totalmente desnecessário. Primeiro, já havia uma maneira perfeitamente boa de fazer poderes inteiros (com duplas e depois simplesmente converter de volta para um número inteiro, verificando o excesso inteiro e o fluxo antes da conversão).

Segundo, outra coisa que você deve lembrar é que a intenção original de C era como um sistemas linguagem de programação, e é questionável se o ponto flutuante é desejável nessa arena.

Como um de seus casos de uso inicial era codificar o Unix, o ponto flutuante teria sido próximo a inútil. O BCPL, no qual C se baseava, também não tinha utilidade para poderes (não tinha um ponto flutuante, da memória).

Como um aparte, um operador de energia integral provavelmente teria sido um operador binário e não uma chamada de biblioteca. Você não adiciona dois números inteiros com x = add (y, z) mas com x = y + z - parte de idioma apropriado em vez da biblioteca.

Terceiro, como a implementação do poder integral é relativamente trivial, é quase certo que os desenvolvedores do idioma usariam melhor seu tempo fornecendo coisas mais úteis (veja abaixo os comentários sobre o custo da oportunidade).

Isso também é relevante para o original C++. Como a implementação original era efetivamente apenas um tradutor que produziu C código, ele carregou muitos dos atributos de C. Sua intenção original era C-With-Classes, não C-With-Classes-Plus-A-Little-Bit-of-Extra-Math-Stuff.

Sobre o motivo de nunca ter sido adicionado aos padrões antes C++11, você deve se lembrar de que os órgãos de definição de padrões têm diretrizes específicas a seguir. Por exemplo, ANSI C foi especificamente encarregado de codificar a prática existente, não para criar um novo idioma. Caso contrário, eles poderiam ter enlouquecido e nos deu Ada :-)

Posteriormente, as iterações desse padrão também têm diretrizes específicas e podem ser encontradas nos documentos da lógica (justificativa sobre o motivo pelo qual o comitê tomou certas decisões, não a justificativa para o próprio idioma).

Por exemplo, o C99 A lógica do documento carrega especificamente dois dos C89 Princípios orientadores que limitam o que pode ser adicionado:

Mantenha o idioma pequeno e simples.
Forneça apenas uma maneira de fazer uma operação.

Diretrizes (não necessariamente aquelas específico uns) são depositados para os grupos de trabalho individuais e, portanto, limitam o C++ Comitês (e todos os outros grupos ISO) também.

Além disso, os órgãos de definição de padrões percebem que há um custo de oportunidade (Um termo econômico que significa o que você deve renunciar a uma decisão tomada) para todas as decisões que tomam. Por exemplo, o custo de oportunidade da compra de que a máquina de US $ 10.000 uber é relações cordiais (ou provavelmente tudo relações) com sua outra metade por cerca de seis meses.

Eric Gunnerson explica isso bem com o seu -100 Pontos Explicação Quanto ao motivo pelo qual as coisas nem sempre são adicionadas aos produtos da Microsoft- basicamente, um recurso inicia 100 pontos no buraco, por isso deve agregar um pouco de valor a ser considerado.

Em outras palavras, você prefere ter um operador de energia integral (o que, honestamente, qualquer codificador de meio decente poderia preparar em dez minutos) ou multi-threading adicionado ao padrão? Para mim, eu prefiro ter o último e não ter que superar as diferentes implementações do UNIX e Windows.

Eu gostaria de ver também milhares e milhares de coleta da biblioteca padrão (hashes, btrees, árvores pretas-vermelhas, dicionário, mapas arbitrários e assim por diante) também, mas, como afirma a lógica:

Um padrão é um tratado entre implementador e programador.

E o número de implementadores nos órgãos de padrões supera em muito o número de programadores (ou pelo menos os programadores que não entendem o custo da oportunidade). Se todo esse material foi adicionado, o próximo padrão C++ seria C++215x e provavelmente seria totalmente implementado pelos desenvolvedores do compilador trezentos anos depois disso.

De qualquer forma, esses são meus pensamentos (bastante volumosos) sobre o assunto. Se apenas os votos fossem entregues bases sobre quantidade e não de qualidade, logo iria soltar todos os outros da água. Obrigado por ouvir :-)

Para qualquer tipo integral de largura fixa, quase todos os pares de entrada possíveis transbordam o tipo, de qualquer maneira. Qual é o uso da padronização de uma função que não fornece um resultado útil para a grande maioria de suas entradas possíveis?

Você praticamente precisa ter um tipo inteiro grande para tornar a função útil e a maioria das grandes bibliotecas inteiras fornece a função.

Editar: Em um comentário sobre a pergunta, o static_rtti escreve "a maioria das entradas faz com que ela transborde? O mesmo se aplica ao Exp e Double Pow, não vejo ninguém reclamando". Isso está incorreto.

Vamos deixar de lado exp, porque isso é além de não double pow(double x, double y). Para que parte de (x, y) pares essa função faz algo útil (ou seja, não simplesmente transbordam ou subfluem)?

Na verdade, vou me concentrar apenas em uma pequena parte dos pares de entrada para os quais pow Faz sentido, porque isso será suficiente para provar meu ponto: se x for positivo e | y | <= 1, então pow não transborda ou subflue. Isso compreende quase um quarto de todos os pares de pontos flutuantes (exatamente metade dos números não-NAN de ponto flutuante são positivos e apenas menos da metade dos números de ponto flutuante não NAN têm magnitude menor que 1). Obviamente, existem muito de outros pares de entrada para os quais pow Produz resultados úteis, mas verificamos que é pelo menos um quarto de todas as entradas.

Agora, vejamos uma função inteira de largura fixa (ou seja, não-bignum). Para quais entradas de porção não transborda? Para maximizar o número de pares de entrada significativos, a base deve ser assinada e o expoente não assinado. Suponha que a base e o expoente sejam ambos n Bits de largura. Podemos facilmente ter um limite na parte de entradas que são significativas:

Se o expoente 0 ou 1, qualquer base será significativa.
Se o expoente for 2 ou mais, nenhuma base maior que 2^(n/2) produzirá um resultado significativo.

Assim, dos pares de entrada 2^(2n), menos de 2^(n + 1) + 2^(3n/2) produzem resultados significativos. Se olharmos para o que é provavelmente o uso mais comum, números inteiros de 32 bits, isso significa que algo da ordem de 1/1000 de um por cento dos pares de entrada não transborda simplesmente.

Porque não há como representar todos os poderes inteiros de qualquer maneira:

>>> print 2**-4
0.0625

Essa é realmente uma pergunta interessante. Um argumento que não encontrei na discussão é a simples falta de valores óbvios de retorno para os argumentos. Vamos contar as maneiras pelas quais os hippéticos int pow_int(int, int) a função pode falhar.

Transbordar
Resultado indefinido pow_int(0,0)
Resultado não pode ser representado pow_int(2,-1)

A função possui pelo menos 2 modos de falha. Os números inteiros não podem representar esses valores, o comportamento da função nesses casos precisaria ser definido pelo padrão - e os programadores precisariam estar cientes de como exatamente a função lida com esses casos.

No geral, deixar a função fora parece ser a única opção sensata. O programador pode usar a versão de ponto flutuante com todos os relatórios de erro disponíveis.

Resposta curta:

Uma especialização de pow(x, n) para onde n é um número natural geralmente é útil para desempenho do tempo. Mas o genérico da biblioteca padrão pow() ainda funciona bonito (surpreendentemente!) bem para esse fim e é absolutamente crítico incluir o mínimo possível na biblioteca C padrão, para que possa ser feita o mais portátil e o mais fácil de implementar possível. Por outro lado, isso não impede que esteja na biblioteca padrão C ++ ou no STL, que tenho certeza de que ninguém está planejando usar em algum tipo de plataforma incorporada.

Agora, para a resposta longa.

pow(x, n) pode ser feito muito mais rápido em muitos casos, especializando -se n para um número natural. Eu tive que usar minha própria implementação dessa função para quase todos os programas que escrevo (mas escrevo muitos programas matemáticos em c). A operação especializada pode ser feita em O(log(n)) tempo, mas quando n é pequeno, uma versão linear mais simples pode ser mais rápida. Aqui estão as implementações de ambos:


    // Computes x^n, where n is a natural number.
    double pown(double x, unsigned n)
    {
        double y = 1;
        // n = 2*d + r. x^n = (x^2)^d * x^r.
        unsigned d = n >> 1;
        unsigned r = n & 1;
        double x_2_d = d == 0? 1 : pown(x*x, d);
        double x_r = r == 0? 1 : x;
        return x_2_d*x_r;
    }
    // The linear implementation.
    double pown_l(double x, unsigned n)
    {
        double y = 1;
        for (unsigned i = 0; i < n; i++)
            y *= x;
        return y;
    }

(Eu deixei x e o valor de retorno como dobra porque o resultado de pow(double x, unsigned n) vai se encaixar em um dobro com tanta frequência quanto pow(double, double) vai.)

(Sim, pown é recursivo, mas quebrar a pilha é absolutamente impossível, pois o tamanho máximo da pilha será aproximadamente igual log_2(n) e n é um número inteiro. Se n é um número inteiro de 64 bits, que oferece um tamanho máximo de pilha de cerca de 64. Não O hardware possui limitações de memória tão extremas, exceto algumas fotos desonestas com pilhas de hardware que só são de 3 a 8 chamadas de função.)

Quanto ao desempenho, você ficará surpreso com o que uma variedade de jardim pow(double, double) é capaz de. Eu testei cem milhões de iterações no meu IBM Thinkpad de 5 anos com x igual ao número de iteração e n igual a 10. Nesse cenário, pown_l Ganhou. glibc pow() levou 12,0 segundos de usuário, pown levou 7,4 segundos de usuário e pown_l levou apenas 6,5 segundos de usuário. Então isso não é muito surpreendente. Estávamos mais ou menos esperando isso.

Então eu deixo x Seja constante (eu o defina para 2.5) e lotei n de 0 a 19 cem milhões de vezes. Desta vez, inesperadamente, glibc pow ganhou, e por um deslizamento de terra! Foram necessários apenas 2,0 segundos de usuário. Meu pown levou 9,6 segundos e pown_l levou 12,2 segundos. O que aconteceu aqui? Eu fiz outro teste para descobrir.

Eu fiz a mesma coisa que acima apenas com x igual a um milhão. Desta vez, pown venceu aos 9.6s. pown_l levou 12,2s e o Glibc Pow levou 16,3s. Agora, está claro! glibc pow tem um desempenho melhor do que os três quando x é baixo, mas pior quando x é alto. Quando x é alto, pown_l Executa melhor quando n é baixo e pown Executa melhor quando x é alto.

Então, aqui estão três algoritmos diferentes, cada um capaz de ter um desempenho melhor do que os outros nas circunstâncias certas. Então, em última análise, o que provavelmente depende de como você está planejando usar pow, mas usando a versão certa é Vale a pena, e ter todas as versões é bom. De fato, você pode até automatizar a escolha do algoritmo com uma função como esta:

double pown_auto(double x, unsigned n, double x_expected, unsigned n_expected) {
    if (x_expected < x_threshold)
        return pow(x, n);
    if (n_expected < n_threshold)
        return pown_l(x, n);
    return pown(x, n);
}

Enquanto x_expected e n_expected são constantes decididas em tempo de compilação, juntamente com possivelmente algumas outras advertências, um compilador de otimização que vale o seu sal removerá automaticamente todo o pown_auto Função Ligue e substitua -a pela escolha apropriada dos três algoritmos. (Agora, se você realmente vai tentar usar Você provavelmente terá que brincar um pouco, porque eu não tentei exatamente compilação O que eu escrevi acima. ;))

Por outro lado, Glibc pow funciona E o glibc já é grande o suficiente. O padrão C deve ser portátil, inclusive para vários dispositivos incorporados (De fato, desenvolvedores incorporados em todos os lugares geralmente concordam que o Glibc já é grande demais para eles), e não pode ser portátil se, para cada função de matemática simples, precisar incluir todos os algoritmos alternativos que poderia ser útil. Então, é por isso que não está no padrão C.

Nota de rodapé: no teste de desempenho do tempo, dei minhas funções sinalizadores de otimização relativamente generosos (-s -O2) que provavelmente serão comparáveis, se não forem piores do que, o que provavelmente foi usado para compilar o GLIBC no meu sistema (Archlinux), portanto os resultados provavelmente são justos. Para um teste mais rigoroso, eu teria que compilar o Glibc e eu Reeally Não sinto vontade de fazer isso. Eu costumava usar o gentoo, então lembro quanto tempo leva, mesmo quando a tarefa é automatizado. Os resultados são conclusivos (ou melhor, inconclusivos) o suficiente para mim. É claro que você pode fazer isso sozinho.

Rodada de bônus: uma especialização de pow(x, n) Para todos os números inteiros é instrumental Se for necessária uma saída inteira exata, o que acontece. Considere alocar memória para uma matriz N-dimensional com elementos p^n. A obtenção de um desativado mesmo resultará em um segfault possivelmente de ocorrência aleatória.

Uma razão para o C ++ não ter sobrecargas adicionais é ser compatível com C.

C ++ 98 tem funções como double pow(double, int), mas estes foram removidos em C ++ 11 com o argumento de que o C99 não os incluiu.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3286.html#550

Obter um resultado um pouco mais preciso também significa obter um pouco diferente resultado.

O mundo está em constante evolução e também as linguagens de programação. o Quarta parte do C decimal TR¹ adiciona mais algumas funções a <math.h>. Duas famílias dessas funções podem ser de interesse desta questão:

o pown funções, isso leva um número de ponto flutuante e um intmax_t expoente.
o powr funções, isso leva dois números de pontos flutuantes (x e y) e calcular x para o poder y com a fórmula exp(y*log(x)).

Parece que os caras padrão finalmente consideraram esses recursos úteis o suficiente para serem integrados na biblioteca padrão. No entanto, o racional é que essas funções são recomendadas pelo ISO/IEC/IEEE 60559: 2011 padrão para números de ponto flutuante binário e decimal. Não posso dizer com certeza o que "padrão" foi seguido na época do C89, mas as futuras evoluções de <math.h> provavelmente será fortemente influenciado pelas futuras evoluções do ISO/IEC/IEEE 60559 padrão.

Observe que a quarta parte do TR decimal não será incluída no C2X (a próxima revisão C principal) e provavelmente será incluída posteriormente como um recurso opcional. Não houve nenhuma intenção que conheço incluir esta parte do TR em uma futura revisão do C ++.

¹ Você pode encontrar alguma documentação de trabalho em andamento aqui.

Talvez porque o ALU do processador não tenha implementado essa função para números inteiros, mas existe uma instrução de FPU (como Stephen aponta, na verdade é um par). Portanto, foi realmente mais rápido lançar para dobrar, chamar Pow com duplas, depois testar o transbordamento e fundir de volta, do que implementá -lo usando aritmética inteira.

(Por um lado, os logaritmos reduzem os poderes à multiplicação, mas os logaritmos de números inteiros perdem muita precisão para a maioria dos insumos)

Stephen está certo que, nos processadores modernos, isso não é mais verdadeiro, mas o padrão C quando as funções matemáticas foram selecionadas (o C ++ apenas usou as funções C) agora é o que, 20 anos?

Um motivo muito simples:

5^-2 = 1/25

Tudo na biblioteca STL é baseado nas coisas mais precisas e robustas que se possa imaginar. Claro, o INT retornaria a um zero (de 1/25), mas essa seria uma resposta imprecisa.

Eu concordo, é estranho em alguns casos.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow