Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 23:09

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: Проездной билет
СообщениеДобавлено: Вт дек 04, 2007 15:05 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Изображение
Предыстория: Еду в автобусе, покупаю билет. Получаю из числа на билете разными способами число 100, например так:
1) 35 7 7 / + 64 +
2) 35 7 7 / 64 + +
3) 3 fact 5 + 7 7 / - 6 4 - ^
4) 3 5 * 7 7 / + 6 * 4 +
5) 35 77 + 6 4 sqrt * -
6) 35 77 + 6 antifact 4 * -
7) 3 fact 5 - 7 7 * + 6 4 - *
и т. д.

А теперь условие задачи:
Получить форт-исходники, построенные с использованием функций из определенного их набора, дающие определенный результат ( число 100)
при преобразовании случайного 6-ти разрядного десятичного числа

набор функций
~ смена знака числа (NEGATE), использование цепочек типа ~ ~ .. - запрещено
+ сложение
- вычитание
* умножение
/ деление - может быть использовано когда нет остатка ( 56 5 / - применить нельзя)
^ возведение в степень ( 30 0 ^ даст 1, 3 3 ^ даст 27 )
v корень n степени - может быть использован когда число является степенью ( 27 3 v даст 3)
s корень квадратный - может быть использован когда число является квадратом ( 25 s даст 5 )
! факториал
i антифакториал - может быть использован когда число является факториалом ( 120 i даст 5 )

Вход - случайные 6-ти значные десятичные числа ( 564502 502564 123234 578434 708762 ...)
Выход - вывод в консоль или в файл форт-исходников, дающих в результате их выполнения число 100
Основное условие - ПОРЯДОК ЦИФР В ЗАПИСИ КАЖДОГО ИСХОДНИКА ДОЛЖЕН ТОЧНО СООТВЕТСТВОВАТЬ ПОРЯДКУ ЭТИХ ЦИФР В ЗАПИСИ ВХОДНОГО ЧИСЛА

Еще один пример, теперь уже в синтаксисе из заданного в наборе функций: на вход поступило число 564502
На выходе ваша программа сформировала такой например результат
56 4 - 50 2 - +
5 6 4 + * 5 0 * + 2 *
5 ~ 6 + 4 50 2 / * *
5 6 - ~ 4 50 * * 2 /
5 6 - ~ 4 50 * 2 / *
5 6 - 4 50 * 2 / ~ *
количество результатов = 6

Получить общий результат для 100 случайных чисел - сумму результатов для каждого из этих 100 чисел,
(допускается использовать только часть функций из их набора).
Цель - получить максимальный результат(время вычисления - фактор незначимый)

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср дек 05, 2007 14:00 
---


Последний раз редактировалось profiT Пт фев 29, 2008 23:59, всего редактировалось 7 раз(а).

Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср дек 05, 2007 16:24 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
profiT есть profiT.
Во-первых: начато-сделано.
Во-вторых: Раз перебор, то конечно ~profit/lib/bac4th.f.

Программа работает корректно.
Ограничения реализации(все они не запрещены условием задачи):
1. входные числа разбиваются только на одно и/или двух разрядные числа.
2. из заданного набора функций взяты не все функции.
3. функции используются после забрасывания всех чисел на стек
Поэтому
при 100 stack-ops-galore выдается результат всего в ~ 1000 вариантов.
Введем понятие IQ для программ такого типа. Пусть это будет суммарный результат для N(здесь это 100) входных параметров(похоже 100 в данном случае - репрезантивно).
IQ(stack-ops-galore)=1000.
Это конечно далеко от максимума.

Между делом вспомнил о Wormball. Такого рода варианты программ, можно заставить жить и размножаться в сетях( при этом "генетически" и "естественно-отборно" в итоге получить реализацию с максимальным IQ).
Числа - пища, преобразование - ее усвоение, если усвоил выше порога - то родил(копия), не усвоил ниже другого порога - умер, сделать объем пищи общим(для конкуренции), для повышения быстродействия ввести фактор времени и т.д. и т.п.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср дек 05, 2007 17:37 
---


Последний раз редактировалось profiT Пт фев 29, 2008 23:59, всего редактировалось 1 раз.

Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср дек 05, 2007 18:09 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Цитата:
PS. Обратите внимание на применённый арсенал средств: ООП (hype3), таблицы переходов (chartable.f), бэкфорт -- работают все вместе.

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

Да - я смотрел только на результаты.
Цитата:
Но именно потому я их заблокировал что они очень сильно увеличивают перебор. Очень сильно.

Что - все виснет - не дождаться. Может дать фикс. интервал времени и выйти.
Цитата:
Другие функции мне просто было лень делать -- вроде "антифакториала"...

