Al Zimmermann's: Statue of Liberty

[Herbert Kociemba]

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 ...

[dimkadimon]

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.

[royvanrijn]

Цитата:

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?)

[dimkadimon]

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 :)

[Archimedes]

Я тоже использую Java и BigInteger класс.

[dmd]

Оказывается задачу s^n=sum((s-1)^n+...) можно описать как линейную над бинарным полем переменных размерностью s-1.

(Оффтоп)

В MiniZinc солверами COIN-BC и SCIP получилось решить 40^7. Для больших степеней и оснований нужна поддержка солвером либы типа GMP. Формально только SCIP имеет поддержку GMP, но к сожалению косячит в вычислениях.

[Archimedes]

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

[porcoroso]

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 ....

[dimkadimon]

Archimedes в сообщении #1451772 писал(а):

А пока сделал оптимизацию алгоритма, запихав низ таблицы сумм в индексированный массив 2^25, из которого находится ближайшие верхнее и нижнее приближения решения.

Я думаю это очень мощная идея и тоже хочу попробовать. Я так понял что массив сортированный и самые близкие решения к данной сумме находятся через бинарный поиск?

[jcmeyrignac]

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

[dimkadimon]

What does that mean?!?

[Archimedes]

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...

[royvanrijn]

Цитата:

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?

[dimkadimon]

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 ;)

[porcoroso]

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 verification
by 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 2917618

The 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 ?