Вообще‑то я не особый любитель игр. Но прочитал тут на любимом хабре про Кужлёвку и захотелось в это дело поиграть. Не буду утомлять описанием игры, скажу только что игра на мой взгляд исключительно достойная, хотя и не без серьёзных (опять‑таки на мой дилетантский взгляд) недостатков. Перехожу к делу. Первый (и пока единственный) затык у меня случился в эпизоде, где Михалычу нужно собрать Серп и Молот из плиток типа пятнашек. Помучившись с этим часа полтора, я понял, что не смогу этого сделать даже за миллион. Хотя может конечно я просто тупой как пробка. Но на берегу спасённый мной мечехвост ждёт сигаретку! Не могу же я бросить древнее живое существо одно, да без курева!
Приветствую, хабровчане! Эх, чувствую, заминусуют меня сейчас некоторые добрые люди... Однако как говорится, истина дороже, а риск дело благородное. Поэтому рискну. Начну с того, что я ни разу не геймер, мне кодить интереснее (а ещё интереснее разбираться во всяких хитромудрых железяках). Изредка играл в Цезаря, до того в Цивилизацию. Но после прочтения вот этой статьи захотелось посмотреть, что же это за штука такая Factorio. И что-то основательно на неё залип, уже неделю отлипнуть не могу. Игра действительно очень качественная, мне угодить очень трудно. Но совершенно добил ютуб-канал одного доброго человека, где несчастных кусак и плевак жгут огнемётами в промышленных количествах и разносят в щепки гранатами деревья! Куда смотрит Гринпис! Где защитники прав насекомых ! Или они пока не добрались до других планет? И поскольку экологического звездолёта с Земли можно ждать ещё долго, придётся кусакам с плеваками самим позаботиться о защите себя и родной планеты.
Ребят, не ждите тут каких-то выдающихся математических красот или полезных в жизни алгоритмов. Пишу просто из чистого спортивного интереса. Меня заинтересовала задачка опубликованная вот здесь, с которой американские зэки коротают свои огромные срока. Судя по комментариям к статье, она уже вызвала определённый интерес и у сообщества. Понимаю что поступаю не очень хорошо, надо было дать время народу ещё подумать самостоятельно. Однако каюсь, грешен, не могу удержаться. И выкладываю сюда своё решение. Кому интересно, добро пожаловать под кат. Если хотите ещё немного подумать самостоятельно, лучше пока не читайте.
Сначала задачка для первоклассника. Дано некоторое положительное число. Нужно умножить на него другое число, заранее неизвестное. Вопрос, как посоветуют это сделать благородные доны ??? Бывалый разраб наверняка скажет, мол мужик, ставь умножитель и не парь мне мОзги. И возможно будет в корне неправ! Ибо кроме монстров от Alterra и Xilinx существует ещё и такое замечательное семейство как iCE-40 от Lattice. Ультрамикропотребляющее. Очень дешевое. Да вот беда, больно мелкие они, и увы, умножителей там нет. Я столкнулся с этим года 4 назад, когда портировал некий ADPCM-кодек с ассемблера adsp-2185 на такой кристалл.
Вычисление логарифмов довольно распространённая операция в цифровой обработке сигналов. Чаще пожалуй приходится считать только свёртки (умножение с накоплением) и амплитуды с фазами. Как правило для вычисления логарифмов на FPGA применяется алгоритм CORDIC в гиперболическом варианте, требующий только таблицы и простых арифметических операций. Однако это не всегда бывает удобно, особенно если проект большой, кристалл маленький и начинаются танцы с оптимизацией. Именно с такой ситуацией и пришлось мне однажды столкнуться. Оба порта блока RAM (Cyclone IV) уже плотненько были в работе, не оставляя свободных окон. Использовать ещё один блок под гиперболический CORDIC не хотелось. Зато был умножитель, для которого во временной диаграмме получалось приличное свободное окно. Денёк подумав, я сочинил следующий алгоритм, в котором не используется таблиц, но есть умножение, точнее возведение в квадрат. И поскольку схемотехнически возведение в квадрат проще общего случая умножения, возможно этот алгоритм представляет интерес для специализированных микросхем, хотя для FPGA разницы конечно нет. Подробнее под катом.
