Category: it

Category was added automatically. Read all entries about "it".

lenin

Иллюзия оптимальности

При нынешнем развитии криптографического и прочего дела на Западе регулярно приходится возводить что-нибудь в очень большую степень. Очевидно, что вычислять ХN путем умножения Х на себя N-1 раз очень неэффективно; гораздо логичнее вычислять X2, X4, X8 и т.п. путем возведения в квадрат очередного результата (не забывая все промежуточные результаты), а потом перемножить степени, соответствующие единицам в двоичной записи числа N.

Посмотрим, как это будет работать, если нам нужно вычислить X63. Для этого мы последовательно вычисляем Х в степенях 2, 4, 8, 16, 32, 48, 56, 60, 62, 63. Как-то это медленновато; интуитивно кажется, что если бы можно было ещё и делить, то после степени 32 можно вычислить 64, поделить на Х и получить искомый результат, и хочется найти способ вычислить то же самое без деления, но быстрее, чем за 10 шагов.

Заметим, что 63 = это 7*8 + 7. Тогда одним из вариантов оптимального пути будет 2, 3, 6, 7, 14, 28, 56, 63 (другой вариант, например, 2, 4, 6, 7, 14, 21, 42, 63).

Дональд Кнут предложил алгоритм получения последовательности операций для определения эффективного пути вычисления XN. Для этого мы строим такое дерево:
             1
             |
             2
            / \
           3   4
          /\    \
         /  \    \
        5    6_   8
       / \   \ \   \
      /  |    \ \   \
     /   |     \ \   \
    7   _10_    9 12  16_
   /   / /\ \    \ \   \ \
  /   / /  \ \    \ \   \ \
14  11 13  15 20  18 24 17 32

по следующей системе: начинаем с дерева, состоящего только из корня (1). Далее на каждом шаге из узла с наименьшим номером K, из которого ещё ничего не растёт, отрастают ветви в новые узлы с номерами K+L, где L - номера во всех узлах пути от корня (1) до K, включая собственно К, если узлы с этими номерами ещё не существуют. И так до тех пор, пока не образуется узел с номером N, после чего мы прослеживаем путь от него до вершины и определяем, каким способом выполнять умножения.

Казалось бы, всё довольно алгоритмически эффективно, красиво и оптимально, кратчайший путь по дереву и всё такое, ан поди ж ты.

Для числа 77 алгоритм даёт 2, 3, 5, 7, 14, 19, 38, 76, 77 (9 шагов), а оптимально - 2, 4, 8, 9, 17, 34, 43, 77 (8 шагов).

И вообще, нарисовать одно общее для всех чисел оптимальное дерево невозможно - ломается на 149.

This entry was originally posted at https://spamsink.dreamwidth.org/1223493.html. Please comment there using OpenID.
lenin

Перефразируя Скалигера-Прокоповича

Вместо эпиграфа:

Если в мучительские осужден кто руки,
Ждет бедная голова печали и муки,
Не вели томить его делом кузниц трудных,
Не посылать в тяжкие работы мест рудных:
Пусть компилятор делает – то одно довлеет,
Всех мук роды сей един труд в себе имеет.


Будучи созданным комитетом лиц из академической среды, язык Алгол-60, по выражению википедии, в остальном довольно разумно организованный, содержит особенности, примечательные удивительным сочетанием полной практической бесполезности с чрезвычайной сложностью и неэффективностью реализации.

