Синус вещественного числа (заданного двоичной дробью) вычисляется за полиномиальное от числа знаков ответа время. Степень этого полинома - это надо спрашивать у специалистов, но думаю, что небольшая. Вот здесь https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Elementary_functions
пишут, что лишь немного больше, чем умножение, то есть всё вместе получается меньше n^2. Размер алфавита и число состояний (если только не ограничивать их обоих, от чего модель перестаёт быть универсальной) меняют сложность в константу раз. Вероятностные машины вряд ли могут что-то ускорить тут, таких примеров (для арифметических операций) я не знаю, хотя и доказательства тут скорее всего не известно.