0

Пишу класс для больших чисел длиной до 2^512. Использую массив unsigned __int64. Сложение чисел происходит неадекватно, за счёт переменной c. Алгоритм брал из книги. Можете подсказать рабочий алгоритм?

class BigInt {
public:
    unsigned __int64 number[8];

    BigInt() 
    {
        for (int i = 0; i < 8; i++) 
        {
            number[i] = 0;
        }
    }

    const BigInt operator+(const BigInt& rv) const 
    {
        BigInt res;
        unsigned __int64 c = 0, t = 0;
        for (int i = 0; i < 8; i++) 
        {
            t = number[i] + rv.number[i] + c;
            c = t % LLONG_MAX;
            res.number[i] = c;
        }
        res.number[7] = t;
        return res;
    }
};
4
  • Что значит «неадекватно за счёт переменной c»? На каких входных данных получается неправильный ответ?
    – VladD
    14 апр 2017 в 19:32
  • Да, переменная t должна быть большей разрядности, чем элементы number. Понятно, почему?
    – VladD
    14 апр 2017 в 19:34
  • @VladD понятно, но суть в том, что даже на малых значениях не работает. 14 апр 2017 в 19:36
  • А можно пример, на каких?
    – VladD
    14 апр 2017 в 20:10

2 ответа 2

2

Использование операций % и / тут совершенно ни к чему. Это стрельба из пушки по воробьям, не говоря уже том, что такие вычисления надо производить в типе, более широком чем ваш unsigned __int64. А в вашем распоряжении такого типа нет.

Ни к чему тут также привязка к конкретному типу через константы вроде LLONG_MAX (да и почему вдруг используется знаковый максимум?).

Не забывайте, что величина c может быть только 0 или 1.

Вот как это может выглядеть

BigInt operator +(const BigInt& rv) const 
{
    BigInt res;
    unsigned __int64 carry = 0;
    for (int i = 0; i < 8; i++) 
    {
        res.number[i] = number[i] + rv.number[i] + carry;
        carry = carry ? res.number[i] <= number[i] : res.number[i] < number[i];
    }
    return res;
}
5
  • И имеет смысл переменную c переименовать в carry, чтобы стало ясно, почему 0 или 1.
    – VladD
    14 апр 2017 в 23:16
  • @AnT а как бы вы реализовали умножение? Алгоритм из книги опять же не работает, либо я что-то не так в нём понимаю. 15 апр 2017 в 10:35
  • @AnT кстати ваша реализация не работает 111111111111111111111+111111111111111111111=303775478148512670606 . Вы считаете, что такую операцию с использованием ulonglong невозможно реализовать? 15 апр 2017 в 11:46
  • @Сергей: Не совсем понимаю, каком образом вы смогли получили такой результат при помощи моей реализации. Чтобы выполнить такое сложение и посмотреть на результат необходимо еще определенное количество кода (перевод из/в десятичное представление). Почему вы решили, что "не работает" именно моя реализация, а не ваш остальной код? 15 апр 2017 в 14:24
  • @AnT, простите, не подумал об этом. Думал это конечный результат. Всё равно проблемы с пониманием. Может сможете посоветовать какие-нибудь книги, статьи, алгоритмы? Как можно число, записывающееся в массив ulonglong переводить в 10 и из10 системы? 16 апр 2017 в 9:22
1

В вашем коде есть по крайней мере одна грубая ошибка: вместо

c = t % LLONG_MAX;
res.number[i] = c;

нужно

c = t / LLONG_MAX;
res.number[i] = t % LLONG_MAX;

Соответственно, финальный res.number[7] = t; не нужен.

Кроме того, тип t должен быть шире, чем тип элементов number.

2
  • Во-первых, почему вдруг LLONG_MAX, а не ULLONG_MAX? Во-вторых, если планируется использовать всю ширину типа, то делить надо было бы на ULLONG_MAX + 1. (Не забываем про +1). А тут уже станвится ясно, что реализация хромает вовсю. 14 апр 2017 в 22:51
  • @AnT: Тьфу ты, и правда. Там +1. Ну для реализации нужно хранить по-хорошему массив unt32_t, и вычислять в uint64_t, да.
    – VladD
    14 апр 2017 в 23:15

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.