А.А. Вылиток, М.О. Проскурня - Введение в системы счисления

Введение в системы счисленияА. А. Вылиток, М. О. Проскурня© 2006—2007, http://cmcmsu.no-ip.info/ОглавлениеВведение в системы счисления ........................................................................................11. Системы счисления .......................................................................................................11.1. Базисные числа ..........................................................................................................21.2. Непозиционные системы счисления........................................................................21.2.1.

Римская система............................................................................................21.2.2. Египетская система.......................................................................................31.2.3. Славянская система ......................................................................................31.3. Позиционные системы счисления............................................................................31.3.1.

Геометрический базис ..................................................................................41.3.2. Фибоначчиев базис .......................................................................................41.3.3. Факториальный базис...................................................................................41.3.4. Какая СС удобнее для вычислительной техники ......................................51.4. Преобразования из одной системы счисления в другую.......................................51.4.1. Перевод из десятичной системы в q-ичную и обратно.............................51.4.2. Обратный перевод ........................................................................................61.4.3.

Перевод из q-ичной системы в систему с основанием qm и обратно.......71.4.4. Перевод из q-ичной в p-ичную систему .....................................................81.4.5. Арифметические операции в q-ичной системе..........................................81.5. Список литературы..................................................................................................101. Системы счисленияАбстрактные идеальные числа не имеют воплощения в природе, поэтому для ихотображения необходимо определиться со способом записи. Системой счисления (СС)называется совокупность правил записи чисел. Запись подразумевает наличие алфавитасимволов, из которых составляются «числительные».Простейшей системой счисления можно назвать единичную СС, алфавит которойсостоит только из одного символа A = { | } (штрих, черта, «палочка»).

Для представлениянекоторого числа N выписывается подряд N штрихов. Например, число 5 в единичнойсистеме счисления записывается как «| | | | |».Главным недостатком единичной СС можно назвать линейную зависимость длинызаписи числа от величины его самого. То есть для записи чисел, превосходящих миллион,потребуется выписать более миллиона штрихов. Более того, для записи количествамолекул во всей вселенной придется использвовать всю доступную материю!1.1.

Базисные числаОдним из способов сокращения длины записи является пополнение алфавитановыми символами, обозначающими масштабные числа. Этот способ хорошопроиллюстрирован в денежной системе. Так, помимо монеты, означающей элементарныйденежный знак, обычно существуют монеты большего достоинства, приравненныенескольким элементарным монетам. Это позволяет представить необходимую денежнуюсумму в виде существенно сокращенного набора монет.Если добавить в алфавит единичной СС дополнительные символы ∇ = 5, ⊗ = 10,… = 100, то запись числа шестнадцать вместо «| | | | | | | | | | | | | | | |» приобретет болеекороткую форму «⊗ ∇ |».

Можно сказать, что до пополнения алфавита мы использовалилинейное разложение исходного числа по базису B = {bk} = {1}, состоящему из одногочисла — единицы:N=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1(1)Числа, составляющие базис, называются базисными (или опорными). Послепополнения алфавита базис также был пополнен до 4 чисел: {b1..4} = {1, 5, 10, 100}. Приэтом представление «⊗ ∇ |» в такой СС по сути является сокращенной записью линейногоразложения (с опущенными знаками «+») с целыми коэффициентами:N = b3 + b2 + b1 = 15 + 5 + 1 ⇒ ⊗ + ∇ + | ⇒ ⊗ ∇ |(2)Далее будут рассматриваться СС, основанные на линейном разложении снеотрицательными целыми коэффициентами.

Для обеспечения единственностипредставления в подобных СС обычно используют критерий минимального количестваслагаемых в сумме разложения, хотя при этом длина самой записи может превосходитьминимально возможную длину (см. «Фибоначчиев базис» в позиционных СС).1.2. Непозиционные системы счисленияК непозиционным можно отнести следующие системы счисления:— единичная,— римская,— египетская,— славянская и другие.Каждая непозиционная система опирается на конечный базис (конечное множествонатуральных чисел). Напомним, что единичная система имеет базис {1}. Для любойсистемы с конечным базисом нетрудно найти такое N', что для всех чисел N > N' длина ихзаписи сократится по сравнению с единичной не более, чем в k раз, где k — наибольшеебазисное число.1.2.1. Римская системаБазис римской системы счисления содержит 7 чисел B = {b1..7} = {1, 5, 10, 50, 100,500, 1000}.

Алфавит A = { I (1), V (5), X (10), L (50), C (100), D (500), M (1000) }.Изначально в римской системе запись произвольного числа была упорядочена поубыванию базисных чисел. Например, XV = b3 + b2 = 10 + 5 = 15, DCLVII = b6 + b5 + b4 +b2 + b1 + b1 = 500 + 100 + 50 + 5 + 1 + 1 = 657.Правда, со временем были введены некоторые изменения. Для сокращения длинызаписи некоторые символы размещаются с нарушением упорядоченности. В этом случаеменьшее базисное число, стоящее слева от большего, входит в сумму с «отрицательнымзнаком», то есть вычитается из общей суммы, а не добавляется к ней.

