Как избежать целочисленного переполнения при использовании функции pow при делении на число?

У меня есть следующее заявление.

d = (pow(a,2*l+1)+1)/(val+1);

Здесь,

  • val, a и l - переменные, не имеющие отношения к вопросу.
  • числитель может превышать диапазон long long int.
  • знаменатель является делителем числителя.

Но окончательный ответ d наверняка будет в диапазоне long long int. Как посчитать d без потери точности? Я бы предпочел ответ без преобразования их в массив и использования умножения и деления в начальной школе.


c++ math integer-overflow integer-arithmetic arithmetic-expressions
person Astitwa Saxena    schedule 12.11.2015    source источник
comment
Вы должны сказать, на какой язык вы ориентируетесь. Я бы предположил, что c или c ++.   -  person t.niese    schedule 12.11.2015
comment
pow для c и c ++ оба возвращают числа с плавающей запятой std :: pow , в зависимости от типа ввода вы получите до long double в качестве вывода, поэтому превышение long long не должно быть проблемой в отношении переполнения, но вы наверняка можете потерять точность , но в зависимости от варианта использования это может быть приемлемо. Если это неприемлемо, вам необходимо использовать такую ​​библиотеку, как GNU GMP.   -  person t.niese    schedule 12.11.2015
comment
Я не могу позволить себе быть неточным. Мой код дает неправильный ответ для вычисления больших чисел, где числитель может достигать 10 ^ 21. Есть ли способ не потерять точность? Принято, что знаменатель всегда будет делить числитель без остатка.   -  person Astitwa Saxena    schedule 12.11.2015
comment
[...]My code gives wrong answer for calculation on large numbers[...] вам нужно объяснить, почему вы получаете или думаете, что получили неправильный результат (например, выполнение == теста с плавающей запятой никогда не будет работать должным образом). В противном случае единственный ответ - нет никакой возможности обойтись без библиотеки с большими числами.   -  person t.niese    schedule 12.11.2015
comment
когда я вычисляю, на что должен отвечать мой код с помощью калькулятора, он не совпадает с выводом, который мой код дает мне для определенного набора значений. хотя разница всего 1 или 2, но не точная, этого достаточно, чтобы дать мне неправильный ответ на мой судья   -  person Astitwa Saxena    schedule 12.11.2015
comment
Я умножаю значение d в желаемом ответе для различных наборов значений val, a и L. Дано, что ответ не превышает long long int range.   -  person Astitwa Saxena    schedule 12.11.2015
comment
Откуда вы знаете, что ваш калькулятор исправен? Когда вы говорите «судья», значит ли это, что вы отправляете это на какое-то соревнование по программированию?   -  person Teepeemm    schedule 13.11.2015
comment
Возможный дубликат Предотвращение переполнения при целочисленном умножении с последующим делением   -  person Fabio says Reinstate Monica    schedule 13.11.2015

Ответы (2)


arrow_upward
0
arrow_downward

У меня сейчас нет времени писать правильный ответ; Я расширю это позже, если у меня будет возможность. Основная идея состоит в том, чтобы использовать алгоритм начальной школы, работая с «цифрами», которые являются степенью знаменателя. Выполните поиск в Google по запросу "умножение Шраге" или найдите ссылки здесь.

person user448810    schedule 12.11.2015
comment
из заголовка связанный с вами алгоритм предназначен для арифметики по модулю, а не для результата деления, или его можно изменить? (лень анализировать, поскольку я все равно подхожу к этим задачам по-разному, но вы должны уточнить, чтобы это не сбивало с толку других) - person Spektre; 13.11.2015

arrow_upward
0
arrow_downward

Я надеюсь, что операнды тоже целые

  1. Я бы использовал мощность в квадрате вместо мощности

    См. Целочисленную степень возведения в квадрат

  2. во время итерации №1

    Каждый раз, когда промежуточный результат кабины и знаменатель делятся на 2, делите их оба, чтобы получить небольшой результат и не потерять точность или правильность результата. Таким образом, каждый раз, когда бит LSB как подрезультата, так и знаменателя равен нулю, сдвигается вправо на 1 бит.

person Spektre    schedule 13.11.2015