spamsink | Слегка тормознутое (Reply)

По вопросу, тангенциально связанному с работой, набрел на алгоритм быстрого умножения Тоома-Кука. В бытность свою школьником, помнится, я читал описание этого алгоритма в небезызвестной книжке Уэзерелла "Этюды для программистов" и не понимал ни грана, т.к. всё объяснялось на уровне ~~Die erste Kolonne marschiert, die zweite Kolonne marschiert~~ переменную туда, переменную сюда, а что, почему и зачем - не объяснялось (или объяснялось, но непонятно - не помню). Не то чтобы этот алгоритм мне был в данный момент нужен, но просто решил прочитать, и мало того, что всё понял, так еще и запомнил настолько, что смогу объяснить.

Заодно узнал, что Андрей Тоом, изобретший алгоритм, когда ему было 20 лет, не только есть, но и прекрасно себя чувствует, преподавая в Бразилии of all places. А вот отдельной страницы в вики про него нет ни по-португальски, ни по-эстонски, ни по-русски, хотя он и упомянут на другой. Причудливо тасуется колода.

По делу, собственно: задача минимизации количества сложений при умножении на наперед заданную константу, как считают, NP-полна, а быстрые хорошие эвристики до сих пор ищут.

Доб. Пара цитат из Автобиографических заметок Андрея Леоновича:

С 1992 по 1997 год я преподавал в католическом Колледже, а затем Университете Воплощённого Слова в городе Сан Антонио. Средний уровень студентов был крайне низкий и руководители университета считали, что знающие математики им не нужны. Однажды в этом университете открылась вакансия и он получил около ста заявлений. Два самых сильных заявления были от недавних иммигрантов из России: оба с большим количеством печатных работ. Их обоих немедленно отвергли, что меня не удивило. Удивило меня другое. Когда комиссия выбрала трёх лучших из оставшихся кандидатов и представила их на рассмотрение декану и он увидел, что вынужден выбирать из трёх математиков, каждый из которых компетентнее, чем он сам, декан объявил, что у нас в сущности достаточно преподавателей и закрыл конкурс. Впоследствии он принимал на работу безо всякого конкурса людей совсем без публикаций, едва способных читать базовые курсы.

Я … предложил своим слушателям голосовать по вопоосу о том, меньше ли единицы бесконечная десятичная дробь 0,999999... (ноль, запятая, бесконечная последовательность девяток). Подавляющее большинство проголосовало, что меньше, включая вице-президента университета, сидевшего среди студентов.