drifting-ice-floe feelingsnippets

Sunday, April 10, 2011

трюки быстрого счёта

Наткнулся давеча на такую вот раздачу: http://rutracker.org/forum/viewtopic.php?t=2918851 (Примечание: лучше не читайте там описание, это наполовину рекламный бред. Впрочем, возможно, вам хочется почитать рекламный бред. А может, вы ещё и порядочный гражданин нероссии и люто-бѣшено ненавидите трекеры... Тогда вам дорога сюда: http://www.glad2teach.co.uk/fast_maths_calculation_tricks.htm).

Аннотация: серия коротких (3-5 минут) роликов, где презентуются всяческие хитровы*$%нные приёмы счёта. Объяснения идут на английском с жутким индусским акцентом (хотя, наверное, бывает и хуже...). Приёмы эти, как утверждается, пришли из Вед, но это весьма сомнительно.

Короче, в целом полезно посмотреть. По крайней мере, сможете после этого, к примеру, 207 и 212 перемножать устно, а не в столбик.

а вообще — что-то осточертела мне вся эта математика. *пошёл Юнга курить* (прим. для особо упоротых: нет, не того, в честь которого соответствующие диаграммы назвали)

Thursday, March 17, 2011

Делить или умножать?

Сегодня информатик на лекции заявил, что следует писать не x / 2.0, а x * 0.5 , ибо деление тормознее умножения. Как показала проверка, это действительно так (в данном случае деление раза эдак в 3 медленнее).

Однако из этого не следует делать вывод, что в критичных местах кода нужно заменять деление на умножение — благо большинство компиляторов управятся с этой тягомотиной куда быстрее вас. Более того, они к тому, что получилось после замены деления на умножение, таких оптимизаций (на уровне машинных инструкций) наприменяют, что вам и не снилось.

Перейдём к циферкам.

Использовался gcc 4.4.5.
Тестовый код:

const int N = 100000000;
double x; int i;
int main() {
    for (i = 0; i < N; ++i)
        x = i / 2.0; // или же i * 0.5
    return 0;
}

При компиляции безо всяких флагов результаты следующие: деление — 5.5 секунд, умножение — 1.6 секунды. Ух ты, надо всюду умножение использовать!

А теперь компилируем со слабой оптимизацией (-O1) и осознаём, что все наши усилия по оптимизации кода были смехотворны: теперь в обоих вариантах получилось 1.1 секунды.

(Между прочим: у fpc, похоже, с floating-point оптимизациями дела обстоят паршиво. У gpc (который из GNU Compiler Collection) — нормально, вроде бы так же, как и у gcc (в общем-то, неудивительно). ~~Надеюсь, в этих ваших Delphi с этим норма~~ а хотя не, фтопку делфи ^_^)

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

Sunday, March 13, 2011

обо всём и ни о чём

(Как-то вот не набирается мыслей на полноценный пост. Хоть на каком-нибудь juick аккаунт заводи...)

Итак, на прошлой неделе...

Обнаружил ништяковый шрифт под названием Consolas. (Если что от Microsoft и может быть хорошего, так это шрифты. Ну ладно-ладно, DirectX ещё, так и быть.) Заодно удосужился наконец разобраться, что такое subpixel rendering и hinting.

Открыл для себя Padrino — веб-фреймворк на Ruby. Всё-таки Rails как-то монструозен, а Sinatra, наоборот, слишком минималистична (или '-ен'? а, пофиг). Ну и с Heroku пришлось подружиться, альтернативных бесплатных хостингов для Ruby-приложений и нет фактически.

А ещё принял участие в perplexed!. Что за турнир — объяснять долго, по ссылке можете заиметь представление. Вообще, чумовая вещь =) Маньяки-организаторы (что символично, индусы) изначально планировали сделать его 12-часовым, но всё же укоротили до 8-ми часов. Никогда ещё такой извращенский код не писал)))

А ещё... Ой, не, пожалуй, хватит ^_^

Saturday, March 12, 2011

наконец-то

В Firefox 4 и IE 9(!!!) наконец-то будет нормальный border-radius, безо всяких там префиксов. Release candidates уже доступны для скачивания.

Учитывая то, что в текущих Opera, Chrome и Safari это свойство уже поддерживается, скоро можно будет прекращать свистопляску с "-moz-border-radius" и "-webkit-border-radius" ^______________^

Saturday, February 26, 2011

Ruby: пообезьянничаем? ;-)

В некоторых, так скажем, «математико-ориентированных» языках программирования операции над векторами реализуются довольно компактным образом. В качестве примеров таких языков можно привести J и R.

В R вектор создаётся функцией c — это сокращение от 'concatenate'. Поскольку создание вектора — весьма частое явление, сократили название до предела. Компактность операций заключается в следующем:

