Saturday, May 25, 2013

21.05.2013 Хазин: Западный проект закончился (нарезка)

Почему в современных языках программирование нет типа данных для рациональных чисел?

Если используется арифметика с плавающей запятой, там все вычисления производятся с округлениями. Более того, ни всякое действительно число может быть адекватно представлено как машинный тип данных. Начнем с того, что действительные числа "недискретны", в то время как числа с плавающей запятой таковыми являются. В частности, можно представить действительные числа с точностью до одного ULP-a (или половины, я уже точно не помню...). Т.е. машина не различает целые интервалы чисел, при чём длина такого интервала различна, зависит от "масштаба". Можно и не лезть в такие дебри, а рассмотреть более простые примеры. Классический пример, число 0.1, которое в двоичной системе счисления имеет бесконечное (периодическое) представление (та же проблема с числом 1/3, которое 0.333333...).

Ниже есть продолжение.

В случае с числом 0.1, при использование fix-point arithmetic, такое число легко представимо (пример, BigDecimal). Но у BigDecimal-а есть свои минусы, в частности, тоже число 1/3 не представимо

BigDecimal one = new BigDecimal("1");
BigDecimal three = new BigDecimal("3");
BigDecimal result = one.divide(three);
System.out.println(result);

Exception in thread "main" java.lang.ArithmeticException: Non-terminating decimal expansion; no exact representable decimal result.
   at java.math.BigDecimal.divide(BigDecimal.java:1616)

нужно использовать RoundingMode (или MathContext), т.е. мы возвращаемся опять к округлениям. Правда, в отличие от floating-point arithmetic, где у нас нет контроля как именно и куда они будут делаться, здесь у нас такой контроль появляется. Но это не особо помогает из-за следующих проблем. Допустим, наш input известен с точностью два знака после запятой, точность output тоже должна быть 2 знака после запятой, с какой точностью нужно делать вычисления? Тут мы наталкиваемся на две проблемы:

- техническая, BigDecimal (MathContext) оперируют термином precision - The number of digits to be used for an operation - количеством знаков используемых при операции, т.е. это включает в себя все знаки и до и после запятой, таким образом если мы оперируем как числами в диапазоне "тысяч" так и числами в диапазоне "миллиардов", нам нужен разный precision...

- принципиальная, при математических преобразованиях мы теряем точность ("погрешность накапливается"). Таким образом, промежуточные значения мы должны хранить с большей точностью. Вопрос с какой? Теоретически, для каждого вычисления мы может его подсчитать (через теорема об оценке конечных приращений aka теорема Лагранжа о среднем значении, но это явно не практично. Поэтому, обычно, такое значение подбирается эмпирически.

Всех этих сложностей можно избежать, если оперировать рациональными числами, почему этого не далают?

P.S. Мой друг получил разные ответы под Linux и Windows запустив один и тот же код на C++ из-за различий в округлениях типа double...

См. также:
Неожиданные эффекты арифметики с плавающей запятой с кодом на Java и ссылками на документацию.
О вреде округления
Rounding error on Professional Entry Test Sample Questions - тригером к написанию этого поста была математическая ошибка в "каком-то" тесте. В конце поста я привожу реальный пример, который иллюстрирует почему при input-е и output-е с заданной точностью промежуточные вычисления должны быть с большей точностью.
Пи равно трём. Часть II. - начинается с обсуждения об отличии рациональных и иррациональных чисел и заканчивается с описания эффекта "накопления погрешности" (см. предыдущею ссылку) при работе с калькулятором.


Сирия атаковала водопровод Хайфы (Hebrew, Russian)



Сирийские хакеры три недели назад провели кибернетическую атаку на систему управления водоснабжением города Хайфа. Об этом сообщил председатель национального совета по научным исследованиям профессор Ицхак Бен-Исраэль, генерал запаса, выступавший в Беэр-Шеве в рамках встреч "Шабат-тарбут".

Бен-Исраэль добавил, что Израилю приходится каждый день отбивать сотни попыток хакеров из разных стран атаковать компьютерные системы, которые имеют жизненное значение, и их вывод из строя может иметь критическое значение.

...Заявление Бен-Ицхака последовало на фоне публикации в New York Times, в которой официальные эксперты обвиняют Иран в инициировании серии хакерских атак на американские корпорации, включая банки и энергетические компании.

По утверждению экспертов, целью хакеров было не получение доступа к информации, а саботаж работы крупных инфраструктурных объектов.

Согласно управлению национальной безопасности США, серия атак началась несколько месяцев назад. Большинство этих атак производится с ближневосточных серверов.
http://cursorinfo.co.il/news/novosti/2013/05/25/siriyskie-hakeri-atakovali-sistemu-kontrolya-vodosnabzheniya-v-hayfe/
http://txt.newsru.co.il/israel/25may2013/hak310.html

В Иордании пройдут учения 18 армий

В ближайшее время на территории Иордании пройдут широкомасштабные военные учения армейских подразделений 18 стран мира.

В общей сложности в учениях примут участие 15 тысяч военнослужащих армий Иордании, Ливана, Египта, Пакистана, Турции, Катара, ОАЭ, Саудовской Аравии, Йемена, а также США, Канады, Великобритании, Франции, Чехии, Польши, Италии и ряда других стран.

Учения будут проходить на полигонах и базах армии Хашимитского королевства, однако министерство обороны Иордании не указало точные сроки их проведения.
http://txt.newsru.co.il/mideast/25may2013/jordan319.html

Мои впечатления о книге "Второе нашествие марсиан" Аркадий Стругацкий, Борис Стругацкий

Из архивов.
Подзаголовок: Записки здравомыслящего.
Эпиграф: О, этот проклятый конформистский мир!

Краткое содержание. Страну за одну ночь, практически без боев захватили Марсиане. Они прибыли на Землю за желудочным соком людей. Они брали "излишки" желудочного сока, не причиняя вреда здоровью и платили за это деньги. Ещё они скупили всю пшеницу и раздали на очень выгодных условиях, какой-от новый посев, который повышал аппетит и следовательно выработку желудочного сока. Фермеры получили от этого огромный доход.

Хорон является образованным человеком, редактором газеты. После захвата Земли марсианами ушел в подполье и стал бороться с ними. За партизанами фермеры устроили травлю и сдавали их марсианам.

Далее я привожу цитату:

"...И Харон говорил.
У людей больше нет будущего. Человек перестал быть венцом природы. Отныне и присно и во веки веков человек будет рядовым явлением натуры, как дерево или лошадь не более. Культура и вообще весь прогресс потеряли всякий смысл. Человечество больше не нуждается в саморазвитии, его будут развивать извне, а для этого не нужны школы, не нужны институты и лаборатории, не нужна общественная мысль, философия, литература,- словом, не нужно все то, что отличало человека от скота и что называлось до сих пор цивилизацией. Как фабрика желудочного сока, Пандарей [один из действующих лиц, весьма посредственный] Альберт Эйнштейн ничем не лучше Пандарея и даже наверняка хуже, потому что Пандарей отличается редкостной прожорливостью. Не в громе космической катастрофы, не в пламени атомной войны и даже не в тисках перенаселения, а в сытой, спокойной тишине кончается...история. "Подумать только,- с надрывом проговорил он, уронив голову на руки,- не баллистические ракеты, а всего-навсего горсть медяков за стакан желудочного сока погубили цивилизацию..."

Ниже есть продолжение.

... [ответ]

"У вас была слишком легкая жизнь, сын мой... Вы заелись. Вы ничего не знаете о жизни. Сразу видно, что вас никогда не били по зубам, что вы не мерзли в окопах и не грузили бревна в плену. У вас всегда было что кушать и чем платить. Вот вы и привыкли смотреть на мир глазами небожителя, этакого сверхчеловека. Экая жалость, что цивилизацию продали за горсть медяков! Да скажите спасибо, что вам за неё дают эти медяки! Вам они, конечно, ни к чему. А вдове, которая одна поднимает троих детей, которая должна их выкормить, вырастить, выучить? А ... калеке, получающему грошовую пенсию? А фермеру? Что вы предложите фермеру? Сомнительный социальный идейки? Книжечки-брошюрочки? Эстетскую ваше философию? Да фермер плевал на все это! Ему нужна одежда, машины, нужна уверенность в завтрашнем дне! Ему нужно иметь постоянную возможность вырастить урожай и получить за него хорошую цену! Вы смогли ему это дать?

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

Харон... постарайтесь хоть на минутку спуститься из облачных сфер на грешную землю. Постарайтесь понять, что человеку больше всего на свете нужно покой и уверенность в завтрашнем дне. Ведь ничего же страшного не случилось. Вот вы говорите, что человек превратился теперь в фабрику желудочного сока. Это громкие слова, Харон. На самом-то деле произошло нечто обратное. Человек, попавши в новые условия существования, нашел превосходный способ использования своих физиологических ресурсов для упрочнения положения в этом мире. Вы называете это рабством, а всякий разумный человек полагает это обыкновенной сделкой, которая должна быть взаимовыгодной. О каком рабстве может идти речь, если разумный человек уже сейчас прикидывает, не обманывают ли его, и, если действительно обманывают, то, уверяю вас, он сумеет добиться справедливости. Вы говорите о конце культуры и цивилизации, но это уже вовсе не правда! Непонятно даже, что вы имеете в виду. Газеты выходят ежедневно, выпускаются новые книги, сочиняются новый телеспектакли, работает промышленность... Харон! Ну чего вам не достаёт? Вам оставили все, что у вас было: свободу слова, самоуправление, конституцию. Мало того, вас защитили от господина Лаомедонта [мэр, систематически разворовывал казну города]! И вам, наконец, дали постоянный источник доходов, который совершенно не зависит ни от какой конъюнктуры".

... Оказывается, два дня назад Харон во главе группы инсургентов [партизанов] из пяти человек захватили марсианскую машину. Каково же было их изумление, когда им из машины выбрался совершенно трезвый Минотавр* [смотри сноску в конце текста] с портативным аппаратом лоя отсасывания желудочного сока. "Что ребята, выпить захотелось?- спросил он.- Давайте, это я вам сейчас устрою. Кто первый?" Инсургенты даже растерялись.

Придя в себя, они без всякого удовольствия накостыляли Минотавру по шее за предательство и отпустили его вместе с машиной. Они-то собирались захватить машину, освоиться с управлением, затем проникнуть на ней на марсианский пост и устроить там побоище, на этот эпизод на них так подействовал, что им стало на все наплевать. Вечером того же дня двое из них ушли по домам, а на другое утро остальных захватили фермеры... Харон, следовательно, побывал в плену у марсиан...обращались с ним превосходно, умыли его, одели, подлечили, дали ему автомобиль... и отпустили с миром.

"...марсиане мне говорили точь-в-точь то же самое, что и вы...И особенно они напирали на то, что я элита общества, что они испытывают ко мне глубокое уважение и не понимают, почему это я и мне подобные занимаются террористическими атаками вместо того, чтобы создать разумную оппозицию. Они предлагают нам бороться с ними легальными средствами, гарантируя полную свободу печати и собраний. Славные ребята - марсиане, верно?"
"У меня нет слов"...
"У меня тоже,-отозвался Харон, снова помрачнев.- У меня к сожалению тоже пока нет слов, а их надо найти. Грош нам всем цена, если мы их не найдем"

----------------------
* Это цитата с начала рассказа.
"Оказывается, Минотавр въехал своей цистерной в ювелирную витрину, и народ собрался посмотреть, как он грязный, распухший, с утра уже опять пьяный даёт показания инспектору. И ведь ясно, полиции не надо было отпускать Минотавра так рано, знали же, что непременно напьётся раз у него запой. Но с другой стороны, как его не выпустить, когда он единственный золотарь в городе? Тут уже одно из двух: либо ты занимайся перевоспитанием Минотавра и тони в нечистотах, либо иди на компромисс во имя гигиены."