Архив

Archive for Март 2009

Песня о скалярном произведении

Эта песня будет о старой и важной проблеме вычислительной математики. Собственно, проблема и сейчас живее всех живых, о чём стандартно предупреждается в любом мало-мальски приличном курсе численных методов… а студенты столь же стандартно об этом забывают… 🙂

Казалось бы, ну что может быть проще скалярного произведения? Пусть у нас речь идёт о векторах размерности, допустим, 100. Вроде, и не нужно быть крутым программистом, чтобы написать нечто вроде

float DotProduct(float x[],float y[]) {
    float r=0.0;
    for(int i=0;i<100;i++) r+=x[i]*y[i];
    return r;
}

Агащазблин. 🙂 Не работает-с. Вернее, работает только в игрушечных ситуациях.

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

±#.#######e±##

Один символ «#» соответствует одному хранимому разряду.

Теперь мысленно промоделируем вычисление скалярного произведения вектора на себя. Вектор будет иметь следующий вид: первые 99 позиций заняты одним и тем же числом 0.0003 = 3е-4, а в последней позиции стоит единица 1 = 1е+0 = 1е-0.

Для i=0…98 будем иметь x[i]*y[i] = 9e-8. Суммируя это число 99 раз, получим 8.909е-6 = 0.000008909е-0. Для i=99 к этому числу прибавится единица:

1.0000000е-0 + 8.909е-6 = 1.0000000е-0 + 0.000008909е-0 = 1.0000089е-0

Два последних разряда не вписываются в сетку, и происходит округление. С поправкой на этот факт, ответ правилен.

А теперь представим, что вектор тот же самый, но его компоненты идут в обратном порядке. 🙂 Чисто математически его скалярное произведение на себя никак не должно измениться.

А что же происходит в программе?

А вот что. После итерации i=0 будем иметь r=1e-0. Итерация i=1 добавляет к нему число 9е-8. Которое, обратим внимание, с разрядной сеткой единицы несоизмеримо!

И вот тут возможны два варианта, в зависимости от реализации арифметики с плавающей точкой. В первом — тупом — несоизмеримое 9е-8 будет просто отброшено. Как нетрудно догадаться, в итоге мы так и получим единицу ответом.

Во втором — умном — будет замечено, что несоизмеримое число «занимает более половины последнего разряда». И с округлением получится r=1.0000001е-0. В итоге, как опять же нетрудно догадаться, ответом будет 1.0000099е-0.

Итого: в ситуации, где ответ один и тот же, их легко может на самом деле получиться три разных. 🙂 С учётом того, что в вычислительных методах скалярное произведение векторов является одной из самых распространённых операций, возможные последствия представить нетрудно.

Этот пример, конечно, игрушечен, но и для реальных ситуаций настроить таких примеров очень нетрудно. Могу, например, с ходу сказать, что «отбрасыванием несоизмеримого» одно время грешили компьютеры от фирмы Fujitsu…

Математики-вычислители столкнулись с этой проблемой ещё в 1950-х годах. Решение её, казалось бы, очевидно: складывать произведения x[i]*y[i] не по возрастанию индексов, а по возрастанию их абсолютных значений. Что естественным образом означает сортировку массива. Способ дико затратный, но иногда приходилось делать и так. Потому что по-другому вообще не получалось.

Сейчас, конечно, делают проще. Просто-напросто объявляют накопитель r типа long double — максимально длинного доступного типа. Либо для накопления применяют специализированные подпрограммки с собственной длинной арифметикой — их немало гуляет в научном мире.

И студентов, конечно, предупреждают, да. Но они таки считают себя крутыми программёрами и редко слушают подобные предупреждения своих старых пердунов преподавателей. За что потом бывают тыкаемы носом в свои дурацкие ошибки… 😉

Реклама

«Монстры против пришельцев»

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

Потом ещё стало известно, что фильм выйдет в 3D. То есть нам была обещана стёбная визуальная феерия.

Ну так вот, именно оно и получилось. Поставив перед собой вполне конкретную задачу без эпического размаха, в данном случае команда создателей справилась с ней на все сто.

Мы получили не шедевральный, но отличный фильм, в котором почти всё — на очень твёрдую четвёрку. Всё, кроме 3D и киноманской обвязки сценария. Эти на не менее твёрдую пятёрку.

Сам по себе сценарий очень прост, но отлично сбалансирован. Ни малейшей пошлости, самая чуточка морали, и ма-а-аленький такой рояль в кустах, который по рассмотрении оказывается даже не роялем, а синтезатором. 🙂 Ну, а обвязка великолепна: в разных сценах и сюжетных ходах спародировано столько старых добрых второсортно-классических фильмов, что устанете узнавать. 🙂

Любителям фантастики-ужастики — смотреть однозначно. Если есть к тому возможность — обязательно в 3D. Хотя и без него кучу удовольствия получите, факт. Но с ним ещё лучше.

