algorithm - potenciacion - potencias

Compruebe si un entero es una potencia entera de otro

Question

Esta es una pregunta de la entrevista : "Dado 2 enteros xey, verifique si x es una potencia entera de y" (por ejemplo, para x = 8 ey = 2 la respuesta es "verdadera", y para x = 10 ey = 2 "falso").

La solución obvia es:

int n = y; while(n < x) n *= y; return n == x

Ahora estoy pensando en cómo mejorarlo.

Por supuesto, puedo verificar algunos casos especiales: por ejemplo, tanto x como y deben ser números impares o pares, es decir, podemos verificar el bit menos significativo de y . Sin embargo, me pregunto si puedo mejorar el algoritmo central en sí mismo.

Answer 1

Aquí hay una versión de Python que reúne las ideas de @salva y @Axn y se modifica para que no genere ningún número mayor que los dados y utiliza solo el almacenamiento simple (leer, "sin listas") reduciendo repetidamente el número de interés. :

def perfect_base(b, n):
"""Returns True if integer n can be expressed as b**e where
n is a positive integer, else False."""
assert b > 1 and n >= b and int(n) == n and int(b) == b
# parity check
if not b % 2:
if n % 2:
return False # b,n is even,odd
if b == 2:
return n & (n - 1) == 0
if not b & (b - 1) and n & (n - 1):
return False # b == 2**m but n != 2**M
elif not n % 2:
return False # b,n is odd,even
while n >= b:
d = b
while d <= n:
n, r = divmod(n, d)
if r:
return False
d *= d
return n == 1

Answer 2

En los casos en que y es 2, hay un enfoque rápido que evita la necesidad de un ciclo. Este enfoque puede extenderse a los casos en que y es una potencia mayor de 2.

Si x es una potencia de 2, la representación binaria de x tiene un único bit establecido. Existe un algoritmo bastante simple para el conteo de bits para contar los bits en un entero en el tiempo O (log n) donde n es el ancho de bits de un entero. Muchos procesadores también tienen instrucciones especializadas que pueden manejar esto como una operación única, aproximadamente tan rápido como (por ejemplo) una negación entera.

Sin embargo, para extender el enfoque, primero adopte un enfoque ligeramente diferente para verificar un solo bit. Primero determine la posición del bit menos significativo. De nuevo, existe un algoritmo simple de manipulación de bits, y muchos procesadores tienen instrucciones especializadas rápidas.

Si este bit es el único bit, entonces (1 << pos) == x . La ventaja aquí es que si está probando una potencia de 4, puede probar la pos % 2 == 0 (el único bit está en una posición par). Si prueba una potencia de cualquier potencia de dos, puede probar la pos % (y >> 1) == 0 .

En principio, podrías hacer algo similar para probar poderes de 3 y poderes de poderes 3. El problema es que necesitarías una máquina que funcione en la base 3, lo cual es un poco improbable. Sin duda puede probar cualquier valor x para ver si su representación en la base y tiene un solo dígito distinto de cero, pero estaría haciendo más trabajo que ya está haciendo. Lo anterior explota el hecho de que las computadoras funcionan en binario.

Sin embargo, probablemente no valga la pena hacerlo en el mundo real.

Answer 3

Encontré esta solución // Compruebe si se puede expresar A como potencia de dos enteros

 int isPower(int A)
{
int i,a;
double p;
if(A==1)
return 1;
for(int a=1; a<=sqrt(A);++a )
{
p=log(A)/log(a);
if(p-int(p)<0.000000001)
return 1;
}
return 0;
}

binarycoder.org

Answer 4

Esto busca el exponente en pasos O (log N):

#define MAX_POWERS 100
int is_power(unsigned long x, unsigned long y) {
int i;
unsigned long powers[MAX_POWERS];
unsigned long last;
last = powers[0] = y;
for (i = 1; last < x; i++) {
last *= last; // note that last * last can overflow here!
powers[i] = last;
}
while (x >= y) {
unsigned long top = powers[--i];
if (x >= top) {
unsigned long x1 = x / top;
if (x1 * top != x) return 0;
x = x1;
}
}
return (x == 1);
}

Los números negativos no son manejados por este código, pero se puede hacer fácilmente con algún código condicional cuando i = 1

Answer 5

Esto parece ser bastante rápido para los números positivos ya que encuentra los límites inferior y superior de la potencia deseada y luego aplica la búsqueda binaria.

