Программирование на языке высокого уровня

числовая величина, «чистая», отвлеченная от каких-либо измеряемых объектов и единиц

измерения, количественная мера, выраженная в стандартных единицах.

Обозначение (форма, внешнее представление) числа – это его название или знак в некотором языке или системе обозначений, позволяющих отличать данное число от других.

9, IX, девять, nine, 1001(2)

Значение числа инвариантно (не зависит от обозначения).

чисел (знаковые обозначения) некоторым регулярным способом.
Непозиционные системы счисления возникли первыми,

они основаны на простом суммировании «весов» – цифр - «разновесов», занятых в записи числа.
Например, римская с.с., где все цифры могут браться плюсом или минусом, в зависимости от позиции этой цифры относительно более «тяжелых».
IX, XI
Позиционные системы счисления : число цифр конечно, вклад каждой цифры зависит от «веса» ее позиции (разряда) в записи числа.

Общие свойства b-ичных позиционных систем счисления (b-с.с.) определяются параметром

b - основанием с.с., которое определяет количество цифр, используемых для записи числа:
от 0 до b – 1, если b  10.
Если b = 16, то используются буквы:
10 – A
11 – B
12 – C
13 – D
14 – E
15 – F

позиции (разряда), в которой расположена цифра ai .

Запись числа

называется k-значной, если индекс
разряда первой значащей цифры числа равен k – 1.

Примеры
10011001(2), 248933, 7DAB(16),
123454(5) - неправильная запись

числа.
N(S) – его значение.
S =
bi – явно указывают веса разрядов,

определяющих вклад каждой цифры в значение числа,

bi называется единицей i-го разряда b-ичного числа.

ai – количество полных единиц i-го разряда, которое останется после вычета всевозможного числа единиц старших разрядов.

единиц i-го разряда в числе.

с.

Доказательство (от противного).

Вход: b > 0, k > 0 (число цифр), набор

ak-1, ak-2, … , a1, a0.
; (S – накапливает степень,
N – значение)
цикл по i := 1 до k – 1




конец цикла;
Выход: N
(2k - 2) операций *
(k-1) операций +

Вход: b > 0, k > 0 (число цифр), набор

цикл по i от k-2 вниз до 0
N := N  b + ai ;
конец цикла;
Выход: N

k-1 операция *
k-1 операция +

N ≥ 0, b > 0;
i := 0;

цикл
ai := N mod b; (mod – остаток от деления нацело)
N := N div b; (div – целое деление)
i := i + 1;
пока N ≠ 0;
k := i;
Выход: набор ai , k ( число значащих цифр)
минимальное число операций деления = k

от деления на 2
325(10) = 101000101(2)

знаков k, то нижний
индекс суммы равен —к .




0.375=(3+(7+5/10)/10)/10=(3+(7+(5+0)/10)/10)/10

S

=

, 1;

+ 0.5 + 0.125
= 1.625

Nf(«1.101(2)») =(1 +(0

+(1 +0)/2)/2)/2
= (1 + (0 + 0.5)/2 )/2
= (1 + 0.25) / 2 = 0.625

Nf(«0.01(3)») = 13-2 = = 0.(1)

первой цифре дробной части числа Nf Алгоритм А4: перевод дробной

части из 10-с. с. в b-с.с

Вход: Nf ( 0 ≤ Nf < 1), b >1;
i := -1;
цикл
([x]-взятие целой части числа)
( остается в том же диапазоне )
i := i – 1;
пока
k := i;
Выход: набор (число значащих цифр).
Алгоритм А4 может не завершиться, если данное число не представимо конечной дробью в b-с.с

Требуется k умножений (выражение Nf*b можно вычислять в цикле один
раз и хранить в промежуточной переменной).

основанием b в том и только в том случае, когда

все числа из разложения q на простые множители входят в такое же разложение b (количество повторений не учитывается).

Пример

121/675 конечна в 15-с.с.:
675 = 33*52; 15 = 3*5;

1/675 = 5*15-3 = 0.005(15);
121*5/15-3 = (2*152 + 10*151 + 5)/15-3 = 2/15-1 + 10/15-2 + 5/15-3
121/675 = 0.2A5(15);

1/10 бесконечна в 2-с.с. !!!!

b > 1, к > 0 (число дробных цифр), набор

(S накапливает степень, — значение )
цикл по i от -1 вниз до -k


;
конец цикла
Выход:

2k операций *, /
k операций +

из b-с.с. в 10-с.с. ( из формулы (7) по схеме

Горнера)

Вход: b >1, k > 0 (число цифр), набор

цикл по i от –k до -1

конец цикла;
Выход:

k операций + и /

на b становится целым (это умножение соответствует сдвигу точки на

k позиций вправо)

Алгоритм А7

• найти целое N1 = N * b1k (умножением или сдвигом точки);
• выполнить для N1 один из алгоритмов А1 или А2, затем АЗ;
• разделить полученный результат на b1k в системе b2

переведем в 10-с.с.  45
3) разделим: 45/8 = 5.625(10)

101.101=1*22+1*20+1*2-1+1*2-3=5+1/2+1/8=5.625

b1 и b2 связаны соотношением b2= b1m для некоторого

натурального т, то такие системы счисления называются кратными.

Перевод числа из одной с. с. в другую для таких систем можно выполнить проще.

Сгруппируем цифры в b1-записи числа по m от точки влево и вправо (добавив при нехватке цифр нужное количество незначащих нулей):

b1 в степени, равной индексу цифры), вынесем за скобки из

каждой группы i общий множитель
(b1im = (b1m)i = b2i)
и обозначим для каждой группы

Тогда значение исходного числа может быть представлено в виде:

N(S’) = Ak’* b2k’ + … + Ai* b2i + ... + А0*b20 + А-1*b2-1+ … А-j b2-j,

что по определению совпадает со значением записи того же числа в b2-с.c. c цифрами Аi, если заметить, что Аi, действительно могут принимать все значения от 0 до b1m − 1 = b2 − 1.

b1 > 1, b2 = b1m, b1 - представление числа;

•

разбить число на группы по т цифр, начиная от точки, в обе стороны (если в крайних группах цифр меньше т, добавить незначащие нули: в целой части спереди, в дробной сзади);
• заменить каждую группу b2-цифрой по формуле (8) или таблице.

Выход: b2 -представление исходного числа.

1, b2= b1m; b2-представление числа;

заменить каждую b2-цифру цепочкой

из т b1-цифр по формуле (8) или таблице;
отбросить незначащие нули слева и справа.

Выход: b1-представление исходного числа.

для арифметических операций сложения, вычитания, умножения и деления (в том

числе, вычисления «столбиком») являются символьными, потому что оперируют входными, выходными и промежуточными данными как строками символов.
Символьные вычисления являются формальными в том смысле, что манипулируют только знаками, не обращаясь к их значениям.
Абстрагирование от смысла данных различной природы и описание алгоритма в терминах чисто символьных преобразований является одним из основных методов программирования обработки данных произвольной природы

слагаемые;
• выравнивание: расположить слагаемые одно под другим в произвольном порядке

так, чтобы разряды с одинаковым весом находились друг под другом; если какое-то число короче других слева или справа, дополнить его нулями;
• начальные установки:
обнулить цифру переноса в следующий разряд;
установить результат равным пустой строке;
• цикл по текущему разряду от младшего до старшего:
определить сумму переноса и цифр в столбце текущего разряда чисел; младшую цифру суммы записать в текущий разряд результата, старшую — в перенос;
конец цикла;
• окончание: если перенос не равен 0, то дописать перенос в начало результата

Выход: строка, представляющая результат.

цифровых символов, — это поразрядное сложение в цикле.
Действительно, из

одного лишь вида знаков «2» и «3» нельзя извлечь информацию, что результатом их сложения будет знак «5».
Эти сведения можно задать, например, двумя таблицами сложения: в одной для каждой пары цифр записать младшую цифру результата, в другой — цифру переноса («0» или «1»);
исчерпав таким образом все немногочисленные случаи, можно заменить операцию сложения значений операцией выборки знака из таблицы.
Чтобы учесть сложение с переносом, можно завести две пары
таблиц или записать в каждую клетку по две цифры.

с. при соответствующей замене таблиц сложения.







Нетрудно обобщить алгоритм А10 для

одновременного сложения нескольких чисел, а также аналогичными рассуждениями показать, что алгоритмы вычисления «столбиком» для вычитания, умножения и деления универсально применимы к произвольной
с. с. при замене соответствующих таблиц.

с. число b всегда имеет представление «10(b)».
Умножение на b

сводится просто к дописыванию 0 справа к
целому числу или (что то же), сдвигом b-ичной точки на один
разряд вправо.
Деление на b равносильно сдвигу точки на один разряд влево
или отбрасыванию младшей цифры целого числа — при делении
нацело.
Аналогично число b всегда представляется единицей с k нулями,
а умножение (деление) на b сводится к сдвигу точки на k
позиций вправо (влево).
Остатком от деления целого числа нацело на b является число,
составленное из k младших цифр. Добавление k нулей справа и
отбрасывание k младших цифр можно рассматривать как две
новые операции арифметического сдвига на k позиций.

можно рассматривать как операции арифметического сдвига на k позиций.
В Си

определены операции арифметического сдвига на k позиций, которые равносильны умножению или целочисленному делению на 2k.
<< — сдвиг влево
>> — сдвиг вправо
Примеры:
a = 5 << 3; /* после выполнения присваивания a будет иметь значение 40 */
b = 112 >> 4; /* b будет равно 7 */

— «истину»,
то таблица сложения совпадет с таблицей значений для

логической операции «исключающее или», а таблицы умножения и переноса при сложении — с операцией «и».
На этом совпадении основана схемная реализация в компьютерах поразрядной двоичной арифметики с помощью примитивных логических элементов (вентилей).

Другая аналогия — «минимаксная»: нетрудно видеть, что
ab = min(a,b), a+b = min(a,b)+ max(a,b).

Наконец, умножение «столбиком» многозначных чисел в двоичной с. с. реализуется только с помощью операций сложения и сдвига.

на выполнение операций
с ними зависят от длины записи числа в

цифрах рабочей системы
счисления.
Для заданной b-с. с. следующие величины:
kn — длина записи (натурального) числа N,
Nk — максимальное натуральное число, записываемое k цифрами,
связаны соотношениями:
kn = [logbN] + 1, где [x] — наибольшее целое, не превышающее x;
Nk = bk − 1.

Верхние оценки для размера результата арифметической операции
над парой целых чисел N1 и N2 (пусть N1 > N2):
для сложения и вычитания — kN1 +1,
для умножения — kN1 + kN2,
для деления — kN1 +1, (так как N2 > 1).

числа, причем каждый разряд обрабатывается
не более одного раза. Поэтому время

работы алгоритма
сложения линейно по k: Тслож(k)~k.
Алгоритмы умножения и деления выполняют сложение
и вычитание несколько раз (не более, чем k), со сдвигом
на одну позицию. Так как время сложения линейно, время
умножения и деления квадратично по k: Tyмн ~k2,, Tдел (k) ~ k2.
В системах команд компьютеров есть команды типа сложения
и умножения, которые работают не с отдельными битами, а с
байтами; они обычно рассматриваются как элементарные.
Проведенные выше оценки сохраняют свою силу, если
заменить базовую с. с. кратной ей (со степенью кратности
равной длине слова).

операции поразрядных сдвигов числа X вправо и влево.

17.5(10) = 16 + 1 + 0.5 = 24 + 20 + 2–1 = 10001.1(2)
17.5 *X = X* (24 + 20 + 2–1 ) =
= X*24 + X*20 + X*2–1 =
= (X << 4) + X + (X >> 1)
2. Если 120(x) делится на 11(10), то как выглядит (чему равно?) 310 в системе счисления с основанием x?
Подбором можно определить, что x = 9, т.к. 120(9) = 99(10) – делится на 11 без остатка.
310 = 32*5= (32)5 = 95 = 100000(9)