Алгоритмы на основе систем счисления? [закрыто]

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

• Биномиальные кучи основаны на двоичных числах, а более сложные косые биномиальные кучи основаны на косых двоичных числах.
• Некоторые алгоритмы генерации лексикографически упорядоченных перестановок основаны на факторадической системе счисления.
• Попытки можно рассматривать как деревья, которые просматривают одну цифру строки за раз для соответствующей базы.
• Деревья кодирования Хаффмана предназначены для того, чтобы каждое ребро в дереве кодировало ноль или единицу в некотором двоичном представлении.
• Кодирование Фибоначчи используется в поиске Фибоначчи и для инвертирования определенных типов логарифмов.

Мой вопрос: какие еще существуют алгоритмы, которые используют умную систему счисления в качестве ключевого шага своей интуиции или доказательства? . Я думаю о том, чтобы составить доклад на эту тему, поэтому чем больше примеров я буду использовать, тем лучше.

У Криса Окасаки есть очень хорошая глава в своей книге « Чисто функциональные структуры данных», в которой обсуждаются «Числовые представления»: по сути, возьмите некоторое представление числа и преобразуйте его в структуру данных. Чтобы дать представление, вот разделы этой главы:

1. Системы позиционных чисел
2. Двоичные числа (двоичные списки с произвольным доступом, представления без нуля, ленивые представления, сегментированные представления)
3. Перекос двоичных чисел (перекос двоичных списков произвольного доступа, перекос биномиальных куч)
4. Тройные и четвертичные числа

Некоторые из лучших приемов дистилляции:

• Различайте плотное и разреженное представление чисел (обычно вы видите это в матрицах или графиках, но это применимо и к числам!)
• Полезны избыточные системы счисления (системы, которые имеют более одного представления числа).
• Если вы сделаете первую цифру отличной от нуля или используете представление без нуля, получение заголовка структуры данных может быть эффективным.
• Избегайте каскадных заимствований (из хвоста списка) и переносов (из списка в список) путем сегментации структуры данных

Вот также список ссылок к этой главе:

• Гибас, МакКрайт, Пласс и Робертс: новое представление линейных списков.
• Майерс: прикладной стек произвольного доступа
• Карлссон, Манро, Поблете: неявная биномиальная очередь с постоянным временем вставки.
• Каплан, Тарджан: чисто функциональные списки с цепочкой через рекурсивное замедление.

«Тернарные числа могут использоваться для удобной передачи самоподобных структур, таких как треугольник Серпинского или множество Кантора». источник

«Четвертичные числа используются в представлении двумерных кривых Гильберта». источник

"Четвертимнимая система счисления была впервые предложена Дональдом Кнутом в 1955 году в ходе поиска научных талантов в средней школе. Это нестандартная позиционная система счисления, в которой в качестве основы используется мнимое число 2i. Она способна для представления каждого комплексного числа с использованием только цифр 0, 1, 2 и 3. " источник

«Римские цифры - это биполярная система». источник

«Senary может считаться полезным при изучении простых чисел, так как все простые числа, выраженные по основанию шесть, кроме 2 и 3, имеют 1 или 5 в качестве последней цифры». источник

«Шестидесятеричная система счисления (основание 60) - это система счисления, в основе которой лежит шестьдесят. Она возникла у древних шумеров в 3-м тысячелетии до нашей эры, она была передана древним вавилонянам и до сих пор используется - в измененной форме - для измерения время, углы и географические координаты, которые являются углами ". источник

так далее...

Этот список - хорошая отправная точка.

На днях я прочитал ваш вопрос и сегодня столкнулся с проблемой: как сгенерировать все разбиения набора? Решение, которое пришло мне в голову и которое я использовал (возможно, из-за чтения вашего вопроса), было следующим:

Для набора с (n) элементами, где мне нужно (p) разделов, подсчитайте все (n) числовые числа в базе (p).

Каждое число соответствует разделу. Каждая цифра соответствует элементу в наборе, а значение цифры говорит вам, в какой раздел поместить элемент.

Это не удивительно, но аккуратно. Он полный, не вызывает избыточности и использует произвольные основания. База, которую вы используете, зависит от конкретной проблемы разделения.

Недавно я наткнулся на классный алгоритм для генерации подмножеств в лексикографическом порядке на основе двоичных представлений чисел от 0 до 2 ⁿ - 1. Он использует биты чисел как для определения элементов, которые следует выбрать для набора, так и для локального изменения порядка. сгенерированные наборы, чтобы привести их в лексикографический порядок. Если вам интересно, у меня есть запись здесь .

Кроме того, многие алгоритмы основаны на масштабировании (например, слабо-полиномиальная версия алгоритма максимального потока Форда-Фулкерсона), который использует двоичное представление чисел во входной задаче для постепенного уточнения грубого приближения до полного решения.

Не совсем умная базовая система, но умное использование базовой системы: последовательности Ван дер Корпута - это последовательности с низким расхождением, сформированные путем обращения представления чисел с основанием n. Они используются для построения 2- мерных последовательностей Холтона, которые выглядят примерно так .

Я смутно помню кое-что о системах с двойным основанием для ускорения умножения матриц.

Система с двойной базой - это система с дублированием, в которой для одного номера используются две базы.

 n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}

Избыточность означает, что один номер можно указать разными способами.

Вы можете найти статью «Гибридный алгоритм вычисления матричного многочлена» Василия Димитрова, Тодора Куклева.

Пытаюсь дать краткий обзор как можно лучше.

Они пытались вычислить матричный полином G(N,A) = I + A + ... + A^{N-1}.

Supoosing N является составным G(N,A) = G(J,A) * G(K, A^J), если мы применим J = 2, мы получим:

         / (I + A) * G(K, A^2)        , if N = 2K
G(N,A) = |
         \ I + (A + A^2) * G(K, A^2)  , if N = 2K + 1

также,

         / (I + A + A^2) * G(K, A^3)           , if N = 3K
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3)     , if N = 3K + 1
         \ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2

Поскольку «очевидно» (в шутку), что некоторые из этих уравнений быстры в первой системе, а некоторые лучше - во второй, поэтому рекомендуется выбрать лучшее из них в зависимости от N. Но это потребует быстрой операции по модулю как для 2, так и для 3. Вот почему приходит двойное основание - вы можете быстро выполнить операцию по модулю для них обоих, давая вам комбинированную систему:

         / (I + A + A^2) * G(K, A^3)       , if N = 0 or 3 mod 6
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6
         | (I + A) * G(3K + 1, A^2)        , if N = 2 mod 6
         \ I + (A + A^2) * G(3K + 2, A^2)  , if N = 5 mod 6

Прочтите статью для лучшего объяснения, так как я не эксперт в этой области.

RadixSort может использовать различные системы исчисления. http://en.wikipedia.org/wiki/Radix_sort Довольно интересная реализация bucketSort.

вот хороший пост об использовании троичных чисел для решения проблемы "поддельной монеты" (где вам нужно обнаружить одну поддельную монету в пакете обычных, используя баланс как можно меньше раз)

Хеширование строк (например, в алгоритме Рабина-Карпа ) часто оценивает строку как число с основанием b, состоящее из n цифр (где n - длина строки, а b - некоторая выбранная база, которая достаточно велика). Например, строка «ABCD» может быть хеширована как:

'A'*b^3+'B'*b^2+'C'*b^1+'D'*b^0

Подставляя значения ASCII для символов и принимая b равным 256, получается,

65*256^3+66*256^2+67*256^1+68*256^0

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

Возведение в степень возведением в квадрат основано на двоичном представлении экспоненты.

В Hackers Delight (книге, которую каждый программист должен знать в моих глазах) есть полная глава о необычных основаниях, таких как -2 как основание (да, правильные отрицательные основания) или -1 + i (i как мнимая единица sqrt (-1)) как основание. Также мне приятно посчитать, какова лучшая база (с точки зрения дизайна оборудования, для всех, кто не хочет его читать: решение уравнения - e, поэтому вы можете выбрать 2 или 3, 3 будет немного лучше (коэффициент В 1.056 раза лучше, чем 2) - но технически практичнее).

Другие вещи, которые приходят мне на ум, - это счетчик серого (если вы считаете в этой системе только 1-битные изменения, вы часто используете это свойство в дизайне оборудования, чтобы уменьшить проблемы с метастабильностью) или обобщение уже упомянутой кодировки Хаффмана - арифметическое кодирование.

Криптография широко использует целочисленные кольца (модульная арифматика), а также конечные поля, операции которых интуитивно основаны на поведении полиномов с целочисленными коэффициентами.

Мне очень нравится этот для преобразования двоичных чисел в коды Грея: http://www.matrixlab-examples.com/gray-code.html

Отличный вопрос. Список действительно длинный. Определение времени - это простой пример смешанного базиса (дни | часы | минуты | секунды | am / pm)

Я создал фреймворк n-tuple для перечисления мета-базы, если вам интересно о нем услышать. Это очень приятный синтаксический сахар для систем счисления. Он еще не выпущен. Напишите мое имя пользователя (на Gmail).

Одно из моих любимых приложений с основанием 2 - это арифметическое кодирование . Это необычно, потому что суть алгоритма использует представление чисел от 0 до 1 в двоичном формате.

Может быть, это АКС .