Вилучення квадратного кореня за допомогою нормальних алгоритмів Маркова

Захотів я одного разу вирахувати квадратний корінь за допомогою нормальних алгоритмів Маркова (НАМ).

Коротко про НАМ:

  • Існує список замін однієї підрядки на іншу, званих правилами
  • Шукаємо з початку списку перше правило, яке можемо застосувати і застосовуємо його для першого входження
  • Якщо таке правило було виявлено, то повертаємось до попереднього пункту та переглядаємо список правил спочатку
  • Якщо правило було завершальним, то завершуємо роботу
  • Якщо більше немає правил, які ми можемо застосувати, то завершуємо роботу
Отже, начебто все просто? Однак як писати програми на НАМ? Для себе я зробив приблизно такий план:
  • Намагаємося написати звичайний алгоритм, який використовує тільки рядки
  • Слідкуємо, щоб останні заміни не перетиналися з першими
  • Перевертаємо алгоритм і записуємо з кінця на початок
Отже, повернемося до обчислення квадратного кореня. Ми будемо використовувати «дитячий» метод (він же арифметичний), який ґрунтується на тому простому факті, що квадрат числа – це сума непарних чисел від 1 до 2n-1:
  • 1 = 1 2 = 1
  • 1 + 3 = 2 2 = 4
  • 1 + 3 + 5 = 3 2 = 9
Як би ми могли реалізувати вилучення кореня ґрунтуючись на цій властивості? Ми будемо послідовно віднімати від числа спочатку 1, потім 3, потім 5 і т.д., поки число стане менше нуля, паралельно вважаючи скільки забирань ми зробили. Отже, вже два лічильники + одна змінна для зберігання результату

Маленька особливість НАМ - немає тут чисел. І змінних нема. Тому нам треба було б симулювати їх. Так як писати довгу арифметику мені було ліньки (та й сумніваюся, що це можливо людині), то арифметичні операції зробив за простим принципом — за допомогою інкременту та декременту.

Я вирішив зробити так, щоб у мене рядок зберігався у форматі . Непарне число я вирішив зберігати в унарній системі числення і позначати одиницю як "#" - так набагато простіше працювати буде.

Тепер, яким чином ми відніматимемо від числа чергове непарне, не втративши дані? Я вирішив, що між непарним числом і індикатором кінця рядка потрібно додати маркер «a», який переміщаючись крізь число його дублюватиме, але вже в іншому вигляді (позначаємо через "-"). Після будемо зрушувати всі мінуси до числа і віднімати їх. Після того, як ми всі числа забрали, нам потрібно збільшити результат на одиницю.

У моїй реалізації була маленька особливість — результат завжди виходить заокругленим нагору. Я вирішив зробити так, щоб цей алгоритм працював із абсолютною точністю 0.5, а не 1 (як в описі). Коли в рядку залишається мінусів більше половини від їх початкового значення, ми повинні взяти і зменшити результат.

У результаті вийшов «пінг-понг», який витягує квадратний корінь заданого числа.

Дуже цікаво виглядає залежність кількості замін від числа:

кореня