Удивительно, но на сей раз приятно порадовал русский дубляж. То есть, конечно, ничего нельзя пока сказать про его адекватность оригиналу — но если рассматривать сам по себе, то очень хорош. Сергей Гармаш на озвучке генерала совершенно великолепен, хотя генерала в фильме и не очень много.

Короче, смотреть. Без вопросов.

P.S. Насекомозавр — просто лапочка. 🙂 Большой, рыжий, толстенький, пушистый; местами трусоват и тормознут — но оччень обаятелен! Вылитый кот моей бабушки. 😉

Рубрики:Фильмы

Старый тест для начинающих программистов. Разбор.

Итак, два дня назад я рассказал об одной задачке, некогда предлагавшейся для проверки мышления студентов — будущих программистов. Это было здесь.

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

Для начала посмотрим на лобовое решение, которое чаще всего и предлагают в качестве ответа. Вот оно:

long fact(long k) {
    long r=1;
    for(long i=1;i<=k;i++) r*=i;
    return r;
}

long C1(long m,long n) {
    return fact(n)/(fact(m)*fact(n-m));
}

Примерно так. Здесь нечего комментировать. Число сочетаний считается прямо по формуле, как отношение трёх факториалов, причём вычисление факториала вынесено в отдельную функцию.

На самом деле это вообще не решение. 🙂 Почему — станет понятно через несколько абзацев.

Реже предлагают следующий вариант:

long C2(long m,long n) {
    long mf=1, nf=1, nmf=1;
    for(long i=1;i<=n;i++) {
        nf*=i;
        if(i==m) mf=nf;
        if(i==n-m) nmf=nf;
    }
    return nf/(mf*nmf);
}

С точки зрения конечного результата он столь же никудышен, как и предыдущий. 🙂 Но идеологически авторов такого варианта уже есть за что похвалить — здесь замечено, что из трёх факториалов n!, m! и (n-m)! два последних сами по себе не нужны. Оба они меньше первого и de-facto всё равно считаются в процессе нахождения n! как промежуточные этапы. То есть наличествует анализ проводимых вычислений и определённая оптимизация программы.

А чем же плохи оба этих варианта? Очень просто: попробуйте для проверки посчитать любым из них… ну, например, следующее:

Сейчас угадаю — программа либо вылетит, либо даст неправильный ответ. 🙂

А чего ж вы хотели, считая факториалы?! 🙂 Факториал — это, знаете ли, такая штука, которая возрастает не очень быстро, а потрясающе быстро. В 2 байта (16 бит) не влезет уже 9!. В 4 байта (32 бита) не влезет уже 13!. В 8 байт (64 бита) не влезет уже 21!. В 16 байт (128 бит) не влезет уже 35!. Ну, вы поняли. При этом результаты, как видно из приведённого примера, вовсе не обязательно являются астрономическими числами.

Посмотрим на формулу внимательнее. Вот она ещё раз:

Давайте обозначим k=min(m,n-m) и K=max(m,n-m). В этих терминах можно записать, что

Теперь замечаем, что множители, образующие К!, полностью сокращаются. Итого в числителе и знаменателе остаётся по k сомножителей:

А зачем я написал сомножители в числителе по убыванию, а не по возрастанию? А вот зачем.

Смотрите. Всегда n будет нацело делиться на 1. Всегда n·(n-1) будет нацело делиться на 1·2, ведь из двух идущих подряд натуральных чисел одно обязательно делится на 2. Всегда n·(n-1)·(n-2) будет нацело делиться на 1·2·3, и так далее.

Вот так-то, парными умножениями-делениями, и надо накапливать результат. Соответствующий код очень прост:

long C3(long m,long n) {
    long k,r=1;
    k=(m<n-m)?m:n-m;
    for(long i=0;i<k;i++) r=(r*(n-i))/(i+1);
    return r;
}

Эта функция будет работать, если только ответ вообще влазит в разрядную сетку. Заметьте — никаких рекурсий, массивов, треугольников Паскаля, динамического программирования и прочих хитростей. 😉

Тут есть только одна тонкость. Обратите внимание на накопление результата r=(r*(n-i))/(i+1). Почему нельзя писать без скобок просто r=r*(n-i)/(i+1)? Да потому что умножение и деление имеют одинаковый приоритет — где гарантии, что компилятор не сгенерирует код, в котором сначала производится деление?! А вот оно делиться нацело вовсе не обязано!!! По той же причине нельзя писать в исконно С-шном стиле r*=(n-i)/(i+1) — здесь деление гарантированно выполняется первым, и результат будет заведомо неправильным.

Такая вот старая задачка. Надеюсь, вам понравилось. 🙂

Старый тест для начинающих программистов :-)

Последний мой пост вызвал вполне предсказуемую реакцию. 🙂 Точнее, целый набор легко предсказуемых реакций. Из которых я хотел бы затронуть лишь одну.

Типичным мнением старшеклассников и первокурсников является следующее: дело математиков формулы выводить, а мы, крутые программёры, будем их прогать. Математики всё равно в программёрстве не шарят нифига, полвека уже застряли на своём допотопном фортране, ну да ведь и нам их математика нужна лишь ровно настолько, чтоб эти формулы понимать.

Я думаю, не очень ошибусь, если предположу, что почти каждый современный школьник, написав первую в своей жизни программу, и решив учиться на программёра, хоть раз в жизни, да подумал нечто подобное. 😉 Другое дело, что у большинства хватает ума не ляпать такое вслух, а из них значительная часть в процессе учёбы быстро понимает, что к чему. 🙂

Заблуждение это настолько старо, глупо и дремуче, что уже давно перестало вызывать улыбку, и тем более — желание с ним спорить. Но я в этой связи вспомнил один тест, который некогда предлагали студентам младших курсов — будущим программистам.

Вот он весь: необходимо написать программу для нахождения так называемого числа сочетаний (оно же — биномиальный коэффициент) по следующей формуле:

Не нужно даже компьютера, вполне достаточно написать на бумаге. И не стоит тратить время на проверку условий относительно n,m — будем считать, что входные данные задаются всегда корректно. На всякий случай напоминаю, что 0!=1.

Желающие могут попробовать, а я обещаю через пару дней разобрать этот тест. 🙂

Только не надо исходники и алгоритмы в комментарии. 😉

Линуксоидизм. Клиника-с.

Здесь был старый текст аж 2009 года. Но он больше не будет.

Причина? Сюда слишком любили набегать некроманты с некрофилами и устраивать вокруг свои пляски с бубном.

Спасибо за понимание.

Рубрики:Работа

Рашен автосервис :-)

Обычно за сюжетами приходится гоняться. Но иногда они сами тебя находят.

Я не знаю, что побудило меня приостановиться возле здоровенного щита «СТО, замена масла» и посмотреть в направлении, на этом самом щите указанном. Но увиденное меня удивило.

Занюханный переулок был наполовину перегорожен древним самосвалом-инвалидом, а прямо посередине другой половины из земли торчала железная труба, также блокирующая проезд. Всё это было обильно посыпано снегом, который тут не убирали минимум месяца полтора. На дорогу к станции техобслуживания оно не походило ни разу.

Не поленившись пробраться по тропинке метров пятьдесят, я был вознаграждён изумительным зрелищем собственно рашен автосервиса. 🙂

— Это просто праздник какой-то! — восхищённо выдохнул я.

— Ага! — не менее восхищённо подтвердила пролезшая следом жена.

Честное слово, я бы не поленился и позвонить, и постучать, благо посетители тут были, как видите, welcome, но…Как вы опять же сами видите, подобраться к воротам не было решительно никакой возможности. 🙂

Добавлю, что весь этот праздник жизни имел место быть не где-нибудь, а в трёх минутах от сáмого центра Новосибирска.

Рубрики:Фотография

Казнить нельзя помиловать?

Вот весна. А это значит, скоро лето. А это значит, что скоро вновь начнутся драмы с ЕГЭ и вопросами поступления… Вот сегодня уже и первый звоночек прозвенел.

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

Ну, ей там на вопросы, конечно, ответили. А потом сбагрили её на меня, благо я с первокурсниками много работаю. Перешли мы на кафедру.

Нормально так поговорили. У меня всё равно «окно», а тётенька вполне адекватная — интересуется, вопросы задаёт. Оказывается, у неё два сына: один в последнем классе учится, другой в предпоследнем. То, сё, разговор плавно подъехал к экзаменам (кто не в курсе, с этого года пока что намереваются все выпускные/вступительные только в форме ЕГЭ принимать). Я возьми, да и спроси, чего она думает об этом ЕГЭ как родительница.

А тётка взяла, да и ударилась в слёзы.

Фигасе. Ну, там, воды конечно дал попить, всё такое… Успокоилась. Так в чём, собственно, дело-то?

И вот тут тётка выдала прелюбопытнейшую речь. Дословно, конечно, не воспроизведу, но смысл следующий. С одной стороны, как мать, она страстно желала бы чтоб этот ЕГЭ провалился к чёртовой бабушке — её сие уже через старшего сына-выпускника достало по самое не могу, а на следующий год всё ж по новой повторится с младшим! А с другой стороны, её банально душит жаба — тоже ж можно понять, как прикинешь объёмы денег, уже вбуханные в репетиторство и натаскивание старшего на эти тесты! Это ж, если завтра-послезавтра ЕГЭ возьмут вдруг и отменят, такая жопа будет!

Я себе всё это как представил, так и не позавидовал. Ну а вот что тут скажешь?

Она потом ещё интересную вещь выдала в конце. Примерно так: «Я, дура, когда про эти ЕГЭ впервые узнала, так радовалась, так радовалась! Думала, всё теперь честно будет, без взяток в приёмных комиссиях. Да чёрт бы с ними, со взятками, один раз взятку дать, и то лучше, чем весь последний школьный год на одном корвалоле жить! Может, ещё и не было никаких взяток-то, я в них что-то всё больше сомневаюсь…»

Очень, очень показательно. Вы не находите?

Рубрики:Работа