Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: runtime компиляция формул:  (Прочитано 11533 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mayor
Специалист

ru
Offline Offline

« : 22-09-2007 13:49 » 

runtime компиляция формул:

требуется нарисовать фрактал по введенным с stdin формулам, в принципе интерпретирование формул уже делал, но тут совсем другая задача: формулы без напряга должны расчитываеться пока что до 6^10 - 6^11 раз  ...
есть ли какая нить библиотека для компиляции простых формул ( +-\*= sin cos arctg ) ?

в какую структуру данных лучше компилировать формулы ?

( оптимизация сейчас особо не горит, прежде всего должен быть понятным алгоритм )

Записан

1n c0de we trust
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #1 : 22-09-2007 14:32 » 

Читаем теорию: А.Ахо, Р.Сети, Дж. Ульман "Компиляторы, принуипы, технологии, инструменты". первые главы.

Принцип простой. Формула разбивается на на элементарные вычисления. Проставляется приоритет вычислений. Строится дерево вычислений.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Mayor
Специалист

ru
Offline Offline

« Ответ #2 : 22-09-2007 16:29 » 

Читаем теорию: А.Ахо, Р.Сети, Дж. Ульман "Компиляторы, принуипы, технологии, инструменты". первые главы.

Принцип простой. Формула разбивается на на элементарные вычисления. Проставляется приоритет вычислений. Строится дерево вычислений.

ну допустим я поначалу буду вводить формулы в прямой или обратной польской нотации, так что расстановка приоритета отпадает...

какую структуру использовать в качестве элемента дерева?

и почему именно дерево, а не список?

Записан

1n c0de we trust
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #3 : 22-09-2007 17:03 » 

Mayor1, Чем список отличается от дерева?
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Mayor
Специалист

ru
Offline Offline

« Ответ #4 : 28-09-2007 19:23 » new

Цитата: дикий кот
Ну. Обычно, для интерпретации формулы удобно компилировать в обратную (меньше ресурсов требует) польскую запись. Или в прямую, которая фактически является программой для стековой машины.
чесно говоря польская нотация удобна для интерпретации, а не для компиляции формул, тк реализация в рантайме дерева жрет слишком много ресурсов для >6^10 операций вычисления ...


Цитата: дикий кот
Библиотеки можно поискать в составе bc - это калькулятор такой gnu'шный.
Но с другой стороны, вообще не понятна постановка задачи. Фрактал же не по формуле строится, а по штуке, которая называется итерационная система функций - iterated function system. Да и то не по любой, нужно условие наличия неподвижной точки и всё такое прочее. Так что, в общем-то, эмс... задача не очень ясна с наскока.
теории фракталов не нашел, тч не знаю что такое ifs, мой код строит фрактал рекурсивно:
из координат линии по 6-8 формулам получаем координаты еще 2х линий, и каждая из полученных линий вызывает функцию породившую ее пока не закончится счетчик итераций\рекурсий
зы одной неподвижной точки для построения фрактала имхо не хватит ...

Mayor1, Чем список отличается от дерева?
ну вообщето список линейная структура без ветвлений, и как оказалось при дальнейшем разборе формулы вида (3+4)*5-(1+2)*6 на базе списка не построить, так что я заменил дерево списком со стеком функций

элементы формулы компилятся вот в такую структуру:
Код:
typedef void(*pff)(void *, double *vars);
typedef struct {
pff func;
union {
double constant;
int indifier;
GSList *plist;
};
} token,*ptoken ;
что полностью исключает проверку условий на этапе расчета формулы и соответвенно делает невозможным обход дерева, но тк структура сложной формулы представляет собой дерево, то его эмуляция выполнена за счет рекурсии

pff функцией для доступа к аргументам формулы и сохранения промежуточных результатов используется:
Код:
typedef struct {
union {
double v_arg;
int n_arg;
};
double value;
double reserved;
...
} calc,*pcalc;
где ... означают любое число аргументов скомпилированной функции

в плане скорости выполнения 6^10 вызовов скомпиленных функций достоверных отличий от fpc скомпиленных формул не заметил

названия моей нотации еще не придумал ... но практического толку от нее мало - очень сложно переписывать в нее формулы :

dx   x1 y1 x2 y2 = x2 + x1 -  1.6 /
dy   x1 y1 x2 y2 = y2 + y1 -  1.6 /
fractal
# x3 = x1 + (x2-x1)/1.6
x3 x1 y1 x2 y2 = x1 + dx +
# y3 = y1 + (y2-y1)/1.6
y3 x1 y1 x2 y2 = y1 + dy +
x4 x1 y1 x2 y2 = x3 + dy +
y4 x1 y1 x2 y2 = y3 + dx -
x5 x1 y1 x2 y2 = x3 + dy -
y5 x1 y1 x2 y2 = y3 + dx +
#begin

к сожалению не осталось времени на создания интерпретатора из польской и инфиксной в мою нотацию

в плане реализации рантайм компилятора остались нерешенные проблеммы:

1. нада создать структуру с элеметом функцией аргумент которой указатель на эту структуру -- из за этого указатель в функции пришлось заменить на войд, как следствие из-за явного преобразования указателей время отладки увеличилось на 7 часов

2. нада сделать возможным ссылаться на часть функции
* x3 x1 y1 x2 y2 = x2 + x1 -  1.6 / =dx x1 + dx +
для упрощения написания интерпретатора польской нотации

3. нада дописать сборщик мусора

4. нада добавить тригонометрические функции

в плане тестирования использовался готовый генератор фракталов на паскале, что усложнило отладку и реализацию компилятора, а также сделало невозможным сравнить скорость вычсления формул скопиленных фпс и моим кодом

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

http://pages.plotinka.ru/~mayor/fractal.tar.bz2  - исходники

Finch: Подправил линки в цитатах. Цитаты скорее всего взяты с другого форума, но ведут на наш форум,  в тему совсем не связанную с данной
« Последнее редактирование: 28-09-2007 20:27 от Finch » Записан

1n c0de we trust
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines