Por que `int pow (int base, int expoent)` não está nas bibliotecas C ++ padrão?

116

Eu sinto que devo simplesmente ser incapaz de encontrar. Existe alguma razão para que a powfunção C ++ não implemente a função "power" para nada, exceto floats e doubles?

Eu sei que a implementação é trivial, apenas sinto que estou fazendo um trabalho que deveria estar em uma biblioteca padrão. Uma função de potência robusta (ou seja, lida com o estouro de alguma forma consistente e explícita) não é divertida de escrever.

Dan O
fonte
4
Esta é uma boa pergunta e não acho que as respostas façam muito sentido. Os expoentes negativos não funcionam? Tome ints sem sinal como expoentes. A maioria das entradas causa o estouro? O mesmo vale para exp e double pow, não vejo ninguém reclamando. Então, por que essa função não é padrão?
static_rtti
2
@static_rtti: "O mesmo é verdadeiro para exp e double pow" é totalmente falso. Vou elaborar minha resposta.
Stephen Canon
11
A biblioteca C ++ padrão tem double pow(int base, int exponent)desde C ++ 11 (§26.8 [c.math] / 11 ponto 2)
Cubbi
Você precisa decidir entre 'a implementação é trivial' e 'nada divertido de escrever'.
Marquês de Lorne

Respostas:

66

A partir de C++11, casos especiais foram adicionados ao conjunto de funções de energia (e outros). C++11 [c.math] /11estados, depois de listar todas as float/double/long doublesobrecargas (grifo meu, e parafraseado):

Além disso, deve haver sobrecargas adicionais suficientes para garantir que, se qualquer argumento correspondente a um doubleparâmetro tiver tipo doubleou um tipo inteiro, todos os argumentos correspondentes aos doubleparâmetros serão efetivamente convertidos para double.

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


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

Desde que eu estava nem intimamente associada com os criadores C, nem C++nos dias de sua criação (embora eu estou bastante antigo), nem parte dos comitês ANSI / ISO que criaram os padrões, este é necessariamente opinião da minha parte. Eu gostaria de pensar que é uma opinião informada , mas, como minha esposa lhe dirá (freqüentemente e sem muito incentivo necessário), eu estive errado antes :-)

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

Eu suspeito que a razão do original pré-ANSI Cnão têm esta característica é porque era totalmente desnecessário. Em primeiro lugar, já havia uma maneira perfeitamente boa de fazer potências de inteiros (com duplas e simplesmente converter de volta para um inteiro, verificando se há estouro e estouro negativo antes da conversão).

Em segundo lugar, outra coisa que você deve lembrar é que a intenção original do Cera ser uma linguagem de programação de sistemas , e é questionável se o ponto flutuante é desejável nessa área.

Já que um de seus casos de uso inicial era codificar o UNIX, o ponto flutuante seria quase inútil. O BCPL, no qual o C foi baseado, também não tinha uso para potências (não tinha ponto flutuante, de memória).

Como um aparte, um operador de potência integral provavelmente teria sido um operador binário em vez de uma chamada de biblioteca. Você não adiciona dois inteiros com, x = add (y, z)mas com x = y + z- parte da linguagem adequada ao invés da biblioteca.

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

Isso também é relevante para o original C++. Como a implementação original era efetivamente apenas um tradutor que produzia Ccódigo, ela carregava muitos dos atributos de C. Sua intenção original era C-com-classes, não C-com-classes-mais-um-pouco-extra-matemática-coisa.

Quanto ao motivo pelo qual ele nunca foi adicionado aos padrões antes C++11, você deve se lembrar que os órgãos de definição de padrões têm diretrizes específicas a seguir. Por exemplo, ANSI Cfoi especificamente encarregado de codificar a prática existente, não de criar uma nova linguagem. Caso contrário, eles poderiam ter enlouquecido e nos dado Ada :-)

As iterações posteriores desse padrão também têm diretrizes específicas e podem ser encontradas nos documentos de justificativa (justificativa de por que o comitê tomou certas decisões, não a justificativa para a linguagem em si).

Por exemplo, o C99documento de justificativa especificamente leva adiante dois dos C89princípios orientadores que limitam o que pode ser adicionado:

  • Mantenha a linguagem pequena e simples.
  • Fornece apenas uma maneira de fazer uma operação.

Diretrizes (não necessariamente aquelas específicas ) são estabelecidas para os grupos de trabalho individuais e, portanto, limitam os 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ê tem que abrir mão para uma decisão tomada) para cada decisão que tomam. Por exemplo, o custo de oportunidade de comprar aquela máquina de uber-gaming de $ 10.000 são relações cordiais (ou provavelmente todas as relações) com sua outra metade por cerca de seis meses.

Eric Gunnerson explica isso bem com sua explicação de -100 pontos sobre por que as coisas nem sempre são adicionadas aos produtos Microsoft - basicamente, um recurso começa 100 pontos no buraco, então tem que adicionar um pouco de valor para ser considerado.

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

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

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

E o número de implementadores nos organismos de padrões supera em muito o número de programadores (ou pelo menos aqueles programadores que não entendem o custo de oportunidade). Se tudo isso fosse adicionado, o próximo padrão C++seria C++215xe provavelmente seria totalmente implementado por desenvolvedores de compiladores trezentos anos depois disso.

De qualquer forma, essa é minha opinião (bastante volumosa) sobre o assunto. Se os votos fossem dados com base na quantidade e não na qualidade, eu logo tiraria todos os outros da água. Obrigado por ouvir :-)

paxdiablo
fonte
2
FWIW, não acho que C ++ siga "Forneça apenas uma maneira de fazer uma operação" como uma restrição. Com razão, porque por exemplo to_stringe lambdas são conveniências para coisas que você já pode fazer. Suponho que se poderia interpretar "apenas uma maneira de fazer uma operação" de forma muito vaga para permitir ambos e, ao mesmo tempo, permitir quase qualquer duplicação de funcionalidade que se possa imaginar, dizendo "aha! Não! Porque a conveniência torna é uma operação sutilmente diferente da alternativa precisamente equivalente, porém mais prolixa! ". O que certamente é verdade para lambdas.
Steve Jessop
@Steve, sim, isso foi mal formulado da minha parte. É mais correto dizer que existem diretrizes para cada comitê do que todos os comitês seguem as mesmas diretrizes. Resposta ajustada para clarifyl
paxdiablo
2
Apenas um ponto (entre alguns): "qualquer macaco de código pode ser ativado em dez minutos". Claro, e se 100 macacos de código (bom termo insultuoso, BTW) fizerem isso a cada ano (provavelmente uma estimativa baixa), teremos 1000 minutos perdidos. Muito eficiente, não acha?
Jürgen A. Erhard
1
@ Jürgen, não era para ser um insulto (já que eu não atribuí o rótulo a ninguém em específico), era apenas uma indicação que powrealmente não requer muita habilidade. Certamente eu prefiro ter o padrão fornecer algo que iria exigir muita habilidade, e resultar em minutos muito mais desperdiçados se o esforço teve que ser duplicado.
paxdiablo
2
@ eharo2, basta substituir o "codificador meio decente" no texto atual por "macaco de código". Eu também não achei um insulto, mas achei melhor ser cauteloso e, para ser honesto, o texto atual passa pela mesma ideia.
paxdiablo
41

Para qualquer tipo integral de largura fixa, quase todos os pares de entrada possíveis excedem o tipo, de qualquer maneira. Qual é a utilidade de padronizar 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 de inteiro grande para tornar a função útil, e a maioria das bibliotecas de inteiro grande fornece a função.


Edit: Em um comentário sobre a questão, static_rtti escreve "A maioria das entradas causa o estouro? O mesmo é verdade para exp e double pow, não vejo ninguém reclamando." Isso está incorreto.

Vamos deixar de lado exp, porque isso não vem ao caso (embora na verdade tornasse meu caso mais forte) e focar double pow(double x, double y). Para qual porção dos pares (x, y) esta função faz algo útil (ou seja, não simplesmente estouro ou estouro negativo)?

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

