Від'ємна основа
Нега-позиційна система числення — це позиційна система числення з від'ємною основою. Особливістю таких систем є відсутність знака перед від'ємними числами, тобто відсутність правил знаків. Будь-яке число будь-якої з нега-позиційних систем, відмінне від 0, з непарним числом цифр — додатне, а з парним числом цифр — від'ємне. Часто число в нега-позиційній системі вимагає для запису на одну цифру більше, аніж те ж саме число в системі з позитивною основою. Зазвичай назва нега-позиційної системи складається з префікса нега- і назви відповідної системи числення з додатною основою;
Наприклад, нега-десяткова (b = -10), нега-трійкова (b = -3), нега-двійкова (b = -2) та інші.
Приклади
Нега-позиційний запис Позиційний
записПодання числа 174(-10) 34(10) 1·(-10)2 + 7·(-10)1 + 4·(-10)0 = 100 − 70 + 4 = 34 46(-10) −34(10) 4·(-10)1 + 6·(-10)0 = −40 + 6 = −34 11001(-2) 1001(2) 1·(-2)4 + 1·(-2)3 + 0·(-2)2 + 0·(-2)1 + 1·(-2)0 = 16 − 8 + 1 = 9
Історія
Нега-позиційні системи числення вперше були запропоновані Вітторіо Грюнвальдом у його роботі «Giornale di Matematiche di Battaglini» 23 (стор. 203—221), опублікованій в 1885 році. Грюнвальд описав алгоритми додавання, віднімання, множення, ділення, отримання кореня, ознак подільності й перетворення систем числення.
Використання
Число x у нега-позиційній системі числення з основою b = -r представляється у вигляді лінійної комбінації числа ступенів -r:
- , де — це цілі числа, які називають цифрами ,що задовольняють нерівності ,де — порядковий номер розряду починаючи з нульового, n — число розрядів.
Кожнен ступінь у такому записі називається розрядом, старшинство розрядів і відповідних їм чисел визначається значенням показника . Зазвичай для ненульового числа вимагають, щоб старша цифра у b-річному поданні була також ненульова.
Нега-позиційні системи можна порівняти із знако-розрядними системами числення, такими як симетрична трійкова система, де основа системи додатна, однак цифри можуть приймати від'ємні значення з деякого проміжку.
Деякі числа мають одне й те ж саме подання в системах числення з основою і (позиційних й відповідним їм нега-позиційних). Приміром, числа від 100 до 109 однаково записуються в десятковій і нега-десяткових системах числення. Аналогічно:
Тобто число 17 має однакове представлення в двійковій і нега-двійковій системах числення — .
Подання чисел від -12 до 12 в різних системах числення:
Десяткове | Нега-десяткове | Двійкове | Нега-двійкове | Трійкове | Нега-трійкове |
---|---|---|---|---|---|
-12 | 28 | -1100 | 110100 | -110 | 1210 |
-11 | 29 | -1011 | 110101 | -102 | 1211 |
-10 | 10 | -1010 | 1010 | -101 | 1212 |
-9 | 11 | -1001 | 1011 | -100 | 1200 |
-8 | 12 | -1000 | 1000 | -22 | 1201 |
-7 | 13 | -111 | 1001 | -21 | 1202 |
-6 | 14 | -110 | 1110 | -20 | 20 |
-5 | 15 | -101 | 1111 | -12 | 21 |
-4 | 16 | -100 | 1100 | -11 | 22 |
-3 | 17 | -11 | 1101 | -10 | 10 |
-2 | 18 | -10 | 10 | -2 | 11 |
-1 | 19 | -1 | 11 | -1 | 12 |
0 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 1 |
2 | 2 | 10 | 110 | 2 | 2 |
3 | 3 | 11 | 111 | 10 | 120 |
4 | 4 | 100 | 100 | 11 | 121 |
5 | 5 | 101 | 101 | 12 | 122 |
6 | 6 | 110 | 11010 | 20 | 110 |
7 | 7 | 111 | 11011 | 21 | 111 |
8 | 8 | 1000 | 11000 | 22 | 112 |
9 | 9 | 1001 | 11001 | 100 | 100 |
10 | 190 | 1010 | 11110 | 101 | 101 |
11 | 191 | 1011 | 11111 | 102 | 102 |
12 | 192 | 1100 | 11100 | 110 | 220 |
Переклад в нега-позиційні системи
Нега-позиційне подання числа може бути отримано послідовними поділами з залишком вихідного числа (тобто на основу нега-позиційної системи) і записом поспіль залишків починаючи з останнього. Зауважимо, що якщо , із залишком , то . Приклад перекладу в нега-трійкову систему:
Отже, нега-трійковим поданням числа 146(10) є число 21102(-3).
Реалізація на C#:
static string negaternary(int value)
{
string result = string.Empty;
while (value != 0)
{
int remainder = value % -3;
value = value / -3;
if (remainder < 0)
{
remainder += 3;
value += 1;
}
result = remainder.ToString() + result;
}
return result;
}
Арифметичні операції
Додавання
Додавання стовпчиком треба робити як і в звичайній системі, наприклад, якщо ви хочете скласти в нега-десятковій системі числення, то це треба робити як і в десятковій системі числення. Але з одним винятком: якщо при додаванні в будь-якому розряді виходить число не менше 10, то в цей розряд потрібно записати число одиниць отриманого числа, а з сусіднього зліва розряду – відняти одиницю. Якщо зліва немає розряду, то приписати зліва 19 (для нега-десяткової, для нега-трійкової – 12, для нега-двійковій – 11). Наприклад (нега-десяткова система):
· · 18115 + 5487 3582
5+7=12, 2 в розряд одиниць, з сусіднього зліва віднімаємо одиницю. 8+5=13, 3 розряд мінус тисяч, з сусіднього зліва віднімаємо одиницю.
· 72 + 49 1901
2+9=11, 1 в розряд одиниць, від сусіднього зліва віднімаємо одиницю. 6+4=10, 0 в розряд мінус десятків, сусіднього зліва — немає, приписуємо зліва 19.
Віднімання
Віднімання стовпчиком треба робити як і в звичайній системі, наприклад, якщо ви хочете відняти у нега-десятковій системі числення, то це треба робити як і в десятковій системі числення. Але з одним винятком: якщо при відніманні в якому-небудь розряді треба зайняти десяток, то ви це робите, але з сусіднього зліва розряду ви не віднімаєте одиницю, а, навпаки, додаєте її туди. Якщо зліва немає розряду, то приписати зліва 1. Наприклад (нега-десяткова система):
1 52 - 39 33
2-9 не можна, займаємо одиницю. 12-9=3, 3 в розряд одиниць, до сусіднього зліва розряду додаємо одиницю. 6-3=3.
2 - 9 13
2-9 не можна, займаємо одиницю. 12-9=3, 3 в розряд одиниць, сусіднього зліва розряду немає, тому приписуємо зліва 1.
Таблиця множення в нега-двійковій системі числення
Таблиця множення в нега-двійковій системі числення
× | 0 | 1 |
---|---|---|
0 | 0 | 0 |
1 | 0 | 1 |
Таблиця множення в нега-трійковій системі числення
Таблиця множення в нега-трійковій системі числення
2 | 0 | 2 | 121 |
---|---|---|---|
1 | 0 | 1 | 2 |
0 | 0 | 0 | 0 |
х | 0 | 1 | 2 |
Таблиця множення в нега-десятковій системі числення
Таблиця множення в нега-десятковій системі числення
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
2 | 4 | 6 | 8 | 190 | 192 | 194 | 196 | 198 |
3 | 6 | 9 | 192 | 195 | 198 | 181 | 184 | 187 |
4 | 8 | 192 | 196 | 180 | 184 | 188 | 172 | 176 |
5 | 190 | 195 | 180 | 185 | 170 | 175 | 160 | 165 |
6 | 192 | 198 | 184 | 170 | 176 | 162 | 168 | 154 |
7 | 194 | 181 | 188 | 175 | 162 | 169 | 156 | 143 |
8 | 196 | 184 | 172 | 160 | 168 | 156 | 144 | 132 |
9 | 198 | 187 | 176 | 165 | 154 | 143 | 132 | 121 |