Ассоциативность арифметических операций.
z = a + b + c 
Я не понял вопрос!
Я не понял вопрос!
Я не понял вопрос!ошибки округления при разном порядке слагаемых разные могут быть.
Там где-то сказано про вещественную арифметику?
Там где-то сказано про вещественную арифметику?Нет, но в противном случае вопрос действительно непонятен.
done
ну да, тогда сортировка действительно адекватная вещь. У тебя всего три числа?
Можешь heap sort'ом сортировать
Можешь heap sort'ом сортировать
Три числа - это две операции. При этом нужно сперва проводить их с меньшими числами. Чтобы выделить наибольшее из трёх чисел, достаточно двух сравнений. Может можно на доп. операциях сэкономить (например, заменить временную переменную на указатель но сомневаюсь, что в обычных случаях будет что-либо существенно проще самого банального алгоритма:
алг Сумма(вещ a, b, c, sum)
ввод a, b, c
вывод sum
начало вещ tmp
| если a > b
| | то sum := b; tmp := a;
| | иначе sum := a; tmp := b;
| всё
| если tmp > c
| | то sum := sum + c; sum := sum + tmo;
| | иначе sum := sum + tmp; sum := sum + c;
| всё
конец
p.s.: если предполагается появление отрицательных чисел, сравнивать надо по модулю, наверное.
p.s.s.: перемножение - это умножения мантисс и сложение порядков. Что касается погрешностей, то их относительные величины складываются, так что результат не должен так сильно зависеть от порядка действий, как в случае сложения (где складываются абсолютные погрешности).
алг Сумма(вещ a, b, c, sum)
ввод a, b, c
вывод sum
начало вещ tmp
| если a > b
| | то sum := b; tmp := a;
| | иначе sum := a; tmp := b;
| всё
| если tmp > c
| | то sum := sum + c; sum := sum + tmo;
| | иначе sum := sum + tmp; sum := sum + c;
| всё
конец
p.s.: если предполагается появление отрицательных чисел, сравнивать надо по модулю, наверное.
p.s.s.: перемножение - это умножения мантисс и сложение порядков. Что касается погрешностей, то их относительные величины складываются, так что результат не должен так сильно зависеть от порядка действий, как в случае сложения (где складываются абсолютные погрешности).
алг Сумма(вещ a, b, c, sum)АААА, ты его так помнишь, или освежил-таки где-то память?
ввод a, b, c
вывод sum
начало вещ tmp
| если a > b
| | то sum := b; tmp := a;
| | иначе sum := a; tmp := b;
| всё
| если tmp > c
| | то sum := sum + c; sum := sum + tmo;
| | иначе sum := sum + tmp; sum := sum + c;
| всё
конец
АААА, ты его так помнишь, или освежил-таки где-то память?сильно сомневался на счёт того, писать "начало/конец" или "нач/кон"... похоже, всё-таки ошибся. Но остальное помнил.
Просто решил, что для таких вопросов надо и язык соответствующий выбирать.
> При этом нужно сперва проводить их с меньшими числами
Это зачем?
Спасибо, я уже пузырьком сделал.
Это зачем?
Спасибо, я уже пузырьком сделал.
Это зачем?А зачем ты это задание выполняешь? Оно как бы на то, чтобы узнать о подводных камнях вещественной арифметики. В частности, надо знать, что a + b == a не эквивалентно b == +0 или b == -0.
Если б я не знал о подводных камнях вещественной арифметики, вопроса бы вообще не возникло.
Задача появилась при попытке формализации геометрических величин в пространстве (например объём тетраэдра по 4м точкам).
И основная проблема - это вырожденные случаи, когда знак нуля может зависеть от порядка. Вот. Мне и нужно было так построить вычисления, чтобы этот знак не зависел от порядка. Всё упирается в a + b + c и a * b * c. Точность в этом случае гораздо менее важна.
А сама задача - полигональное пересечение 2х геометрий.
Вот как раз и хотелось бы узнать, есть ли способы, кроме сортировки (уж отсортировать-то я, наверное, смогу) вычислить эти величины.
Если есть зависящие от языка, то интересует java. Как-то так
Задача появилась при попытке формализации геометрических величин в пространстве (например объём тетраэдра по 4м точкам).
И основная проблема - это вырожденные случаи, когда знак нуля может зависеть от порядка. Вот. Мне и нужно было так построить вычисления, чтобы этот знак не зависел от порядка. Всё упирается в a + b + c и a * b * c. Точность в этом случае гораздо менее важна.
А сама задача - полигональное пересечение 2х геометрий.
Вот как раз и хотелось бы узнать, есть ли способы, кроме сортировки (уж отсортировать-то я, наверное, смогу) вычислить эти величины.
Если есть зависящие от языка, то интересует java. Как-то так
А вы организуйте вычисления в пересечении 2 геометрий так, чтобы 2 раза один и тот же определитель считать не пришлось. А вообще без эпсилона вы от более сложных вырожденных случаев в этой задаче не избавитесь.
В качестве эпсилона выступает расстояние, на котором можно склеивать элементы.
А вот при вычислении относительного положения всё же надеюсь избавиться от шаманства вокруг нуля.
А вот при вычислении относительного положения всё же надеюсь избавиться от шаманства вокруг нуля.
http://aszt.inf.elte.hu/~gsd/halado_cpp/ch06s06.html
посмотри эту штуку. Для нормализации результатов туда можно вставить сортировку входных элементов, либо доработать менеджер для кеширующих вычислений, хранящий уже полученные значения.
Оба способа получатся хреновым в некоторых случаях. Например тебе нужно определить угол треугольника, и считаешь ты его через теорему косинусов. В случае реализации указанной фишки для угла ABC ты получаешь одинаковый результат, независимо от порядка перемножения сторон BA и BC. Но теперь представь, что таким же образом ты уже получил значения углов BAC и BCA, в таком случае ты можешь выяснить исходный узел через теорему о сумме углов треугольника и уже рискуешь получить неверный результат.
Вывод: часто не имеет смысла использовать машинную вещественную арифметику в вырожденных случаях, потому что в этом оказывается невозможно использовать значительную часть теорем касающихся исследуемых свойств объекта. Так что обычно для вычислений в вещественной арифметике достаточно показать близость результата вырожденному и бессмысленно исследовать этот момент подробнее. А если последнее всё же необходимо, то следует подумать об алгоритмах, которые это особо учитывают, а не модифицировать применяемые для общего случая
посмотри эту штуку. Для нормализации результатов туда можно вставить сортировку входных элементов, либо доработать менеджер для кеширующих вычислений, хранящий уже полученные значения.
Оба способа получатся хреновым в некоторых случаях. Например тебе нужно определить угол треугольника, и считаешь ты его через теорему косинусов. В случае реализации указанной фишки для угла ABC ты получаешь одинаковый результат, независимо от порядка перемножения сторон BA и BC. Но теперь представь, что таким же образом ты уже получил значения углов BAC и BCA, в таком случае ты можешь выяснить исходный узел через теорему о сумме углов треугольника и уже рискуешь получить неверный результат.
Вывод: часто не имеет смысла использовать машинную вещественную арифметику в вырожденных случаях, потому что в этом оказывается невозможно использовать значительную часть теорем касающихся исследуемых свойств объекта. Так что обычно для вычислений в вещественной арифметике достаточно показать близость результата вырожденному и бессмысленно исследовать этот момент подробнее. А если последнее всё же необходимо, то следует подумать об алгоритмах, которые это особо учитывают, а не модифицировать применяемые для общего случая
Оставить комментарий
danilov
Нужно написать функцию перемножения (и сложения) 3х чисел, a,b и с так, чтобы результат не зависел от порядка их следования.Что-то ничего кроме сортировки в голову не приходит. Но хочется побыстрее.
Желательно не используя специфику языка (но если что, язык - java)
upd. Арифметика вещественная