> c(1, 2, 3) ** 3
[1]  1  8 27
> c(1, 2, 3) * c(5, 3, 1)
[1] 5 6 3 
> log10(c(1, 10, 100, 1000))
[1] 0 1 2 3

Думаю, идея ясна.

Можно ли что-нибудь подобное реализовать в Ruby? Запросто! Чтобы вышеприведённые примеры работали, потребуется всего-то порядка 30 строк кода.

/0.

Иногда бывает удобно вернуть из функции значение $+\infty$ или $-\infty$ . Это бывает проще, чем обёртывать вызов функции всяческими предпроверками. Пример: пересечение пары прямых на плоскости. В случае деления на ноль (если по формулам Крамера считать) просто получится точка с как минимум одной «ненормальной» координатой. А потом можно и проверить точку на финитность — нужно только знать, как. (В реальности, конечно, есть ещё и ошибки округления...)

Так вот, в C/C++ за работу с бесконечностями и нечислами (например, sqrt(-1.0)) отвечает <math.h>. В нём определены «константы» INFINITY и NAN (на самом деле это макросы, но кого это волнует?), а также горстка полезных «функций» (тоже макросы): isfinite, isnan, isinf, signbit. Всё это работает только для чисел с плавающей запятой.

Первые две функции проверяют аргумент на конечность и «NaN»-овость соответственно. isinf возвращает -1, 0 или 1 (потому как у бесконечности есть знак).

signbit возвращает ненулевое значение в случае отрицательности аргумента. Это может показаться странным: почему бы просто не сравнить аргумент с нулём? Дело в том, что у нуля тоже есть знак. (Правда, я понятия не имею, где это может пригодиться.) То есть signbit(1.0 / INFINITY) вернёт ноль, а signbit(1.0 / -INFINITY) — что-то иное.

(Что-то какой-то неоконченностью отдаёт. Ну и хоен с ним.)

Saturday, February 12, 2011

Как вычисляется факториал

Как найти n! ? Казалось бы, берём и перемножаем все числа от 1 до n, чего тут думать-то? Однако не так всё просто.

Итак, зададимся целью вычислить 1000000! (безо всяких приближений) за вменяемое время (порядка 1-2 минут). Предполагается, что работа с длинными числами встроена в язык, причём их умножение реализовано более-менее адекватно (ну хотя бы алгоритмом Карацубы). Далее в посте будет использоваться Ruby, в котором именно Карацуба и реализован.

Попытки посчитать "по определению" ни к чему толковому не приводят:

def factorial(n)
    r = 1
    for i in 1..n do
        r *= i
    end 
    return r
end

user     system      total        real
25000!      3.320000   0.060000   3.380000 (  3.393819)
50000!     14.210000   0.190000  14.400000 ( 14.458802)
100000!    58.970000   0.870000  59.840000 ( 60.115690)

Как видим, время ~ n², хотя число множителей ~ n. Невесело как-то. Эдак 1000000! нам часа два ждать придётся...

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

Чтобы сделать длины перемножаемых чисел примерно равными, поступим следующим образом. Заметим, что
$n! = n\cdot(n-1)\cdot\,\,\ldots\,\,\cdot 1 = (n(n-2)(n-4)\cdot\,\,\ldots\,) \cdot ((n-1)(n-3)(n-5)\cdot\,\, \ldots\,)$

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

def g(n, step)
    return n if n <= step
    return g(n, step*2) * g(n-step, step*2)
end

def factorial(n)
    g(n, 1)
end

Ничего сложного в этом нет, а время выполнения улучшилось на порядок:

user     system      total        real
25000!      0.330000   0.000000   0.330000 (  0.365312)
50000!      1.030000   0.030000   1.060000 (  1.098816)
100000!     3.560000   0.030000   3.590000 (  3.666322)

И в принципе, если лень заморачиваться, это вполне неплохой алгоритм. Тот самый 1000000! вычисляется за 4 с небольшим минуты.
Этот алгоритм можно ещё немножко ускорить, если заметить, что
$2n\cdot(2n-2)\cdot(2n-4)\,\cdot\,\,\ldots\,\, = 2^n\cdot(n(n-1)(n-2)\,\cdot\,\,\ldots\,)$ , т.е. g(2n, 2) = 2ⁿ*g(n, 1). Вместо уймы умножений на 2 лучше накапливать степень двойки в отдельной переменной, а в конце сделать сдвиг влево на это значение:

class Factorial
    @shift = 0
    def g(n, step)
        return n if n <= step
        if n.even? and step == 2 then
            @shift += n/2
            return g(n/2, 1)
        end
        return g(n, step*2) * g(n-step, step*2)
    end
    def fac(n)
        @shift = 0
        v = g(n, 1)
        return v << @shift
    end
end

Однако можно ускорить вычисление факториала ещё раза эдак в два! Но для этого нужно применять куда более хитрые методы.
(На этом вступление заканчивается ^____^)