Например, вместозаписи IIII для числа четыре стали использовать запись IV, вместо записи VIIII — записьIX. Не любые комбинации символов допустимы. Разрешены следующие «нарушения» :— непосредственно перед V или X может стоять один символ I— непосредственно перед L или C может стоять один символ X— непосредственно перед D или M может стоять один символ CМожно считать, что эти изменения просто дополнили базис ещё несколькимичислами, а алфавит, соответственно, ещё несколькими составными «символами»: 4 (IV), 9(IX), 40 (XL), 90 (XC), 400 (CD), 900 (CM).1.2.2.

Египетская системаЕгипетская система счисления опиралась на базис из 4 чисел B = {b1..4} = {1, 10,100, 1000}, алфавит A = { I (1), ∩ (10), ∫ (100), ρ (1000) }.В этой системе, например, число 352 записывается как ∫ ∫ ∫ ∩∩∩∩∩ I I.1.2.3. Славянская системаСлавянская алфавитная непозиционная СС обладала следующим базисомB = {b1..18} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500,600, 700, 800, 900}.СимволЧислоСимволЧислоСимволЧислоА (Аз)1И10Р (Рцы)100В (Ве́ди)2К (Ка́ко)20С (Сло́во)200Г (Глаго́ль)3Л (Лю́ди)30Т (Тве́рдо)300Д (Добро́)4М (Мысле́те)40У (Ук)400Е (Есть)5Н (Наш)50Ф (Ферт)500S (Зело́)6Ѯ (Кси)60Х (Хер)600З (Земля́)7О (Он)70Ѱ (Пси)700I (Иже)8П (Поко́й)80Ѡ (Оме́га)800Ѳ (Фита́)9Ч (Червь)90Ц (Цы)9001.3.

Позиционные системы счисленияВ отличие от непозиционных, позиционные СС обладают бесконечным базисомB = {b0..∞}, где 0 < bk < bk + 1. В записи числа в позиционной системе каждому базисномучислу соответствует фиксированная позиция. В этой позиции с помощьюсоответствующего символа алфавита указывается число вхождений базисного числа всумму разложения по базису:∞N = ∑ ak bk ,k =0⎡ b ⎞где ak ∈ ⎢0, k +1 ⎟⎟ .⎣ bk ⎠(3)Следует сказать, что в общем случае базис может содержать не толькоположительные, но и отрицательные числа.

Это позволяет отказаться от использованиязнака минус «–» перед записью отрицательного числа1.1.3.1. Геометрический базисДля СС с базисом B = {b0..∞}, базисные числа которого определяются как членыгеометрической прогрессии bk = p k с основанием p > 1, линейное разложение числа N побазису B будет являться полиномом от p некоторой степени n:nN = ∑ ak p k = an p n + an −1 p n −1 + ... + a1 p1 + a0 p 0 .(4)k =1bk +1 p k +1= k = p , алфавит подобных СС содержит всего p символов дляbkpпредставления чисел {0, …, p − 1}. Наиболее известными являются позиционные СС сгеометрическим базисом с основаниями 10, 2, 16, 8, 60.A10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}Так какA2 = {0, 1}A16 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}1.3.2. Фибоначчиев базисЕсли в качестве базиса позиционной СС использовать последовательность чиселФибоначчи B = {b1..∞} = {Fk} (где Fk = Fk − 1 + Fk − 2, F0 = F1 = 1), то алфавит будетсодержать всего 2 символа для чисел {0, 1}, так как отношение соседних опорных чиселне превышает 2:bk +1 Fk +1 Fk + Fk −1F=== 1 + k −1 < 2 .bkFkFkFkОдним из интересных свойств такой СС является отсутствие идущих подряд 1 взаписи любого числа.

Так, две единицы подряд означают, что в разложении имеетсясумма двух соседних Фибоначчиевых чисел, но она равна следующему базисному числу.∞N = ∑ ak F k(5)k =11.3.3. Факториальный базисCC с базисом B = {b1..∞} = {k!}, элементы которого образуют факториальный рядтребуют бесконечного алфавита в общем случае, так какbk +1⎯k⎯⎯→ ∞ .→∞bk∞N = ∑ ak k!k =11За информацией по СС с симметричным базисом обращайтесь к дополнительной литературе.(6)1.3.4. Какая СС удобнее для вычислительной техникиДля использования в вычислительной технике удобны позиционные СС сгеометрическим базисом.

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

Если оценитьстоимость C представления некоторого числа x как произведение необходимогоколичества разрядов nx на количество состояний каждого разряда p, то окажется, чтоминимум достигается при p = 3.Для доказательства достаточно оценить максимальное количество представимыхчисел при заданной стоимости представления С = nx p. Если рассматривать максимумmax x = ppnx=pCpкак функцию X (p), то экстремум она имеет в нуле своей первой⎛C ⎞⎛C⎞C⎜⎜ − 2 ⎟⎟∂X ⎛⎜ p ⎞⎟ − CC ⎜⎜⎝ p −1⎟⎟⎠⎝p ⎠(1 − ln p )= pln p + p= CpпроизводнойX'(p).Производная∂p ⎜⎝ ⎟⎠ p 2pпринимает значение 0 в точке e (когда обнуляется разность в скобках).