Come implementare elevamento a potenza di un numero razionale, senza radice ennesima?

Question

La sua disposizione per me solo registrazione (di base "e"), il peccato, abbronzatura e sqrt (solo radice quadrata) le funzioni e gli operatori aritmetici di base (+ - * / mod). Ho anche la "e" costante.

sto sperimentando diversi problemi con Deluge (zoho.com) per queste restrizioni. Devo implementare elevazione a potenza di basi razionali (frazione) ed esponenti.

Answer 1

Di 'si vuole calcolare pow(A, B)

Si consideri la rappresentazione di B in base 2:

B = b[n]   * pow(2, n    ) +
    b[n-1] * pow(2, n - 1) +
    ...
    b[2]   * pow(2, 2    ) +
    b[1]   * pow(2, 1    ) +
    b[0]   * pow(2, 0    ) +
    b[-1]  * pow(2, -1   ) +
    b[-2]  * pow(2, -2   ) +
    ...

 = sum(b[i] * pow(2, i))

dove b[x] può essere 0 o 1 e pow(2, y) è una potenza intera di due (cioè, 1, 2, 4, 1/2, 1/4, 1/8).

Poi,

pow(A, B) = pow(A, sum(b[i] * pow(2, i)) = mul(pow(A, b[i] * pow(2, i)))

E così pow(A, B) può essere calcolata usando solo moltiplicazioni e operazioni radice quadrata

Answer 2

Se si dispone di una funzione F () che fa e ^ x, dove e è la costante, e x è un numero qualsiasi, allora si può fare questo: (a è di base, b è esponente, ln è log-e)

a ^ b = F (b * ln (a))

Se non si dispone di F () che fa e ^ x, poi diventa più complicato. Se il vostro esponente (b) è razionale, allora si dovrebbe essere in grado di trovare interi m e n in modo che b = m / n, con un ciclo di qualche tipo. Una volta che avete m ed n, è fare un altro ciclo che i multipli di per sé M volte per ottenere un ^ m, quindi multipli di per sé n volte per ottenere un ^ n, poi dividere un ^ m / a ^ n per ottenere un ^ (m / n), che è un ^ b.