Арифметика багаторозрядних цілих чисел. Lab3 (довга арифм). Форми представлення чисел

Программірованіе_в_алгорітмах_ (1) .pdf

С. М. Окулов програмування в алгоритмі 6-е видання (з дистанційним управлінням) Москва Лабораторія знань 2017

стор.2

УДК 519.85 (023) ББК 22.18 О-52 С е р і я про з зв про в а н а в 2008 р Окулов С. М. О-52 Програмування в алгоритмах [Електронний ресурс] / С. М. Окулов.- 6-е изд. (Ел.) .- Електрон. текстові дан. (1 файл pdf: 386 с.) .- М. : Лабораторія знань 2017 .- (Розвиток інтелекту школьников) .- Систем. вимоги: Adobe Reader XI; екран 10 ". ISBN 978-5-00101-449-2 Мистецтво програмування представлено у вигляді навчального курсу, який розкриває секрети найбільш популярних алгоритмів. Висвітлено такі питання, як комбінаторні алгоритми, перебір, алгоритми на графах, алгоритми обчислювальної геометрії. Наводяться обрані олімпіадні задачі з програмування з вказівками до вирішення. Практичні рекомендації з тестування програм є необхідним доповненням курсу. для школярів, студентів та фахівців, серйозно вивчають програмування, а також для викладачів навчальних закладів. УДК 519.85 (023) ББК 22.18 деривативних електронне видання на основі друкованого аналога: програмування в алгоритмах / С. М. Окулов.-4-е изд.: БИНОМ. Лабораторія знань, 2013.-383 с.: ил .- (Розвиток інтелекту школьников) .- ISBN 978-5-9963-0848 -4. відповідно до ст. 1 299 і 1301 ЦК України у разі усунення обмежень, встановлених технічними засобами захисту авторських прав, правовласник вправі вимагати від порушника в озмещенія збитків або виплати компенсації ISBN 978-5-00101-449-2 ○ Лабораторія знань, 2015 c

стр.3

Зміст Передмова. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. Арифметика багаторозрядних цілих чисел. . . . . . 8 1.1. Основні арифметичні операції. . . . . . . . . . . . . . 8 1.2. Завдання. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2. Комбінаторні алгоритми. . . . . . . . . . . . . . . . . . . . . . . . 27 2.1. Класичні задачі комбінаторики. . . . . . . . . . . . . . 27 2.2. Генерація комбінаторних об'єктів. . . . . . . . . . . . . . 34 2.2.1. Перестановки. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2.2. Розміщення. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.2.3. Сполучення. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.2.4. Розбиття числа на складові. . . . . . . . . . . . . . 58 2.2.5. Послідовності з нулів і одиниць дліниNбез двох одиниць поспіль. . . . . . . . . . . 64 2.2.6. Підмножини. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2.2.7. Дужкові послідовності. . . . . . . . . . . . . 71 2.3. Завдання. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3. Перебір і методи його скорочення. . . . . . . . . . . . . . . . 87 3.1. Перебір з поверненням (загальна схема). . . . . . . . . . . . . . . . 87 3.2. Приклади завдань для розбору загальної схеми перебору 89 3.3. Динамічне програмування. . . . . . . . . . . . . . . . .106 3.4. Приклади завдань для розбору ідеї методу динамічного програмування. . . . . . . . . . . . . . . . . . . . . . . . .108 3.5. Метод гілок і меж. . . . . . . . . . . . . . . . . . . . . . . . . . . .116 3.6. Метод «решета». . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .121 3.7. Завдання. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .126 4. Алгоритми на графах. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .158 4.1. Подання графа в пам'яті комп'ютера. . . . . . . .158 4.2. Пошук в графі. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .159 4.2.1. Пошук в глибину. . . . . . . . . . . . . . . . . . . . . . . . . . .159 4.2.2. Пошук в ширину. . . . . . . . . . . . . . . . . . . . . . . . . . .161

стр.4

4 Зміст 4.3. Дерева. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162 4.3.1. Основні поняття. Стягують дерева. .162 4.3.2. Породження всіх каркасів графа. . . . . . . . . . .163 4.3.3. Каркасмінімальноговеса.МетодДж.Краскала. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .165 4.3.4. Каркас мінімальної ваги. Метод Р. Пріма168 4.4. Можливості підключення. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .170 4.4.1. Досяжність. . . . . . . . . . . . . . . . . . . . . . . . . . . . .170 4.4.2. Визначення зв'язності. . . . . . . . . . . . . . . . . . . . .172 4.4.3. Двусвязного. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .173 4.5. Цикли. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .176 4.5.1. Ейлерови цикли. . . . . . . . . . . . . . . . . . . . . . . . . . .176 4.5.2. Гамільтона цикли. . . . . . . . . . . . . . . . . . . . . .177 4.5.3. Фундаментальне безліч циклів. . . . . . .179 4.6. Найкоротші шляхи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .180 4.6.1. Постановка задачі. Висновок шляху. . . . . . . . . . . .180 4.6.2. Алгоритм Дейкстри. . . . . . . . . . . . . . . . . . . . . . .182 4.6.3. Шляхи в бесконтурном графі. . . . . . . . . . . . . . . . .183 4.6.4. Найкоротші шляхи між усіма парами вершин. Алгоритм Флойда. . . . . . . . . . . . . . . . .186 4.7. Незалежні і домінуючі безлічі. . . . . . . .188 4.7.1. Незалежні безлічі. . . . . . . . . . . . . . . . . . .188 4.7.2. Метод генерації всіх максимальних незалежних множин графа. . . . . . . . . . . . . . . . . . .189 4.7.3. Домінуючі безлічі. . . . . . . . . . . . . . . .194 4.7.4. Завдання про найменшому покритті. . . . . . . . . . . .195 4.7.5. Метод рішення задачі про найменшому розбитті. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .196 4.8. Розмальовки. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202 4.8.1. Правильні розмальовки. . . . . . . . . . . . . . . . . . . . .202 4.8.2. Пошук мінімальної розмальовки вершин графа. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .203 4.8.3. Використання завдання про найменшому покритті при розфарбуванні вершин графа. . . . . . .207 4.9. Потоки в мережах, паросполучення. . . . . . . . . . . . . . . . . . . .208 4.9.1. Постановка задачі. . . . . . . . . . . . . . . . . . . . . . . . .208 4.9.2. Метод побудови максимального потоку в мережі. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .210 4.9.3. Найбільше паросочетание в дводольному графі. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .215

стор.5

Зміст 5 4,10. Методи наближеного рішення задачі комівояжера. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .219 4.10.1. Метод локальної оптимізації. . . . . . . . . . . .219 4.10.2. Алгоритм Ейлера. . . . . . . . . . . . . . . . . . . . . . . . .222 4.10.3. Алгоритм Крістофідеса. . . . . . . . . . . . . . . . . .225 4.11. Завдання. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .227 5. Алгоритми обчислювальної геометрії. . . . . . . . . .249 5.1. Базові процедури. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .249 5.2. Пряма лінія і відрізок прямої. . . . . . . . . . . . . . . . . .255 5.3. Трикутник. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .262 5.4. Багатокутник. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .266 5.5. Опукла оболонка. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .272 5.6. Завдання про прямокутниках. . . . . . . . . . . . . . . . . . . . . . . .284 5.7. Завдання. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .293 6. Вибрані олімпіадні задачі з програмування. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .300 7. Нотатки про тестування програм. . . . . . . . . . . . . . . .358 7.1. Про програмування. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .359 7.2. Практичні рекомендації. . . . . . . . . . . . . . . . . . . . . .360 7.3. Тестування програми вирішення задачі (на прикладі). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .370 Бібліографічний покажчик. . . . . . . . . . . . . . . . . . . . . . . .382

У найпростішому випадку, для однорозрядних чисел, правила двійкового складання мають вигляд:

При додаванні () виникає два випадки:

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

двійкове віднімання

Тут розглядаються правила, що працюють в разі віднімання меншого числа з більшого. Всі інші випадки розглядаються нижче в розділі 3.2, присвяченому двійковій арифметиці зі знаками. У найпростішому випадку, для кожного розряду, правила двійкового віднімання мають вигляд:

Коли проводиться віднімання () здійснюється займ з більш старшого розряду. Знак питання означає, що розряд зменшуваного змінюється в результаті позики за правилом:

При відніманні (0 - 1) в розряді різниці виходить 1, розряди зменшуваного, починаючи з наступного, змінюються на протилежні (інвертується) до першої зустрічної одиниці (включно). Після цього проводиться віднімання з змінених розрядів зменшуваного.

Розглянемо кілька прикладів віднімання багаторозрядних чисел (з більшого числа віднімається менша).

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

Двійкова арифметика з урахуванням знаків чисел

Прямий, зворотний і додатковий коди

У двійковому коді знак числа є розряд, який приписують зліва від значущих розрядів числа. Знак "" позначається логічним, знак "" - логічної. Для наочності всі приклади будемо розглядати для цілих чисел, відокремлюючи знаковий розряд точкою.

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

Так, в восьмирозрядному форматі

Зворотний код (ОК) для позитивних чисел збігається з прямим, тобто до значущим розрядами приписується знаковий розряд. Для негативних чисел значущі розряди інвертується (нулі замінюються на одиниці, одиниці - на нулі), після чого приписується знак.

Для того ж числа зворотний код має вигляд:,.

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

Додатковий код (ДК) для позитивних чисел збігається з зворотним і прямим, тобто до значущим розрядами приписується знаковий розряд. Для негативних чисел додатковий код на 1 більше, ніж зворотний. Після утворення значущих розрядів приписується знаковий розряд.

Для значущих розрядів негативного числа справедлива формула:

Напишемо число в 7-розрядному додатковому коді:

Таким чином в додатковому коді , Отже, зазначений недолік зворотного коду подолано.

Розглянемо утворення додаткової коду для числа 10. Для позитивного числа, а для негативного числа додатковий до д отримують у такий спосіб:

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

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

Для наочності візьмемо два десяткових числа, наприклад, і, і зробимо всі можливі варіанти обчислень:

.

Число позитивне, тому ОК \u003d ПК, Для перевірки числа потрібно перевести його значущі розряди в десятковий код по (П3-2):.

• . Спочатку отримаємо додатковий код негативного числа:

  

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

  Знову отримали знак числа і його значущі розряди, що займають жорстко задані позиції в обраному форматі числа. Оскільки отримано від'ємне число, то ДК ПК, Для перевірки його значущих розрядів потрібно спочатку вирахувати зворотний код, потім перевести його в прямий код інверсією -

  

  а потім вже перевести його в десятковий код по (П3-2):.

• - Спочатку отримаємо ДК негативного числа.

  

  Після цього зробимо обчислення.

Арифметика багаторозрядних чисел

виконав:
студент 3 курсу
математичного факультету
33 групи

Введення .................................................................. .................. ... 3

Подання числа в будь-якій системі числення .............................. ...... 4
Операції над довгими числами .. ................................................ ..... .5
Додавання багаторозрядних чисел ...................................................... .6
Віднімання багаторозрядних чисел ................................................... ... 7
Множення багаторозрядних чисел ................................................... 8
Швидке множення ............................................................... ...... ... 11
Порівняння "швидкого" і "шкільного" множення ... ... ........................... 22
Точність обчислень і її поліпшення ............................................. ... 23

Висновок ............................................................ ..................... .24

Література ............................................................ ..................... .26

Додаток ... .. ................................................... ........................ .27

Вступ
Для безлічі додатків надаються процесором базових типів цілком вистачає. Однак, зустрічається багато задач, вихідні дані яких занадто великі. Число з 1000 цифр не поміститься ні в один регістр. Тому комп'ютерне подання таких чисел і операції над ними доводиться реалізовувати самостійно.
При цьому час виконання зовнішнього алгоритму, що використовує такі числа, дуже сильно залежить від ефективності їх реалізації. Наприклад, якщо оцінка часу визначається O (n2) множеннями, то використання для цієї операції в два рази більше швидкого алгоритму дає
прискорення в 4 рази. Тому ми будемо, мабуть, найбільш серйозно зацікавлені не просто в правильних, але можливо більш ефективних алгоритмах, які при необхідності можна реалізувати на пристойному рівні.

Подання числа в будь-якій системі числення
Зазвичай, невід'ємне ціле число N довжини n представляється у вигляді N \u003d a0 + a1 * BASE + a2 * BASE2 + ... + an-1 BASEn-1,
де BASE - основа системи числення, все коефіцієнти 0. ai< BASE.
Наприклад, число в цій інтерпретації матиме вигляд
1234510 \u003d 5 + 4 * 10 + 3 * 102 + 2 * 103 + 1 * 104 (BASE \u003d 10).
Довге число зберігається в масиві, де i-й елемент відповідає коефіцієнту числа при BASE.
Як приклад, розглянемо масив для:: (5, 4, 3, 2, 1).
Як видно, цифри зберігаються в зворотному порядку. Це - якась "заготовка на майбутнє": справа в тому, що реалізації алгоритмів при цьому мають більш природний вигляд.
Таке уявлення N є окремим випадком многочлена n-го ступеня P (x) \u003d a0 + a1 * x + a2 * x2 + ... + an-1 xn-1, який також зручно зберігати в вигляді масиву коефіцієнтів. Тому більшість основних операцій над числами при відповідному спрощення алгоритмів працюють для довільних многочленів (додавання, множення тощо).
Знак числа, як і місце десяткового дробу, можна запам'ятати в окремій змінної і враховувати при виконанні операцій. Далі ми будемо оперувати лише з цілими невід'ємними числами.
Підстава системи числення BASE зазвичай залежить від максимального розміру базового типу даних на комп'ютері, і вибирається, виходячи з таких міркувань:
1. Основа повинна підходити під один з базових типів даних
2. BASE має бути якомога більше, щоб зменшити розмір уявлення довгого числа і збільшити швидкість операцій з ними, але досить малого розміру, щоб всі операції з коефіцієнтами використовували базовий тип даних.
3. Для зручності можна вибрати BASE як ступінь 10 (висновок інформації, налагодження).
Операції над «довгими числами»
Розглянемо досить популярну в програмуванні завдання на роботу з "довгими" числами. Реально з "астрономічними" або "мікроскопічними" числами доводиться стикатися не так вже й часто. Проте, вправи, що розглядаються в цій публікації, можуть послужити хорошою тренуванням в області програмування і зайняти гідне місце в класах з поглибленим вивченням інформатики або на гуртках з програмування. Алгоритми, представлені нижче, записані на Turbo Pascal, версія 7.0 і на Сі ++. При бажанні або необхідності вони можуть легко бути адаптовані до будь-якої іншої програмному середовищі. Діапазон представлення цілих чисел (Integer, Word, LongInt) обмежений, про що не раз вже говорилося (втім, для дійсних величин це зауваження теж актуально). Тому при вирішенні завдань завжди доводиться діяти з оглядкою, - як би не допустити виникнення помилки виходу за діапазон або переповнення. Наприклад, обчислюючи факторіал ( n! = 1 * 2 * 3 * … * n), В діапазоні подання величин типу Integer вдасться правильно отримати тільки 7! \u003d 5040, а в діапазоні уявлення типу LongInt - 12! \u003d 479001600. Для більших значень, звичайно, можна використовувати дійсні типи даних, але це вже не гарантує точного результату. Тому корисно для отримання точних значень при діях з багатозначними числами розробити інші способи представлення таких чисел, алгоритми виконання арифметичних та інших операцій, процедури введення та виведення результатів і т.д.
Числа, для представлення яких в стандартних комп'ютерних типах даних не вистачає кількості двійкових розрядів, називаються "Довгими". Реалізація арифметичних операцій над такими "довгими" числами отримала назву "Довгої арифметики". Найбільш природним способом представлення багатозначного числа є запис кожного його розряду у вигляді окремого елемента лінійного масиву (або списку, де пам'ять під цифру буде приділятися в міру потреби, в той час як в масиві доводиться заздалегідь задавати максимальну кількість елементів в ньому). Нехай (для зручності подальших дій) розряди "довгого" числа при записи в масив нумеруються з одиниці, починаючи з розряду одиниць, тобто цифра з розряду одиниць - елемент масиву з номером один, цифра з розряду десятків - елемент масиву з номером два і т.д. Визначимо для роботи з "довгими" невід'ємними числами тип даних:
Але якщо ми будемо реалізовувати арифметичні операції над цим числом, то розмір масиву повинен бути достатнім, щоб розмістити в ньому і результат, наприклад, множення. Множення найскладніше з усіх арифметичних дій і його кінцевий результат найбільше місце в пам'яті комп'ютера. Найбільш простими діями над багаторозрядними числами є додавання і віднімання.
Додавання багаторозрядних (довгих) чисел
Практично кожен вміє складати довгі числа, використовуючи для цього листок паперу і олівець. Чим ми тепер займемося - це перенесемо, яку ми маємо розуміння на мову, зрозумілий комп'ютером.
Схема для складання дуже проста: складаємо цифри зліва направо (цифри зберігаються в зворотному порядку). Якщо зафіксовано переповнення (тобто при додаванні отримана цифра, велика максимально можливої \u200b\u200bв даній системі числення), то відбувається "перенесення" в наступний розряд.
Знайдемо суму чисел А і В. Будемо складати елементи масивів з однаковими номерами та зберігати отримані результати, як елементи масиву С (алгоритм роботи з такими масивами нагадує складання в стовпчик). Якщо на якомусь етапі отримаємо З [i], то на місці C [i] залишаємо залишок від ділення C [i] на 10 (кількість одиниць даного розряду), а до елементу C додамо 1 (перенесення 1 в наступний розряд).
Якщо число А складається з N цифр, а число В - з M чисел, то число С має або max (N, M) цифр, або max (N, M) +1 цифру. Позначимо через До величину max (N, M) +1.
Перед виконанням складання слід доповнити незначущими нулями число з меншою кількістю цифр так, щоб кількість цифр зрівнялося. Цього можна досягти і обнулила масиви А і В до введення цифр.
Алгоритм складання двох багаторозрядних чисел представлений в Додатку 1.
Після виконання даного алгоритму в перших До елементах масиву С буде зберігатися сума чисел А і В, С цифра молодшого розряду. Остання перевірка дозволяє прибрати незначний нуль з старшого розряду числа С.
Віднімання багаторозрядних чисел
Віднімання здійснюється аналогічно, з тією лише різницею, що здійснюється перенесення "запозичення". Ми працюємо з позитивними числами, тому якщо від'ємник велике за розміром - відбувається вихід.
Якщо довжини однакові, але одне більше іншого - це призведе до того, що в кінці процесу залишиться невикористане запозичення, а результат буде доповненням до BASEB.Size.
Для визначеності будемо вважати, що А\u003e B. Якщо немає, то необхідно поміняти числа місцями, а результат зробити негативним.
Якщо число А складається з N цифр, тоді число В не може мати більш ніж N цифр. Різниця буде містити не більше ніж N цифр.
Знайдемо різницю чисел А і В. Будемо віднімати елементи масиву В з елементів масиву А з відповідними номерами. Отримані результати будемо зберігати в масиві С. Якщо на якомусь етапі отримаємо C [i]<0, то к элементу C[i] прибавляем 10, а от элемента C отнимаем 1(забираем 1 из следующего разряда).
Алгоритм віднімання двох багаторозрядних чисел представлений в Додатку 2.
Множення багаторозрядних чисел
Найбільш природним способом представлення багатозначного числа є запис кожного його розряду у вигляді окремого елемента лінійного масиву (або списку, де пам'ять під цифру буде приділятися в міру потреби, в той час як в масиві доводиться заздалегідь задавати максимальну кількість елементів в ньому). Нехай (для зручності подальших дій) розряди "довгого" числа при записи в масив нумеруються з одиниці, починаючи з розряду одиниць, тобто цифра з розряду одиниць - елемент масиву з номером один, цифра з розряду десятків - елемент масиву з номером два і т.д. Визначимо для роботи з "довгими" невід'ємними числами тип даних:
Const MNax \u003d 2000;
Type Digit \u003d 0..9;
DlChislo \u003d Array Of Digit;
Для вирішення поставленого завдання необхідно вміти виконувати наступні дії:
1) введення "довгого" числа;
2) власне множення двох "довгих" чисел;
3) висновок "довгого" числа;
4) визначення кількості цифр у записі числа.
Кожну з підзадач реалізуємо у вигляді окремої підпрограми. Почнемо з введення. Ввести велике число доцільно у вигляді рядка, а в подальшому перетворити в масив цифр. У процедурі врахований вказаний вище спосіб розміщення "довгого" числа в масиві, тобто з точки зору користувача число записується як би в зворотному порядку.
(Процедура перетворення довгого числа, записаного у вигляді рядка, в масив цифр; змінна OK приймає значення True, якщо в запису числа немає сторонніх символів, відмінних від десяткових цифр, інакше - false)
Procedure Translate (S: String; Var A: DlChislo; Var OK: Boolean);
Var I: Word;
Begin
Zero (A); I: \u003d Length (S); OK: \u003d True;
While (I\u003e \u003d 1) And OK Do
Begin
If S [I] In [ "0" .. "9"]
Then A: \u003d Ord (S [I]) - 48
Else OK: \u003d False; I: \u003d I - 1
End
End;
У процедурі викликається підпрограма Zero (A), призначення якої - запис нуля в кожен розряд довгого числа. Ось текст цієї процедури:
(Процедура обнулення довгого числа)
Procedure Zero (Var A: DlChislo);
Var I: Integer;
Begin
For I: \u003d 1 To NMax Do A [I]: \u003d 0;
End;
Таким чином, довге число записано в масив, де попереду (як елементи з великими номерами) стоять незначущі нулі. При виконанні дій і виведення відповіді вони не враховуються.
Зараз розробимо функцію визначення кількості значущих цифр у записі числа, оскільки вона буде потрібно при реалізації підпрограми множення.
(Функція визначення кількості цифр у записі довгого числа)
Function Dlina (C: DlChislo): Integer;
Var I: Integer;
Begin
I: \u003d NMax;
While (I\u003e 1) And (C [I] \u003d 0) Do I: \u003d I - 1;
Dlina: \u003d I
End;
При її розробці було використане таке міркування: якщо число не дорівнює нулю, то кількість цифр у його записи одно номером першої цифри, відмінною від нуля, якщо перегляд числа здійснюється від старшого розряду до молодшого. Якщо ж довге число дорівнює нулю, то виходить, що кількість цифр в його записи одно одній, що і було потрібно.
Ну і, нарешті, головна процедура, заради якої і була пророблена вся попередня робота. При складанні алгоритму використовується ідея множення "стовпчиком", хоча в нашому варіанті складання виконується не по закінченню множення, а по ходу його, тобто перемноживши чергові цифри, відразу ж додаємо результуючу цифру в потрібний розряд і формуємо перенесення в наступний розряд.
(Процедура множення довгих чисел. A, B - множники, C - твір)
Procedure Multiplication (A, B: DlChislo; Var C: DlChislo);
Var I, J: Integer; P: Digit; VspRez: 0..99;
Begin
Zero (C);
For I: \u003d 1 To Dlina (A) Do (Цикл за кількістю цифр в першому числі)
Begin
P: \u003d 0; (Спочатку перенесення дорівнює нулю)
For J: \u003d 1 To Dlina (B) Do (Цикл за кількістю цифр в другому числі)
Begin
VspRez: \u003d A [I] * B [J] + P + C;
C: \u003d VspRez Mod 10; (Чергове значення цифри в розряді I + J - 1)
P: \u003d VspRez Div 10 (Перенесення в наступний розряд)
End;
C: \u003d P (останній перенесення може бути відмінний від нуля, запишемо його в поки що вільний розряд)
End
End;
Цілком програма представлена \u200b\u200bв Додатку 3.

БИСТРОЕ_УМНОЖЕНІЕ
Ми поставили собі за мету написати не тільки, як відбувається множення над довгими числами, а й встановити, як його зробити більш швидким.
Складемо алгоритм множення:
1. Знайти найменше число Len - ступінь двійки: Len. A.Size + B.Size. Для розглянутих чисел Len \u003d 8.
2. Доповнити A і B провідними незначущими нулями до Len. А нашому прикладі A \u003d (3,4,0,0,0,0,0,0), B \u003d (5,4,3,2,1,0,0,0).
3. Обчислити БПФ дійсних векторів на обох масивах цифр.
4. Скалярним перемножити перетворені вектора, отримавши вектор розміру Len.
5. Застосувати зворотне перетворення Фур'є, результатом якого буде згортка.
6. Перетворити згортку в масив цілих чисел, зробити переноси.
Цифри великих чисел зберігаються в целочисленном форматі. Тому для БПФ їх необхідно скопіювати в тимчасові масиви типу з плаваючою крапкою. Якщо передбачається отримувати результат максимальної довжини N, то необхідно виділити для них пам'ять як мінімум розміру
MaxLen \u003d 2k, де MaxLen - мінімальна ступінь двійки, велика N. Наприклад, якщо максимальний результат буде складатися з 1000 цифр по підставі BASE, то мінімальний обсяг пам'яті MaxLen \u003d 1024, так як саме такої довжини ШПФ буде обчислюватися.
real * LongNum1 \u003d NULL, * LongNum2 \u003d NULL;
// Ініціалізацію можна робити тільки 1 раз за всю програму.
void FastMulInit (ulong Len) (
ulong MaxLen;
if ((Len & -Len) \u003d\u003d Len) // Len \u003d ступінь двійки
MaxLen \u003d Len;
else (// інакше обчислити MaxLen - найменший ступінь 2,
MaxLen \u003d 2; // таку що 2MaxLen. Len
do MaxLen * \u003d 2; while (MaxLen< Len);
}
LongNum1 \u003d new real;
LongNum2 \u003d new real;
}
// деініціалізацію
void FastMulDeInit () (
delete LongNum1;
delete LongNum2;
}
Розібрана у відповідному розділі функція RealFFT () виробляє перетворення "на місці", повертаючи результуючі вектори в стислому вигляді.
Відповідно, функція скалярного твори повинна враховувати такий формат.
// Скалярний множення комплексних векторів в стислому вигляді: LongNum1 \u003d LongNum1 * LongNum2
void RealFFTScalar (real * LongNum1, const real * LongNum2, ulong Len) (
Complex * CF1 \u003d (Complex *) LongNum1;
const Complex * CF2 \u003d (Complex *) LongNum2;
// перші два елементи - згруповані в одне комплексне дійсні числа

LongNum1 \u003d LongNum1 * LongNum2;
for (ulong x \u003d 1; x< Len/2; x++) // остальные – комплексные, как им и
CF1 [x] \u003d CF1 [x] * CF2 [x]; // слід бути після ДПФ
}
Зробимо більш детальний розбір останнього кроку.
Всі обчислення відбуваються в форматі чисел з плаваючою точкою, використовують ірраціональні числа, тому результат буде не набором цілих чисел, а, скоріше, наближенням до нього. Для отримання відповіді кожну координату згортки необхідно округлити до найближчого цілого числа.
a a a a ... .. a
b b b b ... .. b
Проблема криється в тому, що якщо точність обчислень недостатньо висока, то округлення може відбутися не до того числа. В результаті алгоритм благополучно завершиться, але відповідь буде невірний.
Частина питань, пов'язаних з точністю, була вирішена в обговоренні БПФ. Однак навіть при абсолютно точної тригонометрії будуть накопичуватися помилки обчислень, так як операції арифметичні операції не можуть вироблятися з абсолютною точністю. Тому частинка типу даних должн бути досить великим, щоб помилка на будь-якому знаку була менше 0.5.
Наприклад, при використанні типу даних розміру 1, дріб 1/3 представляється у вигляді 0.3. При додаванні трьох дробів отримуємо
1/3 + 1/3 + 1/3 \u003d (в форматі чисел з плаваючою точкою) 0.3 + 0.3 + 0.3 \u003d 0.9
Якщо ж розмір - дві цифри, то 1/3 \u003d 0.33,
1/3 + 1/3 + 1/3 \u003d 0.33 + 0.33 + 0.33 \u003d 0.99. Точність обчислень сильно зросла.
Взагалі кажучи, шляхів збільшення точності два. Один з них пов'язаний зі збільшенням довжини використовуваного типу: Від float до double, далі до long double, потім до double double2 ...
Інший підхід більш гнучкий. Він передбачає при фіксованому типі зменшувати довжину підстави BASE. Таким чином число стане довшим, буде займати більше пам'яті, але за рахунок цього збільшується точність.
Обмеження БПФ-множення
Цікаву оцінку для помилок дав Колін Персіваль.
Нехай потрібно перемножити вектори з 2n координат з використанням ШПФ для векторів з дійсними координатами. Тоді з його результатів слід, що похибка err множення x на y оцінюється зверху виразом
err< 2n BASE2 (.*3n + . 5 (3n+4) + .(3n+3)) (2)
де. - точність складання / множення,. - точність геодезичних обчислень,
Звідси при заданих.,. не складає труднощів знайти мінімально можлива підстава BASE.
Наприклад, при використовуваному типі double (53 біта),. \u003d 2-53. Помилки тригонометрії обмежені величиною. \u003d. / 2.
Оцінимо верхню межу помилок (2) числом .. Приблизно порахувавши константи, отримуємо 2n BASE2 2-53 (11.83 n + 11.07)< .
Для чисел довжини 220 це веде до нерівності BASE< 4100. Такова оценка худшего случая, обоснованная математически.
На практиці, однак, хорошим вибором буде BASE \u003d 10000. БПФ-множення при такій підставі може працювати навіть для багато великих чисел. Однак, при цьому не буде математичних гарантій правильного результату.
При округленні слід дивитися на різницю між округляється значенням і результатом округлення. Якщо вона менше 0.2, то множення, швидше за все, дає правильний результат, якщо більше - рекомендується зменшити BASE або скористатися іншим базовим типом для зберігання коефіцієнтів.
Після виконання кроку 5 немає готового твору, а є лише згортка - результат без переносів. Як вже говорилося при розгляді піраміди множення, значення коефіцієнтів згортки можуть бути багато більше підстави, досягаючи 2N * BASE2. Якщо додатково згадати, що при зворотному перетворенні Фур'є відбувається розподіл результатів виконання функції RealFFT () на N, то максимальний розмір цифри стає дорівнює 2N2 * BASE2, тому слід подбати, щоб не сталося переповнення. Зокрема, не слід оголошувати BASE довше 4х десяткових цифр.
Останні два типи підтримують далеко не всі процесори

Як резюме до вищесказаного, зауважимо, що проблеми всього три:
1. Точність тригонометрії
2. Точність при обчисленні ШПФ
3. Переповнення базового типу.
Перша проблема вирішена при обговоренні БПФ. Друга і третя вирішуються шляхом зменшення BASE, або збільшення базового типу. При цьому ефективність алгоритму падає, так як менше підставу означає подовження кількості цифр, а більший базовий тип не завжди доступний.
Наступна функція перетворює згортку Convolution довжини Len в велике число C, роблячи округлення і виконуючи переноси. В кінці виконання змінна MaxError буде містити максимальну помилку округлення.
RealFFT () не виробляє нормалізацію результату, тому її необхідно зробити тут же.
real MaxError;
void CarryNormalize (real * Convolution, ulong Len, BigInt & C) (
real inv \u003d 1.0 / (Len / 2); // коефіцієнт нормалізації
// ДПФ проводилося над "комплексним" вектором
// в 2 рази меншою довжини
real RawPyramid, Pyramid, PyramidError, Carry \u003d 0;
short * c \u003d C.Coef;
ulong x;
// В C помістимо тільки ту частину результату, яка туди влазить
// ДПФ має довжину, рівну 2k, але вектор коефіцієнтів
// міг бути ініціалізован на меншу кількість елементів, що не на ступінь 2.
if (Len\u003e C.SizeMax) Len \u003d C.SizeMax;
MaxError \u003d 0;
for (x \u003d 0; x< Len; x++) {
RawPyramid \u003d Convolution [x] * inv + Carry;
// Додаємо 0.5, щоб округлення відбулося до найближчого цілого
Pyramid \u003d floor (RawPyramid + 0.5);
PyramidError \u003d fabs (RawPyramid - Pyramid);
if (PyramidError\u003e MaxError)
MaxError \u003d PyramidError;
Carry \u003d floor (Pyramid / BASE); // обчислюємо переноси
c [x] \u003d (short) (Pyramid - Carry * BASE);
}
// Все готово, залишилося лише встановити розмір С, за першим
// ненульова коефіцієнту.
do (x--;) while (c [x] \u003d\u003d 0);
C.Size \u003d x + 1;
}
Тепер можна реалізувати алгоритм цілком.
// Обчислити C \u003d A * B, працює виклик FastMul (A, B, A)
void FastMul (const BigInt & A, const BigInt & B, BigInt & C) (
ulong x;
const short * a \u003d A.Coef, * b \u003d B.Coef;
if (! LongNum1 ||! LongNum2) error ( "FastMul not initalized.");
// Крок 1
ulong Len \u003d 2;
while (Len< A.Size + B.Size) Len *=2;
if (Len< 8) Len = 8; // FFT работает

// Крок 2. Переписуємо число під тимчасовий масив і доповнюємо провідними нулями
// Порядок цифр зворотний, тому провідні нулі будуть в кінці
for (x \u003d 0; x< A.Size; x++) LongNum1[x] = a[x];
і т.д.................