Довга арифметика (автор статті Окулов з
Відомо, що арифметичні дії, виконувані комп'ютером в обмеженому числі розрядів, не завжди дозволяють отримати точний результат. Більш того, ми обмежені розміром (величиною) чисел, з якими можемо працювати. А якщо нам необхідно виконати арифметичні дії над дуже великими числами, наприклад, 30! = 265252859812191058636308480000000?
У таких випадках ми самі повинні подбати про подання чисел в машині і про точне виконання арифметичних операцій над ними.
Числа, для представлення яких в стандартних комп'ютерних типах даних не вистачає кількості двійкових розрядів, називаються "довгими". Реалізація арифметичних операцій над такими "довгими" числами отримала назву "довгої арифметики".
Організація роботи з "довгими" числами багато в чому залежить від того, як ми представимо в комп'ютері ці числа. "Довге" число можна записати, наприклад, за допомогою масиву десяткових цифр, кількість елементів в такому масиві дорівнює кількості значущих цифр у "довгому" числі. Але якщо ми будемо реалізовувати арифметичні операції над цим числом, то розмір масиву повинен бути достатнім, щоб розмістити в ньому і результат, наприклад, множення.
Існують і інші вистави "довгих" чисел. Розглянемо одне з них. Уявімо наше число
30! = 265252859812191058636308480000000 у вигляді:
30! = 2 * (10 4) 8 + 6525 * (10 4) 7 + 2859 * (10 4) + 8121 * (10 4) 5 + 9105 * (10 4) 4 + 8636 * (10 4) 3 + 3084 * (10 4) 2 + 8000 * (10 4) 1 + 0000 * (10 4) 0.
Це уявлення наштовхує на думку про масиві, представленому в табл. 1.
Номер елемента в масиві А
Алгоритм імітує звичне складання стовпчиком, починаючи з молодших розрядів. І саме для простоти реалізації арифметичних операцій над "довгими" числами використовується машинне подання "задом наперед".
Результат: З = 3476782713546912.
Нижче наведено текст процедури складання двох "довгих" чисел.
Четверте завдання. Реалізація операцій порівняння для "довгих" чисел (А = В, А В, А = В).
Реалізація функції А> В також прозора.
Інші функції реалізуються через функції Eq і More.
Для самостійного рішення може бути запропонована наступна, більш складна, завдання. Потрібно розробити функцію, яка видає 0, якщо А більше В, 1, якщо А менше В, і 2 за однакової кількості чисел. Але порівняння повинно бути виконано з урахуванням зсуву. Про що йде мова? Пояснимо на прикладі. Нехай А одно 56784, а В - 634. При зсуві числа В на 2 позиції вліво функція повинна сказати, що В більше А, без зсуву, що А більше В. Інший приклад. При А рівному 56700, а В - 567 і зсуві 2 функція повинна "сказати", що числа рівні. Рішення може мати наступний вигляд:
П'яте завдання. Множення довгого числа на коротке. Під коротким розуміється ціле число типу LongInt.
Процедура дуже схожа на процедуру складання двох довгих чисел.
Шоста завдання. Віднімання двох довгих чисел з урахуванням зсуву
Якщо поняття зсуву поки не зрозуміло, то залиште його в спокої, насправді віднімання з урахуванням зсуву потрібно при реалізації операції ділення. На початку з'ясуйте логіку роботи процедури при нульовому зсуві.
Введемо обмеження: число, з якого віднімають, більше числа, яке віднімається. Працювати з "довгими" негативними числами ми не вміємо.
Процедура була б схожа на процедури додавання і множення, якби не одне "але" - запозичення одиниці зі старшого розряду замість перенесення одиниці в старший розряд. Наприклад, у звичайній системі числення ми віднімаємо 9 з 11 - йде запозичення 1 з розряду десятків, а якщо з 10000 віднімаємо 9 - процес запозичення трохи складніше.
Сьома завдання. Розподіл двох довгих чисел, тобто знаходження цілої частини приватного і залишку.
Написати вихідну (без уточнень) частина логіки не складає труднощів. це:
А далі? Далі починаються проблеми. Ділити стовпчиком нас навчили в школі. наприклад,
Що ми робили? На кожному етапі в розумі підбирали цифру (1, 3, 5 і т.д.), таку, що твір цієї цифри на дільник дає число менше, але найбільш близьке до числа. Якому? Це важко сказати словами, але з прикладу ясно. Навіщо нам це робити в розумі, нехай робить комп'ютер. Однак спростимо приклад, залишимо його для тестування остаточної логіки процедури, тим більше що і числа "довгі". Нехай число А буде менше Вnbsp * 10, тоді в результаті (цілої частини поділу) буде одна цифра. Наприклад, А одно 564, а В - 63 і проста десяткова система числення. Спробуємо підібрати цифру результату, але не методом прямого перебору, а методом ділення відрізка навпіл. Нехай Down - верхня межа інтервалу зміни підбирається цифри, Up - нижня межа інтервалу, Ost дорівнює делимому.
С = В * ((Down + Up) Div 2)
Ціла частина приватного дорівнює 78, залишок від ділення - 27856 мінус 27612, тобто 244.
Пора наводити процедуру. Використовувані "цеглинки": функція порівняння чисел (More) з урахуванням зсуву і функція множення довгого числа на коротке (Mul) описані вище.
Залишилося розібратися зі зрушенням, значенням змінної sp в нашому викладі. Знову повернемося до звичайної системі числення і спробуємо розділити, наприклад, 635 на 15. Що ми робимо? Спочатку ділимо 63 на 15 і формуємо, підбираємо в розумі першу цифру результату. Підбирати за допомогою комп'ютера ми навчилися. Підібрали - це цифра 4, і це старша цифра результату. Змінимо залишок. Якщо спочатку він був 635, то зараз став 35. Віднімати з урахуванням зсуву ми вміємо. Знову підбираємо цифру. Другу цифру результату. Це цифра 2 і залишок 5. Отже, результат (ціла частина) 42, залишок від ділення 5. А що зміниться, якщо підставою буде не 10, а 10000? Логіка збігається, тільки в розумі вважати трохи важче, але ж у нас же є молоток під назвою комп'ютер - нехай він забиває цвяхи.
Методичні рекомендації. Представлений матеріал викладається на чотирьох заняттях за відомою схемою: 10-15-хвилинне виклад ідей, а потім робота учнів під керівництвом викладача.
1-е заняття. Введення, висновок і складання довгих чисел (завдання 1, 2, 3).
2-е заняття. Функції порівняння (завдання 4).
3-е заняття. Множення і віднімання довгих чисел (завдання 5, 6).
4-е заняття. Розподіл довгих чисел (завдання 7). Безумовно, ця схема не догма. Залежно від рівня підготовки учнів на самостійне виконання може бути винесена значна частина матеріалу. Зауважу тільки, що в силу сформованої традиції в ряді випадків допускаються при викладі свідомі помилки. В результаті роботи кожен учень повинен мати власний модуль для роботи з "довгими" числами.
Теми для досліджень
1. Рішення задач: пошук найбільшого загального дільника двох "довгих" чисел; пошук найменшого спільного кратного двох "довгих" чисел; витяг квадратного кореня з "довгого" числа і т.д.
2. "Довгі" числа можуть бути негативними. Як зміняться описані вище операції для цього випадку?
3. Для зберігання "довгих" чисел використовується не масив, а стек, реалізований за допомогою списку. Модифікувати модуль роботи з "довгими" числами.
Сайт створено в системі uCoz