ГНОМОН. От фараонов до фракталов - Газале М.
ISBN 5-93972-171-0
Скачать (прямая ссылка):
7Гд_1 ^ 7 ^ 7TS — 1 ИЛИ 7Гs—1 — 1 < 7 < 7Гs. (9.14)
Например, любое число 7, состоящее из трех значащих десятичных цифр, таково, что
100 ^ 7 ^ 999 или 99 < 7 < 1000.
Аналогично, любое число 7, состоящее из трех значащих двоичных цифр, или битов, таково, что
(Ю00.)2 < 7 < (ПП-Ь или (111.)2 < 7 < (Ю000.)2,
то есть
8 ^ 7 ^ 15 или 7 < 7 < 16.
Многие авторы употребляют в своих трудах такие конструкции, как «десятичные числа» или «двоичные числа». Совершенно очевидно, однако, что относить эти атрибуты следует вовсе не к числам, но к их представлениям. И все же для простоты мы также будем прибегать к таким языковым сокращениям, распространяющим на числа признаки их представлений, и наоборот. Таким же сокращением является запись 7 = (101.)2 = (12.)3 = 5, т. е. целое число, десятичное представление которого есть 5, имеет также
206
Глава IX
представления (101.) 2 в двоичной системе счисления и (12.)з в троичной. Все четыре представления, включая и саму букву 7, соответствуют одному и тому же целому числу, абстрактной математической сущности, и абсолютно эквивалентны друг другу. Для достижения наилучшего понимания мы рекомендуем читателю четко уяснить для себя грань между числом и его представлением.
Нахождение цифр целого числа
Допустим, нам необходимо представить в системе счисления по основанию b некое целое число 7, выраженное в системе счисления с каким-либо другим основанием, скажем, в десятичной; для нахождения знаков нового представления числа 7 существует несколько алгоритмов. Описанные ниже методы (как, впрочем, и все остальные, если уж на то пошло) вытекают непосредственно из алгоритма деления и включают в себя следующие шаги:
Метод 1.
1. Делим 7 на то Получаем частное <71 и остаток ?q
2. Делим <7i на mi Получаем частное <72 и остаток 5J
3. Делим (72 на m2 Получаем частное <73 и остаток
s. Делим qs-i на ms-1 Получаем частное 0 и остаток
Примеры для b = (5, 4, 3, 2): 7Го = 1, = 2, 7Г2 = 6, 7Г3 = 24,
7Г4 = 120.
1. 7 = 115 = 2x57+1
57 = 3 х 19 + 0 19 = 4 х 4 + 3
4 = 5 x 0 + 4 115 = (4301. )ь
2. 7 = 24 = 2x12 + 0
12 = 3 х 4 + 0
4 = 4 х1 + 0
1 = 5x0 + 1 24 = (ЮОО.)ь = тгз
3. 7 = 119 = 2x59 + 1
59 = Зх 19 + 2 19 = 4 х 4 + 3
4 = 5 х 0 + 4 119 = (4321.)ь = тг4 - 1
(119 — наибольшее четырехразрядное конформное целое число).
Нахождение цифр целого числа
207
Метод 2. Вышеописанный алгоритм смены основания можно шаг за шагом представить следующим образом ([А] обозначает целую часть числа А)\
1,
7 = т0
1.
1.
или, в общем виде,
57 =
7 '
то
7 1
momi _
• • 1
•>
Г 71
-7Гг-
7
то
т 1
+ <507
7
т0
т 1
+ (57
Г 7 1
тот\т2_
7711
7
ШоШ1
+ <57
ГПп
7
_7Гг+1 _
TTli
7
7Гг+1 _
7
_7Гг+1 _
(9.15)
Согласно одной из теорем теории чисел [тА] — m[A\ = ([тА] mod m), где (N mod m) означает остаток от деления N на т. Таким образом,
67
1.
TTi
mod т,
(9.16)
Вернемся к примеру с числом 7 = 115:
fi1 -°о —
<*7 =
Г1151 mod = 1, % = ( Г1151
L 1 J L 6 J
Г1151 mod 3^j = 0, 1 1
L 2 J 1 1
mod 4) = 3, mod 5 ) = 4.
Применим этот метод к преобразованию числа 7 = 315 из десятичной системы в двоичную:
*o7=( Г 3151 mod
L 1 J
SJ=( Г315! mod
L 2 J
Г315! mod
L 4 J
% = { Г315! mod
L 8 J
Sl = ( Г 3151 mod
L i6 J
1,
= 1,
= 0.
= 1,
1,
Ь1 -°б —
Р -8
mod 2
mod 2
mod 2
mod 2
= 4, = 0, = 0, = 1.
208
Глава IX
Так как 315 < 2г для всех г > 8, цифра является наибольшей значащей, а искомое число равно (100111011.)2- Первый метод смены основания является итерационным. Для того чтобы, пользуясь этим методом, вычислить цифру 5?, необходимо знать все цифры 5J, где 0 < j < i — 1. Преимущество второго метода в том, что он основывается на явном выражении для SJ,
