Так вот, алгоритм Толи, конечно, прост и неплох, но ему нужно примерно n^1.53 операций. Если то, что написано в этой не понятно где спертой и, кстати, не понятно почему вусмерть отцензуренной книжке -- правда, то это еще одна пощечина Гуру. А ведь оно похоже, похоже, таки работает, хотя там одно место еще надо бы прорешать...
Соловьев замечтался и не заметил, как с последним его словами лицо полковника Кузнецова начало наливаться багрянцем.
// Персонажи вымышленные
-- Достали! Достали, дурень! А ты не думал, где они это достали, а?
-- Но это как-бы не наше де...
-- Не наше дело? Да, вопросы задавать не твое дело! А ты не думал, что если эти алгоритмы где-то достали, то их где-то придумали?! Что где-то в Лэнгли или еще черт знает где сидит такая группа криптографов и математиков, которая эти все гениальные штуки придумывает и, заметь, -- не публикует! Они бурят науку на какую-то спец-службу, а мы об этом узнаем от каких-то варягов, которые сперли у кого-то со стола закрытую монографию и сидят, дырки для ордена вертят! Причем нам дали только выдранный из середины кусок! Уцензуренный в ноль! Почему об этом не узнали мы? Где радиоперехваты? Где шифрограммы? Где следы этих очень стойких шифров? Да даже на посольской линии их нет!
// Кузнецов намекает на вскрытие и перехват сообщений от американского посольства в МИД, идущих по специальному, защищенному кабелю. Аналогичный случай, но с советским представительством, был в Берлине, в 1953 году -- операция "Золото". Считается, что тоннель-подкоп обнаружили до официального скандала и гнали по этому кабелю дезинформацию и маловажные данные.
-- Эээ...
-- Бэ! Задумался, наконец! Оно хоть работает, Вася? Это не деза?
-- Да вроде нет, Александр Васильевич...
-- Вроде?! Опять твое "вроде"! Ты мне точно скажи! Срока тебе -- неделя!
У Соловьева оставалось семь дней, чтобы понять, как этот чертов алгоритм работает так быстро и почему "+1", а не "-1" по модулю _так_ важно для этого чертового быстрого умножения с помощью преобразования Фурье.
// Быстрое умножение с помощью преобразования Фурье, о котором идет речь тут было опубликовано Шёнхаге и Штрассеном в 1971 году. Умножение двух целых чисел выполняется за O(n log n log log n) операций. В 2007 году Мартин Фюрер опубликовал работу, в которой умножение выполняется "почти" за O(n log n) -- O(n log n 2^O(log* n)).//
Социализм - это учет и контроль. А распечатка текстов с ноута - процесс хлопотный и нервный. Файлов много, печатаются параллельно, то сбойнет что-то, то просто пропустишь. Чтобы ничего не пропустить Катя вела учет. В Excel. Простенькая табличка - когда, какой файл, сколько страниц , в какой ящик и на какой полке спрятали. Плюс название и описание - иногда кусок вступления, иногда содержание, иногда еще что-нибудь. Все это периодически допечатывалось и пряталось в отдельную коробку. И вот Кате потребовалась простенькая доработка - чтобы при начале печати нового файла его имя автоматически добавлялось в табличку. Сделал за два часа, добавив кроме имени файла еще и дату начала печати, и количество страниц. Казалось бы, сделал и сделал, но в голове возникла мысль и не давала покоя. Excel популярен, более того преподаватель в институте как-то сказал, что электронные таблицы были очень популярны еще до возникновения майкрософт.
А ведь микропроцессор обещают уже летом. И ЭВМ на нем будет ну никак не позже нового года. Конечно, в СССР это будет, прежде всего, управляющая ЭВМ. Но очень хочется выйти и на западные рынки, прежде всего американский. И для этого программа, позволяющая позиционировать компьютер не только как игрушку, была бы исключительно полезна. Вопрос в том насколько сложно ее сделать и что, собственно, она должна уметь. Обдумывание последнего заняло почти неделю, по истечении которой я решил обсудить результат с Федором и Иванами. Они не программисты, но обсуждать это с ребятами Староса или с ТЭЦ пока не хотелось.
Идея не то, чтобы не встретила энтузиазма, она оказалась просто не понята, и только вера в своего директора заставила отнестись к ней полностью серьезно. Добавив по результатам обсуждения в ТЗ синус, косинус, экспоненту и логарифмы, я передал его тем же программистам с ТЭЦ, которые адаптировали тетрис для геологов. С нашей стороны содействие оказывали два Ивана.
Управились неожиданно быстро, всего через четыре месяца гордая команда демонстрировала мне результат своих трудов. Результат не впечатлял. Это был совсем не Excel. Даже через час после начала показа я все еще не понимал можно ли на этом делать что-то полезное и востребованное. Хотя на словах все было красиво. 63 столбца, 254 строки и максимальная длина текста в ячейке 63 символа. Куча разных функций, включая логические и агрегирующие. Пересчёт таблицы с учётом зависимостей между ячейками. И все это требовало для работы всего лишь 46к оперативки. И две Спирали. На одной хранилась сама таблица, а другая использовалась для хранения программы и дополнительных функций. Можно было обойтись и одной, но тогда все время приходилось переставлять диск. Для снижения объема занимаемой памяти хранилась только информация в ячейках, содержащих данные, а также сведения о том, какие ячейки являются пустыми. Еще было много разных слов, но их смысловая нагрузка от меня ускользала. Судя по рассказу, в ходе разработки возникла целая куча проблем, для решения которых активно привлекались друзья, знакомые и знакомые знакомых. Вопрос генератора случайных чисел обсуждался консилиумом двух докторов, пяти кандидатов и неизвестного количества не титулованных участников. Первоначальная идея оптимизации нового и популярного алгоритма RANDU под восьмибитное слово привела к неожиданным выводам - существует линейная зависимость между тремя соседними элементами последовательности и, как следствие, этот алгоритм вообще использовать нельзя. В результате получилось две функции генератора: одна использует линейный конгруэнтный метод, результат которого назвать случайным - это сильно погрешить против истины, и вторая на методе Фибоначчи с запаздываниями, алгоритм хороший, но уж очень медленный. В общем, по результатам работы, десять статей для журнала 'Радио' уже написано и еще чуть больше на подходе. Пришлось слегка остудить горячие головы, отложив все публикации на период после опытной эксплуатации. Предложив подготовить на завтра десяток демонстрационных примеров, вернулся в кабинет и попытался уложить скачущие мысли. Мыслей было много и все на разные темы. Как практически применить новую программу так и не придумалось, но заметный, хотя и не совсем понятный энтузиазм всех разработчиков вселял некоторый оптимизм. Затем мысли зацепились за случайные числа. О том, что проблемы с этим были еще и в 90х я знал все от того же преподавателя, который похоже очень любил приводить их в примет того, как все бывает непросто. Подробностей я ,конечно же не помнил, точнее говоря даже и не знал никогда, но зато знал где посмотреть. Еще разбирая завалы всякого мусора на винте, я нашел и несколько жемчужин, в то числе и широко известное, но мало кем читаное "Искусство программирования" Кнута. Руки до него до сих пор так и не дошли, но похоже настало и его время, может найдется что-то интересное. Шесть часов спустя стало понятно - интересного действительно очень много. Но чтобы понять, что именно, нужны специалисты. Нет, не смотря на то ли тяжелый язык изложения, то ли удачный перевод, понять, что к чему было вполне возможно. А вот решить, что же с этим делать и, что это дает, было гораздо сложнее. Кое-что было понятно сразу. Например, о возможных проблемах с RANDU была публикация еще в 65 году, но на нее никто особо не обратил внимания. Гораздо интереснее оказалось, что генераторы последовательности Фибоначчи с запаздыванием успешно применявшиеся с 1958 года, фактически провалились на крайне простом критерии случайности. Выяснилось это, правда, только в 90х, тогда же предложили методы решения этой проблемы, отбрасывая ненужные элементы последовательности. Все это, а так же и другие методы, достаточно подробно описывалось, местами даже с кодом на каком-то странном ассемблере. Не меньший интерес представляли и задачи с решениями.
