dc ( настольный калькулятор ) — кроссплатформенный калькулятор с обратной польской записью , поддерживающий арифметику произвольной точности . [1] Он был написан Лориндой Черри и Робертом Моррисом в Bell Labs . [2] Это одна из старейших утилит Unix , предшествовавшая даже изобретению языка программирования C. Как и другие утилиты того времени, он обладает мощным набором функций, но лаконичным синтаксисом. [3] [4] Традиционно программа калькулятора bc (с инфиксной нотацией ) была реализована поверх dc.
В этой статье приведены некоторые примеры в попытке дать общее представление о языке; полный список команд и синтаксиса можно найти на странице руководства по конкретной реализации.
dc — старейшая из сохранившихся программ на языке Unix . Когда Bell Labs получила PDP-11 , dc, написанный на языке B , стал первым языком, запущенным на новом компьютере, даже до появления ассемблера. [2] Кен Томпсон высказал мнение, что dc была самой первой программой, написанной на этой машине. [5]
Чтобы умножить четыре и пять в dc (обратите внимание, что большая часть пробелов необязательна):
$ cat << EOF > cal.txt 4 5 * p EOF$ dc cal.txt 20 $Результаты также доступны с помощью команд:
$ echo "4 5 * p" | dc или
$ dc - 4 5*pq 20$ dc 4 5 * p 20 q$ dc -e '4 5 * p' Это переводится как «поместить четыре и пять в стек, затем с помощью оператора умножения извлечь два элемента из стека, умножить их и поместить результат в стек». Затем pкоманда используется для проверки (вывода на экран) верхнего элемента в стеке. qКоманда завершает вызванный экземпляр dc. Обратите внимание, что числа должны быть отделены друг от друга, даже если некоторые операторы не нуждаются в этом.
Арифметическая точность изменяется с помощью команды k, которая устанавливает количество дробных цифр (количество цифр после точки ), используемых для арифметических операций. Поскольку точность по умолчанию равна нулю, эта последовательность команд дает 0в результате:
2 3 / п
Регулируя точность с помощью k, можно получить произвольное количество десятичных знаков. Эта последовательность команд выводит .66666.
5 тыс.2 3 / п
Для вычисления : ( вычисляет квадратный корень из вершины стека и используется для ввода отрицательного числа):v_
12 _3 4 ^ + 11 / v 22 -п
Чтобы поменять местами два верхних элемента стека, используйте rкоманду. Чтобы дублировать верхний элемент, используйте dкоманду.
Чтобы прочитать строку из stdin , используйте ?команду. Это оценивает строку так, как если бы это была команда dc, поэтому необходимо, чтобы она была синтаксически правильной и представляет потенциальную проблему безопасности, поскольку !команда dc допускает произвольное выполнение команды.
Как упоминалось выше, pпечатает верхнюю часть стека с новой строкой после нее. nизвлекает верхнюю часть стека и печатает ее без завершающей новой строки. fпечатает весь стек по одной записи на строку.
dc также поддерживает произвольные входные и выходные основания . iКоманда извлекает верхнюю часть стека и использует ее для входного основания. Шестнадцатеричные цифры должны быть в верхнем регистре, чтобы избежать конфликтов с командами dc, и ограничены AF. Команда oделает то же самое для выходного основания, но имейте в виду, что входное основание влияет на разбор каждого числового значения впоследствии, поэтому обычно рекомендуется сначала задать выходное основание. Поэтому 10oустанавливает выходное основание на текущее входное основание, но, как правило, не на 10 (десять). Тем не менее Aoсбрасывает выходное основание на 10 (десять), независимо от входного основания. Чтобы прочитать значения, команды K, Iи Oпомещают текущую точность, входное основание и выходное основание на вершину стека.
Например, для преобразования из шестнадцатеричного формата в двоичный:
$ echo 16i2o DEADBEEFp | dc 11011110101011011011111011101111 Помимо этих основных арифметических и стековых операций, dc включает поддержку макросов , условных операторов и сохранения результатов для последующего извлечения.
Механизм, лежащий в основе макросов и условных операторов, — это регистр , который в dc — это место хранения с одним именем символа, в котором можно сохранять и из которого можно извлекать данные: scвыталкивает вершину стека и сохраняет ее в регистре c, а lcзначение регистра c помещает в стек. Например:
3 сбн 4 лк * п
Регистры также можно рассматривать как вторичные стеки, поэтому значения можно помещать и выталкивать между ними и основным стеком с помощью команд Sи L.
Строковые значения заключены в [символы ]и и могут быть помещены в стек и сохранены в регистрах. aКоманда преобразует младший байт числового значения в символ ASCII или, если вершина стека является строкой, заменяет его первым символом строки. Нет других способов создания строк или выполнения манипуляций со строками, кроме как выполнить ее с помощью xкоманды или распечатать ее с помощью Pкоманды.
Персонаж #начинает комментарий к концу строки.
Макросы затем реализуются, позволяя регистрам и записям стека быть строками, а также числами. Строку можно вывести на печать, но ее также можно выполнить (т.е. обработать как последовательность команд dc). Так, например, мы можем сохранить макрос для добавления единицы и последующего умножения на 2 в регистре m:
[1 + 2 *] см
и затем (используя xкоманду, которая выполняет вершину стека) мы можем использовать ее следующим образом:
3 лм хр
Наконец, мы можем использовать этот механизм макросов для предоставления условий. Команда =rизвлекает два значения из стека и выполняет макрос, сохраненный в регистре, rтолько если они равны. Таким образом, эта строка печатается equalтолько в том случае, если два верхних значения в стеке имеют одинаковое значение:
[[равно]p] см 5 5 =м
Другие условные операторы — >, !>, <, !<, !=, которые выполняют указанный макрос, если два верхних значения в стеке больше, меньше или равны («не больше»), меньше, больше или равны («не меньше») и не равны соответственно. Обратите внимание, что порядок операндов в сравнениях неравенств противоположен порядку для арифметики; 5 3 -вычисляется как 5 - 3 = 2, но запускает содержимое регистра , поскольку .5 3 <tt3 < 5
Циклы тогда возможны путем определения макроса, который (условно) повторно вызывает себя. Простой факториал вершины стека может быть реализован как:
# F(x): вернуть x!# если х-1 > 1# вернуть х * F(x-1)# в противном случае# вернуть х[d1-d1<F*]dsFxp
Команда 1Qвыходит из макроса, позволяя выполнить ранний возврат. qвыходит из двух уровней макросов (и самого dc, если в стеке вызовов меньше двух уровней). zпомещает текущую глубину стека перед zоперацией.
Это реализовано с помощью макроса, хранящегося в регистре a, который условно вызывает себя, выполняя сложение каждый раз, пока в стеке не останется только одно значение. zОператор используется для помещения числа записей в стеке в стек. Оператор сравнения >выталкивает два значения из стека при выполнении сравнения.
dc -e "1 2 4 8 16 100 0d[+z1<a]dsaxp" И результат — 131.
Простое число является допустимым выражением постоянного тока, поэтому его можно использовать для суммирования файла, где каждая строка содержит одно число.
Это снова реализовано с помощью макроса, хранящегося в регистре a, который условно вызывает сам себя, выполняя сложение каждый раз, пока в стеке не останется только одно значение.
dc -e "0d[?+z1<a]dsaxp" < файл Оператор ?считывает другую команду из входного потока. Если входная строка содержит десятичное число, это значение добавляется в стек. Когда входной файл достигает конца файла, команда становится нулевой, и в стек не добавляется никакое значение.
{ echo "5" ; echo "7" ; } | dc -e "0d[?+z1<a]dsaxp" И результат — 12.
Входные линии также могут быть сложными командами постоянного тока.
{ echo "3 5 *" ; echo "4 3 *" ; echo "5dd++" ; } | dc -e "0d[?+z1<a]dsaxp" И результат — 42.
Обратите внимание, что поскольку dc поддерживает произвольную точность, не возникает проблем с числовым переполнением или потерей точности, независимо от того, сколько строк содержит входной поток, в отличие от столь же лаконичного решения в AWK .
Недостатки этого решения: цикл останавливается при обнаружении пустой строки во входном потоке (технически, любой входной строки, которая не добавляет хотя бы одно числовое значение в стек); и для обработки отрицательных чисел начальные экземпляры '-' для обозначения отрицательного знака должны быть изменены на '_' во входном потоке из-за нестандартного отрицательного знака dc. Оператор ?в dc не обеспечивает четкого способа отличить чтение пустой строки от чтения конца файла.
В качестве примера относительно простой программы на dc приведем следующую команду (в одну строку):
dc -e '[[Введите число (метры) или 0 для выхода]PAP]sh[q]sz[lhx?d0=zAk.0254/.5+0kC~1/rn[ футов ]Pn[ дюймов]PAPdx]dx' преобразует расстояния из метров в футы и дюймы; большая часть работы связана с запросом ввода, печатью вывода в подходящем формате и циклическим преобразованием другого числа.
В качестве примера приведем реализацию алгоритма Евклида для нахождения НОД :
dc -e '??[dSarLa%d0<a]dsax+p' # кратчайший
dc -e '[a=]P?[b=]P?[dSarLa%d0<a]dsax+[НОД:]Pp' # более простая для чтения версия Вычисление факториала входного значения,
dc -e '?[q]sQ[d1=Qd1-lFx*]dsFxp' Существуют также квайны на языке программирования dc; программы, которые выдают свой исходный код в качестве выходных данных.
dc -e '[91Pn[dx]93Pn]dx' dc -e '[91PP93P[dx]P]dx' dc -e '2p3p[dl!d2+s!%0=@l!l^!<#]s#[s/0ds^]s@[p]s&[ddvs^3s!l#x0<&2+lx]ds.x' Эту программу написал Мишель Шарпантье. Она выводит последовательность простых чисел. Обратите внимание, что возможна более короткая реализация, которая требует на четырнадцать символов меньше.
dc -e '2p3p[pq]s$[l!2+ds!l^<$dl!%0<#]s#[+dvs^1s!l#x2l.x]ds.x' dc -e '[n=]P?[p]s2[lip/dli%0=1dvsr]s12sid2%0=13sidvsr[dli%0=1lrli2+dsi!>.]ds.xd1<2' Эту программу также написал Мишель Шарпантье. [6]
Есть более короткий
dc -e "[n=]P?[lfp/dlf%0=Fdvsr]sF[dsf]sJdvsr2sf[dlf%0=Flfdd2%+1+sflr<Jd1<M]dsMx" и более быстрое решение (попробуйте с 200-битным числом 2 200 -1 (вход 2 200^1-)
dc -e "[n=]P?[lfp/dlf% 0=Fdvsr]sFdvsr2sfd2%0=F3sfd3%0=F5sf[dlf%0=Flfd4+sflr>M]sN[dlf%0=Flfd2+sflr>N]dsMx[p]sMd1<M" Обратите внимание, что последний можно ускорить еще больше, если заменить доступ к константе на доступ к регистру.
dc -e "[n=]P?[lfp/dlf%l0=Fdvsr]sF2s2dvsr2sf4s4d2%0=F3sfd3%0=F5sf[dlf%l0=Flfdl4+sflr>M]sN[dlf%l0=Flfdl2+sflr>N]dsMx[p]sMd1<M" Реализация алгоритма Чудновского на языке программирования dc. Программа будет выводить все лучшие и лучшие приближения по мере выполнения. Но поскольку pi — трансцендентное число, программа будет продолжать работу до тех пор, пока не будет прервана или не исчерпаются ресурсы машины, на которой она запущена.
dc -e '_640320[0ksslk3^16lkd12+sk*-lm*lhd1+sh3^/smlxlj*sxll545140134+dsllm*lxlnk/ls+dls!=P]sP3^sj7sn[6sk1ddshsxsm13591409dsllPx10005v426880*ls/K3-k1/pcln14+snlMx]dsMx' Быстрая реализация «разделяй и властвуй» той же формулы, которая удваивается в размере на каждой итерации. Она оценивает конечное число, если суммирует как точное рациональное число, и выполняет только одно большое деление и квадратный корень на итерацию. Она быстрая, но все равно будет быстро замедляться по мере увеличения размера дроби.
dc -e '1Sk1SR13591409dSBSP426880dSQ4/3^9*SC[0r-]s-[lkE*1-k10005vlQ*lP/nAan0k]dSox[Lkd1+Skdd1+Sk3^lC*SQ2*1-d3*d*4-*dSR545140134LB+dSB*lk2%0=-SP]dszx[LRLRdLP*LPLQdLQ*SQ*+SP*SR]sc[d1-d0<yd0<yd0=z0=zlcx]sy0[lcxlox1+lyxllx]dslx' Более сложный пример использования dc, встроенный в скрипт Perl , выполняет обмен ключами Диффи–Хеллмана . Это было популярно в качестве блока подписи среди шифропанкистов во время дебатов ITAR , где короткий скрипт мог быть запущен только с помощью Perl и dc, вездесущих программ в операционных системах типа Unix: [7]
#!/usr/bin/perl -- -export-a-crypto-system-sig Diffie-Hellman-2-lines ( $g , $e , $m ) = @ARGV , $m || die "$0 gen exp mod\n" ; print `echo "16dio1[d2%Sa2/d0<X+d*La1=z\U$m%0]SX$e"[$g*]\EszlXx+p | dc` Комментированная версия немного проще для понимания и показывает, как использовать циклы, условные операторы и qкоманду возврата из макроса. С версией GNU dc команда |может использоваться для выполнения модульного возведения в степень произвольной точности без необходимости писать функцию X.
#!/usr/bin/perlmy ( $g , $e , $m ) = map { "\U$_" } @ARGV ; die "$0 gen exp mod\n" unless $m ; print `echo $g $e $m | dc -e ' # Шестнадцатеричный ввод и вывод 16dio # Считать m, e и g из stdin в одну строку ?SmSeSg # Функция z: вернуть g * вершину стека [lg*]sz# Функция Q: удалить вершину стека и вернуть 1 [sb1q]sQ# Функция X(e): рекурсивное вычисление g^e % m # То же самое, что и Sm^Lm%, но обрабатывает произвольно большие экспоненты. # Стек на входе: e # Стек на выходе: g^e % m # Так как e может быть очень большим, здесь используется свойство g^e % m == # if( e == 0 ) # вернуть 1 # x = (g^(e/2)) ^ 2 # if( e % 2 == 1 ) # x *= g # вернуть x % [ d 0=Q # вернуть 1, если e==0 (иначе стек: e) d 2% Sa # Сохранить e%2 в a (стек: e) 2/ # вычислить e/2 lXx # вызвать X(e/2) d* # вычислить X(e/2)^2 La1=z # умножить на g, если e%2==1 lm % # вычислить (g^e) % m ] SXle # Загрузить e из регистра lXx # вычислить g^e % m p # Распечатать результат '` ;Если переменная окружения DC_LINE_LENGTH существует и содержит целое число, большее 1 и меньшее , вывод цифр числа (в соответствии с базой вывода) будет ограничен этим значением, после чего будут вставлены обратные косые черты и символы новой строки. Длина строки по умолчанию — 70. Специальное значение 0 отключает переносы строк.
