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

В математике , дополнение цепь для вычисления натуральное число $п$ может быть задана с помощью последовательности из натуральных чисел , начиная с 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-й степени любого числа $n$ с использованием только семи умножений вместо 30 умножений, которые можно получить при повторном умножении:

п

² =

п

×

п

п

³ =

п

² ×

п

п

⁶ =

п

³ ×

п

³

п

¹² =

п

⁶ ×

п

⁶

п

²⁴ =

п

¹² ×

п

¹²

п

³⁰ =

п

²⁴ ×

п

⁶

п

³¹ =

п

³⁰ ×

п

Методы вычисления цепочек сложения [ править ]

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

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

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

Длина цепочки [ править ]

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

{\ Displaystyle \ журнал _ {2} (п) + \ журнал _ {2} (\ ню (п)) - 2,13 \ Leq l (п) \ Leq \ журнал _ {2} (п) + \ журнал _ { 2} (n) (1 + o (1)) / \ log _ {2} (\ log _ {2} (n))}

,

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

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

Цепочка Брауэра [ править ]

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

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

l * (2 n -1) \leq n - 1 + l * (n)

где - длина кратчайшей звездной цепочки. Для многих значений n , в частности для $n$ $<12509$ , они равны: ^[7] $l$ $($ $n$ $) =$ $l$ $*$ $($ $n$ $)$ . Но Хансен показал, что существуют некоторые значения n, для которых $l$ $($ $n$ $) \neq$ $l$ $*$ $($ $n$ $)$ , например $n$ $= 2$ $6106$ $+ 2$ $3048$ $+ 2$ $2032$ $+ 2$ $2016$ $+ 1, для$ которых $l$ $*$ $($ $n$ $l^{*}$ $) = 6110, l (n) \leq 6109$ . Наименьшее из таких n - 12509.

Гипотеза Шольца [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

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

Брауэр, Альфред (1939). «По цепочкам сложения» . Бюллетень Американского математического общества . 45 (10): 736–739. DOI : 10.1090 / S0002-9904-1939-07068-7 . ISSN 0002-9904 . MR 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).
Ф. Бержерон, Дж. Берштель. С. Брлек «Эффективное вычисление цепочек сложения»

[1] Д. Кнут, Искусство программирования , том 2, «Получисленные алгоритмы», раздел 4.6.3, 3е издание, 1997

[2] Дауни, Питер; Леонг, Бентон; Сетхи, Рави (1981), "Вычисление последовательностей с добавлением цепочек", SIAM журнал по вычислениям , 10 (3): 638-646, DOI : 10,1137 / 0210047. В ряде других статей утверждается, что поиск кратчайшей цепочки сложения для одного числа является NP-полным, цитируя эту статью, но она не требует и не доказывает такой результат.

[otto-3] Отто, Мартин (2001), Цепочки сложения-вычитания Брауэра (PDF) , Diplomarbeit, Университет Падерборна, заархивировано из оригинала (PDF) 19 октября 2013 г. , извлечено 19 октября 2013 г. .

[4] Шёнхаге, Арнольд (1975), «Нижняя граница длины дополнительных цепочек», Теоретическая информатика , 1 (1): 1–12, DOI : 10.1016 / 0304-3975 (75) 90008-0

[G169-5] Guy (2004) с.169

[Clift-6] Клифт, Нил Майкл (2011). «Расчет оптимальных цепочек сложения» (PDF) . Вычислительная техника . 91 (3): 265–284. DOI : 10.1007 / s00607-010-0118-8 .

[7] Ахим Flammenkamp, Кратчайший Сложение Цепи

[1]