C++ and other lectures

В семинаре 2.3 кто-то мог в конце пропустить небольшой шедевр от одного из студентов. Вот чуточку причёсанная мной но близкая к оригиналу студенческая трактовка Problem FT. Определяет простоту числа через тест Ферма. https://godbolt.org/z/PsvMs3fG1 Обратите внимание: программа совершенно корректно справляется с 49979687 (простое) и с 271747319 (составное 15791×17209). Разумеется проблема тут в том что вместо настоящего случайного числа rand() использован просто адрес функции rand и он себя показывает неплохим случайным числом (!) Но давайте заметим ещё кое-что, чего я на семинаре не упомянул. Именно в этом коде замена rand на rand() способна ухудшить ситуацию. Кто увидит почему? Кто также назовёт ещё одну потенциальную проблему в этом коде из-за которой (даже при rand() как вызове) на самом деле легко подобрать тест который не будет пройден?

Заканчиваем семинар посвященный времени и памяти: разбираем функции для работы со временем и псевдослучайные числа. Начинаем со времени, знакомимся с функциями для работы с ним. Далее мы мотивируем рандомизированные алгоритмы и знакомимся с псевдослучайными числами. После перерыва на решение задач я также разберу структуры и побитовое решето с прошлого семинара. https://youtu.be/qpSCYugCknk

Вторая часть второго логического семинара посвящена работе с отдельными битами. Мы начнём с мотивирующего примера решета с побитовым хранением признаков и разберем многие интересные битовые трюки и техники. https://youtu.be/ZizuOhdl5oA Когда я записывал семинар у меня был небольшой насморк, что особенно заметно во второй части. Я даже по аудитории в перерыве ходил в маске чтобы не перезаражать особо студентов. Надеюсь это не сильно сказалось на качестве записи.

В продолжение предыдущего поста выношу из комментариев обстоятельный диалог с нейросетью на тему упрощения алгебраических выражений. Я хотел добиться, чтобы мне упростили a * c - a * d - b * c - e * f + e * d + b * f до (a - b) * (c - d) - (e - b) * (f - d). Там сначала разминочный вопрос который сетка с лёгкостью прошла, а вот дальше... https://chat.openai.com/share/8894392f-253b-4ade-a059-d2dad90619da У меня не получилось. Хочется обратиться к экспертам в инжиниринге запросов на моём канале. А вы сможете добиться от нейросети правильного ответа? #llm #questions

Интересный пример предварительной пессимизации (или несовершенства компиляторов, как посмотреть), инспирированный решением одного моего студента. https://godbolt.org/z/qa59c5MM1 Тут очевидно, что функция double_area делает то же самое, что wicked_double_area (если раскрыть скобки). Мало того, весь контекст локальный и всё доступно для оптимизаций. Но и clang и gcc не справляются — в генерированном коде получается шесть умножений против двух. Кто возьмётся исследовать что происходит? #questions

Начинаем второй логический семинар по языку C. Он будет также из трёх частей и будет посвящён времени и памяти. В первой его части мы разберёмся с двумя крайне важными концепциями -- со структурами в языке и с асимптотикой алгоритмов. Для иллюстрации и того и другого я выбрал простые числа. https://youtu.be/duVH3_hp60I

Начинаем второй семинар по языку C. https://youtu.be/duVH3_hp60I #c_graduate

Я иногда устраиваю для ребят так называемые "допсеминары". Это с моей стороны чистая благотворительность — предложение собраться у меня в офисе, обычно в выходной, чтобы я рассказал о чём-нибудь интересном. Студенты не обязаны туда приходить и на их успеваемость это никак не влияет (вообще я и на обычных занятиях надеюсь, что они взыскуют более знаний чем оценок). Тем не менее для видеозаписи полного курса, я склонен включить этот допсеминар в курс, так как он на самом деле очень важный. Также в курс запланирован допсеминар про сборку и некоторые другие, которым ещё предстоит быть прочитанными (если студенты на них придут, разумеется). https://youtu.be/KLv-5jWlKjM В этом видео речь пойдёт о работе в консоли. Мы научимся работать с пакетным менеджером, узнаем основы идеологии Unix, научимся писать сначала однострочники, а потом и полноценные bash-скрипты, освоим несколько консольных супероружий, таких как grep sed и awk и многое другое. В конце мы с некоторой грустью поймём границы применения техники. #c_graduate

Третья и завершающая часть первого семинара по языку C, https://youtu.be/qaCsf7wOpRQ Мы продолжаем практиковаться в азах языка C и программирования. На этот раз мы посмотрим на простые и красивые алгоритмы связанные с числами Фибоначчи. Мы увидим случай когда математика заводит нас в алгоритмический тупик, разберемся с переполнениями беззнаковых типов, изобретём интересную систему счисления, а в конце — сыграем в игру, в которой очень легко победить. А впереди нас ждёт допсеминар по Unix Shell, запись которого я выложу в ближайший вторник. #c_graduate

Дополнения к семинару 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 Было бы интересно если бы кто-нибудь исследовал корректность такого рода оптимизации. Мы явно ухудшаем размер кода, но неясно будет ли хотя бы теоретически выигрыш в быстродействии.

Очень интересный вопрос, выношу из комментариев на youtube. Что если мы попытаемся обобщить русское крестьянское возведение в степень до гауссовых нумералов? То есть до комплексных чисел с целыми действительной и мнимой частями. При этом допустим мы всё ещё хотим результат по модулю m, благо для гауссовых нумералов он определён. Обычное возведение в комплексную степень комплексных чисел делается через экспоненту и логарифм, но это плавающая арифметика и там мы потеряем точность. Задал вопрос на stackexchange https://cs.stackexchange.com/questions/162098/raise-gaussian-integer-to-gaussian-integer-power Просьба кидать в этот тред (или можете сразу на stackexchange) ваши идеи для такого алгоритма.

