Consider log(a)/log(b), the logarithm base b of a. Is the answer rational?

Compute g=gcd(a,b). If g=1 then the answer is irrational.

Compute x=log(a)/log(g). If x is not an integer then irrational. Because we only care if it is an integer, x can be found by binary search, looking at powers of g.

Similarly y=log(b)/log(g).

If x and y are both integers, then the answer is x/y.

Next, consider log(a1/a2)/log(b1/b2). Assume the fractions have both been reduced and a2 > 1 and b2 > 1.

Run the procedure above with (a1, b1), then (a2, b2). If the answers are both rational and equal to each other, then that is the final rational result. Otherwise, irrational.

These methods have the nice feature that we never have to factor any integer.

Not sure if they are correct, or whether there are more efficient ways.

## No comments :

Post a Comment