Вот одна из этих особенностей, о которой я недавно узнал. Полная реализация языка в соответствии с "Пересмотренным сообщением об Алголе-60" от 1962 года должна была компилировать следующую программу (детали синтаксиса оператора вывода могли варьироваться):
begin
    procedure call(Q); procedure Q;
        begin Q(3); end;
    procedure jump(A); label A;
        begin goto A end;
    procedure out(B); real B;
        begin print(` value', b) end;
    call(out);
    if true then
        call(jump)
    else
        3: print(` label 3')
end


Эта программа должна была успешно выполняться и печатать что-то типа "value 3.00000 label 3".

(Для тех, кто не любитель птичьих языков: цифра 3 в конструкции Q(3) в этой программе означает не пойми что - то ли число, то ли метку - и компилятор этого не знает, пока не просмотрит всю программу. Когда он это узнает, то выясняется, что так можно было, и нужно порождать выполняемый код.)

Большинство западных авторов компиляторов решило на это дело забить, и или просто не допускало числовые метки, или диагностировало в этом случае какую-нибудь ошибку, но не таковы были советские программисты.

Алгол БЭСМ-6 имени В. М. Курочкина компилирует и выполняет программу правильно.

К чести стандартизаторов языка, это безумие было в конце концов устранено в "Модифицированном сообщении об Алголе-60" к середине 1970-х годов путём ликвидации меток, обозначаемых числами.

This entry was originally posted at https://spamsink.dreamwidth.org/1220252.html. Please comment there using OpenID.
lenin

Программистский вопрос; возможно, тупой

Вопрос про регулярные выражения.
Приглашаются также продвинутые пользователи текстовых редакторов, ворд-процессоров и т. п., знающие магический смысл сочетания .* в строке поиска по тексту.

Collapse )

This entry was originally posted at https://spamsink.dreamwidth.org/1215605.html. Please comment there using OpenID.
lenin

Занимательная кодология

Если взять файл с программой на языке программирования Паскаль, записанной в кодировке ГОСТ-10859, имевшей хождение на советских компьютерах в 60-х – 80-х годах прошлого века, и рассмотреть ее в кодировке ASCII, имеющей хождение и посейчас, то львиная доля кодов (в частности, цифры и знаки препинания и арифметических операций) окажется управляющими - так, например, в кодировке ГОСТ каждая цифра кодировалась байтом с соответствующим значением, от 0x00 до 0x09, русские буквы превратятся в знаки препинания и цифры, и только некоторые латинские буквы превратятся в заглавные латинские буквы.

Так вот, к чему я это всё.

Операторы вывода (WRITE), которыми изобилуют программы на Паскале, выглядят в ASCII как KGB2%.

This entry was originally posted at https://spamsink.dreamwidth.org/1213630.html. Please comment there using OpenID.
lenin

(no subject)

Какие неленивые люди в Великобритании живут! Одни придумывают головоломки на тему новой банкноты, посвященной Тьюрингу, другие их тут же решают почём зря...



This entry was originally posted at https://spamsink.dreamwidth.org/1208981.html. Please comment there using OpenID.
lenin

В каждой шутке есть доля шутки

Знаете такую шутку? Извините, Вы не можете использовать указанный пароль. Такой пароль уже использует пользователь Misha. Пожалуйста, придумайте другой пароль. (https://bash.im/quote/399755 - 2008 год)

Так вот, вы будете смеяться, но лет 30-35 до появления этой хохмы на баше подобная ситуация существовала в реальности на БЭСМ-6.

В цитате ниже "ШИФР" = аккаунт, "ЭК ..." - экстракод операции системного вызова установки/смены пароля (те, кто работал в MS DOS, увидят сходство с "INT 21h, AH = ...."), "СМ" - сумматор (регистр шириной 48 разрядов).
5.3.37. ЗABEДEHИE ПAPOЛЯ HA ШИФP.

                     ЭK 050, AИCП = 143B.

      BXOДHAЯ ИHФOPMAЦИЯ:

 CM:  24- 1 PP. - ПAPOЛЬ B ДBOИЧHO-ДECЯTИЧHOM BИДE. OДHA  ИЗ
                  ДBYX  CTAPШИX  ЦИФP  ПAPOЛЯ HE ДOЛЖHA БЫTЬ
                  HYЛEM.

      BЫXOДHAЯ ИHФOPMAЦИЯ:

 CM:            = 0 - ЗAДAH HEKOPPEKTHЫЙ ПAPOЛЬ;
                = 1 - ДAHHЫЙ ПAPOЛЬ YCTAHOBИTЬ HEЛЬЗЯ;
      БEЗ ИЗMEHEHИЯ - ПAPOЛЬ YCTAHOBЛEH.


Трюк заключается в том, что хранились только 2 из 6 цифр пароля; оставшиеся 4 цифры определяли расположение записи о пользователе в системной таблице из 3*512 = 1536 элементов. Если при установке пароля вычисленное место было пустым, то запись переносилась туда, а если там уже была запись о пользователе с паролем, то возвращалась ошибка.

Подтверждение пароля заключалось в проверке, действительно ли в позиции, вычисленной по указанному паролю, хранится запись о пользователе с данным шифром (и что первые две указанные цифры пароля совпадают с хранящимися, разумеется).

Всего возможных паролей, таким образом, могло быть 1536*99 = 152064, но автоматически перебрать их было нереально, поскольку запуск процесса занимал заметную долю секунды, а каждая неудачная попытка протоколировалась. This entry was originally posted at https://spamsink.dreamwidth.org/1198647.html. Please comment there using OpenID.
lenin

Не могу молчать

Вы не поверите, какие безумные мудаки работают в Microsoft!

Эти мудаки мало того, что запрятали в windows 10 опцию "focus follows mouse" (довольно стандартную и привычную в Unix) хрен знает куда — в стандартных Settings её нет, нужно вызывать программу control), так ещё и сделали emoji picker (Win-точка) так, что он в принципе неработоспособен в режиме "focus follows mouse".


This entry was originally posted at https://spamsink.dreamwidth.org/1195435.html. Please comment there using OpenID.
lenin

Чудеса в грузовике

Сегодня мне должны были доставить UPS-ом некий заказ с Амазона, довольно громоздкую, хотя и не очень тяжелую коробку.

11/05/2020 8:35 A.M.	Sunnyvale, CA, United States	Out For Delivery Today


Примерно в пять вечера у меня на телефоне появилось сообщение от Амазона, что заказ доставлен в 4:49 P.M. к входной двери, хотя я, сидя в гостиной неподалеку от двери, никакого шебуршания не слышал. Открываю - смотрю, ничего нет (время 5:08). Обошел вокруг дома, вдруг бросили рядом с гаражом - ничего нет.

Смотрю на сайте UPS - "доставлено", то же время. Ну, думаю, неправильно прочли адрес, и поди ищи этот заказ, если случайный адресат окажется любопытен или ленив и тащить её к моему дому, или даже писать записку. 

Звоню в UPS. Милая дама говорит мне, что заказ ещё едет. Ась, — говорю я, — у вас на сайте написано, что доставлено. Не бойтесь, — отвечает дама после паузы, — это ошибка, в нашей системе уже исправлено, доставят позднее. Я уезжаю из дому примерно через час после разговора; на тот момент сайт UPS всё ещё показывал "доставлено".

Вернулся домой я примерно в полночь. Ничего доставлено не было, но зато статус сменился на

In Transit	11/05/2020 11:07 P.M.	Sunnyvale, CA, United States	Delivery will be delayed by one business day.

Что-то мне подсказывает, что водитель подъехал к дому, просканировал коробку, чтобы отметить как доставленную, приподнял и понял, что ему лень тащить её к моей двери, оставил корячиться завтрашней смене.

А Амазон продолжает считать, что заказ доставлен:

4:49 PM Delivered Sunnyvale, CA US
8:35 AM Out for delivery Sunnyvale, CA US

Не думали, не гадали, никак не ожидали амазоновские программисты такого вот конца, наивные. Что скажешь, morfizm ?

This entry was originally posted at https://spamsink.dreamwidth.org/1193487.html. Please comment there using OpenID.