OSDev

для всех
Текущее время: 28 мар 2024, 22:38

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 44 ]  На страницу 1, 2, 3, 4, 5  След.
Автор Сообщение
СообщениеДобавлено: 22 фев 2015, 16:44 
Аватара пользователя

Зарегистрирован: 17 фев 2013, 16:13
Сообщения: 163
При разработке ЯП мы сталкиваемся с необходимостью разрабатывать для него стандартную библиотеку, в том числе математическую её часть. Но здесь есть ряд трудностей, о которых я расскажу. Решения всех этих трудностей у меня пока нет.

Первое. У нас есть набор функций, некоторые из которых могут быть параллельными. Однако в ряде случаев встраивание параллельных команд может замедлить функцию в последовательном исполнении на одном ядре. Это не часто случается, но случается. Поэтому с моей точки зрения нужно либо иметь по две версии каждой такой функции, либо в языке должна быть предусмотрена возможность перекомпиляции кода с игнорированием команд параллельной обработки. В последнем случае мы не всегда будем получать корректный код. Это уже задача разработчика библиотеки: так всё подстроить, чтобы работало в любом случае.

Второе. Вред погони за универсальностью. В математике с этой точки зрения всё просто: сказал «решим систему уравнений, получим вектор X» и всё, все довольны. В программировании всё сложнее. Я однажды проводил конкурс на своём сайте. Выяснилось, что, например, при решение целочисленной системы линейных уравнений лучше всего применять совершенно другие алгоритмы, чем те, что все изучали в школе. В том конкурсе я не участвовал, так как у меня уже была версия программы, работающая в 60 раз быстрее, чем у будущего победителя – просто был реализован сразу правильный алгоритм. Таким образом, в математической библиотеки должны быть не функции на все случаи жизни, а алгоритмы на все случаи жизни. Те же системы линейных уравнений бывают совершенно разными, и они решаются разными способами, более того, каждый алгоритм может иметь разные реализации, зависящие от особенностей входных данных. Простой пример: в Maple есть функция быстрого решения целочисленной СЛУ, однако эта реализация используется там в любых случаях, даже когда очевидно, что использовать её вредно для здравого смысла.

Третье. Ещё вред от погони за универсальностью. Возьмём, например, структуру данных «граф». Реализуем для неё все стандартные алгоритмы. Например, алгоритм решения задачи о максимальном потоке. Допустим, мы реализовали хотя бы 15 разных алгоритмов (приходилось это делать как-то), и говорим: «всё, теперь у нас полно алгоритмов на все случаи жизни, где может понадобиться максимальный поток». А фиг там! На самом деле сама структура данных «граф» может быть реализована совершенно по-разному в зависимости от того, что мы с этим графом делаем. Например, динамический граф с возможностью добавлять или удалять рёбра и вершины, реализованный через STL (если хочешь убить проект, используй STL) даёт приблизительно в 13 раз более медленную реализацию алгоритма Форда – Фалкерсона, чем граф статический, в котором все рёбра заранее можно упорядочить в памяти компьютера так, чтобы максимально эффективно работать с кэшем. А ведь есть ещё сеть целочисленная, вещественная, единичная, с верхней и нижней гранецами пропускной способности, с двумя, тремя, четырмя и т. д. параметрами на рёбрах. Есть дофига всякокой фигни, и когда программист пишет template <class T, class U, class V, … > graph : public fuckingGraph { std::link <U> edges … } - он уже фактически начинает копать могилу своему творчеству. Так делает, например, Р. Седжвик. Нет, я не спорю, что он написал хорошую книжку для выпускника обычной средней школы с уклоном в информатику, но реально это тупик.

