Инфиксная запись функций (С++)

В общем-то, последующее — полный изврат и к применению не рекомендуется :)

#include <functional>

template <typename Func> struct infix_operator;
template <typename Func> infix_operator<Func>& operator|(int, infix_operator<Func>&);
template <typename Func> int operator|(const infix_operator<Func>&, int );

template <typename Func>
struct infix_operator {
    typedef infix_operator<Func> infix_t;
    int left;
    static Func func;
    friend infix_t& operator|<>(int, infix_t&);
    friend int operator|<>(const infix_t&, int);
};
template <typename Func> Func infix_operator<Func>::func;

template <typename Func>
infix_operator<Func>& operator|(int left, infix_operator<Func>& op) {
    op.left = left; return op;
}

template <typename Func>
int operator|(const infix_operator<Func>& op, int right) {
    return infix_operator<Func>::func(op.left, right);
}

static struct : infix_operator<std::plus<int>> {} PLUS;
static struct : infix_operator<std::multiplies<int>> {} TIMES;
static struct : infix_operator<std::divides<int>> {} DIV;
static struct : infix_operator<std::modulus<int>> {} MOD;

#include <iostream>
int main() {
    std::cout << (((2 |PLUS| 3) |TIMES| (36 |DIV| 6)) |MOD| 17) << std::endl;
}

On variadic templates

GCC developers, February 2008:

We have implemented the complete specification of variadic templates in the GNU C++ compiler [8], which are available in GCC 4.3. The implementation itself was relatively straightforward in GCC, implying that this feature can be implemented in other C++ compilers without architectural changes. Our basic implementation approach involved adding flags to each kind of template parameter and each function parameter stating whether these parameters are in fact parameter packs.
...

Microsoft guys,  September 2011:

We've developed a new scheme for simulating variadic templates.  Previously in VC9 SP1 and VC10, we repeatedly included subheaders with macros defined differently each time, in order to stamp out overloads for 0, 1, 2, 3, etc. arguments.  (For example, included the internal subheader repeatedly, in order to stamp out make_shared(args, args, args).)  In VC11, the subheaders are gone.  Now we define variadic templates themselves as macros (with lots of backslash-continuations), then expand them with master macros.  This internal implementation change has some user-visible effects.  First, the code is more maintainable, easier to use (adding subheaders was a fair amount of work), and slightly less hideously unreadable.  This is what allowed us to easily implement variadic emplacement, and should make it easier to squash bugs in the future.  Second, it's harder to step into with the debugger (sorry!).  Third, pair's pair(piecewise_construct_t, tuple, tuple) constructor had "interesting" effects.  This requires N^2 overloads (if we support up to 10-tuples, that means 121 overloads, since empty tuples count here too).  We initially observed that this (spamming out so many pair-tuple overloads, plus all of the emplacement overloads) consumed a massive amount of memory during compilation, so as a workaround we reduced infinity.  In VC9 SP1 and VC10, infinity was 10 (i.e. "variadic" templates supported 0 to 10 arguments inclusive).  In the VC11 Developer Preview, infinity is 5 by default.  This got our compiler memory consumption back to what it was in VC10.  If you need more arguments (e.g. you had code compiling with VC9 SP1 or VC10 that used 6-tuples), there's an escape hatch.  You can define _VARIADIC_MAX project-wide between 5 and 10 inclusive (it defaults to 5).  Increasing it will make the compiler consume more memory, and may require you to use the /Zm option to reserve more space for PCHes.

Ещё один неплохой шрифт

Что-то осточертел мне Consolas. (А уж стандартные шрифты — и подавно.)
Решил порыться в инете и наткнулся на то, что вы видите справа:

Недостаток — нету bold. Но это компенсируется забавными 'e', 'g', 'j', а также прыгающими циферками :-)

Оно работает o_O

Решил тут запилить паттерн Visitor с блэкдже использованием std::shared_ptr:

#include <memory>
#include <type_traits>

...

struct Node : public std::enable_shared_from_this<Node> {
    virtual ~Node() {}
    virtual void accept(Visitor&) = 0;
};

#define DEFINE_ACCEPT_METHOD \
    virtual void accept(Visitor& v) { \
        v.visit(std::static_pointer_cast<std::remove_pointer<decltype(this)>::type>(shared_from_this())); \
    }

