Извлечение квадратного корня с помощью нормальных алгоритмов Маркова

    Захотел я однажды вычислить квадратный корень с помощью нормальных алгоритмов Маркова (НАМ).

    Кратко о НАМ:
    • Существует список замен одной подстроки на другую, называемых правилами
    • Ищем с начала списка первое правило которое можем применить и применяем его для первого вхождения
    • Если такое правило было обнаружено, то возвращаемся к предыдущему пункту и просматриваем список правил сначала
    • Если правило было заключительным, то завершаем работу
    • Если больше нет правил, которые мы можем применить, то завершаем работу

    Итак, вроде бы все просто? Однако, как писать программы на НАМ?
    Для себя я сделал примерно такой план:
    • Пытаемся написать обычный алгоритм использующий только строки
    • Следим за тем, чтобы последние замены не пересекались с первыми
    • Переворачиваем алгоритм и записываем с конца к началу

    Итак, вернемся к вычислению квадратного корня. Мы будем использовать «детский» метод (он же арифметический), который основывается на том простом факте, что квадрат числа — это сумма нечетных чисел от 1 до 2n-1:
    • 1 = 12 = 1
    • 1 + 3 = 22 = 4
    • 1 + 3 + 5 = 32 = 9

    Как бы мы могли реализовать извлечение корня основываясь на этом свойстве? Мы будем последовательно отнимать от числа сначала 1, потом 3, потом 5 и т.д., пока число не станет меньше нуля, паралельно считая сколько отниманий мы сделали. Итого, уже два счетчика + одна переменная для хранения результата

    Маленькая особенность НАМ — нету здесь чисел. И переменных нету. Поэтому нам надо бы симулировать их. Так как писать длинную арифметику мне было лень (да и сомневаюсь что это возможно человеку), то арифметические операции сделал по простому принципу — с помощью инкремента и декремента.

    Я решил сделать так, чтобы у меня строка хранилась в формате {Результат}.{Число}{ОчередноеНечетноеЧисло}{ИндикаторКонцаСтроки}
    Нечетное число я решил хранить в унарной системе исчисления и обозначать единицу как "#" — так гораздо проще работать будет.

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

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

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

    Очень интересно выглядит зависимость количества замен от числа:

    Посмотреть код: paste.org.ru/?3uweqh
    Посмотреть пример выполнения: paste.org.ru/?34caeb
    Скачать программу: sites.google.com/site/nsinreal/markovsqrt.zip
    Поделиться публикацией

    Комментарии 19

      +1
      Забавно, люблю такие штуки с грамматиками и автоматами. Мьсье знает толк.

      А что за интерпретатор, кстати?
        +1
        Самописный, на C#. Осторожно, быдлокод: paste.org.ru/?lrqfbp
          +2
          Понятно. Вот, кстати, онлайн-реврайтер. При желании можно сравнить.

          utilitymill.com/utility/markov_rewriter
            0
            Ругается: Timed out. A utility only has 2 second(s) of time to do it's work.
            +2
            Можно было писать на РЕФАЛе (например, рефал-5), тогда не пришлось бы писать интерпретатор. А отличалось бы исключительно оформлением под синтаксис, ибо рефал — те же НАМ, только с го и гейшами.
              +2
              А вот замечательный интерпретатор от моего знакомого — kc.vc/CIPQ
              Написан на C#, GUI. Имеется редактор кода с подсветкой + динамически интерпретирует, быстро или по шагам.
              image

              (где end rules указатель => на |-> заменить надо, в остальном 100% совместимо)
            –2
            Это, должен заметить, шедевр!
              0
              Мне кажется программа была бы раз в 5 короче, если бы вы использовали не 10ую, а 1ую систему исчисления :)
                0
                Да, но проблема в том, что унарная система исчисления неудобна для человека… А если делаешь лишний перевод из десятичной в унарную и наоборот, то может оказаться что количество действий вообще огромное
                  0
                  Ну я имел ввиду просто считать в унарной и не переводить. Но даже с переводом должно быть, как мне кажется, короче. Все-таки основа перевода (инкремент и декремент) у вас уже есть, а вот перемещение «a» и "*" в стороны сократится в 10 раз. Но нужно пробовать ;)
                    0
                    Сократится в коде, но при этом количество шагов увеличится неимоверно
                      0
                      Что да, то да.
                0
                Почему именно этот алгоритм?
                  +1
                  Из-за относительной простоты реализации. А какой бы вы взяли?
                    +2
                    например
                    но за статью спасибо
                      0
                      Я знаю этот алгоритм, но на НАМ реализовать мне такое будет действительно сложно
                      +1
                      Если что, я не критиковал. Просто поинтересовался.

                      Отдельная мысль: если бы я хотел считать, то я бы считал тем методом, которым в школе учили. В столбик.
                      Как деление. Только я не знаю как он «по научному» называется (:
                      Патернализм мышления, знаете ли (:
                    +1
                    О, как, свои люди на хабре!
                    В аспирантуре тематика исследования заключается в акселерации продукционных алгоримов Маркова. Чуть позже посмотрю код программы, возможно получится приложить то, что исследовано:) Прямо подмывает теперь написать краткую статейку о возможностях акселерации + модернизировать программу если получится.
                      0
                      Да, если будете модернизировать программу, учтите, что в ней есть маленькая бага. Когда первая цифра результата — 9-ка и результат по идее должен быть нецелым, то тогда получается 09. К примеру 82 превращается в 09. Жду статьи

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое