Умножение длинных чисел

289

28 октября 2017, 17:19

Интересует не столько решение, сколько причина по которой программа выводит неверный результат

uint64_t temp = 15482202590115775738;
uint64_t temp2 = 2* temp;
std::cout<< temp2;

Результат выводится неверно. (Запускаю на 64х разрядном компиляторе)

Answer 1

Запустил. Получил 12517661106521999860.

И что значит "неверный результат"? А какой результат вы ожидали?

В языках С и С++ беззнаковый тип uint64_t реализует арифметику по модулю 264 = 18446744073709551616 = UINT64_MAX + 1.

Математически 15482202590115775738 * 2 дает 30964405180231551476, что превышает 264 и по модулю 264 равно 12517661106521999860.

Именно это число и выводит ваша программа. Все правильно.

Однако отдельно стоить заметить, что бессуффиксные целые литералы в С и С++ всегда имеют знаковый тип. И если литерал не помещается в самый большой знаковый тип long long и компилятор не хочет использовать какой-нибудь расширенный тип, то программа является некорректной (см. комментарий @jfs). На вашей платформе, я подозреваю, тип long long является 64-битным. Тогда правильно: 15482202590115775738u

Answer 2

Как-то мне тоже понадобилась длинная арифметика. Но использовать GMP было нельзя, так как длинная арифметика нужна была для микроконтроллеров без операционной системы и кучи. Пришлось написать свою библиотеку С++ шаблонов для работы с длинными целыми числами, которая не использует кучу. Вот ссылка:

https://sourceforge.net/projects/muntl/?source=frontpage&position=6

Там в архиве есть и описание на русском языке.