2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 59, 60, 61, 62, 63, 64, 65 ... 88  След.
 
 Re: Factorials
Сообщение23.04.2013, 06:57 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #714391 писал(а):
Блин, посмотреть за битвой с трибун? Или все таки вписаться в борьбу за "Bragging Rights"?!

А может, побороться за первое место с конца турнирной таблицы? :D

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


19/12/10
1546
Несмотря на мои насмешки над Gerbicz, признаю, что он достаточно хороший математик и талантливый программист. О чём уже писал ранее
whitefox в сообщении #647509 писал(а):
Вы к нему не справедливы.
Gerbicz вполне хороший математик и талантливый программист.
Вот только характер у него склочный.

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

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


22/03/08

7154
Саратов

(Оффтоп)

whitefox в сообщении #714396 писал(а):
Несмотря на мои насмешки над Gerbicz, признаю, что он достаточно хороший математик и талантливый программист. О чём уже писал ранее.

"Не лучше ли при жизни быть приличным человеком?" (c) В. Высоцкий

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


21/02/10
1594
Екатеринбург
whitefox в сообщении #714396 писал(а):
Но ведь это закон жизни: если где-то прибыло, то в другом месте убыло.


Вот только на этом форуме Gerbicz почему то всегда поворачивается тем местом где убыло.

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


22/03/08

7154
Саратов

(Оффтоп)

"Да, я везде. Да, я гений. Смотрите, я здесь первый! И здесь я победил."
Это смысл его сообщений, переданный моими словами, но абсолютно точно.

Цитата:
Rank Score Contestant Last Improvement
1 1.000 Helge Keller Karlsruhe, Germany 20 Apr 2013 16:13
2 1.000 Jarek Wroblewski Wroclaw, Poland 20 Apr 2013 16:30
3 1.000 Robert Gerbicz Halasztelek, Hungary 20 Apr 2013 16:52

Без комментариев...

 Профиль  
                  
 
 Re: Factorials
Сообщение23.04.2013, 07:15 
Аватара пользователя


01/06/12
1013
Adelaide, Australia
Pavlovsky в сообщении #714391 писал(а):
Блин, посмотреть за битвой с трибун? Или все таки вписаться в борьбу за "Bragging Rights"?!


Конечно вписаться!

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


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

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


19/12/10
1546
Pavlovsky в сообщении #714398 писал(а):
Вот только на этом форуме Gerbicz почему то всегда поворачивается тем местом где убыло.

Почему только на этом форуме? :lol:
Вы опять к нему не справедливы :D
Он так поступает везде.

 Профиль  
                  
 
 Re: Factorials
Сообщение23.04.2013, 07:18 
Аватара пользователя


21/02/10
1594
Екатеринбург
А вольфрам (вольфрам еще называют железякой :D ) спокойно работает с 1000!
$1000!=2^{994}*3^{498}*5^{249}*7^{164}*11^{98}*13^{81}*17^{61}*19^{54}*23^{44}
*29^{35}*31^{33}*37^{27}*41^{24}*43^{23}*47^{21}*53^{18}*59^{16}*61^{16}*67^{14}
*71^{14}*73^{13}*79^{12}*83^{12}*89^{11}*97^{10}*101^9*103^9*107^9*109^9*113^8*127^7
*131^7*137^7*139^7*149^6*151^6*157^6*163^6*167^5*173^5*179^5*181^5*191^5*193^5*197^5
*199^5*211^4*223^4*227^4*229^4*233^4*239^4*241^4*251^3*257^3*263^3*269^3*271^3*277^3
*281^3*283^3*293^3*307^3*311^3*313^3*317^3*331^3*337^2*347^2*349^2*353^2*359^2*367^2
*373^2*379^2*383^2*389^2*397^2*401^2*409^2*419^2*421^2*431^2*433^2*439^2*443^2*449^2
*457^2*461^2*463^2*467^2*479^2*487^2*491^2*499^2*503*509*521*523*541*547*557*563*569
*571*577*587*593*599*601*607*613*617*619*631*641*643*647*653*659*661*673*677*683*691
*701*709*719*727*733*739*743*751*757*761*769*773*787*797*809*811*821*823*827*829*839
*853*857*859*863*877*881*883*887*907*911*919*929*937*941*947*953*967*971*977*983*991*997$

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


01/06/12
1013
Adelaide, Australia
whitefox в сообщении #714396 писал(а):
Несмотря на мои насмешки над Gerbicz, признаю, что он достаточно хороший математик и талантливый программист. О чём уже писал ранее


Согласен у него есть большой талант, только очень жалко что он так себя ведёт и этим "портит всю картину". Кстати я думал что рекорд будет не меньше 350, а уже 292!

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


22/03/08

7154
Саратов
dimkadimon в сообщении #714400 писал(а):
Jarek построил 297 как я понял практически вручную!

Jarek действительно гигант. Восхищаюсь!

И при этом он нигде не выпячивает свои заслуги.

-- Вт апр 23, 2013 08:25:02 --

Pavlovsky в сообщении #714402 писал(а):
А вольфрам (вольфрам еще называют железякой :D ) спокойно работает с 1000!

Ага, я выше приводила разложение

$1000! = A \cdot (500!)^2$

в Вольфраме. Число А имеет всего 300 десятичных знаков :-)
Так что, можно начать строить решение для 500!, потом к нему добавить число А.
А построение решения для 500! можно начинать с построения решения для 250!
И так далее :wink:

Кстати, я читаю сообщения Gerbicz без перевода, это даёт мне прекрасную возможность многое не понимать :D
Так вот, без перевода поняла следующее: у него есть Бейсик, который спокойно может составить решение для 1016!
Мне бы такой Бейсик :-)
Да плюс ещё кластер (который, я не сомневаюсь, у Gerbicz тоже есть).

Сравниваю производительность своей машины и машины mertz. Примерно в 20 раз.
Поиск решений с добавлением 4 шагов у него выполнялся несколько минут, а у меня 2-3 часа. Поиск решений с добавлением 5 шагов у него выполнялся до 12 часов, у меня это будет уже несколько суток. По одной программе!
Разве не очевидно, что многое решает техника? Особенно в задачах с преобладанием перебора.

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


19/12/10
1546
Raw Score -- это Равиль Скорина? :D

-- 23 апр 2013, 08:36 --

(dimkadimon)

dimkadimon в сообщении #714403 писал(а):
этим

Нашли клаву с русской буквой "э"? :-)

 Профиль  
                  
 
 Re: Factorials
Сообщение23.04.2013, 07:38 
Заблокирован


21/04/13

78
whitefox в сообщении #714388 писал(а):

(Оффтоп)

wanderers в сообщении #714351 писал(а):
Ребята, чего вам неймется? Я выложил описание алгоритма, решающего проблему, поставленную на конкурсе.

Выше уже отмечалось, что Ваше описание Вашего алгоритма из того же разряда, что и описание данное Ферма его Великой теореме.

Пока по поводу моего алгоритма я получил вопросы только от dimkadimon и ему ответил: надо быть либо не в теме, либо не знаю, кем, чтобы не понять, какие таблицы строить. Что касается базы данных, то она никакого отношения к описанному алгоритму не имеет и отвечать о деталях ее построения я не подряжался: поищите халяву в другом месте.

 Профиль  
                  
 
 Re: Factorials
Сообщение23.04.2013, 07:40 
Аватара пользователя


21/02/10
1594
Екатеринбург
Алгоритм разбиваем на два этапа.
1) Строим все простые числа.
2) Используя только операцию умножения, строим из простых чисел 1000!

Есть 162 простых числа меньше 1000. То есть после первого этапа у нас будет последовательность длиной 162 плюс небольшие накладные расходы. На втором этапе пользуемся теоремой Оливоса. У нас получится 162(это неверно надо 324) умножения плюс небольшие накладные расходы. Итого получается 324 (это неверно надо 486) операции плюс небольшие накладные расходы.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #714409 писал(а):
Алгоритм разбиваем на два этапа.
1) Строим все простые числа.
2) Используя только операцию умножения, строим из простых чисел 1000!

Есть 162 простых числа меньше 1000. То есть после первого этапа у нас будет последовательность длиной 162 плюс небольшие накладные расходы. На втором этапе пользуемся теоремой Оливоса. У нас получится 162 умножения плюс небольшие накладные расходы. Итого получается 324 операции плюс небольшие накладные расходы.

Что-то я не поняла, разве все простые числа входят в разложение 1000! в первой степени?
Я посмотрела факторизацию 1000!, там степени у простых чисел ого какие.

 Профиль  
                  
 
 Re: Factorials
Сообщение23.04.2013, 07:57 
Аватара пользователя


21/02/10
1594
Екатеринбург
Выпишем степени простых чисел из разложения на простые множители 1000!

Код:
994,498,249,164,98,81,61,54,44,35,33,27,24,23,21,18,16,14,13,12,11,10,9,8,7,6,5,4,3,2,1


Если бы эта последовательность была аддитивной (показанная последовательность написана задом на перед), тогда по теореме Оливоса у нас было бы 162 умножения. А так придется в последовательность добавить еще несколько чисел, что бы последовательность стала аддитивной. Надо добавить совсем немного 5-6 чисел.

-- Вт апр 23, 2013 10:03:03 --

Ой соврал. умножений потребуется 2*162=324 плюс накладные расходы. Итоговая длина последовательности получается 3*162=486 плюс накладные расходы. Много!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 59, 60, 61, 62, 63, 64, 65 ... 88  След.

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



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

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


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

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