amarao_san

Category:

Охота за корнями

Внезапно, всем пропонентам sin(1/x) как «нерисуемой» функции.

Идея для графиков непрерывных или функций с конечным числом разрывов второго порядка.

Если у нас есть одинокий корень (одинокий — это у которого нет соседа слева и справа), то мы точно знаем, что сосед где-то в соседних 8 пикселах.

Если мы находим разрыв, то количество соседей сокращается, но сохраняется. Если разрыв слева и справа (от пиксела), то да, мы можем прерваться пораньше, и не заметить пиксел сверху/снизу.

Но для продолжительного пиксела (пиксела у которого нет особых точек где-либо) мы можем быть абсолютно уверены, что слева и справа пикселы быть должны, т.е. можно продолжать копать для каждого оторванного пиксела, пока не сольётся.

Вторая эвристика:

Если мы докопались до lattice приличных размеров (40x40 = 1600 точек, уже прилично), то можно выключать детерминированность и переходить на теорвер (т.е. монте-карлу).

Понятно, что можно придумать такую функцию, которую даже монте-карла не возьмёт. Например, если у функции одинокий мега-пик размером в ширину постоянной планка, то вероятность попасть во внутрь пика (т.е. на смену знака) низкая, но визуально его всё равно (на hidpi экране) видно не будет, так что ошибка получается несущественная.


Error

default userpic

Your IP address will be recorded 

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.