Обернене число

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Самообернена функція: y = 1/x. Для кожного x окрім 0, y показує його обернене число

Обернене число для x, позначається 1/x або x−1, це число, яке добуток якого з x породжує одиницю. Оберненим дробу a/b буде b/a. Для отримання оберненого для дійсного числа треба розділити 1 на число. Наприклад, обернене для 5 є 1/5, а для 0.25 це 1 розділений на 0.25, або 4. Функція f(x), яка відображає x в 1/x, це один з найпростіших прикладів самооберненої функції.

Практичне застосування[ред.ред. код]

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

  1. Використати розширений алгоритм Евкліда для обчислення k−1, обернене k mod 2w, де w є числом бітів у слові. Таке число існуватиме, бо числа непарні, а модуль не має непарних дільників.
  2. Для кожного числа в списку, помножити його на k−1 і взяти менше значиме слово результату.

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

Див. також[ред.ред. код]