Factorials

[Nataly-Mak]

(Оффтоп)

А-а-а, поняла. Не смотрю я ведь мультики

[Vovka17]

Pavlovsky в сообщении #697450 писал(а):

... Умеет очень высоко прыгать!

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

[Nataly-Mak]

Ну, вы уже вошли в зону 22+, что совсем не плохо.
Прорваться в десятку очень сложно, соперники чересчур сильные.
Те, кто в начале конкурса был в лидерах, сейчас уже вытеснены из десятки, например, Valentin Dobrota, который довольно долго был на первом месте.
Наблюдаю за dimkadimon, пока держится в десятке, но очень трудно. Был на границе (10-ое место), потом поднялся на 7-ое, сейчас опять оттеснили на 9-ое. Острая борьба в десятке.

В моей команде тоже пока всё застопорилось. Ищем новые идеи. Я со своим ручным подходом выдохлась давно.
Хотя... что-то всё-таки продолжаю делать.

Интересно решение для 29!
Берём оптимальное решение для 26!, остаётся умножить на 27*28*29=21924 (тривиальная эвристика ).
Начинаю составлять число 21924 вручную, сначала это удаётся мне за 5 операций, что даёт решение в 21 шаг, не интересно, такое решение у меня уже было.
Думаю дальше, удалось составить за 4 шага, это уже дало решение в 20 шагов, есть улучшение.
Наконец, подключаю программу mertz. Программа находит представление числа 21924 за 3 шага! И таким образом получаю решение в 19 шагов. Конечно, до оптимального ещё 2 шага, но и то хлеб

-- Вт мар 19, 2013 05:23:22 --

(Оффтоп)

Pavlovsky
очень понравился ваш аватар
dimkadimon
а вы не добавите аватар?

Может быть, мне сменить аватар к грядущему юбилею (5 лет на форуме)?
Не наскучила коллегам моя физиономия?

[Nataly-Mak]

Это полином для 29! по решению, о котором рассказано в предыдущем посте (19 шагов):

f(x)=$64 x^{19}-576 x^{18}-23664 x^{17}-237664 x^{16}-1276608 x^{15}-4265952 x^{14}-9250760x^{13}-12777744 x^{12}-10066692 x^{11}-2557220 x^{10}+2079969 x^9+1302762 x^8-112640 x^7-88800 x^6$
$f(36)=29!$

Упаковка, предложенная Вольфрамом:

$x^5 (x+2) (2 x+5)^2 (2 x (x+2)+1) (2 (x-28) (x+2) x+x) ((x+2) (2 x (x+2)+1)-6)^2$

Может быть, кто-нибудь сможет выжать из этого полинома лучшее решение, чем решение в 19 шагов.
Можно попробовать уменьшить коэффициенты в полиноме, потом снова упаковать. Авось, что-то интересное получится.

Как уже писала, мне очень интересно получить оптимальные полиномы для всех N. Это просто делать, когда есть известное оптимальное решение.

[dimkadimon]

Nataly-Mak в сообщении #697995 писал(а):

Это полином для 29! по решению, о котором рассказано в предыдущем посте (19 шагов):

Пожалуйста не нарушайте правила конкурса - не надо показывать полное решение (особено если оно достаточно хорошее).

[Nataly-Mak]

А где вы видите полное решение?
Это всего лишь полином! И даже предложенная Вольфрамом упаковка не помогает найти решение хотя бы в 19 шагов. Я сейчас попыталась по этой упаковке составить решение, ничего не получилось.
А у вас получилось?

(Оффтоп)

Вообще уже очень сильно наскучили эти ваши замечания. Может быть, уже достаточно их в этой теме?
Вот я одного не понимаю: вам-то что за дело до нарушений правил конкурса? Вы вроде в администрацию данного конкурса не входите (?)
Или вы боитесь, что используя этот полином, кто-то из конкурсантов найдёт решение в 19 шагов для 29! и тем самым обойдёт вас?
Но вы ведь тут в равных условиях со всеми конкурсантами: вы тоже можете использовать этот полином.

[Pavlovsky]

У всех кризис идей. Мои алгоритмы все реже и реже стали выдавать результаты. И хотя по моим оценкам выйти на рубеж 24,5+ им по силам. Но произойдет это через одну - две недели. Сколько человек к этому времени преодолеет рубеж 24,5 не известно. Одно можно сказать точно в десятку я пока не попадаю.
Отталкиваясь от темы про полиномы, упорно ищу алгебраические преобразования экономящие операции. Увы кроме уже известного A(A+1)B^2=AB(AB+B), ничего интересного не нашел.
Кстати это преобразование можно применить и к:
$x^5 (x+2) (2 x+5)^2 (2 x (x+2)+1) (2 (x-28) (x+2) x+x) ((x+2) (2 x (x+2)+1)-6)^2$
Из него легко виделить конструкцию:
$2x(x+2) (2 x (x+2)+1)$

[Nataly-Mak]

