355
правок
Изменения
→Fast expansion sum
====Fast expansion sum====
<wikitex>
В отличие от ExpansionSum, FastExpansionSum не сохраняет свойства неперекрываемости и несмежности, но гарантирует, что если если входное расширение было ''строго неперекрывающимся'', то на выходе получится расширение с таким же свойством.
{{Определение
|definition=
Расширение называется '''строго неперекрывающимся''', если если его компоненты попарно неперекрываются, ни одна компонента не смежна никаким двум другим, а также любая пара смежных компонент состоит из степеней двойки.
}}
'''Например''', $11000 + 11$ и $10000 + 1000 + 10 + 1$ - строго неперекрывающиеся расширения, а $11100 + 11$ и 1$00 + 10 + 1$ - нет.
Для расширения эта характеристика означает, что ноль в записи расширения должен появляться ''как минимум'' каждые $p + 1$ бит. Например, расширение, каждая компонента которого есть $p$-битное число, и максимальная величина которой равна $1111$, может быть не больше $1111.01111011110\dots$.
Каждое несмежное расширение является строго неперекрывающимся, а также каждое строго неперекрывающееся расширение есть неперекрывающееся. В общем случае, обратное не верно.
{{Теорема
|statement=