struct SomeNode : public Node {  
    ...
   DEFINE_ACCEPT_METHOD;
    ...
};

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

template <class NodeType>                                                                                       
struct VisitableNode : public Node {
    virtual void accept(Visitor& v) {
        v.visit(std::static_pointer_cast<NodeType>(shared_from_this()));
    }
};

struct SomeNode : public VisitableNode<SomeNode> { 
    ... 
};

визуализация ОДУ в Asymptote

Задали нам, понимаешь, изоклины порисовать на досуге. Ну вот какой уважающий себя программер будет подобной фигнёй вручную заниматься? И вспомнил я тут про Asymptote.
Несколько минут ковыряния в документации привели к следующему: для рисования поля направлений и интегральных кривых имеется модуль slopefield, а для рисования изоклин — модуль contour.

Ну и вот что получилось:

import contour;
import slopefield;
import graph; // чтобы оси нарисовать

settings.outformat = "png";
unitsize(2cm);

pair a = (-5, -5);
pair b = (5, 5);

limits(a, b); // картинка ограничена прямоугольником с углами в a и b
xaxis("$x$", EndArrow);
yaxis("$y$", EndArrow);

real f(real x, real y) { return  x^2 + y^2 - 1; }
real[] isoclines = map(new real(real x){return x*x;}, // анонимная функция применяется к
                     uniform(1, 10, 9)                // массиву {1,2,3,4,5,6,7,8,9,10}
                   ); 

add(slopefield(f, a, b));
draw(contour(f, a, b, isoclines), green);

currentpen = red + 1.5;             // 1.5 - толщина пера в bp (bp == 1/72 дюйма)
for (var i : uniform(-5, 5, 20)) {  // range-based for, так сказать
    draw(curve((i, i), f, a, b));
    draw(curve((0, i), f, a, b));
} 

gсс 4.6+ и венда

Почитывая "C++ Concurrency in Action", осознал, что пользоваться установленной в универе MS VC++ 2010 буду неспособен. Во-первых, потому что в GCC 4.6+ уже реализовали порядка половины стандарта C++0x, включая атомарные типы, мьютексы, потоки и т.п. Во-вторых, потому что терпеть не могу проприетарщину.

Возможных решений вырисовывалось несколько:

• Cygwin: преимущество перед прочими вариантами - gcc, vim и прочие привычные штуковины из мира UNIX в одном флаконе. Только вот в его репозиториях даже в experimental лежит лишь gcc 4.5. Фэйл. Нет, ну не совсем фэйл: можно было кое-как собрать свежий gcc из исходников. Однако, как выяснилось, у меня не настолько прямые руки...
• Mingw-w64: форк полудохлого mingw. В разделе Automated builds можно скачать свежие сборки. Однако, чтобы заработали std::thread, std::mutex и тому подобные няшки, нужно, стоя на одной руке, почесать левой ногой за правым ухом. Я даже пробовал, но как-то не вышло :'-(
  (Точнее говоря, с помощью вот этого вот совета мне удалось заставить работать std::thread, но не std::mutex, без которого использовать многопоточность - тот ещё маразм. При попытке заюзать мьютексы g++ плевался чем-то вроде "error: there are no arguments to '__gthread_mutex_timedlock' that depend on a template parameter, so a declaration of '__gthread_mutex_timedlock' must be available")

• И вот сегодня я внезапно наткнулся на вот это: http://code.google.com/p/mingw-builds/ Обсуждение сборок здесь. Все многопоточные фичи вроде работают. В общем, человеку под ником niXman - респект и уважуха :-)
  А поскольку everything just works, то и говорить особо не о чем. Единственное, что можно отметить: читайте "Description" на гуглокоде во избежание недоразумений. Например, в текущем snapshot-е GCC 4.7.0 для работы std::thread надо компилять сорцы с флагом -static.
• Ещё, наверное, возможен вариант в виде Live USB с линухом. Однако ну его на фиг, ибо наш препод, как выяснилось в прошлом году, даже Vim/GVim ни разу не видел.

В итоге я, ясен пень, остановился на mingw-builds. И вам советую во избежание плясок с бубном)

map::iterator: избавляемся от ->first и ->second

Решил тут в процессе изучения С++ старый свой код порефакторить. Попался такой вот кусочек:

typedef unordered_map<int,double> ColumnMap;
typedef ColumnMap::const_iterator ColumnMapIter;
...
for(ColumnMapIter it = row->begin(); it != row->end(); ++it) {
    ColumnMap *tmp = other -> rlist[it -> first];
    ColumnMapIter it_col = tmp -> find(col);
    if (it_col != tmp->end()) {
        val += (it -> second ) * (it_col -> second);
    }
}

Согласитесь, что в этих first и second чёрт ногу сломит. Однако в плюсах имеется такая редкоиспользуемая фича, как указатели на члены класса. Почитать про них можно, например, здесь: http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=142
С их-то помощью и можно заменить first и second на что-нибудь более понятное.

Смотрите:

typedef unordered_map<int,double> ColumnMap;
typedef ColumnMap::const_iterator ColumnMapIter;
...
typedef ColumnMap::value_type ColumnMapPair;
const ColumnMapPair::first_type ColumnMapPair::* column = &ColumnMapPair::first;
ColumnMapPair::second_type ColumnMapPair::* value = &ColumnMapPair::second;
...
for(ColumnMapIter it = row->begin(); it != row->end(); ++it) {
    ColumnMap *tmp = other -> rlist[*it.*column];
    ColumnMapIter it_col = tmp -> find(col);
    if (it_col != tmp->end()) {
        val += (*it.*value) * (*it_col.*value);
    }
}

занятненький подкаст

Рыская по Википедии, случайно наткнулся на skepticality.com. На данный момент это официальный подкаст журнала "Skeptic", выпускаемого организацией "The Skeptics Society".

Сейчас на сайте выложено 160+ выпусков на самые разнообразные темы. Между прочим, каждый из них снабжён пачкой ссылок для заинтересовавшихся затронутыми в нём топиками.
Короче, рекомендую всем желающим объективно воспринимать реальность :-)

[oh shi~] теория музыки

Интересующимся сабжем советую погуглить "music theory Z/12Z". Можно найти довольно убойную муть.

Вот, например, с моноидами аффинных отображений, их генераторами и тому подобным:
www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/FINALFULL/Bartlett.pdf

[жж] ностальгия

Знаете что? Хочу, чтоб интернет был таким, как 5 лет назад.

Во-первых, сегодня он таков, что знакомиться с кем-либо по сети совершенно не хочется. Раньше на момент начала общения о собеседнике было неизвестно ничего, кроме его ника и, быть может, аватарки, пары фотографий да истории сообщений на форуме. Сейчас же почти каждый зарегистрирован "вконтакте". И хрен бы с ним, если бы просто зарегистрирован — с некоторых пор какого-то чёрта всё это проиндексировано поисковиками и даже регистрации не нужно, чтобы узнать инфу о человеке: загуглил имя, фамилию и ещё что-нибудь — вот тебе и фотка, и интересы, и откуда родом, и где учится (ну, разумеется, если параноиков типа меня в расчёт не брать). А теперь вот ещё и френдлисты открыли. Это вообще, на мой взгляд, диковато: "скажи мне, кто твои друзья, и я скажу, кто ты". (Правда, концентрация истинных друзей там колеблется от 5 до 50 процентов в зависимости от политики френдования. Но общее представление всё же заиметь можно.) В итоге теряется весь интерес: ведь блин, вся суть знакомства в _постепенности_ раскрытия одной личности перед другой. А со всеми этими грёбаными социальными сетями можно безо всякого знакомства сделать вывод о том, что человек — кусок идиота (причём вывод вполне может оказаться неправильным); заранее узнать о наличии общих знакомых, вкусах в плане музыки и кино; о том, куда субъект ездил отдыхать этим летом и так далее. Ну что за скукота?

Во-вторых, в техническом аспекте тоже творится кошмар: как подумаешь, что весь трафик этого идиотского "вконтактика" идёт по голому HTTP безо всяких SSL — жуть берёт. Средневековье какое-то. А ведь у FaceBook HTTPS-доступ есть, между прочим. Но у нас-то Россия: как обычно, отстаём в техническом плане. И почти всем пофиг — народ и аббревиатуры "HTTP" в большинстве своём не слышал. А уж криптографические протоколы — так это и вовсе какая-то неведомая ёбаная хуйня, кому оно надо?
И, блеать, не думайте, что это всё чисто теория. Вот, нате вам видео, как чел снифать кукисы в public Wi-Fi сети: http://www.youtube.com/watch?v=jsFODcwiRFY

