amarao_san

Categories:

ох ядрёна математика

Отлаживаю equart. Всё хорошо, но графики чуть-чуть рваные. Почему — не понимаю. Чуть-чуть точечек не хватает. Отлаживаю, довожу до 16х16 с графиком прямой линии. Перевожу вывод в ascii.

Two dots are missing
Two dots are missing

Это график y = x/10 в окрестностях нуля (с переворотом оси, т.е. минусы по вертикальной оси сверху). Что мы видим? Что переход через ноль не видно.

Начинаю разбираться. Сэмплинг у меня аж 4х4 (16 замеров). И в окрестностях нуля (в 4 пикселах вокруг нуля) у меня два фиксела (пиксела) с только положительными значениями уравнения, а 2 — с только отрицательными. Т.е. никто не поймал ситуации, что есть смена знака. Это очень, очень странно. По-идее, если функция гладкая и всячески аналитически приятная, то сэмплинг просто обязан поймать.

Вот код сэмплинга (я отрезал лишнее)

Rust in pictures
Rust in pictures

Мне нужно добавить сколько-то сэмплов. У меня уже могут быть сэмплы и мне нужно добавить.

Задачка на math.stackexchange осталась нерешённой, так что я сколхозил свой алгоритм: режем область на ceil(sqrt(N)) x ceil(sqrt(N)) квадратиков (т.е. округляем N вверх до ближайшего числа с целым значением корня). Дальше проверяем каждую область на «есть в ней уже значение», и если нет, до добавляем.

И что мы получаем? Вот такую красоту (прям с экрана отладки фотографирую)

debug screen of mathematical despair
debug screen of mathematical despair

Правильно, все сэмплы оказались выше линии. Что и есть правда.

Но! Если вы думаете, что я такой глупый и просто «не подумал», то нет. Всё интереснее.

У меня есть код, который проверяет вхождение probe в окно. probe может быть разный, но внутри он вызывает функцию in_window, которая, это самое и проверяет для одной точки (x,y).

И в первой версии я спокойно шпарил от границы до границы (включительно). И проверка у меня была соответствующая (<=, =>). Но у меня посыпались тесты, потому что оказалось, что если обе границы включительные, то ... то увы, половина областей оказывается несправедливо has_probes, потому что у окна слева и справа точки на границе, а т.к. обе границы включаются, то и в центральном окне (где точек нет), функция говорит, что точки есть. Я поправил. Сделал по программистской традиции слева (отрицательную) границу включаемой, а правую исключаемой. И всё заработало.

... Но есть один нюанс, который и стал поводом для этого поста. Мы не можем указать точные границы интервала (x, y). Для отрезка [x,y] можем, а для (x, y) — не можем.

Привет, матанализ.

И получается, что мой наивный алгоритм гарантировано будет упускать корни на очень простых функциях, которые точно меняют знак в простейшем комплекте точек 2х2 по углам квадрата. Всегда будет такая нииизенькая функция, которая будет проскакивать под самым нижним замером. (См рисованную схему).

Что делать? Ну, очевидно, менять код распределения замеров так, чтобы начинать с углов. Сначала углы, потом всё остальное. Но это потребует переделки очень, очень многого.

... Хотя есть альтернативный метод. Я могу подглядывать в общую «знаковость» соседнего фиксела (пиксела). Если у нас полная положительность и нет nan'ов, а там полная отрицательность и нет nan'ов, то между нами есть хотя бы один корень.

Возникает вопрос: а если оба фиксела так сделают, то что будет? Будет утолщение и удвоение линии. Чего не хочется. Что делать? Всегда смотреть в одном направлении. Например, у меня не включается верхняя граница (по обоим осям). Вот по ним и будем заглядывать. Худшее, что будет, это сдвиг линии на fixel_size/sqrt(probes), т.е. при разумном числе (например, 16, 25, 36, etc), практически незаметный, и очень консистентный.

Этот подход надёжнее, чем включение в себя обоих границ (отрезка), потому что отрезки будут двоить линию функции, если линия проходит точно по границе (например, x+0y = 0).

Но придётся придумать понятие «заглядывать в соседние фикселы». Ужасно рвёт и абстракции, и итераторы. Если заглянуть в соседний правый (x+1) фиксел ещё можно, то в соседний «нижний» (y+1) — уже прям боль.

Шаг первый: подглядывать в соседа раньше (для удобства работы с циклами).

Результат: 

Some dots are missing
Some dots are missing

(я покрасил жёлтым положительные области, голубым отрицательные).

Внезапно: А ЗНАЕТЕ ЛИ ВЫ, ЧТО В УРАВНЕНИИ ОКРУЖНОСТИ ВНУТРИ ОТРИЦАТЕЛЬНО???!

Но при этом я оставил старый алгоритм распределения probe'ов, т.е. у меня и «подглядывает влево», и иклюзивная точка на левой границе. Делаю +1 к положению точки (т.е. вместо step_x * dx  я делаю (step_x+1) * dx), становится так:

Я не до конца понимаю почему одной точки не хватает, пока что пропускаю эту проблему.

... нет, нельзя. Это не отдельная точечка, это проблема. Вот это «прямая»:

Надо фиксить. Я пока не понимаю как.

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.