¿Cómo calcular eficazmente una función periódica?

Question

Estoy escribiendo un programa para calcular un valor de función periódica para cualquier argumento grande arbitrario:

$f(k) = (\sum_{n=1}^{2^k} n)\mod\ (10^9 + 7)$ , donde $n,k \in \mathbb{N} $

Sé que $ f(k + P) = f(k) $ que limita el valor de $k$ Tendría que calcular.

Lo que me confunde es que Wolfram Alpha dice que tiene un periodo de $ \frac {2{i}\pi}{\log(2)} $ . ¿Es posible programar ese periodo?

Answer 1

Dado que su función es en realidad $f(k) = (2^{2k-1} + 2^{k-1})\pmod{10^9+7}$ basta con tabular los valores de $2^k$ .

$10^9+7$ es primo, así que por Teorema de Fermat sabemos que $2^{10^9+6}\equiv 1\pmod{10^9+7}$ .

Supongamos que quiere calcular $f(k)$ . Calcular las potencias es costoso, así que calcularemos $z=2^{k-1}\pmod{10^9+7}$ y luego $f(k) = z\cdot(2z+1) \pmod{10^9+7}$ .

Calcula primero $k' = k-1\pmod{10^9+6}$ . A continuación, calcule $2^{k-1} \equiv 2^{k'}\pmod{10^9+7}$ utilizando el habitual algoritmo de exponenciación recursiva rápida:

pow2(k):
  result = 1
  power = 1
  while k > 0:
    power = (power * 2) mod 1000000007
    if k is odd, result = (result * power) mod 1000000007
    k = int(k/2)
  return result

(En C, utilice k >>= 1 en lugar de k=int(k/2) , power <<= 1 etc.)

Tenemos $k < 10^9 + 7$ por lo que se iterará como máximo unas 30 veces. Si esto es demasiado lento, puede almacenar en caché los resultados para $0 k 10^6$ y entonces iterará como máximo diez veces por llamada.

Dejemos que $z = \mathrm{pow2}(k-1\pmod{10^9+6})$ y entonces su respuesta es $(2z+1)\cdot z\pmod{(10^9+6}$ .

Wolfram|Alpha parece haberse vuelto temporalmente loco.