#include <iostream>
#include <cmath>
using namespace std;
//x is the dividend, y the divisor.
bool isIntegerPower(int x, int y)
{
int low = 0, high;
int exp = 1;
int val = y;
//Loop by changing exponent in the powers of 2 and
//Find out low and high exponents between which the required exponent lies.
while(1)
{
val = pow((double)y, exp);
if(val == x)
return true;
else if(val > x)
break;
low = exp;
exp = exp * 2;
high = exp;
}
//Use binary search to find out the actual integer exponent if exists
//Otherwise, return false as no integer power.
int mid = (low + high)/2;
while(low < high)
{
val = pow((double)y, mid);
if(val > x)
{
high = mid-1;
}
else if(val == x)
{
return true;
}
else if(val < x)
{
low = mid+1;
}
mid = (low + high)/2;
}
return false;
}
int main()
{
cout<<isIntegerPower(1024,2);
}

Answer 6

Haría mejor en dividir repetidamente y en x. La primera vez que obtienes un resto distinto de cero sabes que x no es una potencia entera de y.

while (x%y == 0) x = x / y
return x == 1

Esto trata con su punto impar / par en la primera iteración.

Answer 7

Implementaría la función así:

bool IsWholeNumberPower(int x, int y)
{
double power = log(x)/log(y);
return floor(power) == power;
}

Esto no debería necesitar verificación dentro de un delta como es común con las comparaciones de coma flotante, ya que estamos verificando números enteros.

Answer 8

Las respuestas anteriores son correctas, me gustó más la respuesta de Paul. Es simple y limpio. Aquí está la implementación de Java de lo que sugirió:

public static boolean isPowerOfaNumber(int baseOrg, int powerOrg) {
double base = baseOrg;
double power = powerOrg;
while (base % power == 0)
base = base / power;
// return true if base is equal 1
return base == 1;
}

Answer 9

Pensándolo bien, no hagas esto. No funciona para x y / o negativo. Tenga en cuenta que todas las demás respuestas basadas en el log presentan en este momento también se rompen de la misma manera.

La siguiente es una solución general rápida (en Java):

static boolean isPow(int x, int y) {
int logyx = (int)(Math.log(x) / Math.log(y));
return pow(y, logyx) == x || pow(y, logyx + 1) == x;
}

Donde pow() es una función de exponenciación entera tal como la siguiente en Java:

static int pow(int a, int b) {
return (int)Math.pow(a, b);
}

(Esto funciona debido a la siguiente garantía provista por Math.pow : "Si ambos argumentos son enteros, entonces el resultado es exactamente igual al resultado matemático de elevar el primer argumento al poder del segundo argumento ...")

La razón para ir con logaritmos en lugar de división repetida es el rendimiento: mientras que el registro es más lento que la división , es más lento por un pequeño múltiplo fijo. Al mismo tiempo, elimina la necesidad de un bucle y, por lo tanto, le proporciona un algoritmo de tiempo constante.

Answer 10

Si tiene acceso a la potencia más grande de y , que puede ajustarse dentro del tipo de datos requerido, esta es una manera realmente ingeniosa de resolver este problema.

Digamos, para nuestro caso, y == 3 . Entonces, necesitaríamos verificar si x es una potencia de 3.

Dado que necesitamos verificar si un entero x es una potencia de 3, comencemos a pensar acerca de este problema en términos de qué información ya está disponible.

1162261467 es la mayor potencia de 3 que puede caber en una int de Java.
1162261467 = 3^19 + 0

La x dada se puede expresar como [(a power of 3) + (some n)] . Creo que es bastante elemental poder demostrar que si n es 0 (lo que sucede si f x es una potencia de 3), 1162261467 % x = 0 .

Entonces, para verificar si un entero dado x es una potencia de tres, verifique si x > 0 && 1162261467 % x == 0 .

Generalizando Para comprobar si un entero dado x es una potencia de un entero y dado, compruebe si x > 0 && Y % x == 0 : Y es la mayor potencia de y que puede caber en un tipo de datos entero.

La idea general es que si A es un poder de Y , A puede expresarse como B/Ya , donde a es un entero y A < B . Sigue el mismo principio exacto para A > B El caso A = B es elemental.

Answer 11

Significa que log _y (x) debe ser un entero . No necesita ningún bucle . en O (1) vez

public class PowerTest {
public static boolean isPower(int x, int y) {
double d = Math.log(Math.abs(x)) / Math.log(Math.abs(y));
if ((x > 0 && y > 0) || (x < 0 && y < 0)) {
if (d == (int) d) {
return true;
} else {
return false;
}
} else if (x > 0 && y < 0) {
if ((int) d % 2 == 0) {
return true;
} else {
return false;
}
} else {
return false;
}
}
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(isPower(-32, -2));
System.out.println(isPower(2, 8));
System.out.println(isPower(8, 12));
System.out.println(isPower(9, 9));
System.out.println(isPower(-16, 2));
System.out.println(isPower(-8, -2));
System.out.println(isPower(16, -2));
System.out.println(isPower(8, -2));
}
}

Answer 12

 double a=8;
double b=64;
double n = Math.log(b)/Math.log(a);
double e = Math.ceil(n);
if((n/e) == 1){
System.out.println("true");
} else{
System.out.println("false");
}