CPP_LECTS_RUS Telegram 120
Дополнения к семинару 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
🔥30👍131😁1



tgoop.com/cpp_lects_rus/120
Create:
Last Update:

Дополнения к семинару 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

BY C++ and other lectures


Share with your friend now:
tgoop.com/cpp_lects_rus/120

View MORE
Open in Telegram


Telegram News

Date: |

Judge Hui described Ng as inciting others to “commit a massacre” with three posts teaching people to make “toxic chlorine gas bombs,” target police stations, police quarters and the city’s metro stations. This offence was “rather serious,” the court said. Administrators The group’s featured image is of a Pepe frog yelling, often referred to as the “REEEEEEE” meme. Pepe the Frog was created back in 2005 by Matt Furie and has since become an internet symbol for meme culture and “degen” culture. Hashtags Telegram offers a powerful toolset that allows businesses to create and manage channels, groups, and bots to broadcast messages, engage in conversations, and offer reliable customer support via bots.
from us


Telegram C++ and other lectures
FROM American