Аннотация. Рассматривается задача точного вычисления арифметической суммы произведений целочисленных частных G(N) = sum(floor(N/k) floor(N/(2k+1))) для положительного целого параметра N. Предлагается и исследуется реализация QSS (Quotient-Split Summation), объединяющая прямое вычисление начального участка с группировкой индексов по одинаковому значению первого целочисленного частного. Для каждого такого блока доказывается, что второй частный принимает не более двух различных значений, что позволяет вычислять вклад блока несколькими арифметическими операциями. Алгоритм имеет O(sqrt(N)) итераций в стандартной модели подсчёта арифметических операций и возвращает точный целочисленный результат. В локальных измерениях на Python QSS оказался примерно в 27,57-2406,83 раза быстрее прямого перебора для проверенных размеров N от 10^4 до 10^8. По сравнению с двумя альтернативными реализациями группировки частных измеренное преимущество составило приблизительно 1,67-2,01 раза. Результаты относятся к конкретным реализациям и конфигурации компьютера и сами по себе не доказывают превосходства над всеми существующими алгоритмами.

Целочисленные частные вида floor(N/k) часто встречаются в задачах теории чисел, комбинаторики и вычислительной математики [1]. При изменении k значение такого частного меняется ступенчато: множество соседних индексов может соответствовать одному и тому же результату целочисленного деления. Использование этих интервалов позволяет заменять многократные вычисления одинаковых величин обработкой целых блоков.

Методы группировки частных и суммирования по интервалам имеют известные применения. В частности, алгоритмы вычисления сумм floor-функций и метод Дирихле для суммирования арифметических функций используют связанные идеи разбиения диапазона и преобразования суммы [2]. Однако рассматриваемая ниже сумма содержит произведение двух частных с разными знаменателями, floor(N/k) и floor(N/(2k+1)), поэтому для эффективного вычисления необходимо учитывать изменения обоих множителей.

Цель настоящей работы - описать и проверить конкретную реализацию QSS, определить её точность и асимптотическую сложность, а также сравнить время её выполнения с прямым суммированием и несколькими вариантами группировки.

Для целого N >= 1 требуется вычислить сумму

Здесь floor(x) обозначает наибольшее целое число, не превосходящее x. Все операции выполняются над целыми числами; приближения с плавающей точкой не используются для вычисления самой суммы.

Прямой алгоритм вычисляет оба частных для каждого k от 1 до N. Его количество итераций линейно по N. Для больших N это приводит к избыточным вычислениям, поскольку первый частный floor(N/k) принимает лишь O(sqrt(N)) различных положительных значений. Для смежной задачи точного суммирования целочисленных частных линейной функции см. документацию AtCoder Library [3]. QSS использует это свойство и дополнительно учитывает поведение второго частного внутри каждого блока.

Пусть s = floor(sqrt(N)). Алгоритм разделяет исходную сумму на две части:

Первую часть QSS вычисляет прямым циклом. Во второй части индексы группируются по значению a = floor(N/k). Для фиксированного положительного a соответствующий интервал имеет вид

Обозначим левую границу текущего блока через l, а правую через r. На всём блоке floor(N/k) = a, поэтому вклад блока равен

Ключевая особенность QSS заключается в том, что для рассматриваемых блоков второй частный принимает не более двух последовательных значений. Это позволяет вычислить сумму внутри блока без перебора всех его элементов.

Рассмотрим блок с постоянным первым частным a, где 1 <= a <= floor(sqrt(N)). Его границы заданы формулой (3). Докажем, что разность вещественных значений N/(2l+1) и N/(2r+1) меньше единицы.

Из определения границ следует l > N/(a+1) и r > N/a - 1. Поэтому 2l+1 > 2N/(a+1), а 2r+1 >= N/a при N/a >= 1. Кроме того, r-l < N/(a(a+1)). Следовательно, получаем оценку

Выходит, что вещественное значение N/(2k+1) на всём блоке изменяется менее чем на единицу. Поскольку эта функция монотонно убывает, её целая часть может принимать на блоке не более двух последовательных значений.

Обозначим b = floor(N/(2l+1)), c = floor(N/(2r+1)). Тогда

Лемма обосновывает возможность обработать каждый блок с помощью одного или двух постоянных значений второго множителя.

Если b = c, оба частных постоянны на всём блоке. Тогда вклад равен

Если b != c, второй частный принимает значение b в начале блока и значение c в его конце. Последний индекс, для которого floor(N/(2k+1)) = b, вычисляется по формуле

Следовательно, индексы от l до q дают вклад a * (q-l+1) * b, а индексы от q+1 до r дают вклад a * (r-q) * c. Общий вклад равен

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

Алгоритм состоит из следующих шагов:

1. Вычислить s = floor(sqrt(N)).

2. Для k от 1 до s добавить к результату произведение двух частных.

3. Вычислить a_start = floor(N/(s+1)) и определить левую границу первого блока.

4. Для каждого a от a_start до 1 вычислить r = floor(N/a), значения второго частного на границах блока и вклад блока по формуле (7) или (9).

5. Вернуть полученную целую сумму.

Первая часть содержит не более floor(sqrt(N)) итераций. Во второй части a_start <= floor(sqrt(N)), поскольку N < (s+1)². Следовательно, число блоков второй части также не превышает floor(sqrt(N)). На обработку каждого блока требуется постоянное число арифметических операций.

Эта оценка относится к числу арифметических операций в стандартной модели. В реальном Python стоимость целочисленных делений и операций с большими целыми числами зависит от размера операндов, поэтому оценка O(sqrt(N)) не означает, что фактическое время выполнения пропорционально ровно sqrt(N) с постоянным коэффициентом.

Корректность реализации проверялась сравнением QSS с прямым вычислением исходной суммы и с альтернативными алгоритмами. Во всех проверках использовалось точное целочисленное равенство результатов.

Для N = 100000000 ранее получено точное значение G(N) = 6137055069634959. Проверки подтверждают корректность исследованной реализации на протестированных значениях. Они не заменяют доказательства, приведённого в разделах 4 и 5, и не являются проверкой всех возможных значений N.

Сравнение проводилось на одном локальном компьютере с использованием Python 3. Для каждого метода выполнялись семь измерений времени; в таблице приведена медиана. Перед измерениями выполнялся предварительный запуск функции. Время указано в миллисекундах.

Сравнивались пять реализаций:

Direct - прямое суммирование всех N слагаемых.

Group-A - группировка по первому частному с перебором элементов внутри каждого блока.

Joint - совместная группировка по интервалам, где оба частных постоянны.

Swapped - альтернативный порядок группирования, начинающий со второго частного.

QSS - исследуемый гибридный алгоритм с прямым начальным участком и аналитической обработкой блоков.

Измерения относятся к конкретным реализациям, параметрам тестирования и конфигурации системы. Для другого компьютера, версии Python или фоновой нагрузки значения могут отличаться.

Отношение времени конкурирующего метода ко времени QSS вычисляется как T_competitor/T_QSS. Значение больше единицы означает, что QSS быстрее соответствующей реализации.

Во всех пяти измеренных масштабах QSS показал наименьшее время среди сравниваемых реализаций. На N = 100000000 прямой алгоритм выполнялся приблизительно в 2407 раз дольше QSS, а реализация Group-A - приблизительно в 2131 раз дольше. Преимущество относительно Joint и Swapped было существенно меньше и находилось в диапазоне примерно 1,67-2,01 раза.

Различие между двумя группами сравнений объясняется прежде всего асимптотикой. Direct и Group-A сохраняют линейный по N перебор элементов. QSS обрабатывает O(sqrt(N)) индексов и блоков. Joint и Swapped уже используют группирование частных, поэтому преимущество QSS над ними связано главным образом с конкретной организацией вычислений и меньшими накладными расходами в исследованных реализациях.

Эксперименты подтверждают практическую эффективность QSS для рассматриваемой суммы. Наибольший выигрыш наблюдается относительно прямого суммирования, где число обрабатываемых индексов сокращается с N до порядка sqrt(N). По сравнению с другими алгоритмами группирования преимущество меньше, поскольку они также избегают полного линейного перебора.

При этом следует различать три утверждения. Во-первых, точность алгоритма обоснована разбиением исходного диапазона на непересекающиеся блоки и леммой о двух возможных значениях второго частного. Во-вторых, сложность O(sqrt(N)) относится к количеству арифметических операций в стандартной модели. В-третьих, численные ускорения получены экспериментально и относятся к конкретным программным реализациям.

Перспективными направлениями дальнейшего исследования являются поиск более компактного аналитического выражения для вклада блоков, исследование дополнительных свойств суммы, проверка на существенно больших значениях N и сравнение с независимыми реализациями на нескольких системах. Отдельная задача - установить, существует ли преобразование, позволяющее уменьшить число арифметических операций ниже порядка sqrt(N).

Исходный код и скрипт сравнительных измерений доступны в репозитории QSS. Для воспроизведения эксперимента следует загрузить файлы репозитория и запустить скрипт сравнительных измерений.

Основная реализация: QSS.py.

Скрипт сравнительных измерений: benchmark.py.

Для воспроизведения требуется Python 3. Запустите команду python benchmark.py из каталога с файлами. Скрипт проверяет совпадение результатов на малых значениях N, выполняет сравнительные измерения и выводит ускорение QSS относительно остальных реализаций.

В работе рассмотрен алгоритм QSS (Quotient-Split Summation), обеспечивающий точное вычисление суммы произведений целочисленных частных G(N). Алгоритм сочетает прямой расчёт начального участка с группировкой по значениям первого частного. Для каждого последующего блока доказывается, что второй частный принимает не более двух последовательных значений, поэтому вклад блока вычисляется за постоянное число арифметических операций.

В стандартной модели подсчёта арифметических операций алгоритм выполняет O(sqrt(N)) шагов. Точность реализации проверена сравнением с альтернативными методами для всех N от 1 до 5000 и на дополнительных контрольных значениях. В проведённых локальных измерениях QSS оказался быстрее прямого перебора в 27,57-2406,83 раза, а по сравнению с двумя другими реализациями группировки - приблизительно в 1,67-2,01 раза.

По итогу, QSS является наиболее быстрым из пяти проверенных вариантов в проведённых экспериментах. Полученные результаты обосновывают его практическую эффективность для данной задачи, но не устанавливают абсолютного превосходства над всеми существующими алгоритмами и не доказывают новизну самой математической постановки.