[Luis Fuentes]

Hola

 Un problemilla sobre potencias.

 Supongamos que queremos calcular la potencia entera \( x^n \) de un número \( x \), haciendo sucesivos productos. ¿Cuál es el menor número de multiplicaciones necesarias?.

 La solución depende de \( n \) y no de \( x \) obviamente.

 Por ejemplo, si queremos hallar \( x^8 \). Podemos hacer:

 \( x^2=x*x \); \( x^3=x^2*x \); \( x^4=x^3*x \);.... \( x^8=x^7*x \)  -> 7 productos

Pero esto no es óptimo. Mejor sería:

 \( x^2=x*x \); \( x^4=x^2*x^2 \); \( x^8=x^4*x^4 \) -> 3 productos

Esto si es óptimo.

No parece fácil dar una función que explicite el numero de productos en función de n. Pero si sería interesante dar un algoritmo, un método, para identificar la forma de obtener el resultado con el menor número de productos.

Es interesante definir la función: \( f:\Bbb N\to \Bbb N \) que lleve \( n \) en el número mínimo de productos  y estudiar sus propiedades.

Por ejemplo:

\( f(2^k)=k. \)
\( f(n)\leq f(n-1)+1 \)
\( f(2^k*b)\leq f(b)+k \)  (quizá se tiene la igualdad?)

A pensar!!!!!!!!!!!!!

CORREGIDO

[sebasuy]

Hola el_manco.

Creo que hay que formular el problema más en detalle pues, por ejemplo, si n=8, podríamos decir x8=x7·x y tenemos un único producto...

Esa apliación f, debería estar def. en los naturales ¿no?

SebasUy

[Luis Fuentes]

Hola a todos

 Ilustro un poco mas la formulacion del problema por si acaso, aunque he tratado de hacerla lo mas clara posible.

 Hay que partir de \( x \) que es lo unico conocido y haciendo unicamente productos obtener la potencia enesima.

 Entonces \( x^8=x^7\cdot x \) no sería solución en un sólo producto porque utiliza \( x^7 \) que es desconocido y hay que calcularlo previamente a partir de \( x \).

 CIERTO. \( n \) es un número NATURAL (es decir entero no negativo).

Saludos.

[manooooh]

Hola

Creo que el menor número de multiplicaciones necesarias está estrechamente relacionado con el proceso de descomponer a \( n \) como suma de potencias de \( 2 \), ya que \( 2 \) es la menor base natural en la que se puede expresar cualquier número (sistema de numeración binario).
Entonces para \( x^7 \) tenemos \( 3 \) iteraciones:

\( 7=2^2+2^1+2^0\implies x^2=x\cdot x\qquad x^4=x^2\cdot x^2\qquad x^7=x^4\cdot x^2\cdot x. \)

¿Cómo deduzco la relación \( 7 \) y \( 3 \)? Sólo Luis Fuentes sabe... .

Es un problema interesante. ¿Algún avance?

Saludos

EDIT: He calculado algunos números:

\( (n=1)=1\\(n=2)=1\\(n=3)=2\\(n=4)=2\\(n=5)=3\\(n=6)=3\\(n=7)=3\\(n=8)=3\\\cdots \)

Poniendo esta secuencia en oeis regresa: https://oeis.org/search?q=1%2C1%2C2%2C2%2C3%2C3%2C3%2C3&language=english&go=Search

Length of binary representation of \( n \).

[Carlos Ivorra]

Mejor sería:

 x^2=x*x; x^4=x^2*x^2; x^8=x^4*x^4 -> 3 productos

Esto si es óptimo.

Por ejemplo:

f(2^k)=k-1.
f(n)<=f(n-1)+1
f(2^k*b)<=f(b)+k-1  (quiza se tiene la igualdad?)

Si dices que \( f(8)= 3 \), será que \( f(2^k) = k \) ¿no?

He calculado algunos números:

\( (n=1)=1\\(n=2)=1\\(n=3)=2\\(n=4)=2\\(n=5)=3\\(n=6)=3\\(n=7)=3\\(n=8)=3\\\cdots \)

¿Cómo calculas \( x^7 \) con tres productos? Yo necesito 4.

Éstas son mis cuentas:

[Luis Fuentes]

Hola

Si dices que \( f(8)= 3 \), será que \( f(2^k) = k \) ¿no?

Si, si. Ya lo he corregido.

Éstas son mis cuentas:

Si. Concuerda con esto:

https://oeis.org/A003313

Si se miran los enlaces resulta que es un problema menos trivial de lo que yo pensaba en su momento. Aquí se puede leer sobre el asunto:

https://koclab.cs.ucsb.edu/teaching/cren/project/2018/Schibler.pdf

Se me ocurrió está cuestión en su día (2006) cuando explicaba la potencia de matrices a mis alumnos y la aplicación de la diagonalización para potencias altas. Decía que calcular una potencia alta "a lo bestia", multiplicando sucesivamente era costoso. Les propuse una potencia octava, y en fin hubo gente que lo hizo muy muy a lo bestia (multiplicando siete veces) y otra no tanto (de la manera óptima con tres productos) y ahí surgió un pequeño debate sobre el asunto...

Saludos.

[Masacroso]

De esto habla uno de los últimos vídeos de Eduardo Sáenz de Cabezón:

EDICIÓN: ah, no se parece tanto al tema del hilo (había olvidado exactamente de qué iba el vídeo, al verlo de nuevo he visto que es un tema diferente) pero trata el tema de la complejidad computacional de multiplicar dos enteros cualesquiera.

[Carlos Ivorra]

Por lo que he visto al tratar de calcular la función, la dificultad computacional se debe a que las cadenas mínimas distan mucho de ser únicas. Por ejemplo, hacen falta 9 productos para calcular \( x^{71} \), pero hay \( 449 \) formas distintas de hacerlo. Para calcular las posibilidades para \( x^n \) en función de las de las potencias inferiores no basta con saber calcular \( f(i) \) para \( i<n \), sino que, en principio, es necesario conocer las distintas formas posibles de calcular cada potencia \( x^i \) y eso ralentiza bastante los cálculos. Mi ordenador ha tardado varias horas en calcular \( f(n) \) para \( n\leq 100 \).

[manooooh]

Hola a todos

Muchas gracias por (re)tomar este ejercicio.

¿Cómo calculas \( x^7 \) con tres productos? Yo necesito 4.

Aquí lo puse, no sé si no lo llegaste a ver:

\( 7=2^2+2^1+2^0\implies x^2=x\cdot x\qquad x^4=x^2\cdot x^2\qquad x^7=x^4\cdot x^2\cdot x. \)

He seguido el ejemplo que puso Luis hace 14 años atrás (¡wow!):

\( x^2=x*x \); \( x^4=x^2*x^2 \); \( x^8=x^4*x^4 \) -> 3 productos

Aunque no logro encontrar el error sospecho que algo anda mal.

Por lo que he visto al tratar de calcular la función, la dificultad computacional se debe a que las cadenas mínimas distan mucho de ser únicas. Por ejemplo, hacen falta 9 productos para calcular \( x^{71} \), pero hay \( 449 \) formas distintas de hacerlo. Para calcular las posibilidades para \( x^n \) en función de las de las potencias inferiores no basta con saber calcular \( f(i) \) para \( i<n \), sino que, en principio, es necesario conocer las distintas formas posibles de calcular cada potencia \( x^i \) y eso ralentiza bastante los cálculos. Mi ordenador ha tardado varias horas en calcular \( f(n) \) para \( n\leq 100 \).

¿Esa función de la que hablás es para calcular la menor cantidad de multiplicaciones? No entiendo por qué hablás de las formas distintas de productos en una multiplicación.

Se me ocurrió está cuestión en su día (2006) cuando explicaba la potencia de matrices a mis alumnos y la aplicación de la diagonalización para potencias altas. Decía que calcular una potencia alta "a lo bestia", multiplicando sucesivamente era costoso. Les propuse una potencia octava, y en fin hubo gente que lo hizo muy muy a lo bestia (multiplicando siete veces) y otra no tanto (de la manera óptima con tres productos) y ahí surgió un pequeño debate sobre el asunto...

Muy buena jugada maestro. Mi pregunta es, ¿cómo hacés para traerlo de vuelta (recordarlo) después de 14 años? ¿Lo tenías anotado en alguna de tus notas?

De esto habla uno de los últimos vídeos de Eduardo Sáenz de Cabezón:

Bueno, en verdad habla del caso general de multiplicar \( n \) números enteros cualesquiera.

¡Grande! No lo recordaba.

Saludos

[Luis Fuentes]

Hola

\( 7=2^2+2^1+2^0\implies x^2=x\cdot x\qquad x^4=x^2\cdot x^2\qquad x^7=x^4\cdot x^2\cdot x. \)

Ahí usas cuatro productos:

\(  x^2=x\cdot x \) 1 producto
\( x^4=x^2\cdot x^2 \) 1 producto
\(  x^7=x^4\cdot x^2\cdot x \) 2 productos, ¡ojo!.

En total \( 1+1+2=4 \).

¿Esa función de la que hablás es para calcular la menor cantidad de multiplicaciones? No entiendo por qué hablás de las formas distintas de productos en una multiplicación.

El problema es que si uno quiere saber la forma óptima de calcular \( x^n \) con el menor número de operaciones y quiera aprovechar que ya sabe la forma óptima de calcular potencias menores, no  llega con conocer cuantas operaciones se usaron para esas potencias menores sino por en medio que otras potencias se han calculado y se pueden aprovechar.

Por ejemplo \( x^7 \) en cuatro operaciones se puede calcular:

1- así, \( x^2,x^4,x^6,x^7 \)
2- o también así, \( x^2,x^3,x^5,x^7 \)

Si ahora queremos calcular \( x^{11} \) y me planteo si lo puedo calcular de la manera más rápida posible a partir de \( x^7 \)... pues depende...

- si seguí el camino 1 con una sola operación más termino \( x^{11}=x^7\cdot x^4 \) porque ya tenía calculado también \( x^4. \)
- pero si seguí el camino 1 con una sola operación más \( x^{11}=x^7\cdot x^4 \) no podemos porque no tenemos calculado \( x^4 \).

Muy buena jugada maestro. Mi pregunta es, ¿cómo hacés para traerlo de vuelta (recordarlo) después de 14 años? ¿Lo tenías anotado en alguna de tus notas?

Al releer el hilo evoqué la situación en la que lo escribí.

Saludos.