Вторая часть первого семинара по основам C. https://www.youtube.com/watch?v=oWGrH0R8iwU Мы продолжаем изучать основы программирования на C. На этом семинаре будут разобраны системы счисления. Чтобы проще делать перевод между системами счисления, мы введём понятие массива. Кроме того мы сразу же используем системы счисления для построения алгоритма эффективного возведения в степень по модулю. Также мы разберём расширенный алгоритм Евклида который я давал на дом в прошлый раз и посмотрим очень красивое построение рекуррентности для решения этой задачи.

Выложил запись первого семинара по основам C https://youtu.be/7YhRFx-oyW4 Буду стараться выкладывать в субботу утром, но это пилотный выпуск и я задержался с монтажом. Разумеется надо будет посмотреть как зайдёт. Небольшой дисклеймер: это не лекции. Я считаю что студенты ходят на лекции по C и их веду не я. Но я объясняю достаточно теории чтобы можно было вместо лекций просто читать Кернигана и Ричи и всё понимать. Записывать это куда сложнее чем записывать лекции. Я выбрал такой вариант: на семинаре я первые минут 30-40 что-то говорю и даю задание на семинар. Потом студенты примерно 1.5 часа решают задачи и это на видео не попадает. И в конце я снова беру слово. Так что запись поделена местом где нужно остановить видео и тоже решать задачи.

Немного о планах на предстоящий учебный год. Ссылки на стримы бакалаврского и магистерского курса будут выкладываться в дискорд в соответствующие текстовые каналы: https://discord.gg/vSEp8yW В стримах возможно удалённое участие, также будут оставаться записи. Я очень надеюсь что получится сделать наконец-то запись и выкладку на Youtube (в хорошем качестве и с видео) пояснительной части моих семинаров по языку C и ассемблеру. Идея того как мы это будем делать проработана, материал давно готов. Пилотную запись надеюсь сделать в первой половине сентября, дальше по графику. Если всё получится, ссылки на записи будут появляться здесь. Также напоминаю, что если вы нашли интересный материал, интересное видео, у вас есть интересный вопрос и т.д. вы можете писать мне в лс, и, если я соглашусь, что это действительно интересно, я вполне могу сделать на этом канале ветку для обсуждения.

В прошлую субботу выступил на Zero Cost Conf Обновлю этот пост когда они нарежут видео для своего сайта, но я прождал неделю и этого не случилось, так что пока придётся смотреть по таймкоду =) Если кратко, то из всех конференций этого лета эта была лучше прочих организована. Формально она была бесплатная, реально Яндекс не поскупился. Меня даже загриммировали, чтобы я не бликовал, это невероятно. https://www.youtube.com/watch?v=B9iR13VyP-c&t=4046s

Всем привет. Через две недели выступаю вот здесь: https://cppzerocostconf.yandex.ru/cxxzerocostconf_2023 с докладом про векторизацию. Сначала разберём всю боль обычной векторизации, повекторизуем руками некоторые вещи. Потом я представлю масштабируемую векторизацию, это новая концепция которая сейчас набирает обороты в ARM и RISCV. Посмотрим как она решает проблемы. А потом поговорим о том как она создаёт проблемы. Можно рассматривать это как продолжение записанного мной прошлым летом допсеминара про SIMD, см. https://t.me/cpp_lects_rus/27 Вход на площадку свободный, но по регистрации. Которую можно пройти уже сейчас. Меня пока в программе нет, но я появлюсь, доклад согласовали. #conference

Выложили по ссылке мой второй вебинар проведённый в рамках программы вебинаров Российского Альянса RISCV для различных университетов. Кратко рассказываю про инструменты разработчика от начала до конца. В начале рассказываю чем компилятор от линкера отличается. В конце загружаю RISCV Linux на System QEMU. Всё это за полчаса, поэтому плотненько. https://www.youtube.com/watch?v=29iNHEhHmd0 Дальнейшие вебинары там будут вести уже другие спикеры (мы изначально договаривались что мои там первые две лекции). Общий плейлист для желающих следить: https://www.youtube.com/playlist?list=PLJujc0We8tx80x0z8W6v68Iotteb4wK3W

Выложили по ссылке моё выступление на C++Russia 2023. Выступление было на конференции отлично принято коллегами и набрало массу лестных отзывов и высоких оценок. Теперь можно представить его более широкой аудитории. https://www.youtube.com/watch?v=lc3UkIZ4zOY&t=110s В языке C++ есть синтаксис и семантика. Когда мы говорим о синтаксисе, мы говорим о контекстно-независимых конструкциях, которые просто что-то означают. Например, if — это всегда if. Но когда мы говорим о семантике, мы сталкиваемся с необходимостью для компилятора что-то сделать или что-то выяснить: разрешить имя, инстанцировать шаблон, вывести тип, вычислить константное выражение. Можно сказать что в каждый такой момент мы стартуем некий процесс, развивающийся по своим правилам. Этот доклад посвящен описанию взаимодействующих семантических процессов в языке, как с точки зрения внутренностей компилятора, так и с точки зрения стандарта языка.

Выложили по ссылке мой вебинар проведённый в рамках программы вебинаров Российского Альянса RISCV для различных университетов. Кратко рассказываю что такое RISCV и как устроена эта архитектура. Очень общий обзор. https://www.youtube.com/watch?v=3Jv9_jBq1fE В этой серии у меня также будет второй вебинар посвящённый конкретно средствам разработки под RISCV. #conference #toolchain