Pavlovsky
значит, полученная мной упаковка не совсем бесперспективная?
Как уже написала, в лоб по этой упаковке решение не составляется даже в 19 шагов.
Но вот если над ней поколдовать, то, конечно, в 19 шагов решение просто обязано получиться. Но цель не в 19 шагах, а меньше!

-- Вт мар 19, 2013 08:48:25 --

Уменьшила коэффициенты в полиноме для 29!

$f(x)=x^{20}+12 x^{19}-657 x^{18}-6613 x^{17}-35489 x^{16}-118510 x^{15}-256989 x^{14}-354957 x^{13}-279642x^{12}-71045 x^{11}+57744 x^{10}+36220 x^9-3098 x^8-2498 x^7-24 x^6$
$f(36)=29!$

Зря старалась
Вольфрам выдал для этого полинома тривиальную упаковку:

$x^6 (x (x (x (x (x (x (x (x (x (x (x (x (x (x+12)-657)-6613)-35489)-118510)-256989)- 354957)-279642)-71045)+57744)[phone])$

[dimkadimon]

Pavlovsky в сообщении #698002 писал(а):

А где вы видите полное решение?
Это всего лишь полином! И даже предложенная Вольфрамом упаковка не помогает найти решение хотя бы в 19 шагов. Я сейчас попыталась по этой упаковке составить решение, ничего не получилось.
А у вас получилось?

А я то думал из этого полинома уже можно получить 19 шагов. Ну в таком случае забираю свои комментарии назад.

[Nataly-Mak]

А вот такая оригинальная упаковка с иррациональностями хороша?

$-1/2 (-2 x+\sqrt{2}-2) x^6 (x+2) (2 x+5)^2 (2 x+\sqrt{2}+2) (16 x+33) (2 x^3+8 x^2+9 x-4)^2$

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

[Nataly-Mak]

dimkadimon в сообщении #698011 писал(а):

А я то думал из этого полинома уже можно получить 19 шагов.

Может быть, и можно, если очень постараться

Pavlovsky выложил свой полином для 26! и сказал, что он получен из готового решения в 16 шагов.
dmd предложил упаковку этого полинома, которая даёт решение только в 17 шагов (упаковка вычисляется за 13 операций).
Но фактически, как сообщил потом dmd, эту упаковку можно преобразовать так, что она будет вычисляться за 11 операций, а это даёт уже оптимальное решение в 15 шагов.
В-о-о-т --- в чём секрет упаковок

Из моего полинома должно получиться решение в 19 шагов, ведь полином же получен из готового решения в 19 шагов. Но такую упаковку полинома ещё нужно найти, что очень не просто.
Я пытаюсь найти упаковку, которая даст решение меньше 19 шагов, но пока безуспешно; даже решение в 19 шагов не могу получить по всем своим упаковкам.

[Pavlovsky]

Nataly-Mak в сообщении #698071 писал(а):

Pavlovsky выложил свой полином для 26! и сказал, что он получен из готового решения в 16 шагов.
dmd предложил упаковку этого полинома, которая даёт решение только в 17 шагов (упаковка вычисляется за 13 операций).

Ээээ все было не так. Я просто выложил полином. И только когда dmd выложил почти оптимальное решение, я раскололся, откуда ноги растут. Кстати dmd сумел построить решение в 15 операций для 26!. Мне это до сих пор не удалось сделать.

[Nataly-Mak]

А, ну да сначала dmd предложил упаковку для вашего полинома, а потом вы раскололись:

Pavlovsky в сообщении #693495 писал(а):

dmd
Классная работа! Не думал, что все будет так просто. Может поделишься как делал преобразования?
Задача появилась так. Если в выражение подставить x=36, то получим 26! Само выражение получилось из решения длиной 16 операций. Сравниваю ваше решение со своим, отличия конечно есть, но есть и много совпадений.

Извините, немного нарушила последовательность событий. Запамятовала малость
Но суть-то от этого не изменилась.

-- Вт мар 19, 2013 13:19:23 --

Pavlovsky в сообщении #698078 писал(а):

Кстати dmd сумел построить решение в 15 операций для 26!. Мне это до сих пор не удалось сделать.

Вот о том и речь: искусство упаковки полиномов очень хитрое.

[Pavlovsky]

Nataly-Mak в сообщении #698080 писал(а):

Вот о том и речь: искусство упаковки полиномов очень хитрое.

После того, как dmd хитро воспользовался моей недальновидностью, я больше полиномами не разбрасываюсь.

[Nataly-Mak]

Ну, так это же не впервой
В конкурсе с раскрасками вы давали подсказки пачками; при этом не всегда получали из своей идеи оптимальный результат (яркий пример: n-символьная строка для C=10; зыбыла, сколько в ней было символов, то ли 84, то ли 87).

Любите вы выкладывать свои идеи. Я только "за"
Сама выкладываю всё, что у меня есть; мне не жалко, пусть пользуются все, кто умеет.