Сложите это, пожалуйста
Написав эту заметку про типы с плавающей точкой, вспомнил, что был и другой интересный случай с этими числами, правда, из практики собеседований, но не суть. Вопрос звучал примерно так: дан массив чисел типа double, как лучше его отсортировать (по возрастающей или убывающей), чтобы просуммировать его с большой точностью.
В этом вопросе, с точки зрения, обывателя или программиста, не вникшего в тонкости работы с этими числами, прекрасно абсолютно всё. Наверняка в школе, вы слышали о том, что перестановка мест слагаемых суммы не меняет (хотя бы в такой формулировке), если этому верить, значит задача лишена смысла. Но раз спрашивают, и я об этом пишу, наверное, смысл есть, но как так?
Начну издалека: когда нас в детстве учат устному счёту 1, 2, 3…нас учат натуральным числам N и их свойствам - числам, которыми я могу посчитать количество предметов, далее, “добавляя” к ним 0 и отрицательные числа, мы получаем Z - целые числа, “присоединяя” к ним обыкновенные дроби мы получаем множество Q – множество рациональных чисел , наконец, решая квадратные и не только уравнения и рассматривая другие конструкции, мы получаем множество вещественных чисел R (примеры, корень из двух, экспонента и так далее). Эту цепочку можно было бы продолжить: комплексные числа, дуальные, кватернионы, а в вещественных выделить алгебраические и трансцендентные…Но я не буду об этом говорить, потому что, они все не имеют отношения к тем числам, что мы имеем в C++ как базовый типы. Об этом немножечко позже.
Непосредственно с числами, даже каким-то образом со способом их определения, связанны основные арифметические операции: сложение, вычитание, умножение, деление. На эту заметку нам хватит сложения: даже эти операции не так уж элементарны…особенно деление. Бинарная операция сложения (т.е. принимающая два аргумента) для множеств N, Z, Q, R (на самом деле и все остальные как я помню, но это не важно) обладает свойствами коммутативности и ассоциативности. Коммутативность — значит всего лишь, что a+b = b+a, совсем просто, а вот ассоциативность, посложнее: a + (b+c) = (a+b) + c. Иными словами, операция у нас бинарная, мы умеет сложить 2 числа, а вот если написать, что мы складываем 3 числа, то можно сначала сложить первые 2, или последние 2, но результат будет одинаков. Если вы думаете, что это какая-то глупость и так всегда, то посмотрите на вычитание: (1 – 2) – 3 = -4, но 1 – (2 – 3) = 0 (вычитание не ассоциативно). На самом деле Z – это кольцо, Q, R – это поле, но мы с этим не будем работать.
В C++ (и во многих остальных ЯП), есть различные операторы, конечно, включая и арифметические, не буду тут давать формального определения оператора в С++, понятно, что это некоторая синтаксическая сущность, тут важно, что для всех операторов стандарт языка предоставляет информацию об их ассоциативности, а именно, либо слева направо, либо справа налево. Большинство слева направо, но нас интересует только operator +.
Прошу ещё раз заметить: в C++ a+b+c это (a+b) + c, то есть в математике, скобки я могу ставить, как угодно, а компилятор, видя выражение без скобок, неявно поставит их таким образом, то есть, на самом деле, нет там никаких скобок, а есть ассемблерные инструкции (картинки с https://godbolt.org/ будут под постами)
#IT #job #c_plus_plus #math #weird #interview
Написав эту заметку про типы с плавающей точкой, вспомнил, что был и другой интересный случай с этими числами, правда, из практики собеседований, но не суть. Вопрос звучал примерно так: дан массив чисел типа double, как лучше его отсортировать (по возрастающей или убывающей), чтобы просуммировать его с большой точностью.
В этом вопросе, с точки зрения, обывателя или программиста, не вникшего в тонкости работы с этими числами, прекрасно абсолютно всё. Наверняка в школе, вы слышали о том, что перестановка мест слагаемых суммы не меняет (хотя бы в такой формулировке), если этому верить, значит задача лишена смысла. Но раз спрашивают, и я об этом пишу, наверное, смысл есть, но как так?
Начну издалека: когда нас в детстве учат устному счёту 1, 2, 3…нас учат натуральным числам N и их свойствам - числам, которыми я могу посчитать количество предметов, далее, “добавляя” к ним 0 и отрицательные числа, мы получаем Z - целые числа, “присоединяя” к ним обыкновенные дроби мы получаем множество Q – множество рациональных чисел , наконец, решая квадратные и не только уравнения и рассматривая другие конструкции, мы получаем множество вещественных чисел R (примеры, корень из двух, экспонента и так далее). Эту цепочку можно было бы продолжить: комплексные числа, дуальные, кватернионы, а в вещественных выделить алгебраические и трансцендентные…Но я не буду об этом говорить, потому что, они все не имеют отношения к тем числам, что мы имеем в C++ как базовый типы. Об этом немножечко позже.
Непосредственно с числами, даже каким-то образом со способом их определения, связанны основные арифметические операции: сложение, вычитание, умножение, деление. На эту заметку нам хватит сложения: даже эти операции не так уж элементарны…особенно деление. Бинарная операция сложения (т.е. принимающая два аргумента) для множеств N, Z, Q, R (на самом деле и все остальные как я помню, но это не важно) обладает свойствами коммутативности и ассоциативности. Коммутативность — значит всего лишь, что a+b = b+a, совсем просто, а вот ассоциативность, посложнее: a + (b+c) = (a+b) + c. Иными словами, операция у нас бинарная, мы умеет сложить 2 числа, а вот если написать, что мы складываем 3 числа, то можно сначала сложить первые 2, или последние 2, но результат будет одинаков. Если вы думаете, что это какая-то глупость и так всегда, то посмотрите на вычитание: (1 – 2) – 3 = -4, но 1 – (2 – 3) = 0 (вычитание не ассоциативно). На самом деле Z – это кольцо, Q, R – это поле, но мы с этим не будем работать.
В C++ (и во многих остальных ЯП), есть различные операторы, конечно, включая и арифметические, не буду тут давать формального определения оператора в С++, понятно, что это некоторая синтаксическая сущность, тут важно, что для всех операторов стандарт языка предоставляет информацию об их ассоциативности, а именно, либо слева направо, либо справа налево. Большинство слева направо, но нас интересует только operator +.
Прошу ещё раз заметить: в C++ a+b+c это (a+b) + c, то есть в математике, скобки я могу ставить, как угодно, а компилятор, видя выражение без скобок, неявно поставит их таким образом, то есть, на самом деле, нет там никаких скобок, а есть ассемблерные инструкции (картинки с https://godbolt.org/ будут под постами)
#IT #job #c_plus_plus #math #weird #interview
Продолжение
Теперь вернемся, к тому какие встроенные типы для чисел в C++ мы имеем – integra и floating point…Первые мы пропускаем, насчёт вторых зададимся вопросом, вот в верху я представил множество различных чисел из алгебры – к чему относятся floating points? Правильный ответ: float и double способны представить некоторые рациональные числа. На этом всё, да, никаких настоящих вещественных чисел они не могут представить, корень из двух будет аппроксимирован некоторым рациональным приближением и так далее. Но, выше я писал, что рациональные числа обладают коммутативностью и ассоциативностью по сложению? Да…но… Уже случай из предыдущего поста, явно не ложится в наше пониманием рациональных чисел, демонстрируя, некоторое “поглощение”. Сложение чисел с плавающей точкой имеет свойства отличные от общеалгебраических, в результат их представления и реализации арифметических операций над ними. При этом, CPU, как и целочисленными значениями, складывает по 2 числа с плавающей точкой за одну инструкцию, было бы странно, если б мы сломали коммутативность: это был бы очевидный баг.
Я утверждаю следующее: можно найти тройку чисел с плавающей точкой (одновременно все float или double), такие что (a+b) +c не равно a + (b +c).
И сейчас я объясню, как я собираюсь их искать. Опять апеллирую к примеру с поглощением малого числа из прошлого поста, идея сводится к тому, что для начала мне нужно найти пару чисел, “большое” число a, и “малое” число b. Причём, число a “поглощает” число b, но число 2*a уже не будет поглощаться… Ещё раз: поскольку это поглощение основано на том, что при сложении числа выравниваются (представляются с одинаковыми экспонентами), малое число должно быть настолько малым, что б выровняться за правый край мантиссы. А если я умножу его на 2 (сдвину на разряд влево) оно учтётся пройдёт по последнему разряду мантиссы и учтётся.
Так же, я хочу числа с простым бинарным представлением, число a=1, число b…подсмотрим сюда, мантисса у нас 23 бита, т .е. я предполагаю, что нужно сдвинуть единицу направо на 24 разряда, иначе говоря мантисса у нас опять 1, а экспонента -24 (минус 24). Да нам удобнее для числа b использовать так называемую научную нотацию, да ещё и наполовину в 16ричной системе счисления…
Вот листинг, берем float т.к. он короче, и берем format т. к. он обещает “умный вывод”, с нулями только если они имеют смысл, и собираем всё с C++20:
Вывод будет:
То есть: во-первых, тройку чисел я нашёл, во-вторых, мы разобрались, что изначальная задача действительно имеет смысл, в-третьих, мы получили ответ на неё, а именно, нужно отсортировать от меньшего числа к большему (в силу ассоциативности слева направо и всех остальных выкладок).
#IT #job #c_plus_plus #math #weird #interview
Теперь вернемся, к тому какие встроенные типы для чисел в C++ мы имеем – integra и floating point…Первые мы пропускаем, насчёт вторых зададимся вопросом, вот в верху я представил множество различных чисел из алгебры – к чему относятся floating points? Правильный ответ: float и double способны представить некоторые рациональные числа. На этом всё, да, никаких настоящих вещественных чисел они не могут представить, корень из двух будет аппроксимирован некоторым рациональным приближением и так далее. Но, выше я писал, что рациональные числа обладают коммутативностью и ассоциативностью по сложению? Да…но… Уже случай из предыдущего поста, явно не ложится в наше пониманием рациональных чисел, демонстрируя, некоторое “поглощение”. Сложение чисел с плавающей точкой имеет свойства отличные от общеалгебраических, в результат их представления и реализации арифметических операций над ними. При этом, CPU, как и целочисленными значениями, складывает по 2 числа с плавающей точкой за одну инструкцию, было бы странно, если б мы сломали коммутативность: это был бы очевидный баг.
Я утверждаю следующее: можно найти тройку чисел с плавающей точкой (одновременно все float или double), такие что (a+b) +c не равно a + (b +c).
И сейчас я объясню, как я собираюсь их искать. Опять апеллирую к примеру с поглощением малого числа из прошлого поста, идея сводится к тому, что для начала мне нужно найти пару чисел, “большое” число a, и “малое” число b. Причём, число a “поглощает” число b, но число 2*a уже не будет поглощаться… Ещё раз: поскольку это поглощение основано на том, что при сложении числа выравниваются (представляются с одинаковыми экспонентами), малое число должно быть настолько малым, что б выровняться за правый край мантиссы. А если я умножу его на 2 (сдвину на разряд влево) оно учтётся пройдёт по последнему разряду мантиссы и учтётся.
Так же, я хочу числа с простым бинарным представлением, число a=1, число b…подсмотрим сюда, мантисса у нас 23 бита, т .е. я предполагаю, что нужно сдвинуть единицу направо на 24 разряда, иначе говоря мантисса у нас опять 1, а экспонента -24 (минус 24). Да нам удобнее для числа b использовать так называемую научную нотацию, да ещё и наполовину в 16ричной системе счисления…
Вот листинг, берем float т.к. он короче, и берем format т. к. он обещает “умный вывод”, с нулями только если они имеют смысл, и собираем всё с C++20:
#include <iostream>
#include <format>
int main()
{
float a = 1.0;
float b = 0x1.p-24;
std::cout << std::format("{}", a+b) << std::endl;
std::cout << std::format("{}", (a + b) + b) << std::endl;
std::cout << std::format("{}", a + (b + b)) << std::endl;
return 0;
}
Вывод будет:
1
1
1.0000001
То есть: во-первых, тройку чисел я нашёл, во-вторых, мы разобрались, что изначальная задача действительно имеет смысл, в-третьих, мы получили ответ на неё, а именно, нужно отсортировать от меньшего числа к большему (в силу ассоциативности слева направо и всех остальных выкладок).
#IT #job #c_plus_plus #math #weird #interview
Не надо плавать
В прошлых постах я довольно подробно расписал подводные камни работы с числами с плавающей точкой, которые моделируют дробные(рациональные) числа. И тут есть интересный момент: это не единственный вариант работы с такими числами (Википедия не даст соврать), я и сам уже упоминал это, но… в C++ их нет ни как базового типа, ни как класса в стандартной библиотеке. Зато, в C++ есть вызывающая много споров возможность перегружать операторы, что подталкивает нас попробовать создать так называемые числа с фиксированной точке “на коленке”, сделав свой класс и перегрузив (хотя бы часть) арифметических операторов.
Тут прежде, чем изливать тонны кода, давайте остановимся на основах: почему это возможно и как это сделать. Итак, язык нам предоставляет базовые integral types, обычно 1,2,4, 8 байтовые со знаком или без (ну уж точно на x86-64 платформе это так) и предоставляет нам арифметические операторы для этих типов. Рассмотрим базовые моменты работы арифметических операторов на примере типов uint8_t, int8_t:
• Сложение для uint8_t происходит по модулю 256 т.е. 1+2 = 3, но 1+255=0
• Сложение знаковых чисел происходит той же самой инструкций ассемблера, т.е. для CPU нет никаких отрицательных чисел, границы этого типа -128…+127
• Перемножение двух int8_t дает результат типа int16_t
• Частное от деления int16_t \ int8_t дает результат типа int8_t, остаток отбрасывается
А теперь основная идея (или трюк, если хотите), я могу взять переменную типа int8_t и мысленно сказать, что она хранит не целое число…а например, число четвертей, то есть мысленно поставить точку после двух левых разрядов. Давайте на примере десятичной системы: я возьму какие-то числа, например 3.14 и 2.71 и скажу – “у меня есть 314 сотых, а также 271 сотая”. Если меня попросят их сложить или вычесть это можно сделать, не выходя за нотацию сотых прямо сразу: 314 + 271 = 585, 314 – 271 = 43. Давайте попробуем умножить, 314*271 = 85094 эм...это точно в сотых? Нет, это точно не в них – правильно будет вот так 851 т.е. сдвинуть на 2 разряда вправо. А причём тут сотые, и какие-то четверти, которые я упоминал ранее? Четверти – это одни четвертые (богатый русский язык), для двоичной системы, это тоже самое, что сотые для десятичной.
В следующий раз понемногу начну показывать код.
#IT #job #c_plus_plus #math #weird #ToBeContinued
В прошлых постах я довольно подробно расписал подводные камни работы с числами с плавающей точкой, которые моделируют дробные(рациональные) числа. И тут есть интересный момент: это не единственный вариант работы с такими числами (Википедия не даст соврать), я и сам уже упоминал это, но… в C++ их нет ни как базового типа, ни как класса в стандартной библиотеке. Зато, в C++ есть вызывающая много споров возможность перегружать операторы, что подталкивает нас попробовать создать так называемые числа с фиксированной точке “на коленке”, сделав свой класс и перегрузив (хотя бы часть) арифметических операторов.
Тут прежде, чем изливать тонны кода, давайте остановимся на основах: почему это возможно и как это сделать. Итак, язык нам предоставляет базовые integral types, обычно 1,2,4, 8 байтовые со знаком или без (ну уж точно на x86-64 платформе это так) и предоставляет нам арифметические операторы для этих типов. Рассмотрим базовые моменты работы арифметических операторов на примере типов uint8_t, int8_t:
• Сложение для uint8_t происходит по модулю 256 т.е. 1+2 = 3, но 1+255=0
• Сложение знаковых чисел происходит той же самой инструкций ассемблера, т.е. для CPU нет никаких отрицательных чисел, границы этого типа -128…+127
• Перемножение двух int8_t дает результат типа int16_t
• Частное от деления int16_t \ int8_t дает результат типа int8_t, остаток отбрасывается
А теперь основная идея (или трюк, если хотите), я могу взять переменную типа int8_t и мысленно сказать, что она хранит не целое число…а например, число четвертей, то есть мысленно поставить точку после двух левых разрядов. Давайте на примере десятичной системы: я возьму какие-то числа, например 3.14 и 2.71 и скажу – “у меня есть 314 сотых, а также 271 сотая”. Если меня попросят их сложить или вычесть это можно сделать, не выходя за нотацию сотых прямо сразу: 314 + 271 = 585, 314 – 271 = 43. Давайте попробуем умножить, 314*271 = 85094 эм...это точно в сотых? Нет, это точно не в них – правильно будет вот так 851 т.е. сдвинуть на 2 разряда вправо. А причём тут сотые, и какие-то четверти, которые я упоминал ранее? Четверти – это одни четвертые (богатый русский язык), для двоичной системы, это тоже самое, что сотые для десятичной.
В следующий раз понемногу начну показывать код.
#IT #job #c_plus_plus #math #weird #ToBeContinued
👍1🔥1
Административное
Автор канала решил начать публиковать контент также на Хабре. В какой-то степени публикации на канале и на Хабре будут перекликаться.
#administrative #today #this_channel #habr
Автор канала решил начать публиковать контент также на Хабре. В какой-то степени публикации на канале и на Хабре будут перекликаться.
#administrative #today #this_channel #habr
Хабр
Игрушечная имплементация чисел с фиксированной точкой в C++
В C++ нет базового типа чисел с фиксированной точкой , в стандартной библиотеке также нет классов для них. В тоже время работа с числами с плавающей точкой (double, float) часто может быть неочевидна...
🔥1
Две странных победы: оппоненты, в обоих случаях, сами довольно осознанно сдали ладью – там не было "вилки", можно было спокойно уйти и так далее, но через несколько ходов после этого они сдались. Там где я белыми, вероятно был план "пролезть" ферзём за рокировку, но что-то пошло не так
#flood #today #chess
#flood #today #chess
Не надо плавать
Часть 2
Поскольку код вышел на Хабре, и более-того, комментаторы и я сам нашли довольно большое количество ошибок и переусложненных моментов, хотелось бы тут остановиться ещё раз на идее.
В языке C++ есть типы double и float, реализованные в соответствии со стандартом IEEE-754.
Знаменитая картинка из Википедии говорит о том, что мы храним отдельно знак, степень 2ки (экспоненту), и мантиссу – считай наши двоичные цифры. Тут хочется напомнить, что целые либо беззнаковые числа хранятся абсолютно иначе: нет ни отдельно знака, ни степени, по сути, хранится только само число.
Смысл статьи на Хабре и потуг предыдущего поста состоит в том, что можно взять целое число произвольного размера (но из тех, что нативно поддерживается компилятором) и сказать, что теперь я трактую n правых разрядов как значение идущее после точки – дробную часть числа, а остальные разряды как левую часть числа, вот пример для 8 битного числа где 2 младших разряда я отдаю под дробную часть 0000 1101, это тоже самое что 11.01 (2) = 3.25 (10) .
Соответственно, написанный код – всего лишь является отражением этой идеи.
#today #IT #c_plus_plus #math #habr #ToBeContinued
Часть 2
Поскольку код вышел на Хабре, и более-того, комментаторы и я сам нашли довольно большое количество ошибок и переусложненных моментов, хотелось бы тут остановиться ещё раз на идее.
В языке C++ есть типы double и float, реализованные в соответствии со стандартом IEEE-754.
Знаменитая картинка из Википедии говорит о том, что мы храним отдельно знак, степень 2ки (экспоненту), и мантиссу – считай наши двоичные цифры. Тут хочется напомнить, что целые либо беззнаковые числа хранятся абсолютно иначе: нет ни отдельно знака, ни степени, по сути, хранится только само число.
Смысл статьи на Хабре и потуг предыдущего поста состоит в том, что можно взять целое число произвольного размера (но из тех, что нативно поддерживается компилятором) и сказать, что теперь я трактую n правых разрядов как значение идущее после точки – дробную часть числа, а остальные разряды как левую часть числа, вот пример для 8 битного числа где 2 младших разряда я отдаю под дробную часть 0000 1101, это тоже самое что 11.01 (2) = 3.25 (10) .
Соответственно, написанный код – всего лишь является отражением этой идеи.
#today #IT #c_plus_plus #math #habr #ToBeContinued
👍1
👍1🥰1
Понедельник – день тяжёлый
И что б совсем не расслабляться – я опубликовал вторую часть стать о всем уже надоевшим числах с фиксированной точкой на Хабре
#today #IT #habr #c_plus_plus #flood #Monday
И что б совсем не расслабляться – я опубликовал вторую часть стать о всем уже надоевшим числах с фиксированной точкой на Хабре
#today #IT #habr #c_plus_plus #flood #Monday
Хабр
Имплементация чисел с фиксированной точкой (часть 2)
Итак, в прошлый раз я представил базовую идею как можно реализовать Fixed-point arithmetic , а так же набросок кода на C++, в котором в комментариях нашли довольно много проблем (а я сам нашёл ещё...
🔥1
Мысли в слух
По итогам публикации на Хабре в комментариях подкинули пищу для размышлений, наверное, наиболее интересная из них сделать нормальный Decimal ориентированный именно на 10тичные дроби (арифметику), в целом.
Как я уже упоминал, я делал нечто подобное на работе, но сложно то решение признать полноценным - на работу с гигантскими суммами оно не было ориентировано - ну что ж, соориентируем
#flood #today #habr
По итогам публикации на Хабре в комментариях подкинули пищу для размышлений, наверное, наиболее интересная из них сделать нормальный Decimal ориентированный именно на 10тичные дроби (арифметику), в целом.
Как я уже упоминал, я делал нечто подобное на работе, но сложно то решение признать полноценным - на работу с гигантскими суммами оно не было ориентировано - ну что ж, соориентируем
#flood #today #habr
Хабр
Имплементация чисел с фиксированной точкой (часть 2)
Итак, в прошлый раз я представил базовую идею как можно реализовать Fixed-point arithmetic , а так же набросок кода на C++, в котором в комментариях нашли довольно много проблем (а я сам нашёл ещё...
Как делить не деля
https://habr.com/ru/articles/833470/ В этот раз написание статьи оказалось даже более трудоёмким делом чем до этого – сказались объём и сложность изучаемых материалов, некоторое супер простое введение на канале напишу попозже
#today #habr #c_plus_plus
https://habr.com/ru/articles/833470/ В этот раз написание статьи оказалось даже более трудоёмким делом чем до этого – сказались объём и сложность изучаемых материалов, некоторое супер простое введение на канале напишу попозже
#today #habr #c_plus_plus
Хабр
Как поделить не деля или оптимизация деления компиляторам(и)
Если вы никогда не пробовали смотреть как код на C++ разворачивается компилятором в код Assembly – вас ждёт много сюрпризов, причём, не нужно смотреть какой-то замудренный исходный код полный...
👍1