усечения при использовании неподписанных долго долго

Question

Это сообщение связано с моего предыдущего поста:

Weird data corruption in C++ code for unsigned long long

Проблема, поднятая в этой должности будет решена, но теперь я столкнулся другой вопрос, связанный с усечением неподписанных долгое длинный тип данных. Это происходит в функции iPow() для повышения базы до степени экспоненты. Исходный код для iPow() разделяли в моем предыдущем посте, но воспроизводится ниже для удобства:

unsigned long long userinput::iPow(){ 

     while(this->revValue) 
     { 
       if (this->revValue & 1ULL) 
       { 
         this->result *= this->value; 
       } 
       this->revValue >>= 1; 
       this->value *= this->value; 
     } 
     return this->result; 
} 

В приведенной выше функции, значение, revValue, и результат все без знака долго долго. Исходный код для объявления класса был разделен в предыдущем посте, но воспроизводится ниже для удобства:

class userinput{ 

     public: 
       userinput(unsigned long long); 
       ~userinput(); 
       unsigned long long reverse(); 
       unsigned long long raise_to_reverse(); 

     private: 
       userinput(); 
       userinput(const userinput&); 
       void operator=(const userinput&); 

     private: 
       unsigned long long value; 
       unsigned int numDigits; 
       unsigned long long revValue; 
       unsigned long long result; 

     private: 
       void calc_numDigits(); 
       unsigned long long iPow(); 


}; 

Я воспроизводящий ниже выходного GdB для значений this-> значение, this-> revValue, и этом-> результат для каждой итерации цикла в iPow():

Enter a number between 0 and 99999 (exlusive): 
1234 

Breakpoint 1, userinput::iPow (this=0x7fffffffde10) at program.cpp:49 
49  while(this->revValue) 
Missing separate debuginfos, use: debuginfo-install glibc-2.15-56.fc17.x86_64 libgcc-4.7.0-5.fc17.x86_64 libstdc++-4.7.0-5.fc17.x86_64 
(gdb) p this->revValue 
$1 = 4321 
(gdb) n 
51   if (this->revValue & 1ULL) 
(gdb) p this->revValue & 1ULL 
$2 = 1 
(gdb) n 
53    this->result *= this->value; 
(gdb) n 
55   this->revValue >>= 1; 
(gdb) p this->result 
$3 = 1234 
(gdb) n 
56   this->value *= this->value; 
(gdb) p this->revValue 
$4 = 2160 
(gdb) n 
49  while(this->revValue) 
(gdb) p this->value 
$5 = 1522756 
(gdb) n 
51   if (this->revValue & 1ULL) 
(gdb) p this->revValue & 1ULL 
$6 = 0 
(gdb) n 
55   this->revValue >>= 1; 
(gdb) n 
56   this->value *= this->value; 
(gdb) p this->revValue 
$7 = 1080 
(gdb) n 
49  while(this->revValue) 
(gdb) p this->value 
$8 = 2318785835536 
(gdb) n 
51   if (this->revValue & 1ULL) 
(gdb) p this->revValue & 1ULL 
$9 = 0 
(gdb) n 
55   this->revValue >>= 1; 
(gdb) n 
56   this->value *= this->value; 
(gdb) p this->revValue 
$10 = 540 
(gdb) n 
49  while(this->revValue) 
(gdb) p this->value 
$11 = 3022197894083133696 
(gdb) n 
51   if (this->revValue & 1ULL) 
(gdb) p this->revValue & 1ULL 
$12 = 0 
(gdb) n 
55   this->revValue >>= 1; 
(gdb) n 
56   this->value *= this->value; 
(gdb) p this->revValue 
$13 = 270 
(gdb) n 
49  while(this->revValue) 
(gdb) p this->value 
$14 = 16658586050838462464 
(gdb) n 
51   if (this->revValue & 1ULL) 
(gdb) p this->revValue & 1ULL 
$15 = 0 
(gdb) n 
55   this->revValue >>= 1; 
(gdb) n 
56   this->value *= this->value; 
(gdb) p this->revValue 
$16 = 135 
(gdb) n 
49  while(this->revValue) 
(gdb) p this->value 
$17 = 8477297326610710528 
(gdb) n 
51   if (this->revValue & 1ULL) 
(gdb) p this->revValue & 1ULL 
$18 = 1 
(gdb) n 
53    this->result *= this->value; 
(gdb) n 
55   this->revValue >>= 1; 
(gdb) p this->result 
$19 = 1681011244301025280 
(gdb) n 
56   this->value *= this->value; 
(gdb) p this->revValue 
$20 = 67 
(gdb) n 
49  while(this->revValue) 
(gdb) p this->value 
$21 = 0 
(gdb) n 
51   if (this->revValue & 1ULL) 
(gdb) p this->revValue & 1ULL 
$22 = 1 
(gdb) n 
53    this->result *= this->value; 
(gdb) n 
55   this->revValue >>= 1; 
(gdb) p this->result 
$23 = 0 
(gdb) n 
56   this->value *= this->value; 
(gdb) p this->revValue 
$24 = 33 
(gdb) n 
49  while(this->revValue) 
(gdb) p this->value 
$25 = 0 
(gdb) 

Как видно на выходе Gdb, максимальное значение достигается этом-> значение $ 17 = 8477297326610710528, после чего значение усекает к ноль в следующей итерации. Следовательно, значение this-> result также обрезается до нуля из-за логики цикла.

Есть ли тип данных, который я могу использовать для печати всех цифр результата iPow(), учитывая диапазон 0-99999 (эксклюзивный)? Или, если нет допустимого типа данных, какую альтернативу я могу использовать для печати всех цифр результата iPow() в stdout?

Пожалуйста, поделитесь своими мыслями.

ТИА Винод

Answer 1

Существует переполнения в вычислениях. unsigned long long имеет 64 бита в вашем случае. В спецификации C++ упоминается, что умножение беззнаковых чисел использует модульную арифметику. То есть результат умножения верен до кратного значения 2 .

В вашем случае:

1681011244301025280 является 0x175426D200000000 (преобразовать в шестнадцатеричное для удобства)

Когда умноженное на себя:

0x175426D200000000 * 0x175426D200000000 = 
(0x175426D2 * 2^32) * (0x175426D2 * 2^32) = 
(0x175426D2 * 0x175426D2) * (2^32 * 2^32) = 
(whatever) * 2^64) ≡ 0 (modulo 2^64) 

Так что вполне понятно, почему ваш большое число, умноженное на себя дает 0, когда 64 бит недостаточно для хранения результата.

Чтобы исключить возможность переполнения, используйте тип bigint (bigint - это ключевое слово для поиска в Интернете).

Вопрос рекомендации для библиотеки bigint является, например, here.