Пытаясь понять простые вычисления большого числа

Question

Пытаясь понять простые вычисления большого числа

Я пытаюсь лучше понять, как работают библиотеки «больших чисел» (например, GMP например).

Я хочу написать свою собственную функцию Add() / Subtract() / Multiply() / Divide()

Класс традиционно определяется …

std::vector<unsigned char> _numbers; // all the numbers
bool _neg; // positive or negative number
long _decimalPos; // where the decimal point is located
// so 10.5 would be 1
//    10.25 would be 2
//    10 would be 0 for example

Сначала мне нужно нормализовать числа, чтобы я мог сделать

Используя 2 номера
10 (х) + 10,25 (у) = 20,25

Для простоты я бы сделал их одинаковой длины,

Для х:
_numbers = (1,0,0,0) десятичный = 2

Для тебя:
_numbers = (1,0,2,5) десятичный = 2

И тогда я могу в обратном порядке добавить х к у в цикле

...
// where x is 10.00 and y is 10.25
...
unsigned char carryOver = 0;
int totalLen = x._numbers.size();
for (size_t i = totalLen; i > 1 ; --i )
{
unsigned char sum = x._numbers[i-1] + y._numbers[i-1] + carryOver;
carryOver = 0;
if (sum > _base)
{
sum -= _base;
carryOver = 1;
}
numbers.insert( number.begin(), sum);
}

// any left over?
if (carryOver > 0)
{
numbers.insert( number.begin(), 1 );
}

// decimal pos is the same for this number as x and y

...

Приведенный выше пример будет работать для добавления двух положительных чисел, но скоро упадет, когда мне нужно будет добавить отрицательное число к положительному числу.

И это становится более сложным, когда дело доходит до вычитания чисел, тогда еще хуже для умножения и деления.

Может кто-нибудь предложить несколько простых функций для добавления () / Subtract () / Multiply () / Divide ()

Я не пытаюсь переписать / улучшить библиотеки, я просто хочу понять, как они работают с числами.

2

bignum c++computation-theory math

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

сложение и вычитания довольно просты

Вам необходимо проверить знаки и величины операндов и при необходимости преобразовать операцию в / из +/-, Типичная моя реализация C ++ для этого выглядит так:

//---------------------------------------------------------------------------
arbnum arbnum::operator + (const arbnum &x)
{
arbnum c;
// you can skip this if you do not have NaN or Inf support
// this just handles cases like adding inf or NaN or zero
if (  isnan() ) return *this;
if (x.isnan() ) { c.nan(); return c; }
if (  iszero()) { c=x; return c; }
if (x.iszero()) return *this;
if (  isinf() ) { if (x.isinf()) { if (sig==x.sig) return *this;
c.nan(); return c; } return *this; }
if (x.isinf()) { c.inf(); return c; }
// this compares the sign bits if both signs are the same it is addition
if (sig*x.sig>0) { c.add(x,this[0]); c.sig=sig; }
// if not
else{
// compare absolute values (magnitudes)
if (c.geq(this[0],x)) // |this| >= |x| ... return (this-x)
{
c.sub(this[0],x);
c.sig=sig;    // use sign of the abs greater operand
}
else    {             // else return (x-this)
c.sub(x,this[0]);
c.sig=x.sig;
}
}
return c;
}
//---------------------------------------------------------------------------
arbnum arbnum::operator - (const arbnum &x)
{
arbnum c;
if (  isnan() ) return *this;
if (x.isnan() ) { c.nan(); return c; }
if (  iszero()) { c=x; c.sig=-x.sig; return c; }
if (x.iszero()) return *this;
if (  isinf() ) { if (x.isinf()) { if (sig!=x.sig) return *this;
c.nan(); return c; } return *this; }
if (x.isinf()) { c.inf(); c.sig=-x.sig;  return c; }
if (x.sig*sig<0) { c.add(x,this[0]); c.sig=sig; }
else{
if (c.geq(this[0],x))
{
c.sub(this[0],x);
c.sig=sig;
}
else    {
c.sub(x,this[0]);
c.sig=-x.sig;
}
}
return c;
}
//---------------------------------------------------------------------------

где:

geq беззнаковое сравнение больше или равно
add без знака +
sub без знака -

деление немного сложнее

увидеть:

Bignum подразделения
аппроксимирующий делитель bignum

Для подразделений вы должны уже реализовать такие вещи, как +,-,*,<<,>> и для некоторых более продвинутых подходов вам нужны даже такие вещи, как: абсолютное сравнение (они нужны вам для +/- тем не мение) , SQR, количество использованных биты обычно разделяются на дробные и целочисленные части.

Наиболее важным является умножение увидеть Быстрое вычисление квадрата потому что это ядро для большинства алгоритмов деления.

спектакль

см. некоторые подсказки BigInteger номера реализации и производительности

преобразование текста

Если ваш номер в ASCII или в BASE=10^n цифры, то это легко, но если вы используете BASE=2^n вместо этого по соображениям производительности необходимо иметь быстрые функции, способные конвертировать между dec а также hex строки, так что вы можете загрузить и распечатать некоторые числа в / из вашего класса. увидеть:

2