Так что IRC/ICQ во всех отношениях лучше были. А ещё Jabber и Skype есть... Но народ же не осилит. Да и надо же куда-то выкладывать в большинстве своём бездарные фоточки и псевдоумные цитаты, чтоб их кто-нибудь "лайкнул", подняв ЧСВ автору. Буэээээ...

Ruby, 64-bit, Bignum и все-все-все

Итак, свершилось! Переехал я на 64 бита, благо Intel Atom N450 их поддерживает. Вроде как всё летает просто: ещё бы, целых 8 новых регистров задействуются! Библиотеки для длинной арифметики, как и полагается, ускорились в два раза.

Ну так вот, попытался я и интерпретатор Ruby на 64 бита пересадить. Точнее, его Bignum-ы. По умолчанию никакой поддержки 64-битовых целых в качестве digit-ов почему-то не предусмотрено. «Ну фиг ли», — решил я, «тоже мне проблема», — добавил в include/ruby/defines.h несколько строчек и пересобрал:

#if defined(__x86_64__)
# define BDIGIT unsigned long
# define SIZEOF_BDIGITS SIZEOF_LONG
# define BDIGIT_DBL __uint128_t
# define BDIGIT_DBL_SIGNED __int128_t
# define PRI_BDIGIT_PREFIX ""
# define PRI_BDIGIT_DBL_PREFIX ""
#elif ...

Ну ладно, даже собралось. Правда, по поводу random.c в процессе появилось несколько варнингов — деление на ноль, например :-))) Хрень в том, что там есть такая строчка:

#define DIGSPERINT (SIZEOF_INT/SIZEOF_BDIGITS)

Почему-то предполагается, что эта шняга всегда не меньше единицы, и на неё спокойно делят. Только вот в нашем случае 4 / 8 = 0, хыхых. Надо будет поковырять rb_rand_dump и rb_rand_load.
Впрочем, с генерацией псевдорандомных длинных чисел разобраться удалось (функция limited_big_rand):

...
#elif SIZEOF_BDIGITS == 4     
# define BIG_GET32(big,i) (RBIGNUM_DIGITS(big)[(i)])
# define BIG_SET32(big,i,d) (RBIGNUM_DIGITS(big)[(i)] = (d))
#else  
    /* SIZEOF_BDIGITS == 8 */ 
# define BIG_GET32(big,i) \   
    ((i) & 1 ? \              
     RBIGNUM_DIGITS(big)[(i)>>1] >> 32 : \
     RBIGNUM_DIGITS(big)[(i)>>1] & 0xffffffff )
# define BIG_SET32(big,i,d) \ 
    do { \
        if ((i) & 1) \        
        RBIGNUM_DIGITS(big)[(i)>>1] = \
        ((d) << 32) + (RBIGNUM_DIGITS(big)[(i)>>1] & 0xffffffff); \
        else \
        RBIGNUM_DIGITS(big)[(i)>>1] &= 0xffffffff00000000ULL, \
        RBIGNUM_DIGITS(big)[(i)>>1] += (d); \
    } while(0);               
#endif 

Был и ещё один глюк: строки в числа преобразовывались верно, а вот наоборот — нифига. Чтобы пофиксить, добавил в функции rb_big2str0 (bignum.c) строки

#if SIZEOF_BDIGITS > 4
    hbase *= hbase;
#endif

сразу после такого же сравнения с двойкой.

Пришлось также вручную подправить значение BASE в ext/bigdecimal/bigdecimal.h: в противном случае возникало переполнение. BASE должно равняться 10**9, а не 10**19. Было следующее:

...
#elif SIZEOF_BDIGITS >= 8
# define RMPD_COMPONENT_FIGURES 19
# define RMPD_BASE ((BDIGIT)10000000000000000000U)
#elif SIZEOF_BDIGITS >= 4
# define RMPD_COMPONENT_FIGURES 9
# define RMPD_BASE ((BDIGIT)1000000000U)
#elif ...

Вообще говоря, эта хрень только в trunk-е появилась, и здравая логика подсказывает, что во избежание переполнения здесь везде надо '>=' заменить на '>'. (По крайней мере, в старых стабильных версиях на 32-битных машинах BASE было равно 10000).