Agora vamos olhar para uma função de potência inteira de largura fixa (ou seja, não bignum). Para quais entradas de porção ele simplesmente 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 tenham nlargura de bits. Podemos facilmente obter um limite na parte das entradas que são significativas:

  • Se o expoente 0 ou 1, qualquer base é significativa.
  • Se o expoente for 2 ou maior, nenhuma base maior que 2 ^ (n / 2) produz um resultado significativo.

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

Stephen Canon
fonte
8
De qualquer forma, tudo isso é discutível. Só porque uma função não é válida para algumas ou muitas entradas não a torna menos útil.
static_rtti
2
@static_rtti: pow(x,y)não underflow para zero para qualquer x se | y | <= 1. Há uma banda muito estreita de entradas (grande x, y muito próximo de -1) para a qual ocorre underflow, mas o resultado ainda é significativo nesse intervalo.
Stephen Canon
2
Tendo pensado mais nisso, concordo com o underflow. Ainda acho que isso não é relevante para a questão, no entanto.
static_rtti
7
@ybungalobill: Por que você escolheu isso como um motivo? Pessoalmente, eu prefiro utilidade para um grande número de problemas e programadores, possibilidade de fazer versões otimizadas de harware que são mais rápidas do que a implementação ingênua que a maioria dos programadores provavelmente escreverá, e assim por diante. Seu critério parece completamente arbitrário e, para ser franco, sem sentido.
static_rtti
5
@StephenCanon: Pelo lado bom, seu argumento mostra que a implementação obviamente correta e ótima de inteiro powé simplesmente uma pequena tabela de pesquisa. :-)
R .. GitHub PARE DE AJUDAR A ICE
11

Porque não há como representar todas as potências inteiras em um int de qualquer maneira:

>>> print 2**-4
0.0625
Ignacio Vazquez-Abrams
fonte
3
Para um tipo numérico de tamanho finito, não há como representar todas as potências desse tipo dentro daquele tipo devido ao estouro. Mas seu ponto sobre os poderes negativos é mais válido.
Chris Lutz,
1
Vejo expoentes negativos como algo que uma implementação padrão poderia tratar, tanto tomando um int sem sinal como o expoente ou retornando zero quando um expoente negativo é fornecido como entrada e um int é a saída esperada.
Dan O
3
ou separar int pow(int base, unsigned int exponent)efloat pow(int base, int exponent)
Ponkadoodle
4
Eles poderiam apenas declarar um comportamento indefinido para passar um número inteiro negativo.
Johannes Schaub - litb
2
Em todas as implementações modernas, qualquer coisa além int pow(int base, unsigned char exponent)é um tanto inútil de qualquer maneira. Ou a base é 0 ou 1, e o expoente não importa, é -1, caso em que apenas o último bit do expoente importa ou base >1 || base< -1, nesse caso, exponent<256sob pena de estouro.
MSalters
9

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

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

A função tem pelo menos 2 modos de falha. Os 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 de fora parece a única opção sensata. O programador pode usar a versão de ponto flutuante com todos os relatórios de erros disponíveis.

phoku
fonte
Mas os dois primeiros casos não se aplicariam também a um powflutuador entre os flutuadores? Pegue dois grandes flutuadores, eleve um à potência do outro e você terá um Overflow. E pow(0.0, 0.0)causaria o mesmo problema do seu segundo ponto. Seu terceiro ponto é a única diferença real entre implementar uma função de potência para inteiros e flutuantes.
numbermaniac
7

Resposta curta:

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

Agora, para a longa resposta.

pow(x, n)pode ser feito muito mais rápido em muitos casos, especializando-se npara um número natural. Tive de 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é pequena, uma versão linear mais simples pode ser mais rápida. Aqui estão 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;
    }

(Saí xe o valor de retorno dobra porque o resultado de pow(double x, unsigned n)caberá em um dobro com a frequência necessária pow(double, double).)

(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 inteiro. Se nfor um inteiro de 64 bits, isso dá a você um tamanho máximo de pilha de cerca de 64. Nenhum hardware tem tal extremo limitações de memória, exceto para alguns PICs duvidosos com pilhas de hardware que têm profundidade 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. Testei cem milhões de iterações em meu IBM Thinkpad de 5 anos xigual ao número da iteração e nigual a 10. Nesse cenário, pown_lvenceu. glibc pow()levou 12,0 segundos do usuário, pown7,4 segundos do usuário e pown_lapenas 6,5 segundos do usuário. Portanto, isso não é muito surpreendente. Estávamos mais ou menos esperando isso.

Então, eu deixo xser constante (eu configurei para 2,5), e fiz um loop nde 0 a 19 cem milhões de vezes. Desta vez, de forma bastante inesperada, glibc powvenceu, e por um deslizamento de terra! Demorou apenas 2,0 segundos do usuário. Meu powndemorou 9,6 segundos e pown_l12,2 segundos. O que aconteceu aqui? Fiz outro teste para descobrir.

Eu fiz a mesma coisa acima apenas com xigual a um milhão. Desta vez, pownvenceu a 9.6s. pown_llevou 12,2s e glibc pow levou 16,3s. Agora está claro! glibc tem powmelhor desempenho que os três quando xestá baixo, mas pior quando xestá alto. Quando xestá alto, tem pown_lmelhor desempenho quando nestá baixo e tem pownmelhor desempenho quando xestá alto.

Portanto, 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, que a utilização mais provável depende de como você está pensando em usar pow, mas usando a versão correta é vale a pena, e com todas as versões é bom. Na verdade, 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);
}

Contanto que x_expectede n_expectedsejam constantes decididas em tempo de compilação, junto com possivelmente algumas outras advertências, um compilador de otimização que valha a pena removerá automaticamente a pown_autochamada de função inteira e a substituirá pela escolha apropriada dos três algoritmos. (Agora, se você realmente vai tentar usar isso, provavelmente terá que brincar um pouco com isso, porque eu não tentei exatamente compilar o que escrevi acima.;))

Por outro lado, glibc pow funciona e glibc já é grande o suficiente. O padrão C deve ser portátil, incluindo para vários dispositivos incorporados (na verdade, desenvolvedores incorporados em todos os lugares geralmente concordam que glibc já é muito grande para eles), e não pode ser portátil se para cada função matemática simples ele precisa incluir todos algoritmo alternativo que pode ser útil. Então, é por isso que não está no padrão C.

nota de rodapé: no teste de desempenho de tempo, dei às minhas funções sinalizadores de otimização relativamente generosos ( -s -O2) que provavelmente são comparáveis, senão piores do que o que provavelmente foi usado para compilar glibc em meu sistema (archlinux), então os resultados são provavelmente justo. Para um teste mais rigoroso, eu teria que compilar glibc mim e eu reeeally não sentir vontade de fazer isso. Eu costumava usar o Gentoo, então me lembro quanto tempo leva, mesmo quando a tarefa é automatizada . Os resultados são conclusivos (ou melhor, inconclusivos) o suficiente para mim. É claro que você pode fazer isso sozinho.

Rodada de bônus: A especialização de pow(x, n)para todos os inteiros é instrumental se uma saída inteira exata for necessária, o que acontece. Considere alocar memória para uma matriz N-dimensional com p ^ N elementos. Tirar p ^ N igual a um resultará em um segfault que pode ocorrer aleatoriamente.

Físico enigmático
fonte
Eu acho que se você se livrar da recursão, vai economizar o tempo necessário para a alocação da pilha. E sim, tivemos uma situação em que o pow estava desacelerando tudo e tivemos que implementar nosso próprio pow.
Sambatyon
"Ninguém tem limitações de memória tão extremas" é falso. PIC geralmente tem uma pilha de chamadas limitada para um máximo de 3 (o exemplo é PIC10F200) a 8 (o exemplo é 16F722A) chamadas (PIC usa uma pilha de hardware para chamadas de função).
12431234123412341234123
oh, cara isso é brutal lol. OK, então não funcionará nesses PICs.
enigmaticPhysicist
Para uma base inteira e também para poder, como a questão está perguntando, compiladores (gcc e clang) irão produzir facilmente um loop sem ramificações a partir de uma implementação iterativa (em vez de recursiva). Isso evita erros de previsão de ramificação de cada bit de n. godbolt.org/z/L9Kb98 . gcc e clang falham em otimizar sua definição recursiva em um loop simples e, na verdade, ramificam em cada bit de n. (Pois pown_iter(double,unsigned)eles ainda se ramificam, mas uma implementação SSE2 ou SSE4.1 sem ramificações deve ser possível no conjunto x86 ou com intrínsecos C. Mas mesmo isso é melhor do que recursão)
Peter Cordes
Merda, agora eu tenho que fazer os benchmarks novamente com uma versão baseada em loop só para ter certeza. Vou pensar sobre isso.
enigmaticPhysicist
6

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

C ++ 98 tem funções semelhantes a double pow(double, int), mas foram removidas do C ++ 11 com o argumento de que o C99 não as incluía.

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 resultado ligeiramente diferente .

Bo Persson
fonte
3

O mundo está em constante evolução, assim como as linguagens de programação. A quarta parte do C decimal TR ¹ adiciona mais algumas funções a <math.h>. Duas famílias dessas funções podem ser de interesse para esta questão:

  • As pownfunções, que recebem um número de ponto flutuante e um intmax_texpoente.
  • As powrfunções, que pegam dois números de pontos flutuantes ( xe y) e calculam xa potência ycom a fórmula exp(y*log(x)).

Parece que os caras padrão eventualmente 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 padrão ISO / IEC / IEEE 60559: 2011 para números de ponto flutuante binários e decimais. Não posso dizer com certeza qual "padrão" era seguido na época do C89, mas as evoluções futuras do <math.h>serão provavelmente fortemente influenciadas pelas evoluções futuras do padrão ISO / IEC / IEEE 60559 .

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 há nenhuma intenção que eu conheça de incluir esta parte do TR em uma revisão futura do C ++.


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

Morwenn
fonte
Há alguma implementação plausível em que usar powncom um expoente maior do que LONG_MAXdeveria produzir um valor diferente de usar LONG_MAX, ou onde um valor menor que LONG_MINdeveria produzir um valor diferente de LONG_MIN? Eu me pergunto qual é o benefício obtido com o uso intmax_tde um expoente?
supercat
@supercat Não faço ideia, desculpe.
Morwenn de
Pode valer a pena mencionar que, olhando para o Padrão, parece também definir uma função opcional "crpown" que, se definida, seria uma versão corretamente arredondada de "pown"; o padrão de outra forma não especifica o grau de precisão exigido. Implementar um "pown" rápido e moderadamente preciso é fácil, mas garantir o arredondamento correto em todos os casos tende a ser muito mais caro.
supercat
2

Talvez porque a ALU do processador não implementou tal função para inteiros, mas existe tal instrução FPU (como Stephen aponta, é na verdade um par). Portanto, era realmente mais rápido lançar para dobrar, chamar pow com duplos, testar o estouro e lançar de volta do que implementá-lo usando aritmética de inteiros.

(por um lado, os logaritmos reduzem as potências à multiplicação, mas os logaritmos de inteiros perdem muita precisão para a maioria das entradas)

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

