Хана пришла этому блогу.

И вот почему. Всякую мелкую бытовуху гораздо приятней обсуждать с френдами, чем выкладывать её в бложик, который всё равно никто не комментирует (хотя кто-то читает-таки вроде бы). IT-related посты куда разумней писать на английском, что, я собственно, и намереваюсь делать на lomereiter.wordpress.com, где пока что в основном сугубо GSoC weekly reports обитают. Что касается всяческих идей, я теперь стал на ε умнее и буду их, пожалуй, копить в голове, изыскивая пути их когда-нибудь монетизировать. Ибо нехер разбрасываться такими вещами.
(Мешанина из русского и английского тоже выглядит крайне убого. Небось отпугивает англоязычных читателей, хотя хз, не осведомлялся. Вообще, всё больше склоняюсь к мнению, что русский язык нахрен не нужен, и более того, было бы неплохо выкинуть все языки, кроме одного, на свалку истории, кому надо — пусть изучают just for fun. Мне даже похрен, английский или китайский останется — просто дико неудобно все эти языковые барьеры преодолевать, сколько ж можно уже, в век транснациональных корпораций-то?..)

Такие дела.

унылая бабка

Пошёл я тут, понимаешь, накануне отъезда в прачечную скармливать тупому баблоприёмнику мелочь в виде 1-2-5-10-рублёвых монеток, скопившуюся за полгода. И тут хренакс - бабка, которая всей их хренью заведует, чё-то бурчать начала, типа "вот вы все сцуки, уже который по счёту такой, а я вот каждый день всю вашу мелочь в магазин отношу... а вы тут ещё смеётесь... я вас запооомню... ууу". Я даже как-то проникся её тяжкой судьбой и отошёл от изначального плана, вместо 49 монеток всего 36 закинул. Такие дела. Придётся какому-нибудь кофейному автомату на вокзале теперь монетки скармливать. Ну не в магазин же идти, правда?

Но вообще между теми же кофейными автоматами и тупым баблоприёмником из местной прачечной есть одно существенное различие. Последний я неспроста называю тупым: эта мразь не выдаёт сдачи. Так что бабку даже, наверное, можно понять :))) Но с другой стороны она ж каждый день тазы со шмотками с места на место таскает, ну что ей стоит несколько килограммов мелочи до магазина дотащить?) (Хотя в худшем случае, т.е. при обслуживании сотни человек в сутки и если каждый закидывает около 150 рублей рублёвыми монетами, по моим прикидкам где-то 50 килограммов выходит. Но такой адский флэшмоб представить трудно :D (хмм... а чо, п*здатая идея, кстати))

[гугл] ололо

Приехали, блджад. Вот что мне Google AdSense в почте щас отобразил:

Russian Language Courses

Learn Russian at Educacentre! 20 years of teaching experience.

www.educacentre.ru

Это гуглу надо учиться русскому, а то их сраный translate порой ухитряется смысл предложений искажать с точностью до наоборот при переводе с русского на английский.
Да и ваще гугл -- трэш. Этот свой Drive вот кинули на рынок без поддержки linux, гниды.
(Наверно, странно это всё писать из chromium через blogger.com, да. Ну а хули, работает же, и хрен с ним.)

[бред] порядок вежливости

А я вот тут намедни придумал способ количественного измерения вежливости. Правда, пока что только дискретно, так что назовём это порядком вежливости PV : человеки -> натуральный ряд (начиная с нуля)

Итак, пусть мы хотим измерить PV(Вася). Познакомим Васю с неким, допустим, Петей, который скажет Васе, что никогда не обижается, а потом в один прекрасный момент... ну, например, сделает как-нибудь так, чтобы Вася за него запнулся. Если PV(Вася) > 0, Вася извинится за то, что запнулся. А если больше 1, то извинится за то, что забыл, что Петя не обижается. Ну и так далее, так что PV(Вася) будет равняться глубине рекурсии.

Возникает естественный вопрос: а можно ли это дело как-то на всю вещественную ось продолжить, по типу факториала и гамма-функции? Наверное, можно что-нибудь изощрённое придумать. Скажем, если бы были средства для удаления памяти Васи за последние N дней, эксперимент можно было бы повторить дофига раз и взять среднее. Или взвешенное среднее. Или ещё что-нибудь, неважно... %-)

о почте россии

...а знаете, это как-то неправильно, что надо физический адрес адресата указывать. Хотя кто-то, наверное, скажет — эй, ну он же адресат, хрен ли тебе не нравится?
А вот не нравится, блджад! С хрена ли адрес обязан быть физическим? Может, я хочу послать человеку анонимусу открытку и при этом не знаю его адреса и знать не хочу, потому что уважаю его анонимность. А?! А вот если бы анонимус мог зайти на сайт российской почты, получить там uuid, который на протяжении им определённого времени будет оной службою маппиться в его физический адрес, а потом сообщить сий uuid мне для использования... Эх, мечты, мечты... :(

A few words about xmlCleanupParser

Today I wrote an application which uses both libxml2 and GStreamer. It crashed for some mysterious reason which turned out to be xmlCleanupParser called twice. Damn it, it turns out that the only reason for that function to exist is getting rid of valgrind messages!

This frees up a few global variables allocated by libxml2. A few
kilobytes at most, but if they get deallocated while somehow the library
is still in use, the application is very likely to crash.
  So never call this in a library.
  In an app the only safe place to call it is close to the exit
It's still useful to make sure there is no memory leak when running a
program under valgrind or equivalent memory checker.

(http://mail.gnome.org/archives/xml/2011-April/msg00048.html)

Cool, huh?!

I think it's worthwhile to emphasize the thought:

NEVER EVER FUCKING CALL xmlCleanupParser() IN A LIBRARY!

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

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

#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.