Ну по крайней мере арифметические операции, ради которых всё затевалось, вроде работают. И скорость числодробления действительно круто возросла: взять хотя бы тот же 1000000! — одна и та же версия ruby с 32-битными digit-ами считает его за 57 секунд, а с 64-битными — всего за 19. Жесть. То бишь действительно удвоение скорости засчёт бóльшей разрядности + дополнительный прирост засчёт использования полного набора регистров (по крайней мере мне кажется, что это основные факторы).

охренительно

Ради любопытства слил сегодня свежий ruby из trunk-а, скомпилял. С удивлением обнаружил, что в 1.9.3dev (rev. 31825) наконец-то заимплементили Тоом-Кука! Не FFT, конечно, но всё же прогресс налицо. (Написать, что ли, летом Шёнхаге-Штрассена? — за два месяца можно управиться =)...)
Произошёл сий коммит, кстати говоря, совсем недавно — 22 мая (rev. 31695).
Да и в целом скорость повыше, чем у 1.9.2-p336, на котором я сидел до этого.
Так что надо почаще обновляться, пожалуй =)

Но охренительно не только это. Есть такая замечательная вещь, как Intel Vtune Amplifier — вроде как самый ништяковый профайлер на сегодняшний день (по крайней мере, для Intel-овских процессоров). Цены на лицензионный продукт просто зверские (900$). Но если побродить по сайту, ВНЕЗАПНО оказывается, что "developers who are developing software on their own time without compensation" могут скачать некоммерческую версию вообще на халяву! (правда, есть один нюанс: только для linux; причём у меня установка превратилась в долгое ковыряние с компиляцией их драйверов; впрочем, для убунты вроде поставляется с уже скомпилированными дровами).

Ну и про ещё одну забавную штуку напишу, коль скоро она соответствует заголовку: оказывается, есть гомеоморфный тору семигранник, у которого каждая грань соседствует со всеми остальными. У кого руки чешутся — можете даже склеить, там внизу есть ссылочка на pdf с развёрткой. Получите конструктивную (в наибуквальнейшем смысле :-)) оценку снизу хроматического числа тора.

О вычислении факториала: часть 2

Когда-то я писал о наиболее продвинутом на сегодняшний день методе вычисления факториала. Сегодня, читая Википедию, наткнулся и на ссылку с оценкой сложности этого метода: держите.

Статью (пока что) не читал. Результат, который там приводится, таков:
временная сложность составляет , где — временная сложность перемножения двух чисел длины .
(Для сравнения: в случае разбиения произведения на два произведения примерно равной длины сложность отличается тем, что вместо log(log(n)) в формуле стоит просто log(n). В случае же тупого перемножения последовательных чисел сложность равна O(n² log n).)

Таким образом, в случае использования метода Шёнхаге-Штрассена сложность —

В случае же использования метода Карацубы, для которого , сложность, соответственно, —

Даже проверил из любопытства: (кривая - график f(N) = 1.532e-10 * (N log N)^log₂3 * log log N)

Release of ruby-numtheory 0.0.3

First, I'd like to say a few words about the history of the project.
Right after I switched to Ruby with respect to solving ProjectEuler.net problems, I realized that there's actually no number-theoretical Ruby libraries at all. Of course, I could just turn to some more advanced tools like PARI-GP or switch to, say, Python which has nzmath library. But: 1) I love Ruby. 2) Number-theoretical algorithms are themselves useful to know and understand for I'm sorta mathematician ;-)
Thus I decided to write my own library. And now, I suppose, it even might be useful for somebody else.

Well, what has been implemented so far?

• Eratosphenes sieve
• Factorization by trial division.
• Common multiplicative functions: moebius, sigma, phi, pi.
• Jacobi symbol
• Powermod (works with negative powers also whenever the inverse exists)
• N-th fibonacci number
• Fast factorial computation by PrimeSwing algorithm
• Multiplicative order
• Miller-Rabin primality test

The gem is at rubygems.org/gems/ruby-numtheory; Thanks to the existence of rake-compiler, precompiled version for Windows is also available. 

The features to be implemented in the near future are some more primality tests (I hope I will eventually understand AKS), and roots modulo n (at least Tonelli-Shanks algorithm). Maybe, something else.

немного об Asymptote

Как-то раз на лекции И. Романовский нахваливал нам MetaPost. Штука эта, безусловно, крута. Только вот есть у неё один существенный недостаток: при редком использовании самобытный синтаксис языка напрочь забывается (сужу по себе).

