algorithm numbers big-o time-complexity

algorithm - Algoritmo O(log log n) para determinar si n es cuadrado perfecto



numbers big-o (1)

¿Hay algún algoritmo O (log b) publicado para determinar si un número b-bit es cuadrado de un entero?

(Me disculpo si esta pregunta está más allá del alcance de este sitio y me gustaría recuperarla si es así)

Actualización: me doy cuenta de que mi pregunta tal como se plantea no es razonable. Así que permítanme enmendarlo preguntando por cualquier algoritmo que sea operaciones sub-polinómicas en b. No necesariamente O (log ^ kb) para una constante k, y tiene una complejidad de espacio "razonable". Las operaciones se definen en el sentido habitual: algo que es razonable para la tarea en cuestión (por ejemplo, agregar, negar, xor, y, o, etc.)

Post script : ahora me doy cuenta de que mi pregunta no tiene sentido. El costo de calcular la raíz cuadrada del piso de un número de n bits es menor que la multiplicación de dos números de n bits.

  1. si b es lo suficientemente pequeño, entonces con el uso de la tabla sqrt es la complejidad O(1)
  2. si no, entonces con el uso de la aproximación de bit es la complejidad O(b/2) = O(log n)

  3. con el uso de la tabla cuadrada perfecta es la complejidad también O(b/2) = O(log n)

    pero con operaciones mucho más rápidas (solo comparar y operaciones de bits) el número de bit b puede ser un cuadrado perfecto de número máximo de b/2 bits, por lo que la tabla tiene 2^(b/2) entradas de números de bit b y búsqueda aproximada de índice (similar a búsqueda binaria) toma b/2 pasos

  4. se puede hacer algo de mejora con la aproximación

    crear la función approx y=approx_sqrt(x); y cómpralo Ahora puedes simplemente verificar los valores de < yc , y+c > que tienen tiempo de ejecución ~T(2c) donde c es constante dependiendo de la precisión de aproximación (1,2,3,...) . La mayoría de las aproximaciones están desactivadas en los valores más grandes para que pueda hacer c=log(b) y su complejidad sea repentinamente O(log b) = O(log log n) que es lo que está buscando, creo.

[Editar]

  1. mucho después del voto negativo, descubrí que esa marca oculta parte de mi texto

    Asumir algún formato o lo que sea por < interval > así que agregué algunos espacios para des-ocultarlo y también encontré que la viñeta # 5 estaba mal, así que la eliminé. Si esa fue la razón del voto negativo, no gracias por ello, lo pasé por alto ... hace poco estaba haciendo algo con primos ... para que mi cerebro lo copie allí sin pensarlo a fondo

  2. como usualmente sin el código y la página de Wiki hay algunos de ustedes que no creen y simplemente votan a la baja así que aquí está mi implementación probada de lo de arriba:

    //--------------------------------------------------------------------------- int is_square(int x,int &cnt) // return sqrt(x) if perfect or 0, cnt = num of cycles ~ runtime { int y,yy; // y=aprox_sqrt(x) for (y=x,yy=x;yy;y>>=1,yy>>=2); // halves the bit count if (y) y=(y+(x/y))>>1; // babylonian approximation if (y) y=(y+(x/y))>>1; if (y) y=(y+(x/y))>>1; // check estimated y and near values cnt=1; yy=y*y; if (yy==x) return y; if (yy<x) for (;;) { cnt++; y++; yy=y*y; if (yy==x) return y; if (yy> x) return 0; } else for (;;) { cnt++; y--; yy=y*y; if (yy==x) return y; if (yy< x) return 0; } } //---------------------------------------------------------------------------

    Le agregué cnt para que pueda probar la complejidad usted mismo. Mi uso aproximado necesita un buen valor de inicio, así que utilizo la mitad del conteo de bits que obviamente es O(log b) pero para los puntos float y los valores float el recuento de exponentes / bits ya es conocido, así que convierte solo a bit / palabra / base / exponente desplazar O(1) . Por cierto, esa es la magia flotante IEEE hecha por la mayoría de las aproximaciones para funciones sqrt o log .

  3. Mis medidas son mejores que mis primeras estimaciones (incluso para la aproximación babilónica no precisa):

    /*---------------- | N | T | ------------------ | 1000000000 | 6 | | 100000000 | 4 | | 10000000 | 2 | | 1000000 | 2 | ----------------*/

    donde N es el bucle N en el que se probó. T es el valor máximo de cnt en los números probados < 0,N > para una aproximación diferente (más adecuada para sus necesidades) puede mirar aquí

Entonces mi respuesta a su pregunta es SÍ , existe un algoritmo más rápido que O(log n) para determinar si n es el cuadrado perfecto (por ejemplo, el mío arriba que también calcula el sqrt ) pero si también está contando la complejidad de las funciones básicas que ¡Me temo que la respuesta es NO porque incluso las operaciones de bits son O(log n) en bignums!

Por cierto, la búsqueda binaria sqrt se puede hacer también sin multiplicación .

Espero eso ayude.