@New-Developer
Изучаю JavaScript

Пояснения по алгоритму нахождения суммы четырех квадратов?

Пытаюсь реализовать алгоритм для теоремы Лагранжа о представлении натурального числа в виде суммы 4 квадратов, начало в п. 4 страницы 8.
Вопросы:
1. Что такое l, как оно вычисляется ?
2. Первоначальное число n там сокращается до нечетного. Где описан процесс сокращения ?
3. Фраза To see how this reduction goes, first note that we can flag each number in [1, log n] as prime or composite using O((lg n)3/2) operations. означает, что нужны только простые числа в этом диапазоне или составные тоже ?
4. Обязательно использовать натуральный логарифм или можно заменить на двоичный ?

Хочу реализовать этот алгоритм для больших чисел, перебор не подойдет.
Плохо знаю высшую математику и не знаю английский.
  • Вопрос задан
  • 551 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
1) l не вычисляется. l перебирает некоторые простые числа до log n (2 и те, которые дают остаток 1 при делении на 4).

2) Процесс описан внизу страницы. Вы представляете n в виде произведения нечетного (и не делящегося на описанные выше простые числа) n' и вот этих всех простых чисел в каких-то степенях. Далее, поскольку мы можем эти простые числа разложить в сумму двух квадратов после предподсчета, то используя описанный в статье ранее трюк можно получить разложение на квадраты n из разложения n'

3) Это трюк, чтобы все эти простые числа найти до логарифма найти.

4) Кажется не обязательно и натуральный логарифм тут используется, чтобы оценка сложности была оптимальная. Но я не уверен. Лучше не надо.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы