Від'ємна основа

Нега-позиційна система числення — це позиційна система числення з від'ємною основою. Особливістю таких систем є відсутність знака перед від'ємними числами, тобто відсутність правил знаків. Будь-яке число будь-якої з нега-позиційних систем, відмінне від 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

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.