algorithm - tabla - ¿Cómo verificar si un número entero es una potencia de 3?

propiedades de la potenciacion de numeros enteros ejercicios

Question

Vi esta pregunta y apareció esta idea.

Answer 1

¿Qué tan grande es tu entrada? Con la memoria O (log (N)) puede hacer más rápido, O (log (log (N)). Precompute las potencias de 3 y luego haga una búsqueda binaria en los valores precalculados.

Answer 2

Aquí hay una implementación agradable y rápida del método de Ray Burns en C:

bool is_power_of_3(unsigned x) {
if (x > 0x0000ffff)
x *= 0xb0cd1d99; // multiplicative inverse of 59049
if (x > 0x000000ff)
x *= 0xd2b3183b; // multiplicative inverse of 243
return x <= 243 && ((x * 0x71c5) & 0x5145) == 0x5145;
}

Utiliza el truco inverso multiplicativo para dividir primero por 3 ^ 10 y luego por 3 ^ 5. Finalmente, necesita verificar si el resultado es 1, 3, 9, 27, 81 o 243, lo cual se hace mediante un hash simple que encontré por prueba y error.

En mi CPU (Intel Sandy Bridge), es bastante rápido, pero no tan rápido como el método de starblue que usa el logaritmo binario (que se implementa en hardware en esa CPU). Pero en una CPU sin tal instrucción, o cuando las tablas de búsqueda son indeseables, podría ser una alternativa.

Answer 3

Divida recursivamente por 3, verifique que el resto sea cero y vuelva a aplicar al cociente.

Tenga en cuenta que 1 es una respuesta válida, ya que 3 a la potencia cero es 1 es un caso marginal que debe tenerse en cuenta.

Answer 4

Entre los poderes de dos hay a lo sumo un poder de tres. Entonces la siguiente es una prueba rápida:

1. Encuentre el logaritmo binario de n buscando la posición del primer bit del número. Esto es muy rápido, ya que los procesadores modernos tienen una instrucción especial para eso. (De lo contrario, puedes hacerlo haciendo giros , ver Bit Twiddling Hacks ).

2. Busque la potencia potencial de tres en una tabla indexada por esta posición y compárela con n (si no hay potencia de tres, puede almacenar cualquier número con un logaritmo binario diferente).

3. Si son iguales, devuelve sí, de lo contrario no.

El tiempo de ejecución depende principalmente del tiempo necesario para acceder a la entrada de la tabla. Si usamos números enteros de máquina, la tabla es pequeña, y probablemente esté en caché (la estamos utilizando muchos millones de veces, de lo contrario, este nivel de optimización no tendría sentido).

Answer 5

Establecer una solución basada ...

DECLARE @LastExponent smallint, @SearchCase decimal(38,0)
SELECT
@LastExponent = 79, -- 38 for bigint
@SearchCase = 729
;WITH CTE AS
(
SELECT
POWER(CAST(3 AS decimal(38,0)), ROW_NUMBER() OVER (ORDER BY c1.object_id)) AS Result,
ROW_NUMBER() OVER (ORDER BY c1.object_id) AS Exponent
FROM
sys.columns c1, sys.columns c2
)
SELECT
Result, Exponent
FROM
CTE
WHERE
Exponent <= @LastExponent
AND
Result = @SearchCase

Con SET STATISTICS TIME ON , registra lo más bajo posible, 1 milisegundo.

Answer 6

Este es un resumen de todas las buenas respuestas debajo de estas preguntas, y las cifras de rendimiento se pueden encontrar en el artículo de LeetCode .

1. iteración de bucle

Complejidad del tiempo O (log (n)), complejidad del espacio O (1)

public boolean isPowerOfThree(int n) {
if (n < 1) {
return false;
}
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}

2. Conversión de base

Convierte el entero a un número base 3 y comprueba si está escrito como un 1 principal seguido de todos 0. Está inspirado por la solución para comprobar si un número es potencia de 2 haciendo n & (n - 1) == 0

Complejidad del tiempo: O (log (n)) según el lenguaje y el compilador, complejidad del espacio: O (log (n))

public boolean isPowerOfThree(int n) {
return Integer.toString(n, 3).matches("^10*$");
}

3 Matemáticas

Si n = 3^i , entonces i = log(n) / log(3) , y así llega a la solución

Complejidad del tiempo: según el lenguaje y el compilador, la complejidad del espacio: O (1)

public boolean isPowerOfThree(int n) {
return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon;
}

4 limitaciones enteras

Debido a que 3^19 = 1162261467 es la mayor potencia de 3 números encaja en un entero de 32 bits, así podemos hacer

Complejidad del tiempo: O (1), complejidad del espacio: O (1)

public boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}

5 limitaciones enteras con conjunto

La idea es similar a la # 4 pero usa un conjunto para almacenar toda la potencia posible de 3 números (de 3 ^ 0 a 3 ^ 19). Hace que el código sea más legible.

6 Recursivo (C ++ 11)

Esta solución es específica para C ++ 11, utilizando meta programación de plantillas para que complier reemplace la llamada isPowerOf3<Your Input>::cValue con resultado calculado.

Complejidad del tiempo: O (1), complejidad del espacio: O (1)

template<int N>
struct isPowerOf3 {
static const bool cValue = (N % 3 == 0) && isPowerOf3<N / 3>::cValue;
};
template<>
struct isPowerOf3<0> {
static const bool cValue = false;
};
template<>
struct isPowerOf3<1> {
static const bool cValue = true;
};
int main() {
cout<<isPowerOf3<1162261467>::cValue;
return 0;
}

Answer 7

Estoy sorprendido de esto Todos parecen haber perdido el algoritmo más rápido de todos.

El siguiente algoritmo es más rápido en promedio, y dramáticamente más rápido en algunos casos, que un while(n%3==0) n/=3; simple while(n%3==0) n/=3; lazo:

bool IsPowerOfThree(uint n)
{
// Optimizing lines to handle the most common cases extremely quickly
if(n%3 != 0) return n==1;
if(n%9 != 0) return n==3;
// General algorithm - works for any uint
uint r;
n = Math.DivRem(n, 59049, out r); if(n!=0 && r!=0) return false;
n = Math.DivRem(n+r, 243, out r); if(n!=0 && r!=0) return false;
n = Math.DivRem(n+r, 27, out r); if(n!=0 && r!=0) return false;
n += r;
return n==1 || n==3 || n==9;
}

Las constantes numéricas en el código son 3 ^ 10, 3 ^ 5 y 3 ^ 3.

Cálculos de rendimiento

En las CPU modernas, DivRem es a menudo una sola instrucción que toma un ciclo. En otros se expande a un div seguido de un mul y un add, que tomaría más como tres ciclos en total. Cada paso del algoritmo general parece largo pero en realidad solo consiste en: DivRem, cmp, cmove, cmp, cand, cjmp, add . Hay mucho paralelismo disponible, por lo que en un procesador superescalar bidireccional típico, cada paso probablemente se ejecutará en aproximadamente 4 ciclos de reloj, dando un tiempo de ejecución de peor caso garantizado de aproximadamente 25 ciclos de reloj.

Si los valores de entrada se distribuyen uniformemente en el rango de UInt32 , estas son las probabilidades asociadas con este algoritmo:

• Regrese en o antes de la primera línea de optimización: 66% del tiempo
• Regrese en o antes de la segunda línea de optimización: el 89% del tiempo
• Regrese en o antes del primer paso del algoritmo general: 99.998% del tiempo
• Regrese en o antes del segundo paso del algoritmo general: 99.99998% del tiempo
• Regrese en o antes del tercer paso del algoritmo general: 99.999997% del tiempo

Este algoritmo supera al ciclo simple while(n%3==0) n/=3 , que tiene las siguientes probabilidades:

• Regresar en la primera iteración: 66% del tiempo
• Regresar en las dos primeras iteraciones: el 89% del tiempo
• Regresar en las primeras tres iteraciones: 97% del tiempo
• Regresar en las primeras cuatro iteraciones: 98.8% del tiempo
• Regresa en las primeras cinco iteraciones: 99.6% del tiempo ... y así sucesivamente a ...
• Regrese en las primeras doce iteraciones: 99.9998% de las veces ... y más allá ...

Lo que es quizás aún más importante, este algoritmo maneja potencias medianas y grandes de tres (y múltiplos de ellas) de manera mucho más eficiente: en el peor de los casos, el algoritmo simple consumirá más de 100 ciclos de CPU porque se repetirá 20 veces (41 veces para 64 bits ) El algoritmo que presento aquí nunca tomará más de aproximadamente 25 ciclos.

Extendiéndose a 64 bits

Extender el algoritmo anterior a 64 bits es trivial: simplemente agrega un paso más. Aquí hay una versión de 64 bits del algoritmo anterior optimizado para procesadores sin una división eficiente de 64 bits:

bool IsPowerOfThree(ulong nL)
{
// General algorithm only
ulong rL;
nL = Math.DivRem(nL, 3486784401, out rL); if(nL!=0 && rL!=0) return false;
nL = Math.DivRem(nL+rL, 59049, out rL); if(nL!=0 && rL!=0) return false;
uint n = (uint)nL + (uint)rL;
n = Math.DivRem(n, 243, out r); if(n!=0 && r!=0) return false;
n = Math.DivRem(n+r, 27, out r); if(n!=0 && r!=0) return false;
n += r;
return n==1 || n==3 || n==9;
}

La nueva constante es 3 ^ 20. Las líneas de optimización se omiten desde la parte superior del método porque bajo nuestra suposición de que la división de 64 bits es lenta, en realidad reducirían la velocidad.

Por qué esta técnica funciona

Digamos que quiero saber si "100000000000000000" es una potencia de 10. Podría seguir estos pasos:

1. Divido por 10 ^ 10 y obtengo un cociente de 10000000 y un resto de 0. Estos se suman a 10000000.
2. Divido por 10 ^ 5 y obtengo un cociente de 100 y un resto de 0. Estos se suman a 100.
3. Divido por 10 ^ 3 y obtengo un cociente de 0 y un resto de 100. Estos se suman a 100.
4. Divido por 10 ^ 2 y obtengo un cociente de 1 y un resto de 0. Estos se suman a 1.

Debido a que comencé con una potencia de 10, cada vez que dividí por una potencia de 10 terminé con un cociente cero o un resto cero. Si hubiera empezado con algo que no fuera una potencia de 10, tarde o temprano habría terminado con un cociente o un resto distinto de cero.

En este ejemplo, seleccioné los exponentes de 10, 5 y 3 para que coincidan con el código proporcionado anteriormente, y agregué 2 solo por el gusto de hacerlo. También funcionarían otros exponentes: hay un algoritmo simple para seleccionar los exponentes ideales dado su valor de entrada máximo y la potencia máxima de 10 permitidos en la salida, pero este margen no tiene espacio suficiente para contenerlo.

NOTA: Puede haber estado pensando en base diez a lo largo de esta explicación, pero toda la explicación anterior puede leerse y entenderse de forma idéntica si está pensando en la base tres , excepto que los exponentes se habrían expresado de manera diferente (en lugar de "10", "5", "3" y "2" Tendría que decir "101", "12", "10" y "2").

Answer 8

Existe un método de tiempo constante (bastante rápido) para enteros de tamaño limitado (por ejemplo, enteros de 32 bits).

Tenga en cuenta que para un entero N que es una potencia de 3, lo siguiente es verdadero:

1. Para cualquier M <= N que sea una potencia de 3, M divide a N
2. Para cualquier M <= N que no sea una potencia 3, M no divide N

La mayor potencia de 3 que cabe en 32 bits es 3486784401 ( 3^20 ). Esto da el siguiente código:

bool isPower3(std::uint32_t value) {
return value != 0 && 3486784401u % value == 0;
}

De manera similar para los 32 bits con 1162261467 es 1162261467 ( 3^19 ):

bool isPower3(std::int32_t value) {
return value > 0 && 1162261467 % value == 0;
}

En general, el número mágico es:

== pow(3, floor(log(MAX) / log(3)))

Cuidado con los errores de redondeo de coma flotante, usa una calculadora matemática como Wolfram Alpha para calcular la constante. Por ejemplo, para 2^63-1 (firmado int64), tanto C ++ como Java dan 4052555153018976256 , pero el valor correcto es 4052555153018976267 .

Answer 9

La solución más rápida es probar si n > 0 && 3**19 % n == 0 como se da en otra respuesta o hash perfecto (abajo). Primero, doy dos soluciones basadas en la multiplicación.

Multiplicación

Me pregunto por qué todos echaron de menos que la multiplicación es mucho más rápida que la división:

for (int i=0, pow=1; i<=19, pow*=3; ++i) {
if (pow >= n) {
return pow == n;
}
}
return false;

Solo prueba todos los poderes, detente cuando crezca demasiado. Evite el desbordamiento ya que 3**19 = 0x4546B3DB es la conexión de alimentación más grande en int firmado de 32 bits.

Multiplicación con búsqueda binaria

La búsqueda binaria podría verse como

int pow = 1;
int next = pow * 6561; // 3**8
if (n >= next) pow = next;
next = pow * 81; // 3**4
if (n >= next) pow = next;
next = pow * 81; // 3**4; REPEATED
if (n >= next) pow = next;
next = pow * 9; // 3**2
if (n >= next) pow = next;
next = pow * 3; // 3**1
if (n >= next) pow = next;
return pow == next;

Se repite un paso, de modo que el exponente máximo 19 = 8+4+4+2+1 se puede alcanzar exactamente.

Hashing perfecto

Hay 20 potencias de tres que se ajustan a un int firmado de 32 bits, por lo que tomamos una tabla de 32 elementos. Con un poco de experimentación, encontré la función hash perfecta

def hash(x):
return (x ^ (x>>1) ^ (x>>2)) & 31;

asignando cada potencia a un índice distinto entre 0 y 31. Lo restante es trivial:

// Create a table and fill it with some power of three.
table = [1 for i in range(32)]
// Fill the buckets.
for n in range(20): table[hash(3**n)] = 3**n;

Ahora tenemos

table = [
1162261467, 1, 3, 729, 14348907, 1, 1, 1,
1, 1, 19683, 1, 2187, 81, 1594323, 9,
27, 43046721, 129140163, 1, 1, 531441, 243, 59049,
177147, 6561, 1, 4782969, 1, 1, 1, 387420489]

y puede probar muy rápido a través de

def isPowerOfThree(x):
return table[hash(x)] == x

Answer 10

Me parece un poco pensar que si por "entero" te refieres a "entero de 32 bits con signo", entonces (pseudocódigo)

return (n == 1)
or (n == 3)
or (n == 9)
...
or (n == 1162261467)

tiene una cierta hermosa simplicidad (el último número es 3 ^ 19, por lo que no hay un número absurdo de casos). Incluso para un entero sin signo de 64 bits, solo quedan 41 casos (gracias @Alexandru por señalar mi error cerebral). Y, por supuesto, sería imposible para la aritmética de precisión arbitraria ...

Answer 11

Para números realmente grandes n , puede usar el siguiente truco matemático para acelerar la operación de

 n % 3 == 0

que es realmente lento y muy probablemente el punto de estrangulamiento de cualquier algoritmo que dependa de la verificación repetida de los desechos. Tienes que entender la aritmética modular para seguir lo que estoy haciendo, que es parte de la teoría elemental de números.

Sea x = Σ _k a _k 2 ^k el número de interés. Podemos dejar que el límite superior de la suma sea ∞ con la comprensión de que a _k = 0 para algunos k> M. Luego

0 ≡ x ≡ a _k a _k 2 ^k ≡ a _k a _2k 2 ^2k + a _{2k + 1} 2 ^{2k + 1} ≡ Σ _k 2 ^2k (a _2k + a _{2k + 1} 2) ≡ a _k a _2k + a _{2k + 1} 2 (mod 3)

desde 2 ^2k ≡ 4 ^k ≡ 1 ^k ≡ 1 (mod 3).

Dada una representación binaria de un número x con 2n + 1 bits como

x ₀ x ₁ x ₂ ... x _{2n + 1}

donde x _k ∈ {0,1} puede agrupar pares pares impares

(x ₀ x ₁ ) (x ₂ x ₃ ) ... (x _2n x _{2n + 1} ).

Deje q denotar el número de emparejamientos de la forma (1 0) y deje que r denote el número de emparejamientos de la forma (0 1). Luego se deduce de la ecuación anterior que 3 | x si y solo si 3 | (q + 2r). Además, puede mostrar que 3 | (q + 2r) si y solo si q y r tienen el mismo resto cuando se divide por 3.

Entonces, un algoritmo para determinar si un número es divisible por 3 podría hacerse de la siguiente manera

 q = 0, r = 0
for i in {0,1, .., n}
pair <- (x_{2i} x_{2i+1})
if pair == (1 0)
switch(q)
case 0:
q = 1;
break;
case 1:
q = 2;
break;
case 2:
q = 0;
break;
else if pair == (0 1)
switch(r)
case 0:
r = 1;
break;
case 1:
r = 2;
break;
case 2:
r = 0;
return q == r

Este algoritmo es más eficiente que el uso de%.

--- Editar muchos años después ----

Me tomó unos minutos implementar una versión rudimentaria de esto en python que comprueba su verdadero para todos los números hasta 10 ^ 4. Lo incluyo a continuación para referencia. Obviamente, hacer uso de este implementaría esto lo más cerca posible del hardware. Esta técnica de escaneo se puede extender a cualquier número que uno quiera alterando la derivación. También conjeturo que la parte de "escaneo" del algoritmo puede reformularse en una fórmula recursiva tipo O(log n) similar a una FFT, pero tendría que pensar en ello.

#!/usr/bin/python
def bits2num(bits):
num = 0
for i,b in enumerate(bits):
num += int(b) << i
return num
def num2bits(num):
base = 0
bits = list()
while True:
op = 1 << base
if op > num:
break
bits.append(op&num !=0)
base += 1
return "".join(map(str,map(int,bits)))[::-1]
def div3(bits):
n = len(bits)
if n % 2 != 0:
bits = bits + ''0''
n = len(bits)
assert n % 2 == 0
q = 0
r = 0
for i in range(n/2):
pair = bits[2*i:2*i+2]
if pair == ''10'':
if q == 0:
q = 1
elif q == 1:
q = 2
elif q == 2:
q = 0
elif pair == ''01'':
if r == 0:
r = 1
elif r == 1:
r = 2
elif r == 2:
r = 0
else:
pass
return q == r
for i in range(10000):
truth = (i % 3) == 0
bits = num2bits(i)
check = div3(bits)
assert truth == check

Answer 12

Pregunta muy interesante, me gusta la respuesta de starblue , y esta es una variación de su algoritmo que convergerá un poco más rápido a la solución:

private bool IsPow3(int n)
{
if (n == 0) return false;
while (n % 9 == 0)
{
n /= 9;
}
return (n == 1 || n == 3);
}

Answer 13

Puedes hacer mejor que la división repetida, que toma O (lg (X) * | division |) vez. Esencialmente haces una búsqueda binaria en potencias de 3. Realmente haremos una búsqueda binaria en N, donde 3 ^ N = valor de entrada). El ajuste del Pth dígito binario de N corresponde a multiplicar por 3 ^ (2 ^ P), y los valores de la forma 3 ^ (2 ^ P) se pueden calcular por cuadratura repetida.

Algoritmo

• Deje que el valor de entrada sea X.
• Genera una lista L de valores cuadrados repetidos que termina una vez que pasas X.
• Deje que su valor candidato sea T, inicializado en 1.
• Para cada E en L invertida, si T * E <= X entonces deje T * = E.
• Devuelve T == X.

Complejidad:

O (lg (lg (X)) * | multiplicación |) - Generar e iterar sobre L toma iteraciones de lg (lg (X)), y la multiplicación es la operación más cara en una iteración.

Answer 14

Solución simple y de tiempo constante:

return n == power(3, round(log(n) / log(3)))

Answer 15

Su pregunta es bastante fácil de responder al definir una función simple para ejecutar el control por usted. La implementación de ejemplo que se muestra a continuación está escrita en Python, pero no debería ser difícil de reescribir en otros idiomas si es necesario. A diferencia de la última versión de esta respuesta, el código que se muestra a continuación es mucho más confiable.

Python 3.6.0 (v3.6.0:41df79263a11, Dec 23 2016, 08:06:12) [MSC v.1900 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> import math
>>> def power_of(number, base):
return number == base ** round(math.log(number, base))
>>> base = 3
>>> for power in range(21):
number = base ** power
print(f''{number} is ''
f''{"" if power_of(number, base) else "not "}''
f''a power of {base}.'')
number += 1
print(f''{number} is ''
f''{"" if power_of(number, base) else "not "}''
f''a power of {base}.'')
print()
1 is a power of 3.
2 is not a power of 3.
3 is a power of 3.
4 is not a power of 3.
9 is a power of 3.
10 is not a power of 3.
27 is a power of 3.
28 is not a power of 3.
81 is a power of 3.
82 is not a power of 3.
243 is a power of 3.
244 is not a power of 3.
729 is a power of 3.
730 is not a power of 3.
2187 is a power of 3.
2188 is not a power of 3.
6561 is a power of 3.
6562 is not a power of 3.
19683 is a power of 3.
19684 is not a power of 3.
59049 is a power of 3.
59050 is not a power of 3.
177147 is a power of 3.
177148 is not a power of 3.
531441 is a power of 3.
531442 is not a power of 3.
1594323 is a power of 3.
1594324 is not a power of 3.
4782969 is a power of 3.
4782970 is not a power of 3.
14348907 is a power of 3.
14348908 is not a power of 3.
43046721 is a power of 3.
43046722 is not a power of 3.
129140163 is a power of 3.
129140164 is not a power of 3.
387420489 is a power of 3.
387420490 is not a power of 3.
1162261467 is a power of 3.
1162261468 is not a power of 3.
3486784401 is a power of 3.
3486784402 is not a power of 3.
>>>

NOTA: La última revisión ha hecho que esta respuesta sea casi la misma que la respuesta de TMS .

Answer 16

si (log n) / (log 3) es integral, n es una potencia de 3.

Answer 17

This is a constant time method! Sí. O(1). For numbers of fixed length, say 32-bits.

Given that we need to check if an integer n is a power of 3, let us start thinking about this problem in terms of what information is already at hand.

1162261467 is the largest power of 3 that can fit into an Java int.
1162261467 = 3^19 + 0

The given n can be expressed as [(a power of 3) + (some x )]. I think it is fairly elementary to be able to prove that if x is 0(which happens iff n is a power of 3), 1162261467 % n = 0.

The general idea is that if X is some power of 3, X can be expressed as Y/3a , where a is some integer and X < Y. It follows the exact same principle for Y < X. The Y = X case is elementary.

So, to check if a given integer n is a power of three, check if n > 0 && 1162261467 % n == 0 .

Answer 18

Another approach is to generate a table on compile time. The good thing is, that you can extend this to powers of 4, 5, 6, 7, whatever

template<std::size_t... Is>
struct seq
{ };
template<std::size_t N, std::size_t... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>
{ };
template<std::size_t... Is>
struct gen_seq<0, Is...> : seq<Is...>
{ };
template<std::size_t N>
struct PowersOfThreeTable
{
std::size_t indexes[N];
std::size_t values[N];
static constexpr std::size_t size = N;
};
template<typename LambdaType, std::size_t... Is>
constexpr PowersOfThreeTable<sizeof...(Is)>
generatePowersOfThreeTable(seq<Is...>, LambdaType evalFunc)
{
return { {Is...}, {evalFunc(Is)...} };
}
template<std::size_t N, typename LambdaType>
constexpr PowersOfThreeTable<N> generatePowersOfThreeTable(LambdaType evalFunc)
{
return generatePowersOfThreeTable(gen_seq<N>(), evalFunc);
}
template<std::size_t Base, std::size_t Exp>
struct Pow
{
static constexpr std::size_t val = Base * Pow<Base, Exp-1ULL>::val;
};
template<std::size_t Base>
struct Pow<Base, 0ULL>
{
static constexpr std::size_t val = 1ULL;
};
template<std::size_t Base>
struct Pow<Base, 1ULL>
{
static constexpr std::size_t val = Base;
};
constexpr std::size_t tableFiller(std::size_t val)
{
return Pow<3ULL, val>::val;
}
bool isPowerOfThree(std::size_t N)
{
static constexpr unsigned tableSize = 41; //choosen by fair dice roll
static constexpr PowersOfThreeTable<tableSize> table =
generatePowersOfThreeTable<tableSize>(tableFiller);
for(auto a : table.values)
if(a == N)
return true;
return false;
}

Answer 19

Here''s a general algorithm for finding out if a number is a power of another number:

bool IsPowerOf(int n,int b)
{
if (n > 1)
{
while (n % b == 0)
{
n /= b;
}
}
return n == 1;
}

Answer 20

I measured times (C#, Platform target x64) for some solutions.

using System;
class Program
{
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
for (uint n = ~0u; n > 0; n--) ;
Console.WriteLine(sw.Elapsed); // nada 1.1 s
sw.Restart();
for (uint n = ~0u; n > 0; n--) isPow3a(n);
Console.WriteLine(sw.Elapsed); // 3^20 17.3 s
sw.Restart();
for (uint n = ~0u; n > 0; n--) isPow3b(n);
Console.WriteLine(sw.Elapsed); // % / 10.6 s
Console.Read();
}
static bool isPow3a(uint n) // Elric
{
return n > 0 && 3486784401 % n == 0;
}
static bool isPow3b(uint n) // starblue
{
if (n > 0) while (n % 3 == 0) n /= 3;
return n == 1;
}
}

Another way (of splitting hairs).

using System;
class Program
{
static void Main()
{
Random rand = new Random(0); uint[] r = new uint[512];
for (int i = 0; i < 512; i++)
r[i] = (uint)(rand.Next(1 << 30)) << 2 | (uint)(rand.Next(4));
var sw = System.Diagnostics.Stopwatch.StartNew();
for (int i = 1 << 23; i > 0; i--)
for (int j = 0; j < 512; j++) ;
Console.WriteLine(sw.Elapsed); // 0.3 s
sw.Restart();
for (int i = 1 << 23; i > 0; i--)
for (int j = 0; j < 512; j++) isPow3c(r[j]);
Console.WriteLine(sw.Elapsed); // 10.6 s
sw.Restart();
for (int i = 1 << 23; i > 0; i--)
for (int j = 0; j < 512; j++) isPow3b(r[j]);
Console.WriteLine(sw.Elapsed); // 9.0 s
Console.Read();
}
static bool isPow3c(uint n)
{ return (n & 1) > 0 && 3486784401 % n == 0; }
static bool isPow3b(uint n)
{ if (n > 0) while (n % 3 == 0) n /= 3; return n == 1; }
}

Answer 21

Python solution

from math import floor
from math import log
def IsPowerOf3(number):
p = int(floor(log(number) / log(3)))
power_floor = pow(3, p)
power_ceil = power_floor * 3
if power_floor == number or power_ceil == number:
return True
return False

This is much faster than the simple divide by 3 solution.

Proof: 3 ^ p = number

p log(3) = log(number) (taking log both side)

p = log(number) / log(3)

Answer 22

#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int main()
{
int n, power=0;
cout<<"enter a number"<<endl;
cin>>n;
if (n>0){
for(int i=0; i<=n; i++)
{
int r=n%3;
n=n/3;
if (r==0){
power++;
}
else{
cout<<"not exactly power of 3";
return 0;
}
}
}
cout<<"the power is "<<power<<endl;
}

Answer 23

while (n % 3 == 0) {
n /= 3;
}
return n == 1;

Tenga en cuenta que 1 es el poder zeroth de tres.

Editar: También debe verificar cero antes del ciclo, ya que el ciclo no terminará para n = 0 (gracias a Bruno Rothgiesser).