Цепочка добавления - Addition chain

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

Примеры

В качестве примера: (1,2,3,6,12,24,30,31) - это цепочка сложения для 31 длины 7, поскольку

2 = 1 + 1

3 = 2 + 1

6 = 3 + 3

12 = 6 + 6

24 = 12 + 12

30 = 24 + 6

31 = 30 + 1

Цепочки сложения можно использовать для возведение в степень. Этот метод позволяет возведение в степень с целыми показателями степени, которые должны выполняться с использованием числа умножений, равного длине цепочки сложения для показателя степени. Например, сложение 31 приводит к способу вычисления 31-й степени любого числа. п используя только семь умножений вместо 30 умножений, которые можно получить при повторном умножении:

п² = п × п

п³ = п² × п

п⁶ = п³ × п³

п¹² = п⁶ × п⁶

п²⁴ = п¹² × п¹²

п³⁰ = п²⁴ × п⁶

п³¹ = п³⁰ × п

Методы вычисления цепочек сложения

Вычислить цепочку сложения минимальной длины непросто; Обобщенный вариант задачи, в котором нужно найти цепочку, одновременно образующую каждое из последовательности значений, является NP-полной.^[2] Не существует известного алгоритма, который мог бы вычислить минимальную цепочку сложения для данного числа с какими-либо гарантиями разумного времени или небольшого использования памяти. Однако известно несколько методов расчета относительно коротких цепочек, которые не всегда оптимальны.^[3]

Один очень хорошо известный метод расчета относительно коротких цепочек сложения - это бинарный метод, похожий на возведение в степень возведением в квадрат. В этом методе цепочка сложения числа ${\displaystyle n}$ получается рекурсивно из цепочки сложения для ${\displaystyle n'=\lfloor n/2\rfloor }$. Если ${\displaystyle n}$ четное, его можно получить одной дополнительной суммой, так как ${\displaystyle n=n'+n'}$. Если ${\displaystyle n}$ нечетно, этот метод использует две суммы для его получения, вычисляя ${\displaystyle n-1=n'+n'}$ а затем добавление одного.^[3]

В факторный метод для поиска цепочек сложения основан на простые множители числа ${\displaystyle n}$ быть представленным. Если ${\displaystyle n}$ имеет номер ${\displaystyle p}$ как один из его простых факторов, то цепочка сложения для ${\displaystyle n}$ можно получить, начав с цепочки для ${\displaystyle n/p}$, а затем присоединить к нему цепочку для ${\displaystyle p}$, модифицированный путем умножения каждого из его чисел на ${\displaystyle n/p}$. Идеи факторного метода и бинарного метода можно объединить в М-арный метод Брауэра выбрав любой номер ${\displaystyle m}$ (независимо от того, разделяет ли он ${\displaystyle n}$), рекурсивно построив цепочку для ${\displaystyle \lfloor n/m\rfloor }$, объединяя цепочку для ${\displaystyle m}$ (изменено так же, как указано выше), чтобы получить ${\displaystyle m\lfloor n/m\rfloor }$, а затем добавляем остаток. Дополнительные уточнения этих идей приводят к семейству методов, называемых методы скользящего окна.^[3]

Длина цепочки

Позволять ${\displaystyle l(n)}$ обозначить самый маленький ${\displaystyle s}$ так что существует цепочка сложения длины ${\displaystyle s}$ который вычисляет ${\displaystyle n}$.Известно, что

${\displaystyle \log _{2}(n)+\log _{2}(\nu (n))-2.13\leq l(n)\leq \log _{2}(n)+\log _{2}(n)(1+o(1))/\log _{2}(\log _{2}(n))}$,

куда ${\displaystyle \nu (n)}$ это Вес Хэмминга (количество единиц) двоичного разложения ${\displaystyle n}$.^[4]

Можно получить цепочку сложения для ${\displaystyle 2n}$ из цепочки сложения для ${\displaystyle n}$ включив одну дополнительную сумму ${\displaystyle 2n=n+n}$, из которого следует неравенство ${\displaystyle l(2n)\leq l(n)+1}$ от длины цепей для ${\displaystyle n}$ и ${\displaystyle 2n}$. Однако это не всегда равенство, так как в некоторых случаях ${\displaystyle 2n}$ может иметь более короткую цепочку, чем полученная таким образом. Например, ${\displaystyle l(382)=l(191)=11}$, наблюдаемый Кнутом.^[5] Это даже возможно для ${\displaystyle 2n}$ иметь цепочку короче, чем ${\displaystyle n}$, так что ${\displaystyle l(2n)<l(n)}$; наименьший ${\displaystyle n}$ для чего это происходит ${\displaystyle n=375494703}$,^[6] за которым следует ${\displaystyle 602641031}$, ${\displaystyle 619418303}$и т. д. (последовательность A230528 в OEIS ).

Цепь Брауэра

А Цепь Брауэра или же цепочка добавления звезд представляет собой цепочку сложения, в которой каждая сумма, используемая для вычисления числа, использует непосредственно предыдущее число. А Число Брауэра - число, для которого оптимальна цепочка Брауэра.^[5]

Брауэр доказал, что

л^*(2^п−1) ≤ п − 1 + л^*(п)

куда ${\displaystyle l^{*}}$ - длина самой короткой звездной цепи. Для многих значений п, и в частности для п < 12509, они равны:^[7] л(п) = л^*(п). Но Хансен показал, что есть некоторые ценности п для которого л(п) ≠ л^*(п), Такие как п = 2⁶¹⁰⁶ + 2³⁰⁴⁸ + 2²⁰³² + 2²⁰¹⁶ + 1 у которого есть л^*(п) = 6110, л(п) ≤ 6109. Самый маленький такой п это 12509.

Гипотеза Шольца

Основная статья: Гипотеза Шольца

В Гипотеза Шольца (иногда называют Шольц – Брауэр или же Гипотеза Брауэра – Шольца), названный в честь Арнольд Шольц и Альфред Т. Брауэр), является догадка с 1937 года, заявив, что

