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. Жесть. То бишь действительно удвоение скорости засчёт бóльшей разрядности + дополнительный прирост засчёт использования полного набора регистров (по крайней мере мне кажется, что это основные факторы).

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.

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 строк кода.

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-ов перед параметрами может быть любой длины :-)

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

GPS & Ruby: dealing with performance bottlenecks

About a month ago, I posted about how to convert pure GPS data into Ruby class instances. But as it turned out this converting in general takes more time than processing the data.

For tests I've used 2.7MB .nmea file. It contains about 5 thousand GPRMC sentences from which about 3 thousand contain useful information.

The first version of readNMEA function takes about 0.87 seconds (on my Asus EeePC 1001P) to make an array of GPRMC class instances. How can we improve that?

Firstly, access to the elements of an array (by index) is faster than access to the elements of a hash (by key). Thus using old-style regular expressions decreases the time from 0.87 to 0.72 seconds:

GPS & Ruby: Introduction

This is the beginning of post series devoted to playing with data obtained by a GPS receiver. Here I assume that you are familiar with basic concepts of object-oriented programming and also assume that you don't know Ruby (honestly, neither do I, but that's gonna change eventually). So don't you worry, there will be a few comments about the code ;-)

In this post I'm gonna acquaint you with the NMEA format used in GPS receivers. Actually, you can read about that in details here, for example. In fact, it's a proprietary one but it's too old to not to be reverse-engineered :-)

We're gonna use just one type of NMEA sentence, namely GPRMC.

Need for s... tatistics.

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

Взять, скажем, сайт edu-43.kirov.ru.
Что доступно извне? Изображения с гистограммами, отображающими количество сдавших в каждой из школ (от 0 до 9 вкл., 10-19 и т.д.; 100-балльники занимают отдельный столбик).

Пример:


Чего хочется? Ну, например, список школ, в которых есть люди, написавшие от 80 до 100 баллов, м? Любопытно же, какие школы рулят в плане конкретного предмета.


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

100 points:
"940018"

90 and more points:
"860009, 940030, 940064"

80 and more points:
"520001, 530010, 550011, 550013, 560001, 570010, 590008, 590009, 600003, 610011, 630009, 640007, 660003, 660004, 670001, 670007, 670008, 690004, 710002, 720014, 740006, 770001, 810006, 840007, 850006, 850017, 870001, 870004, 880007, 880010, 900001, 900003, 910006, 910007, 910008, 920003, 930004, 930007, 940012, 940023, 940036, 940037, 940040, 940052, 940056, 940067, 940069, 940076, 940210"

Отталкиваясь от этого, можно и немного дальше проанализировать. Скажем, 940018 — это лицей №21, там учится некая Ксюша, которая на всерос по биологии ездила (между прочим, призёр), так что ежу понятно, у кого 100 баллов...


P.S.: что-то как-то сумбурненько получилось, ну да ладно))

libxml-ruby1.9.1 и Unicode

Вот почему

parser = XML::HTMLParser.string((IO.read 'page.html'),
:encoding => XML::Encoding::UTF_8)
doc = parser.parse
obj = doc.find('//tr/td/font[@color="#cc0000"]')
content = obj.first.content.force_encoding("UTF-8")
p content.index "не найден"

выводит 80, а если то же самое, только вместо первой строки — 

parser = XML::HTMLParser.file('page.html',
:encoding => XML::Encoding::UTF_8)

, выводит nil?

Переезд на Ruby 1.9.1

Вообще говоря, Ruby я увлёкся недавно — около месяца тому назад. Особенно меня философия Rails привлекла, да и сам язык довольно красив.

В процессе освоения 1.8, который идёт в Дебиане по умолчанию, столкнулся с пиздецом в виде строк, которые почему-то ведут себя тупо как последовательности байтов. После Питона (в котором, надо сказать, проблемы с Юникодом тоже были немалые) с этим ужасом работать невозможно.

Поэтому поставил ruby1.9.1. После этого попытался запустить Rails. (Естественно, поставил его gem-ом, чтоб поновее был.) 

Во-первых, пришлось вручную сделать ln -s /usr/bin/ruby1.9.1 /usr/bin/ruby и для rake точно так же, иначе неудобно работать.

Во-вторых, кучу библиотек за собой ruby1.9.1 почему-то не потянул. А зря: пришлось вручную потом apt-cache-м искать нужные пакеты (libopenssl-ruby1.9.1, ruby1.9.1-dev, libsqlite3-ruby1.9.1, libxml-ruby1.9.1, возможно, ещё какие-то понадобятся...)

В-третьих, старые проекты пришлось немного модифицировать. А именно, в config/environment.rb заменить версию рельсов, а также переименовать session_key в key; потом запустить rake rails:update (так надёжней, хотя возможно, что достаточно просто переименовать application.rb в application_controller.rb).

В-четвёртых, пришлось заюзать костыль: http://gist.github.com/339265

В-пятых, пришлось немножко подправить код из-за следующего:

Ruby 1.9 introduces an incompatible syntax change for conditional statements such as 'if' and 'case/when'. Previously a colon could be used as a shorthand for a 'then' statement