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

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

 На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
 Печатать страницу | Печатать всю тему Пред. тема | След. тема

 Re: Al Zimmermann's: Statue of Liberty06.04.2020, 11:53

25/08/12
167
Germany
 A complete run of 76^16 to search for solution with an error less than 3^16 takes 110s on my machine. I do not use tables yet, though I have plenty of RAM (64 GB) installed on my machine. But if you say that the speed only increases by a factor of 4 I think I will not implement the idea of prestoring all values generated by the 24 or 25 smallest powers. I stopped my computations meanwhile and wait for some better idea to come into my mind. Not sure that this will happen ...

 Re: Al Zimmermann's: Statue of Liberty06.04.2020, 15:22

01/06/12
1006
 Последний раз редактировалось dimkadimon 06.04.2020, 15:48, всего редактировалось 3 раз(а). Herbert Kociemba в сообщении #1451826 писал(а):A complete run of 76^16 to search for solution with an error less than 3^16 takes 110s on my machine. I do not use tables yet, though I have plenty of RAM (64 GB) installed on my machine. But if you say that the speed only increases by a factor of 4 I think I will not implement the idea of prestoring all values generated by the 24 or 25 smallest powers. I stopped my computations meanwhile and wait for some better idea to come into my mind. Not sure that this will happen ...Wow that's blazing fast! I have no idea how you have done that, because I can only do $35^{16}$ in that time! Either Java's BigInteger class is so terribly slow or you are using some very clever pruning tricks. Or maybe recursion is making it too slow?! Need to investigate.This problem is really defeating me like no other before it. Nothing I try has even remotely come to beating the trivial solutions. I have spent a good 2 weeks on this, writing almost 1000 lines of code.

 Re: Al Zimmermann's: Statue of Liberty06.04.2020, 15:45

06/04/20
4
 Цитата:Wow that's blazing fast! I have no idea how you have done that, because I can only do $35^{16}$ in that time! Either Java's BigInteger class is so terribly slow or you are using some very clever pruning tricks.I can confirm that this has nothing to do with Java, I'm using BigInteger as well and my code does $76^{16}$ in 33s...But that still isn't nearly enough speed to get good scores sadly... I really need to do something smarter and I'm intrigued by the problems/algorithm's jcmeyrignac was referring to... can we get another hint? (pie-cutting was already a hint?)

 Re: Al Zimmermann's: Statue of Liberty06.04.2020, 15:49

01/06/12
1006
 royvanrijn в сообщении #1451914 писал(а):I can confirm that this has nothing to do with Java, I'm using BigInteger as well and my code does $76^{16}$ in 33s...Thank you Roy. This gives me some hope. Oh and welcome to our friendly forums :)

 Re: Al Zimmermann's: Statue of Liberty06.04.2020, 16:47

07/06/16
38
Омск
 Я тоже использую Java и BigInteger класс.

 Re: Al Zimmermann's: Statue of Liberty06.04.2020, 18:30

16/08/05
1119
 Оказывается задачу s^n=sum((s-1)^n+...) можно описать как линейную над бинарным полем переменных размерностью s-1.(Оффтоп) В MiniZinc солверами COIN-BC и SCIP получилось решить 40^7. Для больших степеней и оснований нужна поддержка солвером либы типа GMP. Формально только SCIP имеет поддержку GMP, но к сожалению косячит в вычислениях.

 Re: Al Zimmermann's: Statue of Liberty06.04.2020, 19:47

07/06/16
38
Омск
 Ещё раз спасибо Херберту что поделился своими данными о быстродействии. Я начал перепроверять алгоритм и нашёл одно условие для ограничения перебора, которое было неоптимально. Теперь алгоритм стал быстрее ещё примерно в 1,7 раза. 76^16 теперь выполняется за 50 секунд.Правда я выяснил что часть приближённых значений я могу потерять с вероятностью порядка 1/1E16, но мне кажется что это допустимая величина.Я использую два компьютера: один четырёхъядерный A10-5700 с 16ГБ ОЗУ, второй - R5 2600 c 20ГБ ОЗУ (второй я собирал специально под эту задачу). На первом быстродействие ограничивается процессором, на втором - быстродействием ОЗУ. Вот про память я не подумал. Жаль что сейчас карантин и все компьютерные магазины закрыты, а иначе можно было бы докупить планку 16ГБ.

 Re: Al Zimmermann's: Statue of Liberty06.04.2020, 21:03

06/04/20
4
 Hello everybody.I decided I have been lurking around here for too long (using google translate).Anyway, runtime can be improved quite a bit. A. I am using C, the only thing faster is assembler.B. No need for bigint libraries, just write proper efficient code (Hint: only need addition, subtraction, and comparison, those are rather basic algorithms ...)C. Precomputed Tables indeed are useful .D. Dmitry I think you missed some search pruning if you have too high a result ...Using the above search for 76^16 is about 2 secs. However search for 83^16 is 30 secs and 86^16 is more than two minutes. So its not good enough for reaching the top four, they have something else ....

 Re: Al Zimmermann's: Statue of Liberty07.04.2020, 03:45

