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


Фотография

Метачисла


  • Авторизуйтесь для ответа в теме
Сообщений в теме: 14

#1 Оффлайн   Zer0Galaxy

Zer0Galaxy

    The Lord of the Pings

  • Пользователи
  • PipPipPipPipPipPipPip
  • 1 121 сообщений

Награды

4                                 

Отправлено 26 Май 2016 - 13:11

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

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: 26 Май 2016 - 15:15


#2 Оффлайн   Syabro

Syabro

    Свой человек

  • Пользователи
  • PipPipPipPipPipPipPip
  • 286 сообщений

Отправлено 27 Май 2016 - 20:19

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



#3 Оффлайн   Zer0Galaxy

Zer0Galaxy

    The Lord of the Pings

  • Автор темы
  • Пользователи
  • PipPipPipPipPipPipPip
  • 1 121 сообщений

Награды

4                                 

Отправлено 30 Май 2016 - 09:27

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

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


#4 Онлайн   Fingercomp

Fingercomp

    Видимый невидимый

  • Пользователи
  • PipPipPipPipPipPipPip
  • 1 844 сообщений

Награды

                                               

Отправлено 28 Июль 2016 - 23:45

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

 

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



#5 Оффлайн   Zer0Galaxy

Zer0Galaxy

    The Lord of the Pings

  • Автор темы
  • Пользователи
  • PipPipPipPipPipPipPip
  • 1 121 сообщений

Награды

4                                 

Отправлено 29 Июль 2016 - 13:31

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

#6 Онлайн   Fingercomp

Fingercomp

    Видимый невидимый

  • Пользователи
  • PipPipPipPipPipPipPip
  • 1 844 сообщений

Награды

                                               

Отправлено 29 Июль 2016 - 14:50

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

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


#7 Оффлайн   eu_tomat

eu_tomat

    Свой человек

  • Пользователи
  • PipPipPipPipPipPipPip
  • 569 сообщений

Награды

                    

Отправлено 29 Июль 2016 - 16:43

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

#8 Онлайн   Fingercomp

Fingercomp

    Видимый невидимый

  • Пользователи
  • PipPipPipPipPipPipPip
  • 1 844 сообщений

Награды

                                               

Отправлено 29 Июль 2016 - 20:30

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


  • eu_tomat и Saintmare это нравится

#9 Оффлайн   eu_tomat

eu_tomat

    Свой человек

  • Пользователи
  • PipPipPipPipPipPipPip
  • 569 сообщений

Награды

                    

Отправлено 29 Июль 2016 - 21:05

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

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

Сообщение отредактировал eu_tomat: 30 Июль 2016 - 00:40

  • Saintmare это нравится

#10 Онлайн   Fingercomp

Fingercomp

    Видимый невидимый

  • Пользователи
  • PipPipPipPipPipPipPip
  • 1 844 сообщений

Награды

                                               

Отправлено 30 Июль 2016 - 00:25

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



#11 Оффлайн   Zer0Galaxy

Zer0Galaxy

    The Lord of the Pings

  • Автор темы
  • Пользователи
  • PipPipPipPipPipPipPip
  • 1 121 сообщений

Награды

4                                 

Отправлено 30 Июль 2016 - 14:02

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

#12 Оффлайн   eu_tomat

eu_tomat

    Свой человек

  • Пользователи
  • PipPipPipPipPipPipPip
  • 569 сообщений

Награды

                    

Отправлено 03 Август 2016 - 11:46

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


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

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

#13 Оффлайн   LeshaInc

LeshaInc

    2B

  • Пользователи
  • PipPipPipPipPipPipPip
  • 1 176 сообщений
  • ГородЛуна

Награды

                 

Отправлено 03 Август 2016 - 11:55

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



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

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

PS: Да, она только для целыз чисел
PPS: Нет, я не мультиакк фингера

#14 Оффлайн   Zer0Galaxy

Zer0Galaxy

    The Lord of the Pings

  • Автор темы
  • Пользователи
  • PipPipPipPipPipPipPip
  • 1 121 сообщений

Награды

4                                 

Отправлено 03 Август 2016 - 12:31

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

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

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

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



#15 Оффлайн   eu_tomat

eu_tomat

    Свой человек

  • Пользователи
  • PipPipPipPipPipPipPip
  • 569 сообщений

Награды

                    

Отправлено 03 Август 2016 - 14:12

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

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

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

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




Количество пользователей, читающих эту тему: 0

0 пользователей, 0 гостей, 0 анонимных


Яндекс.Метрика