Проект Эйлера № 211 - вопрос эффективности

Question

Я медленно пробирался через список проблем Project Euler, и я пришел к тому, что я знаю, как решить, но, похоже, я не могу (учитывая способ, которым было написано мое решение) .

Я использую Common Lisp для этого, и мой скрипт работает уже более 24 часов (намного больше, чем их цель в одну минуту).

Для краткости, вот мое решение (это спойлер, но только если у вас есть чертовски быстрый процессор):

(defun square? (num)
  (if (integerp (sqrt num)) T))

(defun factors (num)
  (let ((l '()))
    (do ((current 1 (1+ current)))
        ((> current (/ num current)))
      (if (= 0 (mod num current))
          (if (= current (/ num current))
              (setf l (append l (list current)))
              (setf l (append l (list current (/ num current)))))))
    (sort l #'< )))

(defun o_2 (n)
  (reduce #'+ (mapcar (lambda (x) (* x x)) (factors n))))

(defun sum-divisor-squares (limit)
  (loop for i from 1 to limit when (square? (o_2 i)) summing i))

(defun euler-211 ()
 (sum-divisor-squares 64000000))

Время, необходимое для решения проблемы с использованием меньших, более дружественных, тестовых аргументов, кажется больше, чем экспоненциально ... что является реальной проблемой.

Потребовалось:

• 0,007 секунды, чтобы решить за 100
• 0,107 секунды, чтобы решить за 1000
• 2,020 секунды, чтобы решить за 10000
• 56,61 секунды, чтобы решить за 100000
• 1835,385 секунд, чтобы решить за 1000000
• 24 + часов для решения за 64000000

Я действительно пытаюсь выяснить, какая часть (и) скрипта заставляет его работать так долго. Я немного подумал о запоминании функции факторов, но не знаю, как на самом деле это реализовать.

Для тех, кто хочет взглянуть на саму проблему, здесь будет .

Буду очень признателен за любые идеи о том, как сделать это быстрее.

** извините, если это кто-то спойлер, это не должно быть .... но если у вас есть вычислительная мощность, чтобы запустить его в приличное количество времени, больше мощности для вас.

Answer 1

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

Когда вы сталкиваетесь с проблемой, связанной с числами, одна из хороших стратегий (как вы, вероятно, уже знаете из решения 210 задач Project Euler) - это посмотреть на маленькие примеры, найти образец и доказать его. [Последняя часть может быть необязательной в зависимости от вашего отношения к математике; -)]

В этой задаче, хотя, глядя на небольшие примеры - для n = 1,2,3,4, ..., вероятно, не даст вам никакой подсказки. Но при работе с теоретико-числовыми задачами есть еще один смысл «небольших примеров», о которых вы, вероятно, уже знаете - простые числа являются строительными блоками натуральных чисел, поэтому начните с простых.

Для простого числа p его единственными делителями являются 1 и p, поэтому сумма квадратов его делителей равна 1 + p ² .
Для простой степени p ^k ее единственными делителями являются 1, p, p ² , & hellip; p ^k , поэтому сумма квадратов его делителей равна 1 + p + p ² + & hellip; + p ^k = (p ^{k + 1 * +1022 * -1) / (р-1).
Это был самый простой случай: вы решили задачу для всех чисел только с одним простым множителем.}

Пока ничего особенного. Теперь предположим, что у вас есть число n, которое имеет два простых множителей, скажем, n = pq. Тогда его множители равны 1, p, q и pq, поэтому сумма квадратов его делителей равна 1 + p ² + q ² + p ² д ^{2 * 1 034 * = (1 + р 2 * +1036 *) (1 + д 2 ).
Как насчет n = p a q b ? Какова сумма квадратов ее факторов?}

[............................ Читать ниже этой строки опасно ............ .......]

Это & sum; _{0 & le; c & le; a, 0 & le; d & le; b} (p ^c q ^d ) ² = ((р * * а тысяча пятьдесят пять + 1 -1) / (р-1)) ((д ^{Ь + 1 * 1 058 * -1) / (Q-1)).}

Это должно дать вам подсказку, как относительно того, что ответ, так и как доказать это: сумма делителей n просто произведение (ответа) для каждой из главных степеней в ее факторизации, так что все вам нужно сделать, чтобы разложить 64000000 (что очень легко сделать даже в своей голове :-)) и умножить ответ для каждого (= оба, потому что единственными простыми числами являются 2 и 5) его простых степеней.

Это решает проблему проекта Эйлера; теперь мораль от этого отнять.

Более общий факт здесь о мультипликативных функциях - функциях на натуральных числах, таких что f (mn) = f (m) f (n) всякий раз, когда gcd (m, n) = 1, т. е. m и n не имеют общих общих факторов. Если у вас есть такая функция, значение функции в определенном числе полностью определяется ее значениями в простых степенях (вы можете доказать это?)

Немного более сложный факт, который вы можете попытаться доказать (это не , что сложно), заключается в следующем: если у вас есть мультипликативная функция f [здесь, f (n) = n ² ] и вы определяете функцию F как F (n) = & sum; _{d делит n} f (d), (как это и было здесь), тогда F (n) также является мультипликативной функцией.

[На самом деле что-то очень красивое - правда, но пока не смотрите на это, и вам, вероятно, это никогда не понадобится. : -)]

Answer 2

Я думаю, что ваш алгоритм не самый эффективный из возможных. Подсказка: возможно, вы начинаете не с той стороны.

edit: Я хотел бы добавить, что выбор 64000000 в качестве верхнего предела, вероятно, является способом, с помощью которого проблемный плакат предлагает вам подумать о чем-то более хорошем.

edit: Несколько советов по эффективности:

• вместо

(setf l (append l (...)))

вы можете использовать

(push (...) l)

, который деструктивно изменяет ваш список, заключая в себе новую ячейку с вашим значением как car, а прежнюю l как cdr, затем указывает l на эту ячейку. Это намного быстрее, чем добавление, которое должно проходить по списку один раз каждый. Если вам нужен список в другом порядке, вы можете изменить его после завершения (но здесь это не нужно).

• почему вы сортируете l?

• вы можете сделать (> current (/ num current)) более эффективным, сравнив вместо этого квадратный корень из num (который нужно вычислять только один раз для num).

• возможно ли найти факторы числа эффективнее?

И подсказка стиля: Вы можете поместить область действия l в объявление do:

(do ((l ())
     (current 1 (+ current 1)))
    ((> current (/ num current))
     l)
  ...)

Answer 3

Умный трюк, который вам не хватает, заключается в том, что вам не нужно вообще вычислять числа Сколько чисел из 1..N кратно 1? N Сколько чисел из 1..N кратно 2? N / 2

Хитрость заключается в суммировании коэффициентов каждого числа в списке. Для 1 добавьте 1 ^ 2 к каждому номеру в списке. Для 2 добавьте 2 ^ 2 к каждому другому числу. Для 3 добавьте 3 ^ 2 к каждому 3-му числу.

Не проверяйте делимость вообще. В конце вы должны проверить, является ли сумма идеальным квадратом, и все. В C ++ это сработало за 58 секунд.

Answer 4

Я бы атаковал это, выполняя простую факторизацию числа (например: 300 = 2 ^ 2 * 3 ^ 1 * 5 ^ 2), что относительно быстро, особенно если вы генерируете это с помощью сита. Исходя из этого, относительно просто генерировать факторы путем итерации i = 0..2; J = 0..1; k = 0..2 и делает 2 ^ i * 3 ^ j * 5 ^ k.

5 3 2
-----
0 0 0 = 1
0 0 1 = 2
0 0 2 = 4
0 1 0 = 3
0 1 1 = 6
0 1 2 = 12
1 0 0 = 5
1 0 1 = 10
1 0 2 = 20
1 1 0 = 15
1 1 1 = 30
1 1 2 = 60
2 0 0 = 25
2 0 1 = 50
2 0 2 = 100
2 1 0 = 75
2 1 1 = 150
2 1 2 = 300

Это может быть недостаточно быстро

Answer 5

Извините, я недостаточно хорошо понимаю LISP, чтобы прочитать ваш ответ. Но мое первое впечатление состоит в том, что временные затраты на решение проблемы грубой силы должны быть:

открытый кронштейн

sqrt (k), чтобы найти делители k (путем пробного деления), возвести в квадрат каждый (постоянное время на фактор) и сложить их (постоянное время на фактор). Это & sigma; ₂ (k), которое я назову x.

плюс

не уверен, какова сложность хорошего целочисленного алгоритма квадратного корня, но, конечно, не хуже, чем sqrt (x) (немое пробное умножение). x вполне может быть больше -O больше, чем k, поэтому я оставляю здесь суждение, но x явно ограничен сверху k ^ 3, потому что k имеет не более k делителей, каждый из которых сам не больше k и, следовательно, его квадрат не больше k ^ 2. Прошло так много времени с моей степени по математике, что я понятия не имею, как быстро сходится Ньютон-Рафсон, но я подозреваю, что это быстрее, чем sqrt (x), и если все остальное не сработает, бинарная отбивная - это log (x).

закрывающая скобка

, умноженное на n (поскольку k находится в диапазоне 1 .. n).

Так что, если ваш алгоритм хуже, чем O (n * sqrt (n ^ 3)) = O (n ^ (5/2)), в случае тупого sqrt, или O (n * (sqrt (n)) + log (n ^ 3)) = O (n ^ 3/2) в умном случае, я думаю, что-то пошло не так, что должно быть идентифицировано в алгоритме. В этот момент я застрял, потому что я не могу отладьте свой LISP.

О, я предположил, что арифметика является постоянным временем для используемых чисел. Это чертовски хорошо должно быть для чисел, таких как 64 миллиона, и куб этого вписывается в 64-битное целое число без знака, едва. Но даже если ваша реализация LISP делает арифметику хуже, чем O (1), она не должна быть хуже, чем O (log n), поэтому это не окажет большого влияния на сложность. Конечно, это не будет супер-полиномом.

Здесь кто-то приходит и говорит мне, насколько я не прав.

Ой, я только что посмотрел ваши фактические временные цифры. Они не хуже экспоненциальных. Игнорируя первое и последнее значения (потому что малые времена точно не измеримы и вы не закончили, соответственно), умножение n на 10 умножает время не более чем на 30 дней. 30 составляет около 10 ^ 1,5, что примерно подходит для грубой силы, как описано выше.

Answer 6

Я переработал программу с некоторыми примечаниями, взятыми из комментариев здесь. Функция «факторов» теперь стала немного более эффективной, и мне также пришлось изменить функцию σ_ (2) (n), чтобы принять новый вывод.

«факторы» пошли от того, чтобы иметь результат как:

$ (factors 10) => (1 2 5 10)

чтобы иметь один как

$ (factors 10) => ((2 5) (1 10))

Пересмотренная функция выглядит следующим образом:

(defun o_2 (n)
"sum of squares of divisors"
  (reduce #'+ (mapcar (lambda (x) (* x x)) (reduce #'append (factors n)))))

После скромных переписываний, которые я сделал, я сэкономил только около 7 секунд в расчете на 100 000.

Похоже, мне придется сойти с задницы и написать более прямой подход.

Answer 7

Я думаю, что вы можете атаковать эту проблему чем-то вроде простого сита. Это только мое первое впечатление.