Перейти к содержимому
Zer0Galaxy

Метачисла

Рекомендуемые сообщения

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

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: стоит добавить, что арифметические операции над метачислами выполняются значительно медленнее, чем над обычными числами. Поэтому использовать метачисла следует только тогда, когда в этом действительно есть необходимость.

Изменено пользователем Zer0Galaxy

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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 -- Приводим число к метачислу

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

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

 

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

Поделиться сообщением


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

 

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

 

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

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

 

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

 

 

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

 

 

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Присоединяйтесь к обсуждению

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

Гость
Ответить в тему...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.


×
×
  • Создать...