LINUX.ORG.RU

Эмулируем сопроцессор через школокалькулятор с обратной польской записью

 


0

5

Не хочется спускать на тормозах срач из Есть ли современный аналог DDD? (да и тупняк в /dev подзапарил).

В тред кастуются mv, xiomar_georgios и все желающие.

Чтобы дать хоть какой-то (мизерный) шанс общелиспу, предлагаю следующую задачу:

«Эмулируем сопроцессор через школокалькулятор с обратной польской записью».

Дано:

На вход подаётся файл фиксированного размера, содержащего дерево двоичных операторов и их операндов. Операнды представлены как 32-битные значения с плавающей точкой (float), операторы - как двоичные константы такой же размерности, что и операнды, эндианнесность - нативная. Операторы состоят из множества («сложить», «вычесть», «умножить»). (Делить не будем во избежание нуля).

На выход - записываем итоговый результат вычислений в любом (хоть двоичном дампе в файл) виде.

В отношении входящих данных гарантируется их корректность.

Пример входных данных в буквенном псевдокоде:

[-] [+] [0.2][0.1][*] [0.3][0.4]

каждое значение обозначено квадратными скобками и занимает 32 бита, запись выше означает выражение ((0,2 + 0,1) - (0,3 * 0,4)).

Ограничений на объём потребляемой памяти и размер стэка нет. Эталонная архитектура - amd64.

Победителем признаётся та реализация, которая будет уделывать конкурентов в лоскуты на гигабайтном входном файле, с минимальной параметризацией на смену типа под double и 32/64-ех битное беззнаковое целое. При смене типа операнда размерность оператора так же меняется!

Итоговые весы выглядят так:

0,4 * разница в double
0,2 * разница в float
0,2 * разница в uint32_t
0,2 * разница в uint64_t

Пример расчёта:

А обгоняет Б в два раза на целочисленных операциях, сливает вдвое на double и поровну на float.

А к Б : 0,4 * 0,5 + 0,2 * 1,0 + 0,2 * 2,0 + 0,2 * 2,0 = 1,2
Б к А : 0,4 * 2 + 0,2 * 1,0 + 0,2 * 0,5 + 0,2 * 0,5 = 1,2

Реализации эквиваленты, ничья.

Адепты раста, хаскеля и похапе, включая суровых сибирских разработчиков на VBA так же приглашаются к участию.

P.S. Так и знал, что в чём-нить обосрусь.

Считаем, что двоичные значения операторов не принадлежат множеству допустимых значений операндов. Для плавающих [+,-,*] = [&infin, -&infin, NaN], для беззнаковых целых - (UINTN_MAX, UINTN_MAX-1, UINTN_MAX-2).

★★★★★

Последнее исправление: LamerOk (всего исправлений: 2)

Победителем признаётся

Победителем специальной олимпиады? Потому что это именно она родимая.

gremlin_the_red ★★★★★
()

«Эмулируем сопроцессор через школокалькулятор с обратной польской записью».

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

А мне не интересно заниматься бесполезной хернёй. Придумай что-то адекватное, применимое в реальности.

К тому же, ты этой задачей умножил на ноль адепта лиспа. Потому как ты хочешь дать ему гигабайтное выражение. Он обделается тут же.

Слишком скучно.

xiomar_georgios
()

Задача должна быть такой, чтоб её можно было сбацать одной левой под пивко за вечерок, скролля порнахб одним глазом.

LamerOk ★★★★★
() автор топика
Ответ на: комментарий от LamerOk

Задача должна соотносится с реальностью. Нахрена кому-то тратить время на говно? У людей есть практика, у людей есть мотивация - делать то и учиться тому, что им будет полезно.

И про что эта задача? Про анализ? Дак все они обристаются на гигабайте. Задача про jit? Слишком тупо.

Но я подумаю. К тому же, как ты собрался валидировать результаты? Есть ты хочешь быстро - эти выражения нельзя исполнять итеративно, а значит всё пойдёт по жопе на той же плавучке. Да и не только не ней.

Ты хочешь что-бы я тебе родил итеративный jit? Ну дак это слишком тупо, повторю.

xiomar_georgios
()

У меня была более интересная/сложная/реальная задача: парсинг SVG path и расчёт его bbox. Тут тебе и парсинг, и strtod и много матана. Но руки так и не дошли запилить некий бенчмарк.

RazrFalcon ★★★★★
()
Ответ на: комментарий от RazrFalcon

более интересная/сложная/реальная задача

Это время, а мы на форуме в интернете. Более сложную реальную интересную задачу лучше сразу закоммитить в апстрим мержреквестом на гитхаб / патчем в рассылку.

LamerOk ★★★★★
() автор топика
Ответ на: комментарий от LamerOk

Какой ещё апстрим? Оно уже и так везде реализовано. Интересно было бы посмотреть решение в контексте разных языков.

RazrFalcon ★★★★★
()
> [+][0.2][0.1][*][0.1]

Это вообще как? У плюса аргументы идут после него, у умножения — один до, один после.

Miguel ★★★★★
()
Ответ на: комментарий от Miguel

Верно, обосрался, щас поправлю.

LamerOk ★★★★★
() автор топика
Ответ на: комментарий от Siborgium

Это запись говна. В школу надо отправить того, что такую херню родил, да и того, кто использовал.

xiomar_georgios
()
Ответ на: комментарий от Siborgium

Это я затупил с утра. Сначала хотел просто fpu, потом понял, что слишком линейно все получается.

LamerOk ★★★★★
() автор топика
Ответ на: комментарий от beastie

Вспоминаем обратную польскуюнотацию всем лором. Пусть уже будет как в топике.

LamerOk ★★★★★
() автор топика

каждое значение обозначено квадратными скобками и занимает 32 бита

[0.1]

Здесь 40 бит. Или 32 бита, не включая скобки? Тогда почему пробел перед «[+]»?

Считаем, что двоичные значения операторов не принадлежат множеству допустимых значений операндов.

Не понял. Можно пример? Ведь вроде «В отношении входящих данных гарантируется их корректность». Не?

monk ★★★★★
()
Ответ на: комментарий от monk

Данные лежат в памяти в двоичном виде в «родном» для процессора формате. Это не текст в ASCII-кодах, а псевдокод для описания формата данных на форуме.

LamerOk ★★★★★
() автор топика
Последнее исправление: LamerOk (всего исправлений: 2)
Ответ на: комментарий от monk

Не понял. Можно пример?

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

Т.е. оператор никогда не может быть операндом.

LamerOk ★★★★★
() автор топика
Ответ на: комментарий от LamerOk

Тогда как double помещается в 32 бита?

Данные лежат в памяти в двоичном виде в «родном» для процессора виде.

И тогда это гандикап для любого языка с динамической типизацией, так как перевод этого гигабайта из «родного» для процессора в «родной» для языка вид займёт больше времени, чем вычисления.

Проще всего такое в nasm’е набросать. С чтением через mmap.

monk ★★★★★
()
Ответ на: комментарий от monk

Тогда как double помещается в 32 бита?

А он не помещается. Описание дано для float. Но потом мы ВНЕЗАПНО хотим использовать тот же код для double (с перекомпиляцией, если что), и для него формат данных уже будет содержать 64 бита на ячейку.

из «родного» для процессора в «родной» для языка

Проблемы языка.

LamerOk ★★★★★
() автор топика
Ответ на: комментарий от monk

так как перевод этого гигабайта из «родного» для процессора в «родной» для языка вид займёт больше времени, чем вычисления.

Подожди, а кто виноват, что твоя мусорная скриптуха не может в нормальные форматы данных? Ты как и любой адепт скриптухи решил, что можно опять украсть парсер и заниматься хернёй и бенчить херню?

Проще всего такое в nasm’е набросать. С чтением через mmap.

Т.е. скриптуха не смогла? Но подожди, ты же мне рассказывал, что твоя скриптуха совсем не скриптуха? Опять что-ли врал?

xiomar_georgios
()
Последнее исправление: xiomar_georgios (всего исправлений: 1)
Ответ на: комментарий от xiomar_georgios

Т.е. скриптуха не смогла? Но подожди, ты же мне рассказывал, что твоя скриптуха совсем не скриптуха? Опять что-ли врал?

Если исходные данные будут в нормальном тэгированном формате SBCL или Racket, то они будут в выигрыше.

На самом деле можно и сделать и с бинарными файлами. Но арифметику придётся использовать нештатными средствами. От лиспов останется только запускалка.

monk ★★★★★
()
Ответ на: комментарий от xiomar_georgios

Лисп опять победил.

(defun calc (ops)
  (car
   (reduce
    (lambda (acc x)
      (if (numberp x) (append acc (list x))
	  (list (apply x acc))))
    ops
    :initial-value '())))

Пока фанатики-теоретики разгонялись и точили лясы, лисперы уже решили прикладную задачу и пошли отмечать сочельник. Всем чмоке в этом чяте.

ugoday ★★★★★
()
Ответ на: комментарий от monk

Если исходные данные будут в нормальном тэгированном формате SBCL или Racket, то они будут в выигрыше.

Это не формат, а говно запартное. Но дело не в этом - даже тут ты врёшь, ведь они не будут в выигрыше. Хотя не врёшь, а просто ошибаешься, ну я надеюсь на это, по крайне мере.

К тому же, тэгирование - это первый признак скриптухи. Т.е. ты действительно меня обманывал.

На самом деле можно и сделать и с бинарными файлами.

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

Но арифметику придётся использовать нештатными средствами. От лиспов останется только запускалка.

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

Да вот, рантайм это то, что читает твой тег и выбирает операцию. В реальности же никакие теги не читаются и никакие операции не выбираются. И именно этим и отличается скриптуха от не скриптухи.

xiomar_georgios
()
Ответ на: Лисп опять победил. от ugoday

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

Прикладную задачу. В целом это показывает в полной мере всю состоятельность данных адептов. Ну а чё - в запартных потугах зачёт ставят за любое говно. Там никаких критериев оценки не существует. А любой школяр думать, что запартные потуги являются какими-то прикладыми задачами, когда на самом деле это специально подобное говно для дошколят.

Так и живём.

xiomar_georgios
()
Ответ на: комментарий от monk

Я даже тебе объясню почему. Во-первых ты будешь читать больше памяти. Во-вторых заранее созданная структура(и заложенная в код, очевидно) быстрее инлайновой(т.е. встроенной в данные).

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

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

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

Правда оверхед никто не отменял. А он будет 25%, даже больше.

xiomar_georgios
()
Ответ на: комментарий от xiomar_georgios

Бла-бла-бла. Если бы за болтовню платили, вы бы уже были миллионером.

ugoday ★★★★★
()
Ответ на: комментарий от xiomar_georgios

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

Потому что в Си оператор + принимает два числа типа double, а в лиспе оператор + принимает два числа типа LispObject. А значит придётся писать свой оператор сложения чисел в предоставленном формате (чтобы обойти необходимость преобразования).

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

monk ★★★★★
()

Ну давайте начнем вот с этого. Набросал решение, на малых наборах данных работает. На больших не проверял, нормальный блоб делать лень. В комплекте генератор строка->блоб, вычислялка блоб->результат. Жду решение от царя на любой не-скриптухе по его выбору.

https://github.com/Siborgium/rpn

Siborgium ★★★★★
()
Последнее исправление: Siborgium (всего исправлений: 1)
Ответ на: комментарий от monk

Потому что в Си оператор + принимает два числа типа double, а в лиспе оператор + принимает два числа типа LispObject.

У тебя явные проблемы с восприятием реальности - ты фанатик, ты неадекватен. Как такую чушь можно писать?

В любой не-скриптухи + транслируется прямо в нативный оператор(операцию), именно поэтому она не скриптуха. Это свойство платформы, а не языка. Чини методичку.

То, что в твоей скриптухи это не так - это лишь следствие нелепости и бездарности скриптухи.

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

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

В целом, если ты действительно мыслишь такой такими категориями - у тебя большие проблемы, повторюсь. Ты фанатик.

xiomar_georgios
()
Ответ на: комментарий от Siborgium

Жду решение от царя на любой не-скриптухе по его выбору.

Жди. К тому же решения у тебя никакого нет. Опять ворованное unsafe-говно даже на уровне хелворда. Какой же позор нелепый.

xiomar_georgios
()
Ответ на: комментарий от Siborgium

Расскажи еще, что использовать стандартную библиотеку = воровать код, я послушаю.

Ты не использует стандартную библиотеку - тебя поимела пропаганда. Ты используешь ворованный рантайм. Т.е. чужую стандартную библиотеку, которая пропаганда выдаёт за твою. Это значит воровать.

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

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

xiomar_georgios
()

Опять царь про скриптуху.

Тем временем, насколько я знаю, у gcc генериться промежуточный код, очень сильно похожий на лисп. Скриптуха захватила gcc, куда бежать, царь?

anonymous
()
Ответ на: комментарий от anonymous

Нету там никакого похожего на лисп. Тебя опять поимела пропаганда. Во-первых в гцц тысячи разных «промежуточных кодов». Во-вторых они похожи на ast, а не на лисп. Просто те, кто родил лисп были слишком бездарны, что не смогли в синтаксис. А далее тебя поимела пропаганда.

Да и опять же, это что-то если есть, то крайне локальное.

xiomar_georgios
()
Ответ на: комментарий от xiomar_georgios

Интересное заявление. А если крестовая STL использует pthreads, то она тоже ворованный код использует? Unsafe там используется намеренно. Конечно, я мог бы тупо читать из файла стандартными средствами, использовать стандартный вектор вместо стека, бла-бла-бла, но это будет медленнее. Ну и чья методичка-то, чья пропаганда? Расскажешь?

Siborgium ★★★★★
()
Ответ на: комментарий от Siborgium

Интересное заявление. А если крестовая STL использует pthreads, то она тоже ворованный код использует?

Нет, кресты являются сями. И не отрицают их. Ты отрицаешь, а значит воруешь.

Unsafe там используется намеренно. Конечно, я мог бы тупо читать из файла стандартными средствами, использовать стандартный вектор вместо стека, бла-бла-бла, но это будет медленнее. Ну и чья методичка-то, чья пропаганда? Расскажешь?

Пропаганда заявляет, что это не медленнее. Ты видишь враньё - почему ты не противодействуешь пропаганде?

К тому же, никаких векторов и станадартных средств у тебя нет. Аллокатор ворованный, вектора ворованные, кодоген ворованный, рантайм - ворованный.

Я даже не знаю как и что тебе нужно написать, что-бы ты чего-то не украл. Такова уж твоя судьба.

xiomar_georgios
()
Ответ на: комментарий от xiomar_georgios

Придумай что-то адекватное, применимое в реальности.

Даны координаты (x,y – напряжения и деформации) для кривых деформаций для разных температур, есть формула для интерполяции между кривыми для промежуточной температуры,есть формула для интерполяции между точками одной кривой.

На входе есть файл с ~2 млн строк формата:

N, T, x, y

где N – номер узла в модели;

T – температура в узле;

x,y – значения напряжений и деформаций для каждого узла. При этом они находятся на линейном участке кривой.

Вид кривой деформаций

Если точка на кривой находится в пределах отрезка 0-1 на соответствующей по температуре кривой, то не делаем ничего. Если она выше (при этом будет находиться на одной прямой с отрезком 0-1), то необходимо найти произведение x, y на соответствующей кривой, которое будет равно произведению x, y из файла и решить нелинейное уравнение, которое я напишу, когда приеду домой, если моя задача Вас заинтересует.

Я наговнокодил решение на питоне, могу и его прикрепить, если нужно. (Но в плане качества кода и с т.з. алгоритмов оно, предполагаю, ужасно и для решения с 5-6 точками уходит секунд 10 примерно)

the_real_kinik ★★
()
Ответ на: комментарий от O02eg

RTL is inspired by Lisp lists.

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

xiomar_georgios
()
Ответ на: комментарий от the_real_kinik

Применение у этой задачи очень даже практическое.

Уровнения интерполяции, конечно же, тоже напишу.

the_real_kinik ★★
()
Ответ на: комментарий от xiomar_georgios

Доказывай, что это писал автор и доказывай, что он писал правду.

Опять царь обосрался и даже не знает, у кого есть доступ к документации GNU. Наверное, что у GNU проекта есть и свой Lisp, тупой царь не в теме.

O02eg ★★★★★
()
Ответ на: комментарий от Siborgium

Читаем wiki:

GCC’s RTL is usually written in a form which looks like a Lisp S-expression:

(set (reg:SI 140)
     (plus:SI (reg:SI 138)
              (reg:SI 139)))

Вообще не похоже на лисп, не правда ли?

ugoday ★★★★★
()
Ответ на: комментарий от the_real_kinik

Даны координаты (x,y – напряжения и деформации) для кривых деформаций для разных температур, есть формула для интерполяции между кривыми для промежуточной температуры,есть формула для интерполяции между точками одной кривой.

Научись формулировать задачу внятно. Эти запартные завывания волнуют кого-то крайне мало за пределами запарты.

На входе есть файл с ~2 млн строк формата:

Если ты используешь такой мусор в качестве данных - ты неадекватен. Меняй на адекватный формат.

Если точка на кривой находится в пределах отрезка 0-1 на соответствующей по температуре кривой, то не делаем ничего. Если она выше (при этом будет находиться на одной прямой с отрезком 0-1), то необходимо найти произведение x, y на соответствующей кривой, которое будет равно произведению x, y из файла и решить нелинейное уравнение, которое я напишу, когда приеду домой, если моя задача Вас заинтересует.

Опять же - это не имеет никакого отношения к формулировке задачи. Это рассуждения запарты для запарты. Нужно вывести это за рамки запарты.

Я наговнокодил решение на питоне, могу и его прикрепить, если нужно. (Но в плане качества кода и с т.з. алгоритмов оно, предполагаю, ужасно и для решения с 5-6 точками уходит секунд 10 примерно)

Прикладывай. Хоть это целиком и полностью нечитаемо, но это хоть что-то.

По крайней мере я посмотрю и скажу может ли это работать быстро, либо нет.

xiomar_georgios
()
Ответ на: комментарий от O02eg

Опять царь обосрался и даже не знает, у кого есть доступ к документации GNU. Наверное, что у GNU проекта есть и свой Lisp, тупой царь не в теме.

О, да у нас нонейм опять обосрался и не знает, что абсолютно неважно что там есть в gnu - там есть что угодно, даже паскаль и жава. Следует ли из этого что-то? Нет. В школу.

xiomar_georgios
()
Ответ на: комментарий от gremlin_the_red

Редко гремлин говорит что-то дельное в девелопмент, но тут я его полностью поддерживаю.

peregrine ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.