Формальні правила двійкової арифметики. Двійкова арифметика Як рахувати

познайомити учнів із двійковою системою числення, вказати її недоліки та переваги використання у обчислювальній техніці;
розвивати логічне мислення; формувати навички виконання арифметичних дій із двійковими числами;
прищеплювати інтерес до предмета.

Програмно-дидактичне забезпечення: ПК, програма Калькулятор.

Хід уроку

I.Організаційний момент

Привітання перевірка відсутніх.

1. Постановка цілей уроку

- Скільки буде:

1000110 2 + 1010101 2 ;
100011110111 2 /101101 2; 1110001110 2 – 11010 2 ;
101101 2 * 100011 2

Після запропонованих відповідей учнів, коментую та пояснюю, що сьогодні на уроці ми навчимося правильно виконувати арифметичні дії у двійковій системі числення.

2. Людина не веде рахунок у двійковій системі, т.к. вона йому не зручна. А хто чи що використовує її для рахунку та чому?

ІІ.Викладення нового матеріалу

Двійкова система числення

З усіх позиційних систем числення особливо проста і тому цікава двійкова система числення.

– Чому рівна основа двійкової системи числення? (q = 2)

– Який вигляд має розгорнута форма запису двійкового числа? (А 2 = а n-1 * 2 n-1 + ... a 0 * 2 0 + a -1 * 2 -1 + ... a -m * 2 -m, де а i дорівнює 1 або 0.)

Двійкова система числення здавна була предметом пильної уваги багатьох вчених. П.С.Лаплас писав про своє ставлення до двійкової (бінарної) системи числення великого математика Г.Ф.Лейбніца: «У своїй бінарній арифметиці Лейбніц бачив прообраз твору. Йому уявлялося, що одиниця представляє божественне початок, а нуль – небуття і що вища істота створює все з небуття точно так само, як одиниця і нуль у його системі виражають усі числа». Ці слова наголошують на дивовижній універсальності алфавіту, що складається всього з двох символів.

Двійкова арифметика.

Щоб краще освоїти двійкову систему числення, необхідно освоїти виконання арифметичних дій над двійковими числами.

Усі позиційні системи «однакові», а саме, у всіх них арифметичні операції виконуються за тими самими правилами:

справедливі одні й самі закони арифметики: комунікативний, асоціативний, дистрибутивний;
справедливі правила складання, віднімання, множення та розподілу стовпчиком;
правила виконання арифметичних операцій спираються на таблиці складання та множення.

Додавання.

Таблиця додавання двійкових чисел проста.

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10
1 + 1 + 1 = 11

При складанні двох одиниць відбувається переповнення розряду та проводиться перенесення у старший розряд. Переповнення розряду настає тоді, коли величина числа в ньому стає рівною або більшою за основу.

Віднімання.

0 – 0 = 0
0 – 1 = 11
1 – 0 = 1
1 – 1 = 0

Віднімання багаторозрядних двійкових чисел відбувається відповідно до вищенаведеної таблиці віднімання з урахуванням можливих позик зі старших розрядів.

Множення.

Операція множення виконується з використанням таблиці множення за звичайною схемою (застосовується в десятковій системі числення) з послідовним множенням множення на чергову цифру множника.

При розподілі стовпчиком доводиться як проміжні результати виконувати дії множення та віднімання.

ІІІ. Закріплення вивченого

Розв'яжіть завдання.

Виконайте складання:

1001001 + 10101 (відповідь 1011110);
101101 + 1101101 (відповідь 10011010)
11000,11 + 11010,11 (відповідь 110011,1)

Виконайте віднімання:

10001000 – 1110011 (відповідь 10101)
1101100 – 10110110 (відповідь – 1001010)
110101,101 – 1001,111 (101011,11)

Виконайте множення:

100001*111,11 (відповідь: 11111111,11)
10011*1111,01 (відповідь: 100100001,11)

Виконайте поділ:

1000000 / 1110 (відповідь:100)
11101001000/111100 (відповідь: 11111)

IV. Підсумки уроку

Оцінювання роботи учнів, назвати тих, хто відзначився на уроці.

V. Домашнє завдання

Вивчити правила виконання арифметичних дій у двійковій системі числення, а також таблиці складання, віднімання та множення у двійковій системі числення.

Виконайте дії:

110010 + 111,01;
11110000111 – 110110001;
10101,101 * 111;
10101110/101.

Складіть таблиці складання та множення у троїчній та п'ятирічній системі числення.

Отже, ми вже знаємо, що таке двійкова система обчислення. Двійкова система - це така ж повноцінна система числення, як і добре всім нам знайома десяткова. У двійковій системі, як і будь-який інший системі обчислення можливі всі арифметичні операції, яких ми звикли в десятковій системі. Тобто додавання, віднімання, множення, розподіл. Розглянемо кожну з арифметичних операцій на конкретних прикладах.

Додавання

Допустимо нам потрібно знайти суму двох двійкових чисел: 10011001110 + 11000101110. Як це зробити. Правила складання двійкових чисел такі самі, як і для десяткових. З тією різницею, що кожен розряд суми може приймати лише два значення – нуль або одиниця. Так само, як і в десятковій системі, для складання чисел їх зручно записати в стовпчик:

+		1	0	0	1	1	0	0	1	1	1	0
+		1	1	0	0	0	1	0	1	1	1	0

	1	0	1	1	1	1	1	1	1	0	0	0

Додавання чисел потрібно проводити порозрядно, починаючи з молодшого розряду. При цьому застосовується таке правило: Нуль плюс нуль вийде, звичайно нуль. Один плюс нуль та нуль плюс один дадуть в результаті один. При додаванні двох одиниць ми отримаємо нуль у поточному розряді та одиницю перенесення у старший розряд. При складанні трьох одиниць (з урахуванням одиниці перенесення з попереднього розряду) отримаємо одиницю у поточному розряді та одиницю перенесення. Ці правила об'єднані в так званій таблиці:

Користуючись таблицею додавання перевірте наведений вище приклад додавання. Спробуйте самі скласти якісь числа.

Розмноження

Множення двійкових чисел, також схоже на множення десяткових. Зараз ми також покажемо цей процес на прикладі. Згадайте, як ви множите два десяткові числа стовпчиком. Ось приклад множення двійкових чисел стовпчиком:

		X		1	0	0	1	1	0	0	1	1	1	0
		X									1	0	1	1

				1	0	0	1	1	0	0	1	1	1	0
+			1	0	0	1	1	0	0	1	1	1	0
+		0	0	0	0	0	0	0	0	0	0	0
	1	0	0	1	1	0	0	1	1	1	0

	1	1	0	1	0	0	1	1	0	1	1	0	1	0

Так само, як і при множенні двійкових чисел, ми множимо перше число на кожен розряд другого і записуємо отримані результати під першою межею, одне під іншим зі зрушенням. Потім отримані проміжні результати складаємо з урахуванням зсуву. Однак у випадку з двійковими числами є одна істотна відмінність. Оскільки будь-який розряд двійкового числа або нуль, або одиниця, проміжне множення сильно полегшується. Насправді, будь-яке число, помножене на одиницю, дорівнює самому собі. Будь-яке число, помножене на нуль, дорівнює нулю! Тому тут і обчислювати щось нічого не потрібно. Саме тому множення двох двійкових чисел зводиться до операцій зсуву та додавання. Це дуже важливо для побудови обчислювальних машин. Тепер ясно, що нам не потрібні якісь там "помножувачі". Для реалізації операцій складання та множення нам потрібні лише суматори та зсувні регістри. З їх пристроєм ви можете познайомитись на нашому сайті.

Віднімання

Для того, щоб спростити операцію віднімання, було придумано так званий "додатковий код". Можна сказати, що з цього коду записуються негативні числа. Для того, щоб записати двійкове число в додатковому коді, необхідно проінвертувати всі його розряди, а потім додати одиницю. Інвертувати розряд двійкового числа - це, отже, замінити вміст на протилежний. (нуль на одиницю, а одиницю на нуль). Нижче наведено приклади перекладу різних чисел у додатковий код. У кожному рядку таблиці ви бачите те саме число записане спочатку в десятковій системі обчислення, потім у двійковій системі в прямому коді, потім інвертований прямий код, а потім у додатковому коді.

Правила переведення числа з десяткового подання до двійкового читайте у розділі «Системи обчислення».

Правило віднімання двох двійкових чисел свідчить:
для того, щоб відняти одне число з другого, необхідно:

Перевести віднімання в додатковий код.
Скласти ці два числа (зменшуване та віднімається в додатковому коді).
При додаванні перенесення із найстаршого розряду не враховувати.
Отриманий результат і є різниця.

Пояснимо це на прикладі. Припустимо, нам потрібно знайти різницю між числами 13 і 5 у двійковій системі числення. Перекладемо спочатку шукані числа у двійкову систему:

Число 13 беремо у прямому двійковому коді (00001101).

Число 5 переводимо додатковий двійковий код 5 (11111011).

Тепер робимо додавання:

+		0	0	0	0	1	1	0	1
+		1	1	1	1	1	0	1	1

	1	0	0	0	0	1	0	0	0

Перенесення з найстаршого розряду, що використовується нами, ми відкидаємо. В результаті одержуємо 1000.

Для перевірки переведемо отриманий результат у десятковий вигляд. 1000 у двійковій системі це 8 у десятковій. Раджу уважно перевірити наведений приклад відповідно до таблиці складання (див вище).

Розмноження та розподіл на 2

Множення на 2 (на 10 у двійковому коді) це окремий випадок множення. Але його слід розглянути окремо. Справа в тому, що так само як при множенні на 10 в десятковій системі потрібно просто додати один нулик наприкінці числа, так і при множенні на два в двійковій системі для отримання результату потрібно зрушити множину на один розряд вліво і додати один нуль в молодший розряд.

Двійкове	десяткове

Аналогічно відбувається розподіл на 2. Тільки навпаки. Для того, щоб розділити двійкове числа на 2 (двійкове 10) потрібно просто відкинути нуль у молодшому розряді числа і всі інші розряди зрушити на один розряд праворуч. Якщо у молодшому розряді шуканого числа не нуль, а одиниця, це означає, що число не ділиться на два націло. У цьому випадку можливе поділ із залишком.

Примітка:Ви можете самі потренуватись у множенні на два з іншими числами. Про переведення з десяткового уявлення числа в двійкове дивись тут.

Поділ на довільне число

Згадаймо, як ми ділимо одне число на інше в десятковій системі числення. Я маю на увазі розподіл стовпчиком або кутом. Так само відбувається розподіл у двійковій системі. Ось приклад розподілу двох двійкових чисел:

Спочатку ми записуємо ділене. У разі це число 1000001 (у десятковому вигляді 65). Потім праворуч від нього малюємо кут. У верхній частині кута записуємо дільник. У нашому випадку це 101 (десяткове 5). Потім ми починаємо знаходити приватне по розрядному. У десятковій системі обчислення в даному випадку ми підбираємо, на яке число від 1 до 9 потрібно помножити дільник, для того, щоб результат був би все ж таки менше, ніж три перші розряди поділеного. Якщо такого числа не знаходиться, то беруть перші чотири розряди поділеного. У двійковій системі числення будь-який розряд може набувати лише два значення – нуль чи одиниця. Тому вибір у нас набагато менший. Дільник можна множити тільки на 1 або на нуль. При цьому в першому випадку він залишиться незмінним, а в другому він дорівнюватиме нулю. Нам доведеться лише перевіряти чи більше дільник, ніж число, що становить перші три розряду ділимого. Як бачимо перші три розряди становлять число 100, що менше, ніж 101. Тому беремо перші чотири розряди поділеного. Число, що становить перші чотири розряди ділимого (1000), природно більше дільника. Тому ми записуємо дільник під першими чотирма розрядами поділеного і віднімаємо ці два числа. Отримуємо різницю 11. Перший розряд приватного записуємо 1.

Знаходимо наступний розряд приватного. Для цього зносимо наступний розряд поділеного (так само, як це робиться при розподілі в десятковій системі). Перевіряємо – чи можна тепер відняти з нього 101. Число 110 більше, ніж 101. Тому ми записуємо одиницю до наступного розряду приватного і робимо віднімання цих двох чисел. Різниця дорівнює 1.

Далі шукаємо третій розряд приватного. Зносимо ще один нуль із чергового розряду поділеного. Але з числа 10 неможливо відняти 101. 10 менше, ніж 101. Тому записуємо в черговий розряд приватного нуль і зносимо останній розряд поділеного. Тепер віднімання можливе. Більше того, результат віднімання дорівнює нулю. Це означає по-перше, що останній розряд приватного дорівнює одиниці, а по-друге те, що число 1000001 поділилося на 101 без залишку. Результат розподілу дорівнює 1101 (десяткове 13).

Висновок

Ви можете поставити запитання: яка практична цінність у знанні правил двійкової арифметики. Набагато зручніше рахувати в десятковому вигляді. Так, для людини зручніше у десятковій. Але саме ці правила дозволили створити електронні схеми, здатні проводити обчислення автоматично. Якщо ви уважно подивіться на правила розподілу чисел, то можете побачити, що всі ці дії зводяться до зсуву розрядів числа та віднімання. Віднімання, як ми вже переконалися, раніше зводиться до складання чисел, одне з яких представлене в додатковому коді. Суматор легко будується на основі найпростіших логічних елементів. Зсув провадиться за допомогою зсувного регістру. На сторінках цього сайту ви знайдете опис усіх цих елементів обчислювальних систем.

Ціль:

учні познайомляться з двійковою системою числення, вкажуть її недоліки та переваги використання у обчислювальній техніці;

розвинуть логічне мислення; сформують навички виконання арифметичних дій із двійковими числами;

виховують у собі вміння самостійно здобувати нові знання.

Ресурси: проектор, інтерактивна дошка, комп'ютер, презентація слайдів, підручник, робочий зошит, смайлики, листи зворотного зв'язку

Способи роботи: Індивідуальна, парна, групова

Критерії оцінки:

Відповіді на питання1-3 бали

Запис конспекту1-2 бали

Виконання завдань -1-4 бали

Активність роботи у групі –1 бал

Моніторинг оцінювання:

1-3 бали – «3»

4-6 балів – «4»

7-10 балів – «5»

Етапи уроку

Час

Діяльність вчителя

Діяльність учня

Оцінювання

Очікуваний результат

Мотивація

Вітання

Перевірка явки учнів

Позитивний настрій

Поділ на групи: "Фрукти"

Організація роботи з визначення теми та мети уроку

Організація діяльності щодо створення критеріїв оцінки роботи

Перевірка кластерів «Кількість інформації»

Перевірка домашнього завдання:

Переведіть двійкові числа у вісімкову систему числення та шістнадцяткову.

а) 10111110001

б) 1001101011001

в) 100100101011

Вітання

Позитивно налаштовуються на урок

Поділяються на групи

Визначають тему та цілі уроку

Створюють критерії оцінки роботи

Показують виконання домашнього завдання

Смайли

Позитивно налаштовуються на урок

Здійснюють поділ на групи

Визначать тему та цілі уроку

Створять критерії оцінки роботи

Виконають домашнє завдання

Осмислення

Організація читання тексту

Читають текст

З позначками - смайлики

Уважно прочитають текст

Рефлексія

Організує роботу зконспектом

Контрольні питання:

1.З чого складається двійкова система числення?

2.Які вчені вивчалидвійкову систему числення?

3.За якими правилами здійснюєтьсявиконання арифметичних процесів над двійковими числами?

4. Розкажіть таблицю складання, віднімання двійкових чисел.

5. Як виконуються операції множення, розподілу двійкових чисел.

Розв'яжіть завдання:

Виконайте складання:

1001001 + 10101 (відповідь 1011110);
101101 + 1101101 (відповідь 10011010)
11000,11 + 11010,11 (відповідь 110011,1)

Виконайте віднімання:

10001000 – 1110011 (відповідь 10101)
1101100 – 10110110

(відповідь – 1001010)
110101,101 – 1001,111 (101011,11)

Виконайте множення:

100001*111,11

(відповідь : 11111111,11)
10011*1111,01

(відповідь : 100100001,11)

Виконайте поділ:

1000000 / 1110 (відповідь :100)
11101001000/111100

(відповідь : 11111)

Запис конспекту

Відповідають на запитання, виконують завдання

Смайли

Запишуть конспект

Дадуть відповідь на запитання, виконають завдання

Уважно слухатимуть один одного, критично оцінять один одного

Зворотній зв'язок

Організує зворотний зв'язок:

1. Що сподобалося на уроці?

2. Що не сподобалося на уроці?

3. Які виникли питання з уроку?

Заповнять листи зворотного зв'язку

Учні зможуть висловити свої думки на папері

Домашнє завдання

Виконайте дії:

1) 110010 + 111,01;

2) 11110000111 – 110110001;

3) 10101,101 * 111;

4) 10101110/101.

Запишуть у щоденник домашнє завдання

Отримають домашнє завдання

Оцінювання

Відповідно до критеріїв виставляє учням суммативну оцінку

Подадуть щоденники на оцінку

У щоденник виставляться об'єктивні оцінки

Двійкова система числення

З усіх позиційних систем числення особливо проста і тому цікава двійкова система числення.

– Чому рівна основа двійкової системи числення? (q = 2)

Двійкова арифметика.

Всі позиційні системи «однакові», а саме, у всіх них арифметичні операції виконуються за тими самими правилами:

справедливі одні й самі закони арифметики: комунікативний, асоціативний, дистрибутивний;

справедливі правила складання, віднімання, множення та розподілу стовпчиком;

правила виконання арифметичних операцій спираються на таблиці складання та множення.

Додавання.

Таблиця додавання двійкових чисел проста.

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10
1 + 1 + 1 = 11

приклад.

Віднімання.

0 – 0 = 0
0 – 1 = 1
1 – 0 = 1
1 – 1 = 0

приклад.

Множення.

приклад.

Поділ.

При розподілі стовпчиком доводиться як проміжні результати виконувати дії множення та віднімання.

приклад.

довільне натуральне число можна єдиним способом у вигляді суми ступенів двійки, наприклад 23 = 16+4+2+1. Позначаючи входять до цієї ступеня двійки одиницями, а чи не входять у її ступеня нулями, можна коротко позначити цю суму булевим набором (в інший термінології - вектором) (10111) 2 . Індекс 2 нагадує, що число записано в двійковій системі. Одиниця, що стоїть у молодшому (самому лівому) розряді, означає доданок 1, одиниця у другому зліва розряді означає доданок 2, одиниця у третьому розряді означає 4, а нуль у четвертому розряді означає відсутність доданку 8, одиниця у четвертому (старшому) розряді означає присутність доданку 16 (у більшості випадків розумно розглядати тільки такі записи чисел у двійковій системі, в яких у старшому розряді стоїть одиниця).

Головна перевага двійкової системи (крім природності її застосування в електронній цифровій техніці) - виняткова простота алгоритмів арифметичних операцій на ній. Таблиця множення в двійковій системі зовсім не вимагає запам'ятовування: будь-яке число, помножене на нуль, дає нуль, а помножене на одиницю дорівнює самому собі. Правило розподілу зводиться до двох рівностей 0/1 = 0, 1/1 =1, завдяки чому розподіл стовпчиком у двійковій системі робиться простіше, ніж у десятковій, і по суті зводиться до багаторазового віднімання. Таблиця складання в двійковій системі трохи складніша за таблицю множення (на відміну від десяткової системи), так як 1 +1 = (10) 2 і виникає перенесення в наступний розряд.

Правило складання двох бітів у двійковій системі визначається формулами x+y = 2v+u, v = x&y, u = xÅy. З огляду на симетрії для їх перевірки досить розглянути не чотири, а три випадки: 0+0 = (00) 2 , 1+0=0+1= (01) 2 , 1+1 = (10) 2 . Схема, що виконує це додавання, називається напівсуматором (в англомовній літературі: half adder) і зазвичай позначається HA або FA2. Ця схема (у базисі (AND, XOR)) зображено малюнку.

Схеми для арифметичних операцій над багаторозрядними двійковими числами. Додавання двох n-розрядних двійкових чисел (x n ,….,x 1) 2 та (y n ,….,y 1) 2 як і в десятковій системі призводить до появи переносів у наступний розряд, які необхідно враховувати у обчисленні. Ці переноси також дорівнюють нулю чи одиниці (якщо перенос дорівнює нулю, то ручному обчисленні він мало виконується, але логічна схема має правильно працювати й у разі, адже вона «не знає», який перенесення прийшов із попереднього розряду). Позначимо перенесення з (i-1)-го розряду до наступного i-го розряду через w i (w 1 =0, тому що попереднього розряду в цьому випадку просто немає). Тоді для обчислення z i (i-го біта результату) потрібно скласти біти x i та y i і біт перенесення w i . Це додавання виконуємо за формулами

x i + y i + w i = 2v i +u i , v i = m (x i, y i, w i), u i = l (x i, y i, w i)

за допомогою схеми FA3. Тоді z i = u = l (x i, y i, w i), а наступний біт перенесення w i +1 = v i = m (x i, y i, w i). При додаванні n-розрядних чисел виходить взагалі n+1-розрядне число. Його старший біт zn+1=wn+1 дорівнює останньому переносу.

Схема додавання трирозрядних чисел наведена на наступному малюнку. Аналогічно виглядає і схема додавання n-розрядних чисел.

Складність зазначеного n-розрядного суматора дорівнює 5n-3. Н.П.Редько довів, що суматорів для n-розрядних чисел меншої складності в базисі (AND, OR, XOR, NOT) не існує. Побудований суматор є мінімальною схемою. Але ця схема має істотний недолік - вона має велику глибину. Глибиною схеми називається максимальне число її елементів, що утворюють ланцюг, що з'єднує якийсь із входів схеми з одним з її виходів. Наприклад, глибина вказаної схеми FA3 дорівнює 3.

Глибина схеми – не менш важлива характеристика схеми, ніж її складність. Складність логічної схеми значною мірою визначає площу відповідної реальної схеми, розташованої на кремнієвому кристалі. Глибина логічної схеми значною мірою визначає затримку реальної схеми, тобто. час, за який сигнал проходить від входів схеми до її виходів, іншими словами, час, який повинен пройти після стабілізації будь-яких значень на входах схеми до того моменту, коли на всіх виходах схеми стабілізуються також певні логічні значення. Складність схеми часто немає істотного значення, оскільки сучасні технології дозволяють розмістити на кристалі дуже великі схеми. А мінімізація затримки схеми дуже важлива, оскільки затримка комбінаційної частини багатотактної схеми визначає її тактову частоту - що менше затримка, то вище частота.

Теоретично вирахувати затримку реальної схеми дуже складно. Ланцюгів елементів схеми, що з'єднують її входи з виходами (ці ланцюги також називають шляхами), зазвичай досить багато і затримка схеми визначається затримкою по найгіршому у певному сенсі шляху, який називається критичним. Наприклад, на схемі FA3 критичний шлях, ймовірно, з'єднує входи X чи Y з виходом m. Затримка по будь-якому шляху визначається не тільки сумою затримок всіх елементів, що лежать на цьому шляху (наведений приклад вона дорівнює 3, якщо вважати затримку кожного елемента одиничною). Слід враховувати також затримку проводів, що з'єднують ці елементи. Затримка елемента залежить від того, між яким його входом і яким його виходом вона вимірюється, а також від електричних характеристик самого елемента та елементів безпосередньо з ним пов'язаних у схемі, вона залежить від температури схеми і навіть від того, які логічні значення подаються в аналізований момент на входи цього елемента і чи змінюється (і в який бік) значення його виході. Тим не менш, хоч і не дуже точно, затримку шляху можна оцінити як суму затримок його елементів. Якщо затримки всіх елементів дорівнюють, то ця величина визначається глибиною схеми. Вочевидь, поняття глибини схеми можна розширити, припустивши, що елементи базису може мати довільні неотрицательные затримки.

Глибина вказаної схеми n-розрядного суматора на перший погляд дорівнює 3n-2. Але уважний аналіз можливих критичних шляхів показує, що вона насправді дорівнює 2n-1. Anyway це дуже багато та побудована таким чином реальна схема матиме велику затримку. На практиці використовуються схеми, що мають одночасно малу складність, що не перевищує Cn (де - невелика константа) і малу глибину, приблизно рівну 2log 2 n. В.М. Храпченко у 1970 р. побудував схему малої складності та глибини, асимптотично рівної log 2 n (тобто рівну (1+ e(n)) log 2 n, де e(n) прагне нуля зі зростанням n). Він же нещодавно довів, що глибина суматора не може бути меншою за log 2 n + log 2 n (log 2 (log 2 n))). Тому побудована ним схема має асимптотично мінімальну глибину. Проте схема Храпченко перевершує звичайні схеми лише за n близько тисячі. Проте існує деяка модифікація його схеми з глибиною приблизно рівною log jn, де j = (Ö5+1)/2, і ця схема має меншу глибину, ніж стандартні схеми, вже починаючи з n = 8. У 2008 р. М. І.Грінчук побудував схему глибини не більшої за log 2 n+log 2 (log 2 n)+6, яка вже за малих n має меншу глибину, ніж усі відомі схеми.

Завдання побудови оптимальних схем для множення n-розрядних чисел виявилося важчим, ніж завдання про побудову оптимальних суматорів. Легко побудувати схему для множення n-розрядних чисел у базисі (OR,AND,XOR,NOT) складності приблизно 6n 2 . Для цього можна використовувати вказану схему для суматора. Проте її глибина буде великою. На початку 60-х років кілька дослідників (у СРСР Столяров і Офман, США Авіценіс і Уоллес) незалежно побудували схему для множення складності порядку n 2 і глибини порядку log 2 n. У сенсі глибини ці схеми по порядку оптимальні, але досі залишається невирішеною задача побудови схеми для множення асимптотично мінімальної глибини. У сенсі складності ці схеми виявилися далекі від оптимальних. А. А. Карацуба побудував у 1962 р. схему для множення, що має складність по порядку не більшу n 1,6 , потім А. Л. Тоом побудував схему складності n 1+ e(n) , де e(n) прагне нуля зі зростанням n. У певному сенсі цей результат остаточний, проте він був уточнений на рубежі 70-х років німецькими математиками А. Шенхаге та Ф. Штрассеном, які отримали для схем множення верхню оцінку складності по порядку, що не перевищує n log 2 n log 2 (log 2 n), а в 2008 р. цю оцінку покращив американський математик М. Фюрер, який замінив подвійний логарифм функцією, що украй повільно зростає. Є припущення, що складність схеми множення по порядку не менше n log 2 n, але це не доведено.

Американський математик С.Кук довів, що можна побудувати схему для розподілу 2n-розрядного числа на n-розрядне, у якої складність не перевищує складності множення n-розрядних чисел. Відомо також, що нижня оцінка складності схеми для поділу по порядку не менша від нижньої оцінки складності множення. Тому в сенсі оцінок складності поділ не представляє нічого нового порівняно з множенням. Однак довгий час найкращою оцінкою глибини розподілу по порядку було (log 2 n) 2 .

Згодом було знайдено схеми для поділу з глибиною по порядку, що дорівнює log 2 n, але їх складність виявилася великою. Американці Рейф і Тейт побудували схеми для розподілу глибини по порядку не перевершує log 2 n log 2 (log 2 n) і одночасно складності по порядку не перевищує n log 2 n log 2 log 2 n, однак і ці схеми, як і схеми Шенхаге Штрассена і Фюрера поки знайшли практичних застосувань, оскільки насправді починають перевершувати використовувані практично схеми лише за великих значеннях n.

		X		1	0	0	1	1	0	0	1	1	1	0
		X									1	0	1	1

				1	0	0	1	1	0	0	1	1	1	0
+			1	0	0	1	1	0	0	1	1	1	0
+		0	0	0	0	0	0	0	0	0	0	0
	1	0	0	1	1	0	0	1	1	1	0

	1	1	0	1	0	0	1	1	0	1	1	0	1	0

		X		1	0	0	1	1	0	0	1	1	1	0
		X									1	0	1	1

				1	0	0	1	1	0	0	1	1	1	0
+			1	0	0	1	1	0	0	1	1	1	0
+		0	0	0	0	0	0	0	0	0	0	0
	1	0	0	1	1	0	0	1	1	1	0

	1	1	0	1	0	0	1	1	0	1	1	0	1	0

Розмноження та розподіл на 2

Поділ на довільне число

Висновок

рекомендована література

Вам також може сподобатися

		X		1	0	0	1	1	0	0	1	1	1	0
		X									1	0	1	1

				1	0	0	1	1	0	0	1	1	1	0
+			1	0	0	1	1	0	0	1	1	1	0
+		0	0	0	0	0	0	0	0	0	0	0
	1	0	0	1	1	0	0	1	1	1	0

	1	1	0	1	0	0	1	1	0	1	1	0	1	0