Четвёртое. Структура библиотеки. Представьте, что мне нужен синус. Подключается библиотека, в которой кроме синуса ещё полсотни функций, которые мне не нужны. Зачем усложнять компиляцию? Может показаться, что это ничего не усложняет, но на самом деле в крупных проектах, состоящих из огромного количества подключаемых модулей, почти все из которых используются лишь на полпроцента, это имеет свой эффект. Нужно так продумывать структуру библиотеки и самого языка, чтобы подключалось только то, что нужно. Для этого структура должна быть хорошо продуманной. Когда мы видим, что одна библиотека ссылается на другую только из-за того, что нам оттуда нужна лишь одна функция, а эта функция требует другую библитеку, а та – третью, то мы получаем ад. Когда нам нужно несколько гигабайт говна из-за того, что понадобилась некоторая функция или возможность. Пример такого говна – концепция Linux ( да-да, забросайте меня гневными воплями : ) Windows тоже говно, так что не расстраивайтесь, равновесие в этой войне достигнуто : ) )

Пятое. Качество. Когда я читаю коды некоторых библиотек или функций, свободно демонстрируемых в интернете, то у меня складывается устойчивое впечатление, что пишут их студенты в рамках своих курсовых работ. Профессионал никогда на напишет такого бреда, какой приходится иногда видеть. Я не преувеличиваю недостаток способностей и опыта, сами посудите, только 10% программистов могут написать бинарный поиск правильно. И, к сожалению, из этих 10% ещё только 10% разбираются в остальных алгоритмах на уровне нормального прилежного студента. Из них ещё 10% способны хорошо кодировать. А из них только 10% делают код не только понятным, но и эффективным. Как-то так.

Шестое. Тесты. При создании библиотеки нужно создавать систему тестов, которая тоже должна быть частью библиотеки. Система тестов должна меняться и совершенствоваться параллельно с реализациями алгоритмов. Вообще, при правильно подходе должна быть документация библиотеки с полным объяснением сложности и скорости работы функций, замеры времени, памяти и прочее. Меня, если честно, достало тестировать чужой код и выгребать из него то говно, которое автор мог выгрести сам, если бы потестировал сам – сам бы всё увидел. Создание системы тестов и теоретический обзор не только заставит лучше подойти к разработке, но и отслеживать ошибки, выполнять нужные модификации, выполняя сразу перетестирование.

Седьмое. Максимальная замкнутость и минимальная зависимость. Я нередко встречал случаи, когда человек подключает целую библиотеку вроде boost только ради того, чтобы использовать там один какой-то тип. Прописать руками пару строк ему влом, лучше заставить всех остальных программистов ставить этот boost. Но это ещё цветочки. Когда я занимался наукой, то видел, что учёные могут подключить 4-5 библиотек. Вот понадобилось человеку два полинома сложить, он берёт библиотеку FLINT, вместо того, чтобы сложить два массива чисел. Затем ему понадобилась функция Lerp (x,y,t)=(1-t)*x+t*y, так он ещё одну библиотеку устанавливает (boot по-моему). Теперь я должен скачать код этого человека, установить все эти библиотеки, которые мне лично нафиг не нужны. Почему так происходит? Потому что нет нормально продуманной стандартной библиотеки ни в одном языке. Библиотека должна быть максимально замкнутой на самой себе (требует только функции из неё же), но при этом каждая функция должна требовать подключения как можно меньшего числа других пакетов библиотеки, когда это не противоречит здравому смыслу.

Пока такие мысли.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 22 фев 2015, 17:32 

Зарегистрирован: 28 окт 2007, 18:33
Сообщения: 1418
Zealint писал(а):
Четвёртое. Структура библиотеки. Представьте, что мне нужен синус. Подключается библиотека, в которой кроме синуса ещё полсотни функций, которые мне не нужны. Зачем усложнять компиляцию?


