5.14. Простые числа
В библиотеке mathn есть класс для порождения простых чисел. Итератор each возвращает последовательные простые числа в бесконечном цикле. Метод succ порождает следующее простое число. Вот, например, два способа получить первые 100 простых чисел:
require 'mathn'
list = []
gen = Prime.new
gen.each do |prime|
list << prime
break if list.size == 100
end
# или:
list = []
gen = Prime.new
100.times { list << gen.succ }
В следующем фрагменте проверяется, является ли данное число простым. Отметим, что если число велико, а машина медленная, то на выполнение может уйти заметное время:
require 'mathn'
class Integer
def prime?
max = Math.sqrt(self).ceil
max -= 1 if max % 2 == 0
pgen = Prime.new
pgen.each do |factor|
return false if self % factor == 0
return true if factor > max
end
end
end
31.prime? # true
237.prime? # false
1500450271.prime? # true
5.15. Явные и неявные преобразования чисел
Программисты, только начинающие изучать Ruby, часто удивляются, зачем нужны два метода to_i и to_int (и аналогичные им to_f и to_flt). В общем случае метод с коротким именем применяется для явных преобразований, а метод с длинным именем - для неявных.
Что это означает? Во-первых, в большинстве классов определены явные конверторы, но нет неявных. Насколько мне известно, методы to_int и to_flt не определены ни в одном из системных классов.
Во-вторых, в своих собственных классах вы, скорее всего, будете определять неявные конверторы, но не станете вызывать их вручную (если только не заняты написанием "клиентского" кода или библиотеки, которая пытается не конфликтовать с внешним миром).
Следующий пример, конечно, надуманный. В нем определен класс MyClass, который возвращает константы из методов to_i и to_int. Такое поведение лишено смысла, зато иллюстрирует идею:
class MyClass
def to_i
3
end
def to_int
5
end
end
Желая явно преобразовать объект класса MyClass в целое число, мы вызовем метод to_i:
m = MyClass.new x = m.to_i # 3
Но при передаче объекта MyClass какой-нибудь функции, ожидающей целое число, будет неявно вызван метод to_int. Предположим, к примеру, что мы хотим создать массив с известным начальным числом элементов. Метод Array.new может принять целое, но что если вместо этого ему будет передан объект MyClass?
m = MyClass.new
a = Array.new(m) # [nil,nil,nil,nil,nil]
Как видите, метод new оказался достаточно "умным", чтобы вызвать to_int и затем создать массив из пяти элементов.
Дополнительную информацию о поведении в другом контексте (строковом) вы найдете в разделе 2.16. См. также раздел 5.16.
5.16. Приведение числовых значений
Приведение можно считать еще одним видом неявного преобразования. Если некоторому методу (например, +) передается аргумент, которого он не понимает, он пытается привести объект, от имени которого вызван, и аргумент к совместимым типам, а затем сложить их. Принцип использования метода coerce в вашем собственном классе понятен из следующего примера:
class MyNumberSystem
def +(other)
if other.kind_of?(MyNumberSystem)
result = some_calculation_between_self_and_other
MyNumberSystem.new(result)
else
n1, n2 = other.coerce(self)
n1 + n2
end
end
end
Метод coerce возвращает массив из двух элементов, содержащий аргумент и вызывающий объект, приведенные к совместимым типам.
В данном примере мы полагаемся на то, что приведение выполнит тип аргумента. Но если мы хотим быть законопослушными гражданами, то должны реализовать приведение в своем классе, сделав его пригодным для работы с другими типами чисел. Для этого нужно знать, с какими типами мы в состоянии работать непосредственно, и при необходимости выполнять приведение к одному из этих типов. Если мы не можем сделать это самостоятельно, то должны обратиться за помощью к родительскому классу.
def coerce(other)
if other.kind_of?(Float)
return other, self.to_f
elsif other.kind_of?(Integer)
return other, self.to_i
else
super
end
end
Разумеется, это будет работать только, если наш объект реализует методы to_i и to_f.
Метод coerce можно применить для реализации автоматического преобразования строк в числа, как в языке Perl:
class String
def coerce(n)
if self['.']
[n, Float(self)]
else
[n, Integer(self)]
end
end
end
x = 1 + "23" # 24
y = 23 * "1.23" # 28.29
Мы не настаиваем на таком решении. Но рекомендуем реализовывать coerce при создании любого класса для работы с числовыми данными.
5.17. Поразрядные операции над числами
Иногда требуется работать с двоичным представлением объекта Fixnum. На прикладном уровне такая необходимость возникает нечасто, но все-таки возникает.
Ruby обладает всеми средствами для таких операций. Для удобства числовые константы можно записывать в двоичном, восьмеричном или шестнадцатеричном виде. Поразрядным операциям И, ИЛИ, ИСКЛЮЧАЮЩЕЕ ИЛИ и НЕ соответствуют операторы &, |, ^ и ~.
x = 0377 # Восьмеричное (десятичное 255)
y = 0b00100110 # Двоичное (десятичное 38)
z = 0xBEEF # Шестнадцатеричное (десятичное 48879)
а = x | z # 48895 (поразрядное ИЛИ)
b = x & z # 239 (поразрядное И)
с = x ^ z # 48656 (поразрядное ИСКЛЮЧАЮЩЕЕ ИЛИ)
d = ~ y # -39 (отрицание или дополнение до 1)
Метод экземпляра size позволяет узнать размер слова для той машины, на которой исполняется программа.
size # Для конкретной машины возвращает 4.
Имеются операторы сдвига влево и вправо (<< и >>соответственно). Это логические операторы сдвига, они не затрагивают знаковый бит (хотя оператор >> распространяет его).
x = 8
y = -8
а = x >> 2 # 2
b = y >> 2 # -2
с = x << 2 # 32
d = y << 2 # -32
Конечно, если сдвиг настолько велик, что дает нулевое значение, то знаковый бит теряется, поскольку -0 и 0 - одно и то же.
Квадратные скобки позволяют трактовать числа как битовые массивы. Бит с номером 0 всегда является младшим, вне зависимости от порядка битов в конкретной машинной архитектуре.
x = 5 # То же, что 0b0101
а = x[0] # 1
b = x[1] # 0
с = x[2] # 1
d = x[3] # 0
# И так далее # 0
Присваивать новые значения отдельным битам с помощью такой нотации невозможно (поскольку Fixnum хранится как непосредственное значение, а не как ссылка на объект). Но можно имитировать это действие путем сдвига 1 влево на нужное число позиций с последующим выполнением операции ИЛИ или И.
# Выполнить присваивание x[3] = 1 нельзя,
# но можно поступить так:
x |= (1<<3)
# Выполнить присваивание x[4] = 0 нельзя,
# но можно поступить так:
x &= ~(1<<4)
5.18. Преобразование системы счисления
Ясно, что любое целое число можно представить в любой системе счисления, поскольку хранятся эти числа в двоичном виде. Мы знаем, что Ruby умеет работать c целыми константами, записанными в любой из четырех наиболее популярных систем. Следовательно, разговор о преобразовании системы счисления может вестись только применительно к числам, записанным в виде строк.
Вопрос о преобразовании строки в целое рассмотрен в разделе 2.24. Для преобразования числа в строку проще всего воспользоваться методом to_s, которому можно еще передать основание системы счисления. По умолчанию оно равно 10, но в принципе может быть любым вплоть до 36 (когда задействованы все буквы латинского алфавита).
237.to_s(2) # "11101101"
237.to_s(5) # "1422"
237.to_s(8) # "355"
237.to_s # "237"
237.to_s(16) # "ed"
237.to_s(30) # "7r"
Другой способ - обратиться к методу % класса String:
hex = "%x" % 1234 # "4d2"
oct = "%о" % 1234 # "2322"
bin = "%b" % 1234 # "10011010010"
Метод sprintf тоже годится:
str = sprintf(str,"Nietzsche is %x\n",57005)
# str теперь равно: "Nietzsche is dead\n"
Если нужно сразу же вывести преобразованное в строку значение, то подойдет и метод printf.
5.19. Извлечение кубических корней, корней четвертой степени и т.д.
В Ruby встроена функция извлечения квадратного корня (Math.sqrt), поскольку именно она применяется чаще всего. А если надо извлечь корень более высокой степени? Если вы еще не забыли математику, то эта задача не вызовет затруднений.
Можно, например, воспользоваться логарифмами. Напомним, что е в степени x - обратная функция к натуральному логарифму x и что умножение чисел эквивалентно сложению их логарифмов.
x = 531441
cuberoot = Math.exp(Math.log(x)/3.0) # 81.0
fourthroot = Math.exp(Math.log(x)/4.0) # 27.0
Но можно просто использовать дробные показатели степени (оператор возведения в степень принимает в качестве аргумента произвольное целое число или число с плавающей точкой).
include Math
y = 4096
cuberoot = y**(1.0/3.0) # 16.0
fourthroot = y**(1.0/4.0) # 8.0
fourthroot = sqrt(sqrt(y)) # 8.0 (то же самое)
twelfthroot = y**(1.0/12.0) # 2.0
Отметим, что во всех примерах мы пользовались при делении числами с плавающей точкой (чтобы избежать отбрасывания дробной части).
5.20. Определение порядка байтов
Интересно, что производители компьютеров никак не могут договориться, в каком порядке лучше хранить двоичные байты. Следует ли размещать старший бит по большему или по меньшему адресу? При передаче сообщения по проводам нужно сначала посылать старший или младший бит?
Хотите верьте, хотите нет, но решение не произвольно. Существуют убедительные аргументы в пользу обеих точек зрения (обсуждать их здесь мы не будем).
Вот уже больше двадцати лет, как для описания противоположных позиций применяются термины "остроконечный" (little-endian) и "тупоконечный" (big-endian). Кажется, впервые их употребил Дэнни Коэн (Danny Cohen); см. его классическую статью "On Holy Wars and a Plea for Peace" (IEEE Computer, October 1981). Взяты они из романа Джонатана Свифта "Путешествия Гулливера".
Обычно нам безразличен порядок байтов в конкретной машинной архитектуре. Но как быть, если все-таки его нужно знать?
Можно воспользоваться показанным ниже методом. Он возвращает одну из строк LITTLE, BIG или OTHER. Решение основано на том факте, что директива l выполняет упаковку в машинном формате, а директива N распаковывает в сетевом порядке байтов (по определению тупоконечном).
def endianness
num = 0x12345678
little = "78563412"
big = "12345678"
native = [num].pack('1')
netunpack = native.unpack('N')[0]
str = "%8x" % netunpack
case str
when little
"LITTLE"
when big
"BIG"
else
"OTHER"
end
end
puts endianness # В данном случае печатается "LITTLE"
Этот прием может оказаться удобным, если, например, вы работаете с двоичными данными (скажем, отсканированным изображением), импортированными из другой системы.
5.21. Численное вычисление определенного интеграла
Я очень хорошо владею дифференциальным и интегральным исчислением…
У.С.Джильберт, "Пираты Пензанса", акт 1
Для приближенного вычисления определенного интеграла имеется проверенная временем техника. Любой студент, изучавший математический анализ, вспомнит, что она называется суммой Римана.
Приведенный ниже метод integrate принимает начальное и конечное значения зависимой переменной, а также приращение. Четвертый параметр (который на самом деле параметром не является) - это блок. В блоке должно вычисляться значение функции от переданной в него зависимой переменной (здесь слово "переменная" употребляется в математическом, а не программистском смысле). Необязательно отдельно определять функцию, которая вызывается в блоке, но для ясности мы это сделаем.
def integrate(x0, x1, dx=(x1-x0)/1000.0)
x = x0
sum = 0
loop do
y = yield(x)
sum += dx * y
x += dx
break if x > x1
end
sum
end
def f(x)
x**2
end
z = integrate(0.0,5.0) {|x| f(x) }
puts z, "\n" # 41.7291875
Здесь мы опираемся на тот факт, что блок возвращает значение, которое может быть получено с помощью yield. Кроме того, сделаны некоторые допущения. Во-первых, мы предполагаем, что x0 меньше x1 (в противном случае получится бесконечный цикл). Читатель сам легко устранит подобные огрехи. Во-вторых, мы считаем, что функцию можно вычислить в любой точке заданной области. Если это не так, мы получим хаотическое поведение. (Впрочем, подобные функции все равно, как правило, не интегрируемы - по крайней мере, на указанном интервале. В качестве примера возьмите функцию f(x)=x/(x-3) в точке x=3.)
Призвав на помощь полузабытые знания об интегральном исчислении, мы могли бы вычислить, что в данном случае результат равен примерно 41.666 (5 в кубе, поделенное на 3). Почему же ответ не так точен, как хотелось бы? Из-за выбранного размера приращения; чем меньше величина dx, тем точнее результат (ценой увеличения времени вычисления).
Напоследок отметим, что подобная методика более полезна для действительно сложных функций, а не таких простых, как f(x) = x**2.