Числовое деление с использованием формата BCD - PullRequest
Новая
       11

Числовое деление с использованием формата BCD

3 голосов
/ 28 июня 2011

У меня есть два объекта std :: deque, содержащие (неупакованные) номера BCD. Каждый байт представляет собой одну цифру BCD. Размер не ограничен, но существует MAX_SCALE = 10, поэтому 1/3 должна привести к 0,3333333333. Для обоих объектов масштаб и знак сохраняются: 

class Numeric
{
   std::deque<uint8_t> m_digits;
   size_t m_scale; // indicates how many digits after "."
   bool sign; // true = positive, false = negative
};

Каждый числовой объект масштабируется до 0 до расчета, 10,34 / 2,1 - до 1034/210, а максимальный масштаб (2) записывается для повторного масштабирования позже.

Какой самый быстрый метод для вычисления отношения в третий числовой объект?

Я уже реализовал сложение, вычитание и умножение, но не могу найти хорошего объяснения, как реализовать (быстрое) деление (с неограниченным количеством цифр).

Ответы [ 2 ]

3 голосов
/ 28 июня 2011

Вы можете использовать метод Ньютона, чтобы найти 1 / а.

Пусть f (x) = 1 / x - a, вы хотите найти f ^ {- 1} (0).

Тогда 

x_{n + 1} = x_n - f(x_n) / f'(x_n)

сходится к f ^ {- 1} (0). Это дает нам 

x_{n + 1} = x_n - (1 / x_n - a) / (-1 / x^2)

1011 * поэтому * 

x_{n + 1} = x_n * (2 - a * x_n)

сходится к 1 / а. Вы проверяете сходимость по критерию 

if (|x_{n + 1} - x_n| < tolerance) then stop

Вам примерно нужно умножить лог n на сходимость. Если умножения O (n ^ 2), это медленнее, чем длинное деление для больших чисел (O (n ^ 2), против O (n ^ 2 log n)). Тем не менее, это быстро реализовать и не так плохо на практике. Фактически, некоторые процессоры используют вариант этой схемы, чтобы найти инверсии и выполнить деления. Обратите внимание, что если у вас есть лучший алгоритм умножения, то метод Ньютона асимптотически превосходит длинное деление.

В качестве первого предположения для x_0, вы можете установить все, кроме самой значащей цифры, в ноль и найти ее обратную сторону.

Пример: а = 3425,23. Первое предположение: 1 / a ~ 1/3000 ~ 0.0033333333

В качестве итерации, итерация 

x_{n + 1} = x_n * (3 - a * x_n^2)

будет сходиться к 1 / sqrt (a) (для начального предположения взять две первые цифры и небольшую таблицу поиска).

0 голосов
/ 28 июня 2011

Делайте все в целочисленной арифметике: для вычисления 10.34 / 2.1 вы хотите вычислить 10340000000000 / 2100, а затем разделить на 10^10. А чтобы рассчитать 10340000000000 / 2100, вам нужно всего лишь приобрести Knuth vol 2, как уже упоминал Александр С. (Это не то, о чем вы когда-либо пожалеете!) Я не думаю, что метод Ньютона применим здесь, если только ваши числа не очень велики.

...