${\displaystyle l(2^{n}-1)\leq n-1+l(n).}$

Это неравенство, как известно, справедливо для всех чисел Хансена, обобщения чисел Брауэра; Нил Клифт проверил на компьютере, что все ${\displaystyle n\leq 5784688}$ являются Хансеном (а 5784689 - нет).^[6] Клифт дополнительно подтвердил, что на самом деле ${\displaystyle l(2^{n}-1)=n-1+l(n)}$ для всех ${\displaystyle n\leq 64}$.^[5]

Смотрите также

• Цепочка сложения-вычитания
• Векторная цепочка сложения
• Цепь Лукас

Рекомендации

1. Д. Э. Кнут, Искусство программирования, Том 2, "Получисловые алгоритмы", раздел 4.6.3, 3-е издание, 1997 г.
2. Дауни, Питер; Леонг, Бентон; Сетхи, Рави (1981), "Вычислительные последовательности с добавлением цепей", SIAM Журнал по вычислениям, 10 (3): 638–646, Дои:10.1137/0210047. В ряде других статей утверждается, что поиск кратчайшей цепочки сложения для одного числа является NP-полным, цитируя эту статью, но она не утверждает и не доказывает такой результат.
3. Отто, Мартин (2001), Цепочки сложения-вычитания Брауэра (PDF), Diplomarbeit, Университет Падерборна, архив из оригинал (PDF) в 2013-10-19, получено 2013-10-19.
4. Шёнхаге, Арнольд (1975), "Нижняя граница длины дополнительных цепочек", Теоретическая информатика, 1 (1): 1–12, Дои:10.1016/0304-3975(75)90008-0
5. Парень (2004) стр.169
6. Клифт, Нил Майкл (2011). «Расчет оптимальных цепочек сложения» (PDF). Вычисление. 91 (3): 265–284. Дои:10.1007 / s00607-010-0118-8.
7. Ахим Фламменкамп, Кратчайшие цепочки сложения

• Брауэр, Альфред (1939). «О дополнительных цепочках». Бюллетень Американского математического общества. 45 (10): 736–739. Дои:10.1090 / S0002-9904-1939-07068-7. ISSN  0002-9904. МИСТЕР  0000245.
• Ричард К. Гай (2004). Нерешенные проблемы теории чисел. Springer-Verlag. ISBN  978-0-387-20860-2. OCLC  54611248. Zbl  1058.11001. Раздел C6.

внешняя ссылка

• http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
• OEIS последовательность A003313 (Длина самой короткой цепочки сложения для n). Обратите внимание, что начальная «1» не засчитывается (поэтому элемент № 1 в последовательности равен 0).
• Ф. Бержерон, Дж. Берстель. С. Брлек «Эффективное вычисление цепочек сложения»