[C con Clase] Mejorar un algoritmo que calcula las combinaciones de base y exponente enteras para un número entero dado

[Davidson, Steven]

Hola User,

2013/6/7 User <usuarioanonimomysql en gmail.com>

> Hola,
>
> He hecho un código que dado un número entero, obtiene las combinaciones de
> base y exponente enteras que existen para ese número. Por ejemplo si
> introducís el número 21952 obtendréis los números de base y exponente 28 y
> 3 respectivamente.
>
> Como se puede ver en el código, el exponente está limitado a 4 con lo que
> no encontrará combinaciones de base y exponente con un exponente mayor a 4.
>
> Me gustaría proponer el reto de que alguien lo mejore haciendo que sea más
> rápido. El código:
>

Bueno, tal y como comentas en tu código fuente, lo que realmente hace es
que "descompone el número introducido". En matemáticas, esto implica que
quieres descomponer en factores (o factorizar). Esto significa que deberías
determinar los factores primos. Por ejemplo,

21952 ÷ 2
10976 ÷ 2
5488 ÷ 2
2744 ÷ 2
1372 ÷ 2
686 ÷ 2
343 ÷ 7
49 ÷ 7
7 ÷ 7
1

Así que,

21952 = 2^6 * 7^3 = 4^3 * 7^3 = 28^3

Habría que comprobar si algunos factores comunes se pueden reescribir para
obtener una base común y así determinar el exponente. Es decir, el programa
debería comprobar si se puede reescribir 2^6 para que sea 4^3, porque
tenemos un 7^3. Esto supone que tenemos dos bases diferentes pero con el
mismo exponente; así que, 4^3 * 7^3 = (4*7)^3 = 28^3. Ahora tenemos la base
común, 28, y el exponente, 3.


Si no te gusta la solución anterior - y prefieres usar la tuya - entonces,
sugiero mejorar el algoritmo de 'eleva()'. En lugar de basarse en
multiplicar la base tantas veces por sí misma, multiplica la base cuadrada.
Esto implica que el exponente se basa en 2 y por tanto, podemos tratar el
exponente como una secuencia binaria: 0 implica que no pertenece al
resultado final y 1 indica que sí. Por ejemplo,

28^3
------

base <-- 28
exponente <-- 3

resultado <-- 1

bucle: exponente > 0
   Si exponente AND 1 != 0, entonces
       resultado <-- resultado * base

   base <-- base * base
   exponente <-- exponente SHR 1

Terminar( resultado )


Aquí AND es la operación AND a nivel de bits (& en C/C++) y SHR es el
desplazamiento a la derecha de una secuencia binaria (>> en C/C++).

Lo que hacemos es convertir el exponente en binario y miramos los bits para
acumular el resultado (AND da 1) o no (AND da 0). Por ejemplo,

3 => 11 (binario)

base <-- 28
11 AND 01 != 0  // => 01 != 0
resultado <-- 28

base <-- 784  // 28^2
exponente <-- 1  // 11 SHR 1 = 1

1 AND 1 != 0  // => 1 != 0
resultado <-- 21952  // 28 * 784

base <-- 614656  // 28^4
exponente <-- 0  // 1 SHR 1 = 0

Terminar( 21952 )


Espero que esto te ayude.

Steven
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.conclase.net/pipermail/cconclase_listas.conclase.net/attachments/20130607/3f81d790/attachment.html>