algorithm - sobre - ¿Primeros N dígitos de un número largo en tiempo constante?

desafio sobre el valor posicional de numeros naturales

Question

En un problema de Project Euler, necesito tratar con números que pueden tener cientos de dígitos. Y necesito realizar algunos cálculos en los primeros 9 dígitos.

Mi pregunta es: ¿cuál es la forma más rápida de determinar los primeros N dígitos de un número entero de 100 dígitos? Los últimos N dígitos son fáciles con módulo / resto. Para los primeros dígitos puedo aplicar el módulo 100 veces para obtener dígito por dígito, o puedo convertir el número a Cadena y truncar, pero todos son tiempo lineal. ¿Hay una mejor manera?

Answer 1

En Java:

public class Main {
    public static void main(String[] args) throws IOException {
        long N = 7812938291232L;
        System.out.println(N / (int) (Math.pow(10, Math.floor(Math.log10(N)) - 8)));
        N = 1234567890;
        System.out.println(N / (int) (Math.pow(10, Math.floor(Math.log10(N)) - 8)));
        N = 1000000000;
        System.out.println(N / (int) (Math.pow(10, Math.floor(Math.log10(N)) - 8)));
    }
}

rendimientos

781293829
123456789
100000000

Answer 2

Tal vez no puedas usar un número largo, sino dos números: [primeros dígitos, últimos dígitos]. Realice operaciones en ambos, truncando cada vez la longitud requerida (dos veces la condición, 9 su caso) la primera a la derecha y la segunda a la izquierda. Me gusta

222000333 * 666000555
147|852344988184|815

222111333 * 666111555
147|950925407752|815

para que pueda hacer solo dos pequeños cálculos: 222 * 666 = 147 [852] y 333 * 555 = [184] 815

Pero el comentario sobre la solución "a ha" es el más relevante para Project Euler :)

Answer 3

Puede contar la cantidad de dígitos con esta función:

(defn dec-digit-count [n]
  (inc (if (zero? n) 0
  (long (Math/floor (Math/log10 n))))))

Ahora sabemos cuántos dígitos hay, y queremos salir solo primero 9. Lo que tenemos que hacer es dividir el número con 10 ^ (dígitos-9) o en Clojure:

(defn first-digits [number digits]
  (unchecked-divide number (int (Math/pow 10 digits))))

Y llámalo así: (first-digits your-number 9) y creo que es en tiempo constante. Solo estoy seguro de la implementación de log10 . Pero, es mucho más rápido que una solución de modulo / loop.

Además, hay una solución aún más fácil. Simplemente puede copiar y pegar los primeros 9 dígitos del número.

Answer 4

Puede ayudarte primero n dígitos de una exponenciación

y la respuesta de esta pregunta

Este algoritmo tiene una compexidad de O (b). Pero es fácil cambiarlo para obtener O (log b)