2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 67, 68, 69, 70, 71, 72, 73 ... 88  След.
 
 Re: Factorials
Сообщение26.04.2013, 18:48 


02/11/12
141
Код:
+ addition

Код:
* multiplication


Код:
No + in your example.


illogical name.

 Профиль  
                  
 
 Re: Factorials
Сообщение26.04.2013, 19:01 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Почему нелогичное название?

Цитата:
Дана аддитивная последовательность:
v = (1,2,3,6,12,24,30,31)

$2=1+1$
$3=1+2$
$6=3+3$
$12=6+6$
$24=12+12$
$30=6+24$
$31=1+30$

Все члены этой последовательности получены сложением. Поэтому последовательность называется аддитивной.

$5^2=5^1 \cdot 5^1= 5^{1+1}$
$5^3=5^1 \cdot 5^2=5^{1+2}$
$5^6=5^3 \cdot 5^3=5^{3+3}$

etc

Это другая аддитивная последовательность:

Код:
1,2,4,8,9,11,20,31

А это не аддитивная последовательность:

Код:
1,2,4,8,9,10,40,31

$40=4 \cdot 10$

 Профиль  
                  
 
 Re: Factorials
Сообщение26.04.2013, 19:34 
Заслуженный участник
Аватара пользователя


06/10/08
6422
mertz
An addition chain is a sequence of integers $a_0,a_1,\dots,a_l$ such that $a_0 = 1$ and each $a_i$ is a sum of two preceding elements.

But since the most important practical application of addition chains is fast exponentiation, they are often described in terms of multiplication of powers: if $a_0,a_1,\dots,a_l$ is an addition chain, then the sequence $x, x^{a_1}, \dots, x^{a_l}$ describes a program that raises $x$ to the power of $a_l$ using multiplications.

 Профиль  
                  
 
 Re: Factorials
Сообщение26.04.2013, 19:44 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Xaositect в сообщении #715948 писал(а):
... and each $a_i$ is a sum of two preceding elements.

В том и дело, что не всегда сумма двух предыдущих членов :-)
Именно это, видимо, и сбило с толку mertz в приведённой последовательности

Код:
1,2,3,6,12,24,30,31

Можно ведь считать, что 6=2*3, 12=6*2 и т.д.
Но также 6=3+3, 12=6+6 и т.д.

 Профиль  
                  
 
 Re: Factorials
Сообщение26.04.2013, 19:50 


02/11/12
141
Цитата:
Tom Rikicki --

For instance, the best length-37 solution I found ended in a
chain of 7 additions, so my primary search only had to consider a
depth of 13 operations.


For N < 20, is there and example of this. looking at all my solutions, they seem to end with 2- 6 multiplies.

 Профиль  
                  
 
 Re: Factorials
Сообщение26.04.2013, 23:26 
Заблокирован


20/10/12

85
The contest is over?

Jarek Wroblewski: "264 may be impossible to be reached by the human race, but I can believe it may be close to the actual optimum."

1 1.000 Robert Gerbicz Halasztelek, Hungary 26 Apr 2013 20:12
13 .264 Raw Score = 1000 Adelaide, Australia 20 Apr 2013 16:00

Probably no.

 Профиль  
                  
 
 Re: Factorials
Сообщение27.04.2013, 00:45 


02/11/12
141
Is anything less than 264 possible?

 Профиль  
                  
 
 Re: Factorials
Сообщение27.04.2013, 01:46 
Аватара пользователя


01/06/12
1013
Adelaide, Australia
Great work Robert. See how much further you can push it.

 Профиль  
                  
 
 Re: Factorials
Сообщение27.04.2013, 03:50 
Аватара пользователя


01/06/12
1013
Adelaide, Australia
На Yahoo я описал свой Dynamic Programming метод: http://tech.groups.yahoo.com/group/AlZi ... ssage/5629

Суть в том что мы можем решить упрощенную задачу: найти оптимальное SLP в котором все операции используют одно из чисел в последовательности S=a1, a2, ..., ai. Tо есть мы берем S и оптимально достраиваем еe до N! используя числа из S. Чтобы реализовать этот метод надо использовать условие что все числа делители N!.

 Профиль  
                  
 
 Re: Factorials
Сообщение27.04.2013, 04:47 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #715281 писал(а):
Вот когда Gerbicz молчит, он делает успехи:
Код:
1    1.000    Robert Gerbicz    Halasztelek, Hungary    25 Apr 2013 00:58
11    .270    Raw Score = 1000    Adelaide, Australia    20 Apr 2013 16:00
Или наоборот?
Когда делает успехи -- молчит :-)

whitefox
надеюсь, вы получили ответ на свой вопрос :D

Gerbicz в сообщении #716041 писал(а):
1 1.000 Robert Gerbicz Halasztelek, Hungary 26 Apr 2013 20:12
13 .264 Raw Score = 1000 Adelaide, Australia 20 Apr 2013 16:00

Насчёт рубежа в 250 шагов, который вас так сильно интересует...
Гении в сотрудничестве с марсианами с небольшой помощью кластера могут всё :D
Будет вам и 250 шагов.
Погодите чуток - будет и белка и свисток.
[насчёт белки --- бабушка надвое сказала, а вот свисток будет точно :wink: ]

P.S. За последние сутки кластер наскрёб всего одну операцию.

-- Сб апр 27, 2013 06:02:01 --

dimkadimon в сообщении #716120 писал(а):
На Yahoo я описал свой Dynamic Programming метод: http://tech.groups.yahoo.com/group/AlZi ... ssage/5629

Суть в том что мы можем решить упрощенную задачу: найти оптимальное SLP в котором все операции используют одно из чисел в последовательности S=a1, a2, ..., ai. Tо есть мы берем S и оптимально достраиваем еe до N! используя числа из S. Чтобы реализовать этот метод надо использовать условие что все числа делители N!.

А разве алгоритм, представленный Pavlovsky, не то же самое?
Вы писали, что с трудом нашли решение в 430 шагов.

Pavlovsky в сообщении #714391 писал(а):
Прибросил алгоритм для 1000! Построить решение длиной около 400 операций легко. Но я так понял лучшее решение сейчас в районе 300 операций.

dimkadimon в сообщении #714400 писал(а):
Мне было не так легко. Я с трудом построил 430. Лучшее сейчас 292. Jarek построил 297 как я понял практически вручную!

Pavlovsky по этому алгоритму нашёл решение в 389 шагов, как я понимаю, без особого труда.

-- Сб апр 27, 2013 06:30:17 --

У-р-р-р-а-а-а! В борьбу включился Алексей Чернов!

Цитата:
4 .721 Alex Chernov Penza, Russia 26 Apr 2013 19:32

Боле-е-е-ю-ю :wink: о-ч-ч-ч-е-н-ь.

Удачи вам, Алексей!

 Профиль  
                  
 
 Re: Factorials
Сообщение27.04.2013, 08:48 
Заслуженный участник
Аватара пользователя


19/12/10
1546
dimkadimon писал(а):
for k=1 to N!
for ai in S
V[k+ai]=min(V[k+ai],V[k]+1) //for addition
V[k*ai]=min(V[k*ai],V[k]+1) //for multiplication
end
end
dimkadimon писал(а):
I have successfully implemented this method and used it in my beam
search.
Только во внешнем цикле нужно выполнить порядка $4\cdot10^{2567}$ итераций.
Какой фильтр для $k$ Вы использовали?

-- 27 апр 2013, 09:52 --

Даже инициализация
dimkadimon писал(а):
V[k]=10000 for all k<=N!
займёт вечность.

-- 27 апр 2013, 10:01 --

dimkadimon писал(а):
k=1
while k<=N!
..next=k+1
..for ai in S
....V[k+ai]=min(V[k+ai],V[k]+1) //for addition
....V[k*ai]=min(V[k*ai],V[k]+1) //for multiplication

....if V[k]+1<V[abs(k-ai)] //for subtraction
......V[abs(k-ai)]=V[k]+1
......next=min(next,abs(k-ai)) //opportunity to go back
....end
..end
..k=next
end
Так, понятно, здесь мы уже не обязаны проходить по всем $k$.
Но проблема с инициализацией остаётся.
Да и хватит ли во Вселенной места, чтобы разместить массив V[k]?

 Профиль  
                  
 
 Re: Factorials
Сообщение27.04.2013, 10:05 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #716141 писал(а):
Даже инициализация
dimkadimon писал(а):
V[k]=10000 for all k<=N!
займёт вечность.

dimkadimon
я что-то вообще не понимаю, что за странный массив такой.
Объявляется некоторый одномерный массив по переменной k.
Но на фига он такой огромный? Неужели в программе будут использованы все элементы этого мамссива для k=1,2,3,...,N! :?:

-- Сб апр 27, 2013 11:15:50 --

Ещё одна хорошая новость - Jarek Wroblewski не стал зрителем:

Цитата:
2 .917 Jarek Wroblewski Wroclaw, Poland 27 Apr 2013 06:17

Молодец!

Так что, конкурс не закончился, господин юный Гений :D
Конкурс продолжается!

(Оффтоп)

Цитата:
Jarek Врублевский: "264 может быть невозможно быть достигнут человеческой расы, но я могу поверить, что она может быть близка к фактической оптимальной".

Здесь как бы намекается на вмешательство неземных цивилизаций :D
Созвучно предположению whitefox.

 Профиль  
                  
 
 Re: Factorials
Сообщение27.04.2013, 10:42 
Аватара пользователя


01/06/12
1013
Adelaide, Australia
whitefox
Метод которой я описал я создал для N<=37, не вижу как он может работать для N=1000. Я просматривал не все k, а только те которые делители N!. Поэтому размер массива V не такой большой как кажется. Если еще ограничить k тогда N>37 будет возможно.

 Профиль  
                  
 
 Re: Factorials
Сообщение27.04.2013, 11:31 
Заслуженный участник
Аватара пользователя


19/12/10
1546
dimkadimon в сообщении #716180 писал(а):
Я просматривал не все k, а только те которые делители N!. Поэтому размер массива V не такой большой как кажется.

1000! имеет порядка $3\cdot10^{106}$ делителей, что всё равно чудовищно много.
dimkadimon в сообщении #716180 писал(а):
Метод которой я описал я создал для N<=37, не вижу как он может работать для N=1000.

Думаю можно массив V заменить ассоциативным массивом.
Инициализацию V[k]=10000 for all k<=N! не выполнять,
выполнить только V[ai]=0 for all i.
В самом алгоритме рассматривать только те k для которых V[k] уже определено, то есть пара (k,V[k]) принадлежит ассоциативному массиву.

-- 27 апр 2013, 12:49 --

(Оффтоп)

Забавная игра слов:
Nataly-Mak в сообщении #716160 писал(а):
человеческой расы
в оригинале:
Gerbicz в сообщении #716041 писал(а):
human race
Словарь
race [reɪs]
/существительное/
1. гонка, гонок
(racing)
guv race — гонка GUV
2. раса, род, расовая принадлежность
(kind, ethnicity)
Sangik race — сангикская раса
human race — человеческий род
3. соревнование, состязание
(competition, contest)
horse races — конные соревнования

 Профиль  
                  
 
 Re: Factorials
Сообщение27.04.2013, 12:00 
Аватара пользователя


21/02/10
1594
Екатеринбург
Цитата:
264 may be impossible to be reached by the human race, but I can believe it may be close to the actual optimum.

Не согласен! :D
Очень грубо оценил потенциал подхода который я использую для решения задачи 1000!
Результат 300 операций практически гарантирован, нужно только время. 280 операций наиболее вероятный результат. 240 операций оптимистический прогноз, нужно что бы хорошо повезло.
И это в рамках подхода, который априори не ищет оптимального решения. И без учета возможности тонкой оптимизации последовательностей.
Полагаю, что оптимальное решение где то в районе 200 операций.

Повторяю, это очень грубая оценка. Требования предъявить доказательства и претензии когда прогноз не сбудется не принимаются! :D

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 67, 68, 69, 70, 71, 72, 73 ... 88  След.

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group