Implementar a função doublé POWER (double base, doublé expoente), que retorna o valor de base elevado a expoente.
Transformar o expoente em uma razão de inteiros (multiplicando ambos por 10 até o numerador ficar inteiro).
Transformar o expoente em uma razão de inteiros (multiplicando ambos por 10 até o numerador ficar inteiro).
Passo 1
Beleza, a ideia é implementar em C (ou parecido) uma função
double power(double base, double expoente);
que calcula
.
Conteúdo: potenciação com expoentes reais, transformando o expoente em uma fração .
O que vamos precisar:
Conteúdo: potenciação com expoentes reais, transformando o expoente em uma fração
O que vamos precisar:
- Saber como converter um decimal em fração
(multiplicar por 10 até o numerador virar inteiro). - Como calcular potência de inteiro
. - Como extrair raiz-enésima (para o denominador
), usando busca binária ou Newton. - Tratar expoentes negativos (invertendo o resultado).
Passo 2
Converter o expoente em uma fração
.
- Seja
o expoente (por exemplo, ). - Enquanto
não for inteiro, aumentamos . - Ex.: para
, já faz inteiro.
- Ex.: para
- Definimos
Assim .
Passo 3
Tratar expoentes negativos.
Se , a gente chama a função com
e depois faz
Se
Isso evita ficar lidando com
negativo depois.
Passo 4
Calcular a parte inteira:
.
Usamos fast exponentiation (exponenciação rápida):
Usamos fast exponentiation (exponenciação rápida):
double powInt(double b, long m) {
double res = 1;
while (m > 0) {
if (m & 1) res *= b;
b *= b;
m >>= 1;
}
return res;
}
Isso faz em
multiplicações.
Passo 5
Extrair a raiz-enésima de
para obter
.
Explicando: queremos tal que
.
Fazemos busca binária no intervalo :
Explicando: queremos
Fazemos busca binária no intervalo
- low = 0, high = max(1, A).
- Enquanto
(p.ex. ): - mid = (low+high)/2
- se
, low = mid; senão high = mid
- Retornamos mid como aproximação de
.
Passo 6
Juntando tudo na função
power
:- Se expoente < 0, vamos inverter o resultado no fim.
- Converter expoente em
. - Calcular
via powInt
. - Extrair raiz-enésima
por busca binária. - Se era negativo, retornar
, senão só resultado.
Resposta
#include <math.h>
#include <stdbool.h>
static double powInt(double b, long m) {
double res = 1.0;
while (m > 0) {
if (m & 1) res *= b;
b *= b;
m >>= 1;
}
return res;
}
static double nthRoot(double A, long n) {
double low = 0.0, high = (A > 1.0 ? A : 1.0), mid;
const double eps = 1e-9;
while (high - low > eps) {
mid = 0.5 * (low + high);
if (powInt(mid, n) < A) low = mid;
else high = mid;
}
return 0.5 * (low + high);
}
double power(double base, double expoente) {
bool invert = false;
if (expoente < 0.0) {
invert = true;
expoente = -expoente;
}
// Passo de transformar expoente em m/n
long k = 0;
while (fabsl(expoente * pow(10.0, k) - round(expoente * pow(10.0, k))) > 1e-12) {
k++;
}
long m = lround(expoente * pow(10.0, k));
long n = 1;
for (long i = 0; i < k; i++) n *= 10;
// 1) base^m
double A = powInt(base, m);
// 2) raiz-enésima
double result = nthRoot(A, n);
return invert ? 1.0 / result : result;
}