Автор |
Сообщение |
|
|
Заголовок сообщения: |
|
|
|
Некоторые замечания после раскомментирования 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 и т.д., хотя перебор функций вроде нормально при этом идет
Немного насчет перебора вообще
Процы Неймана и Гарварда и новые и старые не приспособлены к переборным алгоритмам
Тянуть перебор программно - это дикие тормоза даже если оптимизировать код.
Нужна систолическая аппаратная структура(лучше перестраиваемая из программы - под разные алгоритмы перебора, еще лучше перед этим описанная в самой программе - типа ПЛИС) в самом ядре проца.
Некоторые замечания после раскомментирования fact и ~
если операнд отрицательный, то факториал для него не существует, а ты анализ знака операнда нигде не делаешь
[code]: 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[/code] Для скорости fact лучше сделать на ассме [code]: 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[/code] С числами-разложениями исходного числа на стеке при переборе происходят нелады(краевые д'эффекты похоже - не вникал) [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 ~ - .............................................[/code]
и потом снова 673229 и т.д., хотя перебор функций вроде нормально при этом идет
Немного насчет перебора вообще
Процы Неймана и Гарварда и новые и старые не приспособлены к переборным алгоритмам
Тянуть перебор программно - это дикие тормоза даже если оптимизировать код.
Нужна систолическая аппаратная структура(лучше перестраиваемая из программы - под разные алгоритмы перебора, еще лучше перед этим описанная в самой программе - типа ПЛИС) в самом ядре проца.
|
|
|
|
Добавлено: Пт дек 07, 2007 19:05 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Цитата: PS. Обратите внимание на применённый арсенал средств: ООП (hype3), таблицы переходов (chartable.f), бэкфорт -- работают все вместе. Не слабо - но и задачка не очень легкая. Цитата: А вот это уже знаю, по-моему тебе просто не попались такие варианты... Да - я смотрел только на результаты. Цитата: Но именно потому я их заблокировал что они очень сильно увеличивают перебор. Очень сильно. Что - все виснет - не дождаться. Может дать фикс. интервал времени и выйти. Цитата: Другие функции мне просто было лень делать -- вроде "антифакториала"...
Что так, это всего лишь дихотомия на таблице из 13 факториалов, зато IQ сильно повысит.
[quote]PS. Обратите внимание на применённый арсенал средств: ООП (hype3), таблицы переходов (chartable.f), бэкфорт -- работают все вместе.[/quote] Не слабо - но и задачка не очень легкая. [quote]А вот это уже знаю, по-моему тебе просто не попались такие варианты... [/quote] Да - я смотрел только на результаты. [quote]Но именно потому я их заблокировал что они очень сильно увеличивают перебор. Очень сильно. [/quote] Что - все виснет - не дождаться. Может дать фикс. интервал времени и выйти. [quote]Другие функции мне просто было лень делать -- вроде "антифакториала"... [/quote]
Что так, это всего лишь дихотомия на таблице из 13 факториалов, зато IQ сильно повысит.
|
|
|
|
Добавлено: Ср дек 05, 2007 18:09 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
|
|
|
Добавлено: Ср дек 05, 2007 17:37 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
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).
Числа - пища, преобразование - ее усвоение, если усвоил выше порога - то родил(копия), не усвоил ниже другого порога - умер, сделать объем пищи общим(для конкуренции), для повышения быстродействия ввести фактор времени и т.д. и т.п.
profiT есть profiT.
Во-первых: начато-сделано.
Во-вторых: Раз перебор, то конечно ~profit/lib/[b]bac4th[/b].f.
Программа работает корректно.
Ограничения реализации(все они не запрещены условием задачи):
1. входные числа разбиваются только на одно и/или двух разрядные числа.
2. из заданного набора функций взяты не все функции.
3. функции используются после забрасывания [b]всех[/b] чисел на стек
Поэтому
при 100 stack-ops-galore выдается результат всего в ~ 1000 вариантов.
Введем понятие IQ для программ такого типа. Пусть это будет суммарный результат для N(здесь это 100) входных параметров(похоже 100 в данном случае - репрезантивно).
[b]IQ(stack-ops-galore)=1000[/b].
Это конечно далеко от максимума.
Между делом вспомнил о Wormball. Такого рода варианты программ, можно заставить жить и размножаться в сетях( при этом "генетически" и "естественно-отборно" в итоге получить реализацию с максимальным IQ).
Числа - пища, преобразование - ее усвоение, если усвоил выше порога - то родил(копия), не усвоил ниже другого порога - умер, сделать объем пищи общим(для конкуренции), для повышения быстродействия ввести фактор времени и т.д. и т.п.
|
|
|
|
Добавлено: Ср дек 05, 2007 16:24 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
|
|
|
Добавлено: Ср дек 05, 2007 14:00 |
|
|
|
|
|
Заголовок сообщения: |
Проездной билет |
|
|
Предыстория: Еду в автобусе, покупаю билет. Получаю из числа на билете разными способами число 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 чисел,
(допускается использовать только часть функций из их набора).
Цель - получить максимальный результат(время вычисления - фактор незначимый)
[img]http://i033.radikal.ru/0712/43/1bfb63540f05.jpg[/img]
Предыстория: Еду в автобусе, покупаю билет. Получаю из числа на билете разными способами число 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 чисел,
(допускается использовать только часть функций из их набора).
Цель - получить максимальный результат(время вычисления - фактор незначимый)
|
|
|
|
Добавлено: Вт дек 04, 2007 15:05 |
|
|
|
|