Метачисла

[Zer0Galaxy 2 187]

Попробуйте угадать, что будет выведено на экран в результате выполнения нижеприведенного кода:

N=1e16
if N+1 > N then print("Норма")
           else print("Лажа")
end

Если вы твердо уверены, что N+1 заведомо больше N и ваш ответ "Норма", то вы, наверное, будете несколько удивлены, когда выполните этот код на компьютере.

Дело в том, что Луа хранит числовые значения в формате с плавающей запятой. Это означает, что каким бы большим число ни было, оно всегда занимает в памяти компьютера одинаковое место, а значит, чем больше число, тем меньше точность, с какой оно хранится. И при достаточно большом N точности, что бы увеличить его на единицу оказывается недостаточно.

Избежать подобной проблемы поможет тип данных, который я назвал "Метачисла". На самом деле метачисла являются луа-таблицами, но большинство арифметических операций с ними можно проводить также как и с обычными числами. С той лишь разницей, что размер памяти, занимаемой метачислом, ограничивается только памятью компьютера, а значит, метачисло может принимать сколь угодно большие значения, не теряя при этом точности.

 

Метачисло может быть создано при помощи библиотеки metanum

pastebin get PsMFQame lib/metanum.lua

Библиотека содержит единственную функцию – функцию создания метачисла.

metanum([num[,divprec]])

Параметр num определяет начальное значение метачисла и может быть обычным числом, строкой или другим метачислом. Если параметр отсутствует, будет создано метачисло равное нулю.

Параметр divprec ограничивает точность метачисла при выполнении операции деления. При делении некоторых чисел, скажем 1 на 3, может возникнуть бесконечная дробь, которая без такого ограничения заняла бы всю память компьютера. Чем больше divprec, тем больше значащих цифр может содержать метачисло. По умолчанию это число равняется 32.

 

Мета числа можно складывать, вычитать, умножать и делить, как между собой, так и с обычными числами. Результатом такой операции всегда будет метачисло.

Метачисла можно возводить в степень, но степенью должно быть обычное число.

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

 

Пример нахождения факториала 300:

mn=require("metanum") –- подключаем библиотеку
f=mn(1)               -- создаем метачисло, равное 1
for i=1,300 do
  f=f*i               -- выполняем умножение 300 раз
end
print(f)              -- выводим результат

Пример нахождения степени двойки:

mn=require("metanum") –- подключаем библиотеку
two=mn(2)             -- создаем метачисло, равное 2
print(two^1024)       -- возводим в степень и выводим результат

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

Но, к сожалению, над метачислами не могут быть выполнены функции библиотеки math. Однако, метачисла обладают некоторыми собственными функциями. К примеру, если мы имеем некое метачисло М, над ним можно выполнить такие действия:

M:tonumber() – преобразует метачисло в число. Внимание! Возможна потеря точности.
M:floor([n]) – возвращает целую часть метачисла. Если задан параметр n, отсекает, оставляя n знаков после запятой.
M:abs() – возвращает абсолютное значение (модуль) метачисла.
M:toexp() – преобразует метачисло к экспоненциальному виду.

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

Изменено 26 мая, 2016 пользователем Zer0Galaxy

[Syabro 81]

Как сравнивать числа?

[Zer0Galaxy Автор темы 2 187]

Как сравнивать числа?

mn=require("metanum")
A=mn(2)
B=mn(1)
if A>B then print("2>1")
       else print("1>2")
end

При необходимости сравнить метачисло с числом, приводим их к одному типу. Например, так:

A=mn(2)
B=1
if A:tonumber()>B then -- Приводим метачисло к числу

или так:

A=mn(2)
B=1
if A>mn(B) then -- Приводим число к метачислу

[Fingercomp 4 409]

Для моего наполеонского проекта (который, к слову, уже на ¾ готов) потребовалась данная библиотека, так как необходимо было хранить действительно большие числа (1357 байт в длину). Проблема только в том, что проект этот очень активно использует побитовые операции из Lua 5.3: >>, <<, |, ~ (и XOR, и BNOT), &. Прошу как-нибудь сделать метаметоды и для этих операций.

 

К слову, библиотека теперь доступна для скачивания через OPPM: oppm install libmetanum.

[Zer0Galaxy Автор темы 2 187]

На сколько я знаю, битовые операции в Луа реализуются при помощи библиотеки bit, а не встроенными методами. Поэтому метаметоды тут не прокатят. Нужно либо перекрывать методы библиотеки либо писать свои функции. Какой из вариантов более приемлем?

[Fingercomp 4 409]

В Lua 5.3 есть побитовые операторы, и для каждой имеются метаметоды:

• __shl — <<, побитовый сдвиг влево.
• __shr — >>, побитовый сдвиг вправо.
• __bnot — ~ (унарный), побитовая инверсия.
• __bxor — ~ (бинарный), исключающее ИЛИ.
• __bor — |, побитовое ИЛИ.
• __band — &, побитовое И.
• Ну и ещё есть __idiv — //, деление нацело, без дробной части.

[eu_tomat 2 154]

В OpenOS используется Lua5.2. Там даже \lib\bit32.lua служит лишь для обратной совместимости с Lua5.3, внесение изменений в этот файл не дает никакого эффекта.

[Fingercomp 4 409]

Шифт-кликни процессор. Магическим образом получается "В OpenOS используется Lua5.3. Там даже /lib/bit32.lua служит лишь для обратной совместимости с Lua5.2, внесение изменений в этот файл даёт некоторый эффект".

[eu_tomat 2 154]

Шифт-кликни процессор. Магическим образом получается "В OpenOS используется Lua5.3. Там даже /lib/bit32.lua служит лишь для обратной совместимости с Lua5.2, внесение изменений в этот файл даёт некоторый эффект".

Осилил магию методом тыка. Оказалось, нужно сделать ШПКМ, держа процессор в руке. Изменено 29 июля, 2016 пользователем eu_tomat

[Fingercomp 4 409]

Два раза шифткликнуть? Три? Попробуй покликать. Должен смениться. Тултип явно говорит, что сменить можно, и версия не древняя годовой давности. В чат ещё должно писаться.

[Zer0Galaxy Автор темы 2 187]

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

[eu_tomat 2 154]

Подумайте как их реализовать наиболее эффективным способом, если метачисло хранит свою мантису в виде строки.

@@Zer0Galaxy, а мантисса обязательно должна храниться в десятичном виде?

@@Fingercomp, а насколько критично быстродействие в твоем проекте?

 

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

[LeshaInc 625]

@@Zer0Galaxy, а мантисса обязательно должна храниться в десятичном виде?@@Fingercomp, а насколько критично быстродействие в твоем проекте?Если оба ответа «да», то придется написать другую библиотеку. Иначе потребуется как минимум одна промежуточная строка и три дополнительных преобразования.

 

Насколько я знаю финнгер перешел на другую библиотеку. Хранить числа в виде строки — неэффективно. Куда лучше держать число в массиве чисел. Скорость критична.

 

Быстрая реализация тут.

В ней нет реализации битовых операций, но даже эмулируя их умножением все работает куда быстрее чем с метачислами.

 

PS: Да, она только для целыз чисел

PPS: Нет, я не мультиакк фингера

[Zer0Galaxy Автор темы 2 187]

 

 

Хранить числа в виде строки — неэффективно. Куда лучше держать число в массиве чисел. Скорость критична.

 В первой реализации мантисса метачисла действительно хранилась в массиве. Но, потом я подумал, что строка, содержащая тоже число, занимает гораздо меньше памяти чем массив и перешел на строки. Может и зря.

 

 

@Zer0Galaxy, а мантисса обязательно должна храниться в десятичном виде?

Конечно, нет. Десятичный вид хранения лишь упрощает функцию tostring.

Библиотека, приведенная Лешей, действительно на много эффективнее, хоть и работает только с целыми числами. Нужно дополнить ее битовыми операциями и вопрос решен.

[eu_tomat 2 154]

Конечно, нет. Десятичный вид хранения лишь упрощает функцию tostring.

Ффу-ухх... Я думал, это для наглядности и удобства пользователя, как учебный пример.

В первой реализации мантисса метачисла действительно хранилась в массиве. Но, потом я подумал, что строка, содержащая тоже число, занимает гораздо меньше памяти чем массив и перешел на строки. Может и зря.

Похоже, зря. Сейчас один символ кодирует 10 значений, хотя в пределе способен кодировать все 256. Потребление памяти и количество операций отличается о предельного в 25,6 раз! Это действительно лучше таблиц?

Кроме того, число в таблице более, чем 8-битное.