C++ and other lectures

Дополнения к семинару 1.2

Я сегодня уже выкладывал и стирал этот пост т.к. он был не идеален. Теперь надеюсь останется.

1.2.1.

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

Интересно что я не сразу это понял сам, хотя если бы меня попросили посчитать i в степени i у меня не было бы проблем. К счастью мне всё объяснили: https://cs.stackexchange.com/questions/162098

1.2.2.

Многие заметили что наивное обобщение русского крестьянского умножения и возведения в степень перестаёт работать на сверхстепень и в этом смысле проблема RPS коварна. Всё дело в том, что шагом для возведения в степень является умножение и для умножения (a * b) mod m = ((a mod m) * (b mod m)) mod m. Но для возведения в сверхстепень шагом должно являться возведение в степень, а там это очевидно не так.

Простой контрпример:
(2 ^ 4) mod 5 = 1
(2 ^ 9) mod 5 = 2

То есть кажется RPS надо бы пометить звёздочкой. Тем не менее тесты к этой задаче допускают тривиальное решение -- там просто нигде нет слишком большого показателя сверхстепени и достаточно уметь быстро возводить в степень и писать обычные циклы.

1.2.3.

Один из студентов сделал интересное решение проблемы NS, не использующее дополнительного массива, а вместо этого использующее обратный ход рекурсии: https://youtu.be/oWGrH0R8iwU?t=3508

Интересно, что компиляторы gcc и clang сильно расходятся в вопросе оптимизации этого кода: clang на O3 не делает ничего. Что делает на O3 gcc я бы охарактеризовал как двойной прыжок с переворотом в воздухе: https://godbolt.org/z/o6bjs3aP1

Было бы интересно если бы кто-нибудь исследовал корректность такого рода оптимизации. Мы явно ухудшаем размер кода, но неясно будет ли хотя бы теоретически выигрыш в быстродействии.

#c_graduate

🔥29👍13❤1😁1

7.1K viewsedited 20:54