Арифметика на нестандартной основе

Я пытаюсь преобразовать мой произвольное число точности класс, чтобы иметь возможность использовать цифры, которые не просто 8 бит на цифру. Я наткнулся на странную проблему: я могу использовать uint16_t
для моего базового типа цифры, но не uint32_t, Мой код вернет плохие результаты. Пример, который я использовал, чтобы найти что-то пошло не так 0x1111111111111111 * 0x1111111111111111, который должен быть0x123456789abcdf00fedcba987654321, Тем не менее, я получаю 0x123456789abcdf0fedcba987654321,

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

Вот соответствующий код:

typedef uint32_t                          digit;            // original code uses uint8_t; uint16_t works too
typedef uint64_t                          double_digit;     // int type to hold overflow values

typedef std::deque <digit>                base;

const digit NEG1 = -1;                    // uint8_t -> 255, uint32_t -> 4294967295
const digit BITS = sizeof(digit) << 3;    // sizeof gives the number of bytes, so multiply that by 8 to get the number of bits
const digit HIGH_BIT = 1 << (BITS - 1);   // uint8_t -> 128

// left bit shift. sign is maintained
integer operator<<(uint64_t shift){
if (!*this || !shift)
return *this;
base out = digits;
for(uint64_t i = 0; i < (shift / BITS); i++)
out.push_back(0);
shift %= BITS;
if (shift){
out.push_back(0);
return integer(out, _sign) >> (BITS - shift);
}
return integer(out, _sign);
}

// right bit shift. sign is maintained
integer operator>>(uint64_t shift){
if (shift >= bits())
return integer(0);
base out = digits;
for(uint64_t i = 0; i < (shift / BITS); i++)
out.pop_back();
shift %= BITS;
if (shift){
base v;
for(d_size i = out.size() - 1; i != 0; i--)
v.push_front(((out[i] >> shift) | (out[i - 1] << (BITS - shift))) & NEG1);
v.push_front(out[0] >> shift);
out = v;
}
return integer(out, _sign);
}

// operator+ calls this
integer add(integer & lhs, integer & rhs){
base out;
base::reverse_iterator i = lhs.digits.rbegin(), j = rhs.digits.rbegin();
bool carry = false;
double_digit sum;
for(; ((i != lhs.digits.rend()) && (j != rhs.digits.rend())); i++, j++){
sum = *i + *j + carry;
out.push_front(sum);
carry = (sum > NEG1);
}
for(; i != lhs.digits.rend(); i++){
sum = *i + carry;
out.push_front(sum);
carry = (sum > NEG1);
}
for(; j != rhs.digits.rend(); j++){
sum = *j + carry;
out.push_front(sum);
carry = (sum > NEG1);
}
if (carry)
out.push_front(1);
return integer(out);
}

// operator* calls this
// Long multiplication
integer long_mult(integer & lhs, integer & rhs){
unsigned int zeros = 0;
integer row, out = 0;
for(base::reverse_iterator i = lhs.digits.rbegin(); i != lhs.digits.rend(); i++){
row.digits = base(zeros++, 0); // zeros on the right hand side
digit carry = 0;
for(base::reverse_iterator j = rhs.digits.rbegin(); j != rhs.digits.rend(); j++){
double_digit prod = (double_digit(*i) * double_digit(*j)) + carry;// multiply through
row.digits.push_front(prod & NEG1);
carry = prod >> BITS;
}
if (carry)
row.digits.push_front(carry);
out = add(out, row);
}
return out;
}

Есть что-то очевидное, что я пропустил, что может привести к неправильным расчетам? Я слишком долго смотрел на этот код за один раз.

Полный модифицированный код Вот.

РЕДАКТИРОВАТЬ: Я проверил код на ideone, и он возвращает правильное значение для этого расчета, но мой компьютер все еще не делает. Есть ли хорошее объяснение этому?

0

Решение

Проблема, по-видимому, связана с непреднамеренным чрезмерным смещением вправо. Вы упоминаете, что ваш идеальный пост не воспроизводит проблему. Во время тестирования я заметил, что в вашем посте ideone тип цифры был по-прежнему установлен на 16-разрядный. В тот момент, когда я изменил это значение на 32-битное (чтобы отразить фрагмент кода SO) и попытался скомпилировать в gcc, я получил кучу предупреждений о чрезмерном смещении вправо. Запуск программы привел к бесконечному циклу, который в сочетании с предупреждениями о сдвиге вправо и тем фактом, что на вашей платформе происходит другое поведение, настоятельно предполагает наличие неопределенного поведения.

В частности, есть места, где вы получаете несоответствие размера битов между типами int (т. Е. У вас еще есть несколько кусков кода для обновления).

Похоже, что создатель проблемы настроен из ZZ. Здесь у вас есть целочисленный тип, заданный Z, и целочисленный тип, заданный base :: value_type. Не гарантируется, что эти два числа имеют одинаковое количество битов, поэтому код сдвига битов и маска битов в этой функции работают неправильно, когда происходит несовпадение битов. И происходит несовпадение для нескольких экземпляров этого шаблона, которые встречаются в вашем коде ideone, когда uint32_t является типом цифр (по крайней мере, в моей среде).

Редактировать: Подтверждение того, что чрезмерное смещение вправо не определено в соответствии со стандартом: Ссылка: SO Post, см. принятый ответ, который цитирует стандарт.

(C ++ 98 §5.8 / 1) утверждает, что:
Поведение
не определено, если правый операнд отрицательный, или больше или равно
на длину в битах повышенного левого операнда.

2

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

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

По вопросам рекламы [email protected]