Обо мне
Привет! Меня зовут Лис и это мой блог. Здесь я могу ныть и страдать, писать про код и обо всем.
Декабрь 2024
ПнВтСрЧтПтСбВс
1
2345678
9101112131415
16171819202122
23242526272829
3031
Теги
Блог страдающего Лиса
Lorem ipsum hello dolor sit world amet

24 окт 2024 Чт Микропроекты и квадратный корень

Я часто думаю, что мне от этого программирования нужно, и понимаю, что мне очень нравится делать микроскопические проекты, демосцены. Все время вспоминая прошлое и прежние времена, когда я радовался кубу, нарисованному где угодно, хоть на туалетной бумаге, теперь я тоже понимаю, что мне все равно нравится рисовать эти кубы. И даже шары (oh my balls!).
Поскольку вчера я сделал шахматную трехмерную доску, то думаю, что можно в принципе, продолжить делать что-то такое в этом же стиле и куда-то складировать на сайте с исходниками, которые никому абсолютно не нужны.
Все что было в детстве — было лучше всего, потому что там радовался всему, даже stosb радовал так, что я аж подпрыгивал от счастья на месте. Раньше у меня были очень простые радости, не то что сейчас, когда ничего не радует, но ладно, это лирическое отступление от темы.
Из ближайших мыслей о проектах — нарисовать стохастические горные вершины, флаппи бёрд, попробовать вырисовывать окружность по принципу вычисления x = \sqrt{r^2 - y^2} . Есть такой метод довольно простого поиска quadratного корня, через серию вычитаний -1, -3, -5, -7 и так далее. Я уже ранее рассказывал об этом методе, где 1+3+5+7+9 дает значение квадратов от чисел 1,2,3,4 и т.д. Если же действовать в обратную сторону, то получим корень.
Возьмем число 100, вычислим куадраутный корень через серию вычитаний:
1) 100-1=99,
2) 99-3=96,
3) 96-5=91,
4) 91-7=84
5) 84-9=75,
6) 75-11=64,
7) 64-13=51,
8) 51-15=36,
9) 36-17=19,
10) 19-19=0
Количество вычитаний получилось 10. А значит, квадратный корень из 100 будет 10. На верилоге это бы записано было таким образом:
always @(posedge clock) if (A >= B) begin A <= A - B; B <= B + 2; C <= C + 1; end
Где A — исходное число, B=1 на старте, C=0 на старте, и это результат. Ну и A будет в остатке потом. Короче, через серию вычитаний можно добиться вычисления квадратного корня. Есть только один баг в том, что если исходное число например 65535, то придется 255 раз вычесть прежде чем добьемся ответа от него. Есть и другие методы, например, поиск корня через серию делений, например, или там, по табличке искать сначала, двоичной.
Есть быстрый, шустрый метод быстро найти квадратный корень (приблизительно) через подсчет количества значимых битов, для начала. Например, нам надо вычислить быстренько квадратный корневище через такой подсчет. Возьмем крупное число, 25612461 например, что в шестнадцатеричном виде будет 186D0AD, а в двоичном виде:
0001 1000 0110 1101 0000 1010 1101
Сразу быстро можно посчитать высоту последнего разряда у числа, который содержит единицу. И это бит номер 24, начиная с 0. Если разделить число 24 на 2, то получится 12 битов. Это значит что результат корня гарантированно старше чем 2^12, и не меньше чем 4096 (то есть 4096^2=16'777'216). Результат будет находиться между 4096^2 и 8192^2.
Понятное дело, что это является лишь грубой оценкой корня и что придется еще искать, но подобный подход позволяет снизить количество проб c 24 до 12 при бинарном поиске. И конечно же, чем больше число, тем больше оно и занимает времени на поиск решения.
<< Ранние записи | Поздние записи >>