Сколько потянется лишних функций, зависит как и от тупости структуры библиотеки, и от тупости компоновщика. Если по-хорошему, то каждая функция должна быть отдельным объектным файлом ("объектным" в несколько более широком смысле -- не только скомпилированный, но ещё не настроенный на конкретное местоположение код, но и информация о типах и т.д. и т.п.), который компонуется с другими объектными файлами во время сборки приложения, причём компоновщик должен брать лишь те объектники, которые реально нужны. Если некая библиотечная подпрограмма зависит от других подпрограмм, её объектник должен содержать внешние ссылки, по которым компоновщик найдёт недостающие подпрограммы и включит их объектники в результирующую программу. Собственно, именно так и веласть сборка программ в стародавние времена -- никому в голову не приходило, что из-за одной функции к программе нужно присобачивать всю библиотеку (хотя б потому, что такая программа вряд ли бы поместилась в тогдашний объём памяти). Правда, контроля типов и т.д. в те времена не было, и их так или иначе приходилось обеспечивать внешними средствами, но это не представляет каких-либо принципиальных сложностей -- достаточно расширить формат объектников (что та же Борланд сделала ещё в Турбо Паскале).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 26 фев 2015, 13:34 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 970
Откуда: Дагоба
Zealint писал(а):
Первое. У нас есть набор функций, некоторые из которых могут быть параллельными. Однако в ряде случаев встраивание параллельных команд может замедлить функцию в последовательном исполнении на одном ядре. Это не часто случается, но случается. Поэтому с моей точки зрения нужно либо иметь по две версии каждой такой функции,

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

Zealint писал(а):
либо в языке должна быть предусмотрена возможность перекомпиляции кода с игнорированием команд параллельной обработки. В последнем случае мы не всегда будем получать корректный код.

Есть ли пример, когда последовательное выполнение корректного параллельного исходного кода изменит семантику?

Zealint писал(а):
Есть дофига всякокой фигни, и когда программист пишет template <class T, class U, class V, … > graph : public fuckingGraph { std::link <U> edges … } - он уже фактически начинает копать могилу своему творчеству. Так делает, например, Р. Седжвик.

Седжвик решает совсем другие задачи. В двух учебных курсах алгоритмов на Курсере Седжвик все задания вообще даёт только на джаве, хотя, понятно, они от этого быстрей работать не будут. Тем не менее, даже там каждое решение, помимо корректности, обязательно оценивается по двум критериям - время работы и потреблённая память, и задание не принимается, если хотя бы по одному критерию задание не впишется в лимит. И замечу, что надо сильно попотеть чтобы получить 100% балл за курс. Седжвик так делает исключительно в учебных целях - для наглядности самого алгоритма и абстрагирования от мелких технических деталей, для чего джава вполне пригодна. Понятно, что после полного понимания алгоритма он может быть реализован на более подходящем языке. Ну это так, оффтоп в защиту Седжвика. Он очень достойный специалист и великолепный профессор.

Zealint писал(а):
Четвёртое. Структура библиотеки. Представьте, что мне нужен синус. Подключается библиотека, в которой кроме синуса ещё полсотни функций, которые мне не нужны. Зачем усложнять компиляцию? Может показаться, что это ничего не усложняет, но на самом деле в крупных проектах, состоящих из огромного количества подключаемых модулей, почти все из которых используются лишь на полпроцента, это имеет свой эффект. Нужно так продумывать структуру библиотеки и самого языка, чтобы подключалось только то, что нужно. Для этого структура должна быть хорошо продуманной.

Я вижу два выхода - радикальный и умеренный. Умеренный заключается в помещении каждой функции в отдельный объектный модуль. Раньше так часто делали статические С-шные библиотеки именно с целью уменьшения кода. Тут есть проблемы – либо геморрой с написанием (плодим тысячи крошечных файлов исходного текста без статических функций/переменных) либо геморрой с устаревшими объектными форматами (т.к. при генерации разных модулей на уровне компилятора обязательно возникнут проблемы со статическими функциями). Разрешение проблемы с умеренным подходом заключается в модернизации объектных форматов (что давно назрело и по другим причинам тоже). Радикальный подход заключается в том, что все языковые и системные библиотеки должны быть реализованы в виде динамически подгружаемых библиотек. Только в этом случае скомпилированный "Hello, World!" сможет иметь размер меньше 50 байт. Но для этого нужна хорошая интеграция языка (компилятора) с операционной системой, иначе каждый 50-байтный "Hello, World!" будет тащить за собой 100-мегабайтные DLL. Лично мне радикальный подход кажется более перспективным, но оба подхода не исключают друг друга.

Zealint писал(а):
Когда мы видим, что одна библиотека ссылается на другую только из-за того, что нам оттуда нужна лишь одна функция, а эта функция требует другую библитеку, а та – третью, то мы получаем ад. Когда нам нужно несколько гигабайт говна из-за того, что понадобилась некоторая функция или возможность. Пример такого говна – концепция Linux ( да-да, забросайте меня гневными воплями : ) Windows тоже говно, так что не расстраивайтесь, равновесие в этой войне достигнуто : ) )

На самом деле развертывание г-на – ещё более масштабный процесс. Здесь мало ссылок на цепочки библиотек. Поистине взрывоподобное увеличение объёма г-на происходит при следующих дополнительных обстоятельствах:
1) Выходят новые версии библиотек. Для совместимости со старыми приложениями система наряду с новыми оставляет некоторые версии старых библиотек (несовместимых по вызовам).
2) Появляются альтернативные версии библиотек, которые по мнению создателей лучше, чем уже существующие, но с совершенно несовместимым API.
3) Функциональность следующего, верхнего уровня использует как одни, так и другие библиотеки (т.к. что-то лучше сделано там, а что-то – сям).
4) Т.к. ряд функций реализованы в виде шаблонов, оказывается, что большое кол-во одних и тех же функций присутствует не только в куче копий пользовательского ПО, но и в библиотеках, которые это ПО использует.
5) Когда объём кода вырастает до размера, превышающего возможность понимания одним программистом, каждый из них вместо использования уже существующей функции (о которой он, может быть, даже не знает) пишет такую же новую (например, в исходниках UEFI Self-Certification Test 2.3 пять разных копий расчёта CRC32 со стандартным полиномом, функционально абсолютно одинаковых). Также вместо изменений в одной функции (эти изменения могут незаметно обрушить всё приложение), программист предпочитает поменять её копию, там где это возможно.
Т.к. каждый из этих шагов вызывает увеличение кода в разы, совокупный их эффект оказывает экспоненциальное влияние на объём.

Zealint писал(а):
Пятое. Качество. Когда я читаю коды некоторых библиотек или функций, свободно демонстрируемых в интернете, то у меня складывается устойчивое впечатление, что пишут их студенты в рамках своих курсовых работ. Профессионал никогда на напишет такого бреда, какой приходится иногда видеть. Я не преувеличиваю недостаток способностей и опыта, сами посудите, только 10% программистов могут написать бинарный поиск правильно. И, к сожалению, из этих 10% ещё только 10% разбираются в остальных алгоритмах на уровне нормального прилежного студента. Из них ещё 10% способны хорошо кодировать. А из них только 10% делают код не только понятным, но и эффективным. Как-то так.

Вывод парадоксален - тщательная фильтрация и уменьшение штата сотрудников для ответственных проектов. Иногда один программист может сделать лучше, чем 100 за то же самое время. На самом деле, этот подход проверен практикой и доказал свою справедливость.

Zealint писал(а):
Шестое. Тесты. При создании библиотеки нужно создавать систему тестов, которая тоже должна быть частью библиотеки.

Абсолютно согласен.

Zealint писал(а):
Седьмое. ... Теперь я должен скачать код этого человека, установить все эти библиотеки, которые мне лично нафиг не нужны. Почему так происходит? Потому что нет нормально продуманной стандартной библиотеки ни в одном языке. Библиотека должна быть максимально замкнутой на самой себе (требует только функции из неё же), но при этом каждая функция должна требовать подключения как можно меньшего числа других пакетов библиотеки, когда это не противоречит здравому смыслу.

Поэтому я уверен, что при разработке ЯВУ необходимо включить ряд типов и математических функций (фактически всё, что часто используется, требует высокой производительности и не зависит от ОС) в стандартные языковые библиотеки. Здесь, однако, надо проявлять величайшую осторожность, иначе эти библиотеки мгновенно превратятся в монстра наподобие STL или Boost. Особенную осторожность нужно проявлять при создании шаблонов и отказываться от их использования без крайней необходимости.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 26 фев 2015, 15:37 
Аватара пользователя

Зарегистрирован: 17 фев 2013, 16:13
Сообщения: 163
Yoda писал(а):
Тем более, по той причине, что когда производительность критична, мы как раз стараемся использовать параллелизм.

И мы делаем это двумя способами. Допустим, у нас много раз вызывается некоторая функция, так много, что этот вызов образует узкое место. Теперь что мы делаем? - либо параллелим саму функцию, либо делаем так, чтобы вызывающий её код запускал функцию в однопоточном режиме на разных ядрах. Второе обычно выигрывает. Хотя может и не сильно. Нужно определиться, какие функции следует делать параллельными, а какие нет. Например, обычный синус и косинус вполне неплохо считаются на одном ядре. Тогда как очень длинный синус или косинус может быть придётся параллелить.

Пример. Как-то для расчётов некоторых физических характеристик приходилось рассчитывать число покрытий доминошками шахматной доски (domino tiling). Для этого лучше всего использовать формулу Кастелейна (она есть по ссылке), только предварительно упростив её. Чтобы работать с размерами около 30x100000, приходилось тащить в промежуточных вычислениях сотни тысяч бит. С одной стороны, можно параллелить косинус, с другой - сами вычисления, которым он нужен. Мы тогда пошли вторым путём.

Yoda писал(а):
Есть ли пример, когда последовательное выполнение корректного параллельного исходного кода изменит семантику?

Прямо сходу нет. Я думаю, любой параллельный алгоритм можно преобразовать в такую форму, чтобы он корректно работал на одном ядре. Но вспоминаю одну свою программу, в которой требовалось минимум два ядра. Одно было "раздающим" задачи и выполняло роль менеджера, а остальные выполняли подзадачи и получали новые по мере своего освобождения. Так как все подзадачи имели разную сложность, было удобнее сделать такой отдельный менеджер, который за всеми следит. Очень трудно было бы написать хорошую программу иным способом в том случае. Есть ещё ряд алгоритмов, особенно для видеокарт, где с самого начала предполагается наличие минимум N ядер. Например, умножается матрица 4x4 на вектор (типичная задача computational geometry). Сразу раскидывается всё на 4 или 16 ядер без каких-либо вариантов.

Yoda писал(а):
Ну это так, оффтоп в защиту Седжвика. Он очень достойный специалист и великолепный профессор.

Не спорю, что он шаристый мужик. Но мой путь изучения алгоритмов был совершенно иным и мне кажется очень неудачным использовать попытки универсального описания алгоритмов через шаблоны и прочие нагромождения, на мой взгляд, это только сложнее понимается. Зачем делать отдельные классы рёбер, вершин графа чего-то ещё, если для простейшего понимания достаточно завести пару массивов? Создавать класс "граф" для этого вообще не нужно. На мой взгляд, лучше объяснить программисту то, как можно проще всего реализовать алгоритм, а если ему нужен промышленный код в качестве обёртки, он сам его состряпает. Разумеется, если бы я написал книгу по алгоритмам, в которой все они были бы раз 5 короче по коду, она вряд ли имела бы успех у большинства : ) Помню, как все эти алгоритмы я учился набивать на скорость... решение задачи о назначениях за 4 минуты 36 секунд : ) Это нереально для кода из универсальных классов.. Не буду спорить, что лучше, это скорее две крайности.

Yoda писал(а):
Поэтому я уверен, что при разработке ЯВУ необходимо включить ряд типов и математических функций (фактически всё, что часто используется, требует высокой производительности и не зависит от ОС) в стандартные языковые библиотеки. Здесь, однако, надо проявлять величайшую осторожность, иначе эти библиотеки мгновенно превратятся в монстра наподобие STL или Boost. Особенную осторожность нужно проявлять при создании шаблонов и отказываться от их использования без крайней необходимости.