Однако существует не менее хороший язык Asymptote, созданный под влиянием MetaPost. Появился он в 2004 году (то бишь где-то вчера утром по меркам старика Романовского) и обладает C++-подобным синтаксисом. Даже Java-подобным, я б сказал.

Например, нарисуем фигурную скобку:

ненависти пост

Решил тут от скуки на kinopoisk.ru зарегаццо. Уже при заполнении профиля задолбался. Программистам сего сайта надо руки отрывать нахрен.

Поле "блог" — ссылка обязательно должна с 'http://' начинаться. А что, блджад, есть блоги, на ftp расположенные?
Аватар — только файлы с расширением jpg/jpeg. Итить-колотить, неужели трудно на сервере в нужный формат конвертировать? С хера ли пользователь должен этим заниматься? Ну ладно, конвертнул. И только при загрузке сервер ответил, что высота должна быть не менее 190 пикселов (и это они «аватаром» называют?). Твою мать, вот почему про то, что надо грузить файл в JPG не более 2МБ, возле кнопки написано, а про минимальный размер — ни слова?

Ну их нахер, короче. Среди российских сайтов КиноБаза рулит и педалит.

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

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

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

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

---

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

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

Сегодня информатик на лекции заявил, что следует писать не 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 с этим норма а хотя не, фтопку делфи ^_^)

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

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

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

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

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

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

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

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

наконец-то

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

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

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.

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

Так вот, в 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) — что-то иное.

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

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

Как найти 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! нам часа два ждать придётся...

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

Чтобы сделать длины перемножаемых чисел примерно равными, поступим следующим образом. Заметим, что


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

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 с небольшим минуты.
Этот алгоритм можно ещё немножко ускорить, если заметить, что
, т.е. 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

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

О несобственных интегралах

Вообще говоря, на английском их называют improper integrals. "Proper" имеет два основных значения: "надлежащий/правильный" (как в "do your job properly") и "собственный" (например, "proper noun" — "имя собственное").

Так что переводчик, похоже, тем ещё кретином был. Это ж надо было совсем нихрена не шарить в математике, чтобы выбрать такой перевод =\
(Если кому-то такие "аргументы" кажутся неубедительными, можете узнать из Википедии, что, например, на нидерландском понятие звучит как "Oneigenlijke", на польском — "niewłaściwa", что google translate переводит как "ненадлежащий" и "неуместный" соответственно. Невменяемо термин переводится, видимо, только в России и Украине.)

Ну да ладно, хотя бы дроби в нашем языке "правильные" и "неправильные", и то хорошо =)

смайлокод

int main(){
    int _ = 0;
    1 ^_^ 2 ^_- 3 -_- 4 -_^ 5 *_* 6 <_< 7;
    return _;
}

кругозорорасширение

Оказывается, есть ряд сайтов, на которых можно "вживую" пощупать различные языки программирования, следуя пошаговым туториалам. То бишь javascript-ом эмулируется интерактивная консоль. Естественно, всё in english only.

tryruby.org  (только вот поддержка браузеров там так себе)
tryhaskell.org
tryerlang.org
try-clojure.org (недоделан, но какое-никакое представление о языке даёт)
trypython.org (требует Silverlight (якого у мене нема, так что не затестил))

Ruby: наследие Smalltalk

I always knew that one day Smalltalk would replace Java.
I just didn't know it would be called Ruby.
 —Kent Beck

Если совсем вкратце, суть языка Smalltalk состоит в том, что:

1. всё, что ни есть — объект, числа и строки в том числе;
2. объектам можно посылать произвольные сообщения, а уж что эти объекты будут с ними делать — на их усмотрение. Сообщение, как нетрудно догадаться, — тоже объект.

Ruby, появившийся на полтора десятка лет позже, включил в себя обе эти черты. У всех объектов есть метод send:

-5.send :abs => 5
51.send :gcd, 34 => 17
7.send :send, :+, 24 => 33

Сообщение — это объект класса Symbol; в коде он начинается с двоеточия. В качестве аргументов send посылаются сообщение и необходимые аргументы. Заметьте, что в последнем примере отсылается сам :send, и, вообще говоря, цепочка :send-ов перед параметрами может быть любой длины :-)

Однако как эти свойства можно применить на практике?