Repite el cuadrado de técnicas de

Question

Aquí está el problema y la solución a mi el texto me da.

Cuando se me acercó por primera vez este problema, miré hacia arriba "repite el cuadrado" en línea y probado el siguiente algoritmo de khan academy.

Encontrar la representación binaria de la exponente

$383 \Rightarrow 101111111$

Esto significa que la cantidad de $3^{383}$ puede ser escrito como

$3^{256+64+32+16+8+4+2+1}$

Esto también significa que

$3^{383} = 3^{256}3^{64}3^{32}3^{16}3^8 3^4 3^2 3^1 $

Khan Academy del artículo dice que para tomar el mod de cada uno de esos factores, multiplicar juntos, y luego reducir el mod. Mientras este sentido, la informática, la $3^{256}$ parece tan duro como $3^{383}$. Bueno, eso está bien, ya tenemos una forma de calcular las grandes exponentes, podemos de forma recursiva ir a través de y calcular el $3^{255}$, etc. de la misma manera, pero esto parece un desperdicio.

Mi texto la solución parece mucho más simple de hacer a mano, pero no puedo encontrar una explicación de por qué o cómo funciona.

Answer 1

Para el método binario, de calcular cada uno de los factores relevantes, tales como $3^{256},3^{64}$, etc., sólo por el uso repetido de cuadratura. (Tenga en cuenta que usted puede calcular cada uno de los factores que usted necesita simplemente guardarlos como calcular $3^{256}$.) Entonces multiplicar juntos (si corresponden a una $1$ en el binario de la expansión de la exponente, por supuesto). Esto se suma los exponentes, por lo que todo funciona.

Para el método en su texto, que, básicamente, va a paso su camino hasta el $3^{383}$ varias veces el cuadrado de lo que tiene y luego, posiblemente, multiplicando por $3$ más, dependiendo de si el siguiente exponente en la secuencia, que van de derecha a izquierda, es par o impar. En este caso resultó que usted necesita para multiplicar por $3$ nuevo cada vez, excepto la primera. Esto funciona básicamente porque a medida que usted vaya a través de su secuencia de exponentes de la derecha a la izquierda, el siguiente número es el doble de la cantidad actual, o el doble de $+1$.

También puede ver el método de su texto de forma recursiva en lugar de forma iterativa. Desde este punto de vista, para calcular el $3^{383}$ es suficiente para calcular los $3^{191}$, cuadrado y se multiplica por $3$; para calcular los $3^{191}$ es suficiente para calcular los $3^{95}$, cuadrado y se multiplica por $3$; etc.

Ambas formas están bien. La manera binaria es un poco más limpio, porque no tiene en este caso el trabajo a realizar en cada iteración dependiendo de si el siguiente exponente es par o impar, o el análogo de trabajo de caso de la implementación recursiva. En consecuencia, probablemente sería más rápido en un equipo para la mayoría de los insumos debido a la sucursal de la predicción. La manera en que su texto requiere un poco menos de memoria (que potencialmente podría importa si su módulo y/o el exponente eran mucho más grandes). El binario requerirá de un poco menos el total de las operaciones.

Answer 2

Usted puede obtener $3^{256}$ $(3^{64})^4$ Los enfoques son similares. La diferencia es donde se pone en el extraño factores. El texto del ejemplo calcula $3^{23}=3^{11+11+1}=3^{11}3^{11}3$, mientras que Khan sería calcular $3^{23}=3^{16+4+2+1}$ Esto es particularmente fácil de ejemplo para su texto, ya por encima de $5$ siempre ha $5 \times 5 \times 3 \equiv 5 \pmod 7$, pero que es un accidente. En promedio, el Khan enfoque, le da un par de menos multiplica, pero la diferencia es pequeña. El uso de lo que te gusta.

Answer 3

Trabajando a través de un paso de su ejemplo le mostrará por qué el libro del método funciona. Tenemos $$\lfloor 383 / 2 \rfloor = 191$$ ($\lfloor x \rfloor$ denotes the floor of $x$). Since $383$ is odd and thus rounding occurred, this implies that $$3^{383} \bmod 7 = 3 (3^{191})^2$$ Thus, if we knew the value of $3^{191} \bmod 7$, then it would be easy to find $3^{383} \bmod 7$ so the next step would be to continue recursively by computing $3^{191} \bmod 7$. Su texto está siguiendo el mismo proceso, excepto que se realiza a todas las divisiones y pisos de primera, de modo que uno se puede comenzar con el más pequeño de los exponentes de la primera. Esto no cambia nada de la lógica anterior, pero no hacer las cosas más eficientes.

Answer 4

Ambos métodos están relacionados con la representación binaria de la exponente. Las ideas que se relacionan todas estas cosas juntas es que cada vez que vaya de un lugar a la izquierda de un número binario, se multiplica el número por dos; y al cuadrado de un número, se multiplica su exponente dos.