Когда начинаешь что-то делать, то кажется, что будешь осторожно следить за раздуванием кода. Однако рано или поздно начнётся беда следующего вида.

Вот у нас функции по работе с графикой. Есть функция поворота: вокруг точки или вокруг прямой (в 3D). Поворот можно задать величиной угла в градусах или радианах, точку через тройку (x,y,z) или через класс «точка» или через какой-нибудь радиус-вектор, а прямую через коэффициенты уравнения или параметрически (вектором и базовой точкой), сам вектор при этом может быть задан разными способами и т. д. и т. п. А подобных функций в геометрии тьма. И не только в геометрии. В общем, суть в том, что одна и та же функция может оказаться в разных условиях вызова, при этом делать некую прокси-функцию, сводящую всё к единому универсальному способу, плохо, это удар по производительности.

Если нам нужно будет теперь написать все возможные случаи вызова этой функции, то можно уже сейчас пойти покупать мыло и верёвку.

Ещё пример: нужна функция сравнения дробных чисел. Есть вариант с абсолютной погрешностью (это неправильно в общем случае, но иногда очень нужно в частном), а есть с относительной. Причём вариантов с относительной погрешностью может быть несколько.

Также бывают алгоритмы приближённого вычисления обратной величины. Их тоже несколько и каждый нужен в своём случае. Если для float32 и float64 вроде бы должно работать встроенное деление, то для float256 придётся ведь реализовать какой-нибудь иной метод (типа Ньютона), в котором число шагов будет отличаться от деления для float128.

PS. Заглянул недавно в boost, нужен был random, пришёл в ужас и написал свой random, работает в 3 раза быстрее : ) Таким образом, появился ещё один random, хотя их там и так много.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 20 мар 2015, 22:45 
Аватара пользователя

Зарегистрирован: 17 фев 2013, 16:13
Сообщения: 163
Есть такая бодяга, которая, как и многие другие «изобретения» Intel, являются следствием желания победить в какой-то вымышленной войне. Одним из них является стандарт IEEE 754, формально выигравший войну с VAX (DEC). Не буду долго рассказывать о плавающей погрешности и прочей ерунде, а просто оставлю здесь код (сам пример не мой, а код мой):

Код:
double x [ ] = { 10e20, 1223,  10e18, 10e15,    3, -10e12 };
double y [ ] = { 10e20,    2, -10e22, 10e13, 2111,  10e16 };
double z = 0.0;
for ( int i = 0; i < 6; i ++ )
   z += x [ i ] * y [ i ];

Правильный ответ z=8779. Мой компилятор даёт программу, которая выдаёт z=154742504910672530000000000.0.
При это прошу сразу обратить внимание, что вычисления даже близко не подходят к границам применения double. Если взять float, то будет ерунда, но это понятно.

Такие дела, и с этим нужно как-то жить.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 21 мар 2015, 04:36 
Аватара пользователя

Зарегистрирован: 28 май 2012, 23:44
Сообщения: 237
Откуда: Санкт-Петербург
Zealint писал(а):
Мой компилятор даёт программу, которая выдаёт z=154742504910672530000000000.0.

У меня бессонница, от нечего делать воспроизвел программу в Delphi (x86):
Код:
type
//  Real = Extended;
  TData = array[0..5] of Real;
const
  X: TData = (10e20, 1223, 10e18, 10e15, 3, -10e12);
  Y: TData = (10e20, 2, -10e22, 10e13, 2111, 10e16);
var
  Z: Real;
  I: Integer;
begin
//  Set8087CW(Default8087CW);
  Z := 0;
  for I := Low(TData) to High(TData) do
    Z := Z + X[I] * Y[I];
  ShowMessage(SysUtils.Format('$%04x: %f', [Get8087CW, Z]));
end;

Первая цифра -- контрольное слово сопроцессора. Результаты:
Код:
$27F:  1.5474250491e+26
$1372: 1.2875059979e+26

$27F -- умолчательное контрольное слово, $1372 -- после специфичной для Delphi инициализации. Если раскомментировать строчку Real = Extended, будет выдавать 0.

Пью зеленый чай в качестве антидепрессанта. :(


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 21 мар 2015, 09:31 
Аватара пользователя

Зарегистрирован: 17 фев 2013, 16:13
Сообщения: 163
Цитата:
Пью зеленый чай в качестве антидепрессанта.

А я завариваю пустырник.

Вообще, невозможность использовать единую абсолютную погрешность и не возможность работать одновременно с большими и маленькими числами (разница между которыми ~15 и более порядков) а также целый ряд проблем с дико нарастающей погрешностью - это далеко не весь список забот, которыми приходится заниматься при работе с плавающей арифметикой. Создатель математической библиотеке или вообще человек, работающий с плавающими числами, должен часами сидеть и над каждой операцией думать, не может ли она дать погрешность выше, чем порядок ожидаемого ответа. С фиксированной арифметикой таких проблем нет, но она требует больше памяти. Говорят, что плавающая арифметика своей непредсказуемостью уже успела принести огромные убытки (в том числе в виде человеческих жертв). А ведь и правда, очень многие программисты не понимают как она работает и как с ней обращаться, чтобы эту непредсказуемость минимизировать.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 21 мар 2015, 10:16 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1126
Просто числа с плавающей точкой ведут себя как с фиксированной. Для double это 52 бита или 15 десятичных знака. Поэтому пример выше у вас явно выходит за границы. Плаваяэющая точка на моей памяти только единажды выигрывала у всех прочих.


Последний раз редактировалось pavia 21 мар 2015, 11:06, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 21 мар 2015, 10:23 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1126
Моя колекция ошибок там в сносках ещё куча примеров.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 23 мар 2015, 12:24 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 970
Откуда: Дагоба
Компилятор GCC выдал 1.28751E+26, компиляторы TinyC, Microsoft C, CLang выдали 1.54743E+26. В принципе, мелкие числа из этого списка вообще можно убрать:
Код:
double x[] = { 10e20,  10e18, 10e15, -10e12 };
double y[] = { 10e20, -10e22, 10e13,  10e16 };
double z = 0.0;
for (int i=0; i<4; i++)
  z += x[i] * y[i];

Сумма в теории должна быть равна 0, но все четыре компилятора дают ровно тот же результат. Интересная бодяга, почему компилятор GCC настойчиво считает не как остальные. Вообще говоря, это повод для разбирательства, т.к. стандарты принимали в первую очередь для обеспечения переносимости.
В целом, природа глюка понятна, – те числа, которые нам, смертным, кажутся целыми и круглыми (большие степени десятки), в плавающем двоичном представлении жутко не целые и не круглые.

Zealint писал(а):
Есть такая бодяга, которая, как и многие другие «изобретения» Intel, являются следствием желания победить в какой-то вымышленной войне. Одним из них является стандарт IEEE 754, формально выигравший войну с VAX (DEC).

В данной формулировке получается, что VAX лишён этой проблемы, верно? Насколько я помню, в войне между VAX и Intel особенностью ваксов была более быстрая арифметика, а интел - как раз более устойчивая к ошибкам и более функциональная. И я полагаю, что в перспективе очень хорошо, что выиграла Intel (собс-но, не всё, что творят мегакорпорации, является злом :)). А приведённая проблема, если я не ошибаюсь, не может иметь решения в рамках форматов чисел с плавающей точкой, надо это учитывать в расчётах и как-то с этим жить. Вот интересный экскурс в тему на хабре: http://habrahabr.ru/post/112953/

UPD.
Прогнал компиляторы через тест Паранойя. Tiny C прошёл безупречно, компилятор GCC провалился с результатом "удовлетворительно, но с недостатками".

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 44 ]  На страницу 1, 2, 3, 4, 5  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB