Skip to content

Instantly share code, notes, and snippets.

@infusion
Last active November 25, 2018 14:10
Show Gist options
  • Save infusion/884a9f504ab1285081cdb80a624244de to your computer and use it in GitHub Desktop.
Save infusion/884a9f504ab1285081cdb80a624244de to your computer and use it in GitHub Desktop.
Calculates the rational power using newton method
# Copyright Robert Eisele https://www.xarg.org/
from fractions import Fraction
import math
# Calculates (a/b)^(c/d) if solution is rational
def pow(a, b, c, d):
xn = Fraction(int(math.pow(a, c / float(d))), int(math.pow(b, c / float(d))))
abc = Fraction(a, b)**c
for i in range(1, 6):
xp = xn - (xn**d - abc) / (d * xn**(d - 1))
if (xp == xn):
return xn
xn = xp
return xn
print(pow(9, 1, 1, 2)) # == 3
# derivation:
# Root: x = (a/b)^(c/d)
# <=> x^d = (a/b)^c
# <=> 0 = x^d - (a/b)^c
# f(x) = x^d - (a/b)^c
# f'(x) = dx^(d-1)
# Newton method:
# xp = xn - f(xn) / f'(xn)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment