July 14th, 2018

moose, transparent

шаламов по-английски

Тайлер Коуэн восхищается рассказами Шаламова в (новом) английским переводе и сокрушается тем, что их почти никто не прочитает:

Have you ever wondered how the contemporary world would react if a masterpiece were dropped into its midst? If your guess was “with a fair amount of indifference unless it was Elena Ferrante and even then it wouldn’t really change anything except give rise to probably what will be a mediocre television series”…well, you were right. For Shalamov, I don’t yet see an Amazon review.

Новый перевод вышел в серии New York Review Books Classics - это камерная музыка, магазин-бутик, артхаус-кино. У него нет и не будет публичных чтений в больших книжных магазинах, турне автора по Америке, рекламного бюджета для объявлений в газетах и журналах; все эти вещи оказывают огромное влияние на популярность книги - когда-то я этого не понимал. У предыдущего перевода в середине 90-х, в более народной серии Penguin Classics (но тоже Classics, видите это проклятое слово), 94 рецензии на Амазоне - не так уж и плохо на самом деле. У первого неаполитанского романа Ферранте - 2366. Сравнивать их кажется чуть нелепым, но не я начал.
moose, transparent

кельтский камень

СЯУ про кельтский камень, он же "rattleback". Это небольшая игрушка в виде эллипсоида, которая на обычном столе легко вращается в одну сторону, а если закрутить в другую быстро останавливается, шатаясь при этом чуть вверх-вниз, и начинает крутиться в противоположную сторону. Наглядная демонстрация имеет очень высокий WTF-фактор, подтверждаю по личному опыту.

Из нескольких объяснений того, как он работает, что я прочитал, ясно, что ключевую роль играет трение с поверхностью (на очень скользкой поверхности эффект не работает, крутится в обе стороны). Но момент импульса игрушки не может просто так уходить "в никуда" от того, что трение останавливает вращение. Верно ли сказать, что каждый раз, когда кельтский камень быстро останавливается и начинает крутиться в другую сторону, он чуть-чуть закручивает Землю в обратную сторону? (relevant xkcd). Но с другой стороны, когда я его первоначально закрутил пальцами, я забрал этот момент импульса у Земли, наверное?

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

В общем, кельтский камень отличная штука.
moose, transparent

умножение карацубы

Анатолию Карацубе было 23 года, когда в 1960 году он обнаружил способ умножения чисел, более быстрый, чем известные до тех пор, и положил тем самым начало всей области быстрых алгоритмов.

История этого открытия описана вкратце в его обзорной статье о сложности вычислений (математика там довольно сухая, зато есть интересный исторический обзор об умножении в древности). Великий математик Колмогоров стремился доказать, что умножение двух n-размерных чисел требует примерно n^2 элементарных операций, и меньшим числом не обойтись. Например, представьте, что вы умножаете 1234 * 5678 в столбик: вам надо по сути дела умножить каждую цифру числа 1234 на каждую цифру числа 5678, т.е. сделать 16 элементарных умножений цифры на цифру; плюс еще много раз складывать промежуточные результаты и приписывать нули в конце. Но общее число операций будет порядка 16 (может, в два или три раза больше, чтобы учесть все сложения и приписывания). А если вы умножаете два числа по 1000 цифр в каждом, то общее число операций будет 1000^2, т.е. миллион (может, в 2-3 раза больше, но это несущественно). Колмогоров считал несомненным, что нет какого-то магического способа умножать числа быстрее, чем умножение в столбик, которым люди пользуются уже 2000 лет. Но он не мог это доказать.

Карацуба: "Осенью 1960 г. в Московском университете на механико-математическом факультете начал работать семинар по математическим вопросам кибернетики под руководством А.Н. Колмогорова, где А.Н. Колмогоровым была сформулирована гипотеза n^2 и поставлен ряд задач об оценке сложности решений линейных систем уравнений и других сходных вычислений. Я активно стал размышлять над гипотезой n^2 и ровно через неделю обнаружил, что алгоритм, которым я надеялся получить нижнюю оценку, дает оценку вида O(n^1,549...). После очередного заседания семинара я сообщил А.Н. Колмогорову о новом алгоритме умножения и об опровержении гипотезы n^2. Это сильно взволновало А.Н. Колмогорова, так как противоречило его довольно правдоподобной гипотезе. На следующем заседании семинара мой метод умножения был рассказан самим А.Н. Колмогоровым, и на этом семинар прекратил свою работу."

Попытаюсь объяснить суть открытия Карацубы в упрощенном виде. Представьте себе, что перед вами поставили задачу перемножить два числа, например 1234 * 5678, но при этом все операции сложения и приписывания нулей вам дают "бесплатно", а вот за каждое умножение двух цифр надо платить, ну не знаю, доллар. Может, кому-то удалось запатентовать таблицу умножения? Понятно, что это можно "обойти", сделав умножение через сложение, но давайте притворимся, что мы так не умеем, и что каждый раз, когда надо умножить две цифры, мы честно платим доллар; естественно, мы хотим делать как можно меньше умножений.

Если умножать в столбик обычным способом, то будет 16 умножений (каждая цифра на каждую), ничего не поделать. Но можно попробовать вывернуться как-то. Что если мы разделим каждое 4-х значное число на два двузначных?

1234 * 5678 = (12*100 + 34) * (56*100 + 78)

Здесь *100 не является по-настоящему умножением (это всего лишь приписывание нулей в конце, бесплатно). Если мы раскроем скобки, то получим сложную формулу в которой будут участвовать произведения чисел 12, 34, 56, 78, плюс всякие нули и сложения. Сколько умножений надо сделать? На первый взгляд четыре, когда мы раскрываем скобки: 12*56, 12*78, 34*56, 34*78. Если мы предполагаем, что два двузначных числа мы перемножаем в столбик, по 4 умножения цифр для каждого (а лучше мы пока не умеем), то выходит всего 4*4 = 16 умножений, и мы ничего не улучшили.

И тут открытие Карацубы. Обратим внимание, что нам на самом деле нужно получить, для окончательного сложения, три вещи: 12*56 (к нему приписать четыре нуля), 34*78 (не приписывать нулей), и 12*78+34*56 (к этому приписать два нуля). Если бы эту сумму двух произведений можно было как-то получить с помощью всего одного умножения, то вместе четырех мы бы получили три двузначных произведения. Карацуба заметил, что если мы скомпонуем вместе 12+34, и 56+78 - это весьма неинтуитивно, потому что мы складываем сотни и тысячи с десятками и единицами, казалось бы, зачем - и умножим, то получим:

(12+34)*(56+78) = 12*56 + 34*78 + 12*78 + 34*56.

Но первые два произведения мы и так уже вычисляем: 12*56 и 34*78. А оставшиеся два - это как раз то, что нам нужно. Значит, достаточно сделать только три умножения:

12*56
34*78
(12+34)*(56+78)

И из результата третьего вычесть первые два, чтобы получить все, что нам нужно для результата (после приписывания нулей и сложений, которые бесплатны). Если каждое из этих трех умножений двузначных чисел (да, 56+78 оказывается трехзначным, но это крохотное усложнение, которое легко учесть и не меняет сути) занимает, как раньше, 4 умножения, теперь у нас всего требуется только 3*4=12 умножений двух цифр. А ведь каждое умножение двухзначных чисел можно по такому же принципу свести к 3-м, а не 4-м умножениям, и тогда выходит всего 3*3=9 умножений, вместо исходных 16.

Это и есть алгоритм Карацубы, в одном из его видов. Естественно, это все становится важным, только когда мы умножаем 50-значные или 1000-значные числа, а не такие маленькие. Но суть в том, чтобы свести задачу к меньшей, с под-задачами на числах в 2 раза короче, но благодаря этому странному трюку оказывается надо делать не 4 под-задачи, а только три. Эти под-задачи в свою очередь разбиваются на три поменьше, и так далее. Кропотливый математический анализ показывает, что число операций для умножения двух n-разрядных чисел становится не n в квадрате, а примерно в степени полтора. А для очень длинных чисел это играет важную роль.