Первые N цифр длинного числа в постоянном времени?

Question

В задаче Project Euler мне нужно иметь дело с числами, которые могут иметь сотни цифр.И мне нужно выполнить некоторые вычисления для первых 9 цифр.

Мой вопрос: каков самый быстрый способ определить первые N цифр из 100-значного целого числа?Последние N цифр легко по модулю / остатку.Для первых цифр я могу применить модуль 100 раз, чтобы получить цифру за цифрой, или я могу преобразовать число в строку и усечь, но все они представляют собой линейное время.Есть ли лучший способ?

Answer 1

Вы можете посчитать количество цифр с помощью этой функции:

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

Теперь мы знаем, сколько там цифр, и мы хотим оставить только первые 9. Что нам нужно, это разделить число на 10^ (цифры-9) или в Clojure:

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

И назовите это как: (first-digits your-number 9) и я думаю, что это в постоянном времени.Я только не уверен насчет реализации log10.Но это намного быстрее, чем решение по модулю / петле.

Кроме того, есть еще более простое решение.Вы можете просто скопировать и вставить первые 9 цифр из номера.

Answer 2

Возможно, вы можете использовать не длинный номер, а набор из двух чисел: [первые цифры, последние цифры].Выполните операции с ними обоими, каждый раз укорачивая до необходимой длины (вдвое больше условия, 9 в вашем случае), первого справа и второго слева.Как и

222000333 * 666000555
147|852344988184|815

222111333 * 666111555
147|950925407752|815

, так что вы можете сделать только два небольших вычисления: 222 * 666 = 147 [852] и 333 * 555 = [184] 815

Но комментарий о "ха"Решение является наиболее актуальным для Project Euler:)

Answer 3

В 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)));
    }
}

выходы

781293829
123456789
100000000

Answer 4

Может помочь первые n цифр возведения в степень

и ответ на этот вопрос).Но это легко изменить, чтобы получить O (log b)