Ben Voigt
fonte
5
Não conheço nenhuma arquitetura atual com uma instrução FPU para pow. O x86 tem uma y log2 xinstrução ( fyl2x) que pode ser usada como a primeira parte de uma powfunção, mas uma powfunção escrita dessa forma leva centenas de ciclos para ser executada no hardware atual; uma rotina de exponenciação de inteiros bem escrita é várias vezes mais rápida.
Stephen Canon,
Não sei se "centenas" é preciso, parece ter cerca de 150 ciclos para fyl2x e depois f2xm1 na maioria das CPUs modernas e isso é processado com outras instruções. Mas você está certo de que uma implementação de número inteiro bem ajustada deve ser muito mais rápida (atualmente), uma vez que o IMUL foi muito mais acelerado do que as instruções de ponto flutuante. No entanto, quando o padrão C foi escrito, o IMUL era muito caro e usá-lo em um loop provavelmente demorava mais do que usar o FPU.
Ben Voigt,
2
Mudei meu voto à luz da correção; ainda, tenha em mente (a) que o padrão C passou por uma grande revisão (incluindo uma grande expansão da biblioteca matemática) em 1999, e (b) que o padrão C não foi escrito para nenhuma arquitetura de processador específica - a presença ou a ausência de instruções de FPU no x86 não tem essencialmente nada a ver com a funcionalidade que o comitê C escolhe padronizar.
Stephen Canon,
Não está vinculado a nenhuma arquitetura, é verdade, mas o custo relativo de uma interpolação de tabela de pesquisa (geralmente usada para a implementação de ponto flutuante) em comparação com a multiplicação de inteiro mudou quase igualmente para todas as arquiteturas, eu imagino.
Ben Voigt,
1

Aqui está uma implementação O (log (n)) realmente simples de pow () que funciona para qualquer tipo numérico, incluindo inteiros :

template<typename T>
static constexpr inline T pown(T x, unsigned p) {
    T result = 1;

    while (p) {
        if (p & 0x1) {
            result *= x;
        }
        x *= x;
        p >>= 1;
    }

    return result;
}

É melhor do que a implementação O (log (n)) do enigmaticPhysicist porque não usa recursão.

Também é quase sempre mais rápido do que sua implementação linear (desde que p> ~ 3) porque:

  • não requer nenhuma memória extra
  • ele faz apenas cerca de 1,5x mais operações por loop
  • ele só faz aproximadamente 1,25x mais atualizações de memória por loop
serg06
fonte
-2

Na verdade, sim.

Desde C ++ 11, há uma implementação pow(int, int)modelada de --- e casos ainda mais gerais, consulte (7) em http://en.cppreference.com/w/cpp/numeric/math/pow


EDITAR: os puristas podem argumentar que isso não é correto, pois na verdade é usada uma digitação "promovida". De uma forma ou de outra, obtém-se um intresultado correto , ou um erro, nos intparâmetros.

Dima Pasechnik
fonte
2
isso está incorreto. A sobrecarga (7) é a pow ( Arithmetic1 base, Arithmetic2 exp )que será lançada doubleou long doublese você leu a descrição: "7) Um conjunto de sobrecargas ou um modelo de função para todas as combinações de argumentos de tipo aritmético não cobertos por 1-3). Se houver algum argumento tem tipo integral, ele é convertido em double. Se qualquer argumento for long double, o tipo de retorno Promovido também será long double, caso contrário, o tipo de retorno será sempre double. "
phuclv
o que está incorreto aqui? Eu apenas disse que hoje em dia (desde C ++ 11) um modelo de pow ( , ) está na biblioteca padrão, o que não era o caso em 2010.
Dima Pasechnik
5
Não, não é. Templeates promovem esses tipos para o dobro ou o dobro longo. Portanto, funciona em duplas por baixo.
Trismegistos
1
@Trismegistos Ainda permite parâmetros internos. Se esse modelo não estivesse lá, a passagem de parâmetros int faz com que ele interprete os bits no int como um float, causando resultados inesperados arbitrários. O mesmo acontece com valores de entrada mistos. por exemplo, pow(1.5f, 3)= 1072693280but pow(1.5f, float(3))=3.375
Mark Jeronimus
2
O OP pediu int pow(int, int), mas C ++ 11 apenas fornece double pow(int, int). Veja a explicação de @phuclv.
xuhdev
-4

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 voltaria a zero (de 1/25), mas essa seria uma resposta imprecisa.

Eu concordo, é estranho em alguns casos.

Jason A.
fonte
3
Requerer um segundo argumento sem sinal é obviamente necessário. Existem muitas aplicações que requerem apenas potências inteiras não negativas.
enigmaticPhysicist