Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Давньоєгипетський спосіб множення, що вважається одним iз найбільш древніх, оснований на використанні операції подвоєння.Стр 1 из 4Следующая ⇒
Незважаючи на те, що в давньоєгипетському способi використову-ються елементи двійкового множення, числа-множники можуть бути початково представленi в системі числення з будь-якою основою р > 2. Для р = 2, давньоєгипетський спосiб множення спiвпадає зi звичайним двійковим множенням методом накопичення сум часткових добутків. У випадку застосування давньоєгипетського способу множення до деяких двох чисел В та А, щодо них здiйснюються наступнi дії: 1) обчислюють усі можливі значення 2 i і В *2 i (i = 0, 1, 2,.., k) доти, поки не буде виконано умову 2 k+ 1 > А; 2) значення А представляють у вигляді поліному з основою 2 (визначають у вигляді суми значень двійок у відповідних ступенях); 3) добуток одержують додаванням значень В *2 i для тих i, що входять до визначення числа А. Розглянемо реалiзацiю алгоритму давньоєгипетського способу множення на прикладi знаходження добутку чисел В = 154 та А = 23. Етап1. Будемо обчислювати всі можливі значення 2 i (i = 0, 1, 2,.., k) і 154 *2 i доти, поки не буде виконано умову 2 k+ 1 > 23. Крок 1.1: i = 0, 154*20 = 154*1 = 154, i + 1 = 1, умову 21 = 2 > 23 не виконано, а тому продовжуємо здiйснювати обчислення далi. Крок 1.2: i = 1, 154*21 = 154*2 = 308, i + 1 = 2, умову 22 = 4 > 23 не виконано, а тому продовжуємо здiйснювати обчислення далi. Крок 1.3: i = 2, 154*22 = 308*2 =616, i + 1 = 3, умову 23 = 8 > 23 не виконано, а тому продовжуємо здiйснювати обчислення далi. Крок 1.4: i = 3, 154*23 = 616*2 = 1232, i + 1 = 4, умову 24 = 16 > 23 не виконано, а тому продовжуємо здiйснювати обчислення далi. Крок 1.5: i = 4, 154*24 = 1232*2 = 2464, i + 1 = 5, умову 25 = 32 > 23 виконано, а тому зупиняємо подальшi обчислення. Етап 2. Представимо число А = 23 у виглядi полiному: 1•20 + 1•21 + 1•22 + 0•23+ 1•24, тобто сформуємо його як суму чисел 1, 2, 4 i 16, якi вiдповiдають значенням ступенiв i = 0, 1, 2, 4 (20 = 1, 21 = 2, 22 = 4, 24 = 16). Етап 3. Обчислимо добуток чисел В = 154 та А = 23 шляхом додавання значень В *2 i для тих i = 0, 1, 2, 4, якi увiйшли до визначення числа А, тобто наступних значень: 154 (i = 0); 308 (i = 1); 616 (i = 2); 2464 (i = 4). У пiдсумку, буде отримано наступну суму, що являє собою добуток 154 на 23: 154 + 308 + 616 + 2464 = 3542. Простаферитичний спосіб множення, назва якого походить від грецьких слiв простезис (додавання) та афайрезис (віднімання), оснований на наступнiй тотожності:
За значеннями суми та різниці співмножників A та B, на основi таблиці виду Х 2 знаходять промiжнi величини C i D виду
C = (A + B)2 / 4, D = (A - B)2 / 4. Остаточно добуток формується після виконання операції віднімання: AB = (С – D). Розглянемо реалiзацiю алгоритму простаферитичного способу множення на прикладi знаходження добутку чисел А = 154 та В = 24. C = (A + B)2 / 4 = (154 + 24) 2 / 4 = 178 2 / 4 = 31684/ 4 = 7921, D = (A - B)2 / 4 = (154 - 24)2 / 4= 130 2 / 4 = 16900 / 4 = 4225, 154*24 = (С – D) =7921 – 4225 = 3696. Давньоіндійський спосiб множення «хрест нахрест» використовує наступну властивість: при множенні двох чисел А i В, представлених у позиційній однорідній системі числення з основою р, відповідно правилам множення поліномів, цифра розряду (з вагою) рi може бути отримана як сума всіх однорозрядних добутків виду (aib0 + ai-1b1 + … + a1bi-1 + a0bi +Пi-1), де ai і bi - цифри i-х розрядів чисел А i В, відповідно, Пi-1 - перенос з розряду рi-1 добутку. Дійсно, якщо представити числа А i В у вигляді поліномів з основою р, то одержимо наступне: Тоді добуток отримає вигляд C = A * B = (anpn + an- 1 pn- 1 + a0p0) * (bkpk + bk- 1 pk- 1 + b0p0). Оскiльки результат С також є позиційним числом з основою p, то він може бути представлений у наступний спосiб: C = cmpm + cm- 1 pm- 1+… + c0p0, де m = n + k. Тоді будемо мати представленi нижче значення: c0 = a0b0, c1 = a1b0 + a0b1 +П0, c2 = a2b0 + a1b1 + a0b2 + П1, … Очевидно, що сума індексів множників однорозрядних добутків aіbj для цифри розряду з вагою рк дорівнює індексу к, тобто: " i, j к=i+j.
Таким чином, для послідовного визначення розрядів результату множення двох чисел за допомогою давньоіндійськогоспособу множення «хрест нахрест», потрібен тільки однорозрядний суматор з основою р. Паралельне формування розрядів результату вимагає застосування значно більшого обсягу устаткування. Розглянемо приклад застосування давньоіндійського способу множення «хрест нахрест» до отримання добутку чисел А = 132 та В = 23. Представимо множники А = 132 та В = 23 у виглядi полiномiв: A = 1*102+3*101+2*100, В = 2*101+3*100. Тоді добуток отримає наступний вигляд: С = А*В = 6*100+(9*101+4*101+(3*102+6*101*101+0*2*100*102))+2*103= =3*103 +0*102+3*101+6*100. Названі вище способи множення (давньоєгипетський, простаферитичний i давньоiндiйський) при р>2 застосовуються рідко. Наприклад: - давньоєгипетський спосіб множення застосовувався в деяких обчислювальних машинах ранніх поколінь;
- простаферитичний спосіб множення використовується в комп`ютерах iз порівняно невеликою довжиною слова, що дозволяє застосовувати постійний запам'ятовуючий пристрій (ПЗП) для збереження квадратів чисел; - давньоiндiйський спосіб «хрест нахрест» використовується в деяких спеціалізованих комп`ютерах, якi виконують великий обсяг множень по основі р > 2, а його модифікація використовується в двійкових комп`ютерах при апаратній реалізації операції множення.
|
||||||
Последнее изменение этой страницы: 2017-02-21; просмотров: 245; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 13.59.82.167 (0.006 с.) |