El método dado por la Khan Academy es lo que yo habría pensado de como "se repitió el cuadrado." De la representación binaria, $\newcommand{two}{\mathrm{two}} 383_\mathrm{ten} = 101111111_\two,$ determinamos que necesitamos nueve dígitos binarios. El dígito izquierdo es el dígito de $2^8 = 256.$ Por lo tanto, escribir nuestro primer poder y, a continuación, empezar a cuadrar: \begin{align} 3^1 &\equiv 3 \pmod7 && \text{(first power)}\\ 3^2 &\equiv 2 \pmod7 && \text{(previous number squared)} \\ 3^4 &\equiv 4 \pmod7 && \text{(squared again)} \\ 3^8 &\equiv 2 \pmod7 && \text{(squared again)} \\ 3^{16} &\equiv 4 \pmod7 && \text{(notice the pattern?)} \\ 3^{32} &\equiv 2 \pmod7 \\ 3^{64} &\equiv 4 \pmod7 \\ 3^{128} &\equiv 2 \pmod7 \\ 3^{256} &\equiv 4 \pmod7 \end{align}

Esto se convierte en repetitivo (y por lo tanto fácil) muy rápidamente en este caso: $2^2 \equiv 4 \pmod7$ $4^2 \equiv 2 \pmod7,$ así que es sólo alternando $2$s y $4$s después de las primeras líneas.

Luego, multiplicamos juntos las facultades que corresponden a los dígitos binarios necesitamos: \begin{align} 100000000_\two &= 256 & 3^{256} &\equiv 4 \pmod7 \\ 101000000_\two &= 256 + 64 = 320 & 3^{320} \equiv 4 \times 3^{64} \equiv 4\times 4 &\equiv 2 \pmod7 \\ 101100000_\two &= 320 + 32 = 352 & 3^{352} \equiv 2 \times 3^{32} \equiv 2\times 2 &\equiv 4 \pmod7 \\ 101110000_\two &= 352 + 16 = 368 & 3^{368} \equiv 4 \times 3^{16} \equiv 4\times 4 &\equiv 2 \pmod7 \\ 101111000_\two &= 368 + 8 = 376 & 3^{376} \equiv 2 \times 3^8 \equiv 2\times 2 &\equiv 4 \pmod7 \\ 101111100_\two &= 376 + 4 = 380 & 3^{380} \equiv 4 \times 3^4 \equiv 4\times 4 &\equiv 2 \pmod7 \\ 101111110_\two &= 380 + 2 = 382 & 3^{382} \equiv 2 \times 3^2 \equiv 2\times 2 &\equiv 4 \pmod7 \\ 101111101_\two &= 382 + 1 = 383 & 3^{383} \equiv 4 \times 3^1 &\equiv 5 \pmod7 \end{align}

En la práctica, por supuesto, sólo tenemos que escribir en el extremo derecho de equivalencias en cada línea. El resto es sólo para mostrar por qué funciona. Básicamente, la idea es que usted puede conseguir el exponente $101111101_\two = 383$ tomando la suma \begin{multline} 100000000_\two + 1000000_\two + 100000_\two + 10000_\two \\+ 1000_\two + 1000_\two + 100_\two + 10_\two + 1_\two. \end{multline} Construimos el poder de $3$ multiplicando las facultades que corresponden a la sumandos de esta suma. Tenga en cuenta que usted podría multiplicar potencias de comenzar con el más alto poder (como se muestra arriba) o empezando con el más bajo de energía.

Pero donde la Khan Academy método simplemente añade las diversas potencias de $2$ para obtener el exponente, el método dado en el texto corresponde a una "shift izquierda y agregar" método de construcción el exponente. Es decir, empezamos con el líder de bits del exponente binario, pero la ponemos en el lugar de uno. Estamos entonces en varias ocasiones multiplicar por $2$ (que se desplaza todos los dígitos binarios un lugar a la izquierda) y (cuando sea necesario) agregar $1$ a escribir otro dígito del número, trabajando de izquierda a derecha. Doblando el exponente se corresponde con el cuadrado de la potencia de $3$ y añadiendo $1$ corresponde a multiplicar por $3$: \begin{align} 1_\two &= 1 & 3^1 &\equiv 3 \pmod7 \\ 10_\two &= 2 \times 1 = 2 & 3^2 &\equiv 2 \pmod7 \\ 101_\two &= 2 \times 2 + 1 = 5 & 3^5 \equiv (3^2)^2 \times 3 \equiv 4 \times 3 &\equiv 5 \pmod7 \\ 1011_\two &= 2 \times 5 + 1 = 11 & 3^{11} \equiv (3^5)^2 \times 3 \equiv 4 \times 3 &\equiv 5 \pmod7 \\ 10111_\two &= 2 \times 11 + 1 = 23 & 3^{23} \equiv (3^{11})^2 \times 3 \equiv 4 \times 3 &\equiv 5 \pmod7 \\ 101111_\two &= 2 \times 23 + 1 = 47 & 3^{47} \equiv (3^{23})^2 \times 3 \equiv 4 \times 3 &\equiv 5 \pmod7 \\ 1011111_\two &= 2 \times 47 + 1 = 95 & 3^{95} \equiv (3^{47})^2 \times 3 \equiv 4 \times 3 &\equiv 5 \pmod7 \\ 10111111_\two &= 2 \times 95 + 1 = 191 & 3^{191} \equiv (3^{95})^2 \times 3 \equiv 4 \times 3 &\equiv 5 \pmod7 \\ 101111111_\two &= 2 \times 191 + 1 = 383 & 3^{383} \equiv (3^{191})^2 \times 3 \equiv 4 \times 3 &\equiv 5 \pmod7 \end{align}

Mientras nosotros no hacemos ninguna aritmética de los errores, inevitablemente vamos a obtener el mismo resultado en la izquierda como en el caso de hacerlo de la otra manera, por lo tanto, tenemos el mismo resultado en la derecha.