Category: it

Category was added automatically. Read all entries about "it".

Программист - он и в JPL программист

Когда-то я писал, что программисты в USNO применяли для интерполяции классическую формулу Лагранжа, что глупо и неэффективно. Видимо, им лень было читать учебник по численным методам дальше первой страницы.

Теперь напоролся на глюк в коде JPL, с помощью которого читаются файлы эфемерид серии DE (DE200, DE405 и т.п.). Вот кусок их кода (подпрограмма READHD в файле testeph1.f):

read(NRFILE,REC=1)TTL,(NAMS(K),K=1,OLDMAX),SS,NCON,AU,EMRAT,
& ((IPT(I,J),I=1,3),J=1,12),NUMDE,(IPT(I,13),I=1,3),
& (NAMS(J),J=K,NCON),
& (IPT(I,14),I=1,3),
& (IPT(I,15),I=1,3)
Тут из первой (заголовочной) записи читаются сначала имена констант
(NAMS(K),K=1,OLDMAX)
числом OLDMAX (= 400), затем разные другие величины, потом остаток имен констант
(NAMS(J),J=K,NCON)
Так получилось, потому что в старых теориях констант было мало, вот и зарезервировали в файле для них 400 мест. За ними в файле следовали прочие параметры. Когда число констант увеличилось сверх лимита (в DE430, например, их 572), решили формат файла не менять, а константы дописать в конец.

Когда я компилировал это код транслятором gfortran из семейства GCC без оптимизации, все работало как нужно. Но стоило включить оптимизацию O2, как получалась полная фигня: порядок чтения нарушался, элементы массива IPT получали неправильные значения.

Засада была вот в этом элементе списка чтения:
(NAMS(J),J=K,NCON)
Переменная K использовалась как параметр цикла в одном из предыдущих элементов этого списка. Поэтому нельзя ожидать, что по окончании цикла она будет иметь определенное значение. Без оптимизации она действительно сохраняла последнее присвоенное значение. Но оптимизирующий компилятор построил код иначе, что и привело к проблемам. Понятно даже, что именно сделал компилятор: он вычислил начальные и конечные значения параметров всех внутренних циклов до начала выполнения оператора READ, когда переменная K еще не имена конкретного значения. 

Ежу понятно, что программисту надо бы читать описание языка, прежде чем генерить год. Однако в индустрии победил подход Дональда Кнута: "мне лень про это писать, спроси у кого-нибудь, кто знает" (книга Кнута The Joy of TEX изобилует подобными советами). А сейчас еще любят учиться по роликам на Ютубе.

Короче говоря, перепишите это оператор так:
        read(NRFILE,REC=1)TTL,(NAMS(K),K=1,OLDMAX),SS,NCON,AU,EMRAT,
& ((IPT(I,J),I=1,3),J=1,12),NUMDE,(IPT(I,13),I=1,3),
& (NAMS(J),J=OLDMAX+1,NCON),
& (IPT(I,14),I=1,3),
& (IPT(I,15),I=1,3)
и будет вам счастье.

Оригинал этого сообщения находится здесь.

Калькуляторная амбидекстрия

Амбидекстр - человек, который одинаково владеет правой и левой рукой, без выделения ведущей.

Я вспомнил это слово, изучая в выходные дни старые микрокалькуляторы, в основном программируемые. Есть два способа вычисления выражений. Первый известен всем и называется "алгебраической логикой вычислений". На калькуляторе с такой логикой вы нажимаете те же кнопочки, что используются в математической записи выражения: 2×2= (получается, очевидно, 4).

Другой способ - обратная бесскобочная (польская) запись. Её суть - сначала вводятся аргументы, а потом указывается, какую операцию над ними нужно совершить. Там нужно нажимать так: 2↑2× (и получается тоже 4).

Традиционно советские программируемые калькуляторы (Б3-21, Б3-34, МК-52 и др.) использовали обратную бесскобочную запись. Столкнувшись с ними где-то в 5-6 классе, я без труда освоил такой метод и даже научился программировать. А мои одноклассники пользовались непрограммируемыми калькуляторами, которые (за исключением Б3-19М) имели алгебраическую логику.

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

Оригинал этого сообщения находится здесь.

Астрономическая задача для программистов

Почему она астрономическая - в самом конце. А сама задача такая.

Вариант 1, простой, но бесполезный.

Дано конечное множество точек на плоскости. Построить выпуклый многоугольник минимальной площади (такой, что его вершинами являются только точки из множества), и найти эту площадь.

Решение, возможно, не самое быстрое, находится сразу. Выбрать произвольную окружность, залючающую все точки множества (это возможно, ибо множество конечно). Выбрать любую точку вне окружности, выпустить из этой точки луч, не пересекающий окружность. Начать вращать луч в каком-то направлении до первого пересечения с точкой множества. Эта точка будет первой вершиной искомого многоугольника. Затем продолжить вращать луч в том же направлении вокруг этой вершины до касания следующей точки множества. И т.д. В итоге построим многоугольник.

Алгоритм нужно еще формализовать, но идея, думаю, понятна.

Вариант 2, реальный, но непонятный.

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

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

Задача, таким образом, не математическая, а алгоритмическая.

К астрономии имеет отношение вот какое. Есть облако частиц. Первоначально оно занимает очень небольшой объем вокруг известной точки. Затем частицы начинают двигаться под действием различных сил (в моем случае - гравитация и световое давление). Через какое-то время облако "расплывается". Требуется оценить объем и плотность расплывшегося облака.

Как я делал до сих пор? Рисовал проекции облака на две взаимно перпендикулярные плоскости и перемножал площадь одной проекции на характерную толщину другой. Вполне себе оценка. Но хочется как-то поизящнее.

UPD. Оказалось, задача эта хорошо известна в вычислительной геометрии и называется "построением выпуклой оболочки". 

Оригинал этого сообщения находится здесь.
инспектор

Алгол жив!

Люди моего поколения еще помнят, что компьютеры появились не сразу в виде смартфонов и планшетов. Когда-то они были очень большие и занимали целый зал. Несколько сотен операций в секунду считалось высокой скоростью. И языки программирования - это не только Си и Visual Basic. Люди еще постарше (я - исключение) помнят такой язык Алгол-60. Число 60 в его названии - год официального опубликования описания этого языка. Причем, синтаксис его был описан с помощью формального языка БНФ - Нормальной Формы Бэкуса. В 60-е годы для этого языка создали массу трансляторов для самых разных машин. В СССР трансляторы с Алгола ТА-1М и ТА-2М работали на ЭВМ с системой команд М-20: М-220, М-222, БЭСМ-4. На советской транзисторной супер-ЭВМ было несколько трансляторов этого языка: ГДР-Алгол, БЭСМ-Алгол, система "Альфа" и др. В книгах и журналах публиковалась масса алгоритмов для решения самых разных (но большей частью вычислительных) задач на языке Алгол. Я уже упоминал книгу Уилкинсона и Райнша "Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра", который содержит программы непревзойденного качества.

Алгол-60 имеет, среди прочих, особенность, которая не встречается в современных языках. Это передача параметра в процедуру по наименованию. Нынешние программисты знают два способа: по значению (единственный способ в Си) и по ссылке. Передача по имени отличается и от того, и от другого, потому что в процедуру передается не значение переменной и не указатель на место в оперативной памяти. Передача выполняется так, как будто фактический параметр подставляется в процедуру вместо формального. С непривычки трудно уловить разницу. Но вот вам пример использования такой передачи под названием "трюк Йенсена":

begin
  
  procedure p(a, b);
    integer a,b;
  begin
    for a:=1 step 1 until 10 do
      b := 0
  end p;

  integer i; integer array s[1:10];
  p(i,s[i])

end

Процедура p имеет два параметра, которые передаются по имени (в противном случае они были бы специфицированы как "value a,b;"). Первый параметр используется в качестве переменной цикла, а второму в этом цикле присваивается нулевое значение. При передача по ссылке (не говоря уже о передаче по значению) такой цикл лишен смысла. Зачем, в самом деле, 10 раз записывать в одно и то же место в памяти нуль? Но в том и фокус, что место это не одно и то же! При вызове процедуры фактическими параметрами являются i и s[i]. Способ передачи по наименованию предполагает подстановку параметров в тело процедуры. И получается, что выполняется следующий цикл:

for i:=1 step 1 until 10 do
      s[i] := 0

Согласитесь, это совсем другое дело. Кстати, хорошая задача для студентов-программистов: как можно реализовать такую передачу в трансляторе?

Но, казалось бы, время этого языка прошло. Ориентированный исключительно на вычисления, он непригоден для решения всех прочих задач. В частности, язык не содержит никаких средств для работы с символами, нет в нем и средств для создания интерфейса с пользователем. А откуда они могли взяться, если в 60-е гг. интерфейсом были устройство ввод перфокарт и АЦПУ (так тогда называли принтеры)? В то же время масса записанных на нем алгоритмов по-прежнему востребована, только перед употреблением эти алгоритмы переписываются на другие, современные языки: на тот же Си, например, или Фортран (в его нынешнем, не историческом виде).

И вот недавно я узнаю, что пациент еще не умер! Частью проекта GNU является конвертер marst с Алгола-60 на Си. Очень компактная программа прекрасно работает у меня в операционных системах на базе Linux, FreeBSD и даже под Windows в окружении CygWin. Конвертер прошел замечательный тест на зрелось - Man or Boy. А вот самый известный рабочий транслятор прошлого ТА-1М такой тест не пройдет, поскольку вообще не допускает рекурсию. С помощью marst я успешно транслировал оригинальный интегратор Булирша и Штёра и проверил некоторые недавние работы, касающиеся выявления устойчивых орбит в системе α Centauri. Если справлюсь с ленью, напишу об этом позже. :)