переполнение при умножении в C++

-3

В моем коде я пытаюсь умножить два числа. Алгоритм прост как (k) * (k-1)^nI сохранил произведение (k-1)^n в переменной p1, а затем i умножьте его на k.For n = 10, k = 10 (k-1)^n-1 должно быть 387420489, и я получил это в переменной p1, но при умножении его на k, я получаю отрицательное число. Я использовал modulous, но вместо 3874208490, я получаю другое большое положительное число. Каков правильный подход?переполнение при умножении в C++

#include <iostream> 

using namespace std; 

typedef long long ll; 

ll big = 1000000000 + 7; 

ll multiply(ll a, ll b) 
{ 
    ll ans = 1; 
    for (int i = 1; i <= b; i++) 
     ans = ans * a; 
    return ans % big; 
} 

int main() 
{ 
    int t; 
    scanf("%d", &t); 
    while (t--) 
    { 
     ll n, k; 
     cin >> n >> k; 
     ll p1 = multiply(k - 1, n - 1); 
     cout << p1 << endl; // this gives correct value 
     ll p2 = (k % big) * (p1 % big); 
     cout << ((p2 + big) % big) % big << endl; 
    } 
}

источник

2016-04-05 satyajeet jha

Пожалуйста, используйте правильный отступ – MIbrah

'я использовал modulous' - использовать средства проверки орфографии и модуль чаще. – greybeard

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

Что такое ll тип? Если это всего лишь int (и я уверен, что это так), он переполняется, потому что 32-разрядный тип подписи не может хранить значения больше (2^31) -1, что приблизительно равно 2 * 10^9. Вы можете использовать long long int, чтобы он работал, тогда ваш код будет работать с результатами менее 2^63.

источник

2016-04-05 21:45:52 Victor

Я предполагал, что это был typedef из 'long long'. –

@Victor длинный длинный –

@satya проверить с этим типом вы можете прочитать номер 10 000 000 000, а затем записать его обратно. Он ведет себя так же, как 32-разрядный тип подписи. – Victor

Не удивительно, что вы получаете переполнение. Я подключен ваше уравнение в Wolfram Alpha, фиксируя п на 10 и итерацию по к от 0 до 100.

Кривого получает очень вертикальный, очень быстро примерно к = 80.

10^21 требует 70 двоичных разрядов чтобы представлять его, и у вас есть только 63 в длинном длинном.

Вам нужно будет решить, каковы пределы параметров этого алгоритма и соответствующие типы данных. Может быть, двойник будет более подходящим?

link to plot is here

источник

2016-04-05 23:10:57

переполнение при умножении в C++

ответ

Смежные вопросы