Что так, это всего лишь дихотомия на таблице из 13 факториалов, зато IQ сильно повысит.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт дек 07, 2007 19:05 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Некоторые замечания после раскомментирования fact и ~
если операнд отрицательный, то факториал для него не существует, а ты анализ знака операнда нигде не делаешь
Код:
: fact DUP 2 < IF DROP 1 ELSE 1 SWAP 1+ 1 ?DO I * LOOP THEN ;
-5 fact ( 1 )
CODE fact
591F20 8945FC           MOV     FC [EBP] , EAX
591F23 8945F8           MOV     F8 [EBP] , EAX
591F26 B802000000       MOV     EAX , # 2
591F2B 3B45F8           CMP     EAX , F8 [EBP]
591F2E 0F9EC0           SETLE   AL
591F31 83E001           AND     EAX , # 1
591F34 48               DEC     EAX
591F35 8D6DFC           LEA     EBP , FC [EBP]
591F38 0BC0             OR      EAX , EAX
591F3A 8B4500           MOV     EAX , 0 [EBP]
591F3D 8D6D04           LEA     EBP , 4 [EBP]
591F40 0F8410000000     JE      591F56  ( fact+36  )
591F46 8B4500           MOV     EAX , 0 [EBP]
591F49 894500           MOV     0 [EBP] , EAX
591F4C B801000000       MOV     EAX , # 1
591F51 E950000000       JMP     591FA6  ( fact+86  )
591F56 8945FC           MOV     FC [EBP] , EAX
591F59 B801000000       MOV     EAX , # 1
591F5E 8B55FC           MOV     EDX , FC [EBP]
591F61 8945FC           MOV     FC [EBP] , EAX
591F64 8BC2             MOV     EAX , EDX
591F66 8D4001           LEA     EAX , 1 [EAX]
591F69 8945F8           MOV     F8 [EBP] , EAX
591F6C B801000000       MOV     EAX , # 1
591F71 BBA61F5900       MOV     EBX , # 591FA6
591F76 3B45F8           CMP     EAX , F8 [EBP]
591F79 7505             JNE     591F80
591F7B 8B45FC           MOV     EAX , FC [EBP]
591F7E FFE3             JMP     EBX
591F80 53               PUSH    EBX
591F81 BB00000080       MOV     EBX , # 80000000
591F86 2B5DF8           SUB     EBX , F8 [EBP]
591F89 53               PUSH    EBX
591F8A 03D8             ADD     EBX , EAX
591F8C 53               PUSH    EBX
591F8D 8B45FC           MOV     EAX , FC [EBP]
591F90 8945FC           MOV     FC [EBP] , EAX
591F93 8B0424           MOV     EAX , [ESP]
591F96 2B442404         SUB     EAX , 4 [ESP]
591F9A F76DFC           IMUL    FC [EBP]
591F9D FF0424           INC     [ESP]
591FA0 71EE             JNO     591F90
591FA2 8D64240C         LEA     ESP , C [ESP]
591FA6 C3               RET     NEAR
END-CODE

Для скорости fact лучше сделать на ассме
Код:
: fact  B=A $ -1 B=aB L1: *B B-- L1 JNZ ;

CODE fact
591FC0 8BD8             MOV     EBX , EAX
591FC2 8D5BFF           LEA     EBX , FF [EBX]
591FC5 F7EB             IMUL    EBX
591FC7 4B               DEC     EBX
591FC8 75FB             JNE     591FC5
591FCA C3               RET     NEAR
END-CODE

С числами-разложениями исходного числа на стеке при переборе происходят нелады(краевые д'эффекты похоже - не вникал)
Код:
673219
..............................................
6 7 3 ~ fact ~ fact ~ * fact - 2 1 9 + * *
6 7 3 ~ fact ~ fact ~ * fact - 21 9 ~ fact - *
6 7 3 ~ fact ~ fact ~ * * 2 29 ~ * ~ - ~
6 7 3 ~ fact ~ fact ~ * * 2 29 ~ * + ~
.............................................
6 73 2 2 * fact + - ~ 9 ~ -
6 73 2 2 * fact + - ~ 9 +
6 73 ~ fact ~ fact ~ fact - 2 7 ~ fact 9 + * *
6 73 ~ fact ~ fact ~ fact - 2 * 7 ~ fact 9 + *
.............................................
6 7 ~ 3 2 * fact + - ~ 7 / 9 ~ fact -
6 7 ~ 3 2 * fact + - ~ 7 / 9 fact ~ fact -
6 7 ~ 32 ~ fact ~ fact ~ fact ~ * + 7 * 9 +
6 7 ~ 32 ~ + ~ - 3 ~ * 9 ~ fact ~ fact +
6 7 ~ 32 ~ + ~ - 3 ~ * 9 ~ fact ~ -
.............................................

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

Немного насчет перебора вообще
Процы Неймана и Гарварда и новые и старые не приспособлены к переборным алгоритмам
Тянуть перебор программно - это дикие тормоза даже если оптимизировать код.
Нужна систолическая аппаратная структура(лучше перестраиваемая из программы - под разные алгоритмы перебора, еще лучше перед этим описанная в самой программе - типа ПЛИС) в самом ядре проца.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB