Дополнения к семинару 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
Я сегодня уже выкладывал и стирал этот пост т.к. он был не идеален. Теперь надеюсь останется.
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