01/06/12
1006
 Archimedes в сообщении #1451772 писал(а):А пока сделал оптимизацию алгоритма, запихав низ таблицы сумм в индексированный массив 2^25, из которого находится ближайшие верхнее и нижнее приближения решения.Я думаю это очень мощная идея и тоже хочу попробовать. Я так понял что массив сортированный и самые близкие решения к данной сумме находятся через бинарный поиск?

 Re: Al Zimmermann's: Statue of Liberty07.04.2020, 11:36

20/01/13
62
 royvanrijn в сообщении #1451914 писал(а):I really need to do something smarter and I'm intrigued by the problems/algorithm's jcmeyrignac was referring to... can we get another hint? (pie-cutting was already a hint?)Hint: IR

 Re: Al Zimmermann's: Statue of Liberty07.04.2020, 13:42

01/06/12
1006
 What does that mean?!?

 Re: Al Zimmermann's: Statue of Liberty07.04.2020, 20:08

07/06/16
38
Омск
 Последний раз редактировалось Archimedes 07.04.2020, 20:17, всего редактировалось 2 раз(а). dimkadimon в сообщении #1452177 писал(а):Я так понял что массив сортированный и самые близкие решения к данной сумме находятся через бинарный поиск?Да, всё правильно.-- 07.04.2020, 23:15 --porcoroso в сообщении #1452063 писал(а):However search for 83^16 is 30 secs and 86^16 is more than two minutes. So its not good enough for reaching the top four, they have something else ....Thank you for information.I suppose 25x speedup is enough argument to write a program in C.PS I hope your nickname is not a hint of our communist past...

 Re: Al Zimmermann's: Statue of Liberty07.04.2020, 20:28

06/04/20
4
 Цитата:porcoroso в сообщении #1452063 писал(а):search for 83^16 is 30 secs and 86^16 is more than two minutes. So its not good enough for reaching the top four, they have something else ....Thank you for information.I suppose 25x speedup is enough argument to write a program in C.Hey, my code now does 83^16 in 180 secs, still not the same... but not an automatic 25x speedup (look at me, championing Java as a "Java Champion" should) I suggest focussing on pruning, a bit of caching perhaps, but most of all: creating a new algorithm, exhaustive search won't get you very far...Yesterday I had an epiphany, a completely new way of thinking about this contest, a fresh way to get the good scores, it was perfect. Coding the entire night, and finally, when I ran the code: much slower than the original code.But I didn't stop there, I added some improvements in code-layout, optimizing it, moving stuff around... and suddenly it hit me: the thing that was completely novel and innovative was in fact the same algorithm I already had... it did *exactly* the same thing, just in a different way. They are even about as fast in solving 83^16 for example. So yeah, how's your life?

 Re: Al Zimmermann's: Statue of Liberty08.04.2020, 07:50

01/06/12
1006
 Последний раз редактировалось dimkadimon 08.04.2020, 07:57, всего редактировалось 3 раз(а). Archimedes в сообщении #1451772 писал(а):А пока сделал оптимизацию алгоритма, запихав низ таблицы сумм в индексированный массив 2^25Кстати если выбросить 1, то можно сделать массив такого же размера (2^25) для чисел от 2 до 26. 1 всегда можно потом без проблем добавить если надо.-- 08.04.2020, 13:39 --Archimedes в сообщении #1452456 писал(а):PS I hope your nickname is not a hint of our communist past...Perhaps his nickname refers to this cool Japanese cartoon: https://en.wikipedia.org/wiki/Porco_Rosso-- 08.04.2020, 13:40 --royvanrijn в сообщении #1452459 писал(а):But I didn't stop there, I added some improvements in code-layout, optimizing it, moving stuff around... and suddenly it hit me: the thing that was completely novel and innovative was in fact the same algorithm I already had... it did *exactly* the same thing, just in a different way. They are even about as fast in solving 83^16 for example. So yeah, how's your life?This is very unfortunate, but it happens to me very frequently. So don't feel bad. In fact you have learned something useful and now you won't repeat this mistake ;)

 Re: Al Zimmermann's: Statue of Liberty08.04.2020, 10:16

06/04/20
4
 Yes, that Cartoon is great ! Try and see it if you can, to let of some steam Roy ...Otherwise I'm pretty stuck, as the modulo approach Herbert suggested does not seem to lead anywhere, JCM hints are too cryptic, and anyway I'm not that great at number theory / algebraic geometry like the Paulsen guys ...Anyway, now I had some doubts maybe my program is too fast, i.e I have bug, so would like to ask somebody's verificationby an example that is not in contest (for 15) . So for 80^15 I get:80^15=>{74,73,70,69,67,66,64,62,54,53,52,51,50,49,47,45,44,39,37,36,33,30,29,28,26,22,20,18,17,16,14,13,12,10,8,7,5,4,3,2,1}as optimal with minimal error 2917618The hopefully full search takes 20 seconds but the solution is found after 0.5 secs.Can anyone here verify that at least this data point is correct ?

 Показать сообщения за: Все сообщения1 день7 дней2 недели1 месяц3 месяца6 месяцев1 год Поле сортировки АвторВремя размещенияЗаголовок по возрастаниюпо убыванию
 Страница 3 из 7 [ Сообщений: 96 ] На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.

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

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

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

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

 Найти: