УДК 681
Деление длинных чисел
А.Ю. Кривоножко, студент 345а группы
Национальный аэрокосмический университет им. Н.Е.Жуковского «ХАИ»
Проблема, в больших числах состоит в том, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, есть ограничения размера чисел, с которыми нужно работать.
Деление в столбик (m+n) - поразрядного целого числа на -разрядное целое число. Задача разбивается на более простые шаги, каждый из которых состоит в делении (n+1) - разрядного числа и на u-разрядное число v, где 0 Пусть и - представленные по основанию b неотрицательные целые числа, такие, что
u/v < b. Найти алгоритм для определения числа q = [u/v].
Условие u/v < b равносильно условию u/b < v, так что [u/b] < v. Это просто условие < . Далее, если записать г = u - qv, искомое число q будет единственным целым числом, таким что 0 < r < v.
Наиболее простой подход к решению поставленной задачи состоит в том, чтобы высказать какую-нибудь догадку относительно величины q, основываясь на наиболее значимых разрядах и и v. Не ясно, достаточно ли надежен такой подход, но он заслуживает исследования.
Согласно этой формуле q получается делением двух первых значащих разрядов числа и на первый значащий разряд числа v. Если результат равен b или больше b, заменяем его на b-1. Примечательно, что q всегда оказывается очень хорошим приближением к искомому ответу - q если только vn-1, относительно велико.
Список использованных источников:
1. Головач, В.В. Дизайн пользовательского интерфейса [Текст] і В.В. Головач, - К. : Университет, 2004. - 215 с.
2. Белов, А.В. С#. Создание приложений для Windows [Текст] / А.В. Белов -М.: Харвест, 2003 .- 384 с.
Нет похожих статей