Мне нужно вычислить выражение, которое выглядит следующим образом:,
A*B - C*D
где их типы: signed long long int A, B, C, D;
Каждое число может быть очень большим (не выходя за пределы его типа). Хотя A*B
может вызвать переполнение, в то же время выражение A*B - C*D
может быть очень маленьким. Как я могу вычислить это правильно?
Например:, MAX * MAX - (MAX - 1) * (MAX + 1) == 1
где MAX = LLONG_MAX - n
и n - некоторое натуральное число.
c++
c
integer-overflow
NGix
источник
источник
A - C
может переполниться. Это вопрос, который стоит рассмотреть, или вы знаете, что это не произойдет с вашими данными?Ответы:
Это кажется слишком тривиальным, я думаю. Но
A*B
тот, который может переполниться.Вы могли бы сделать следующее, не теряя точности
Это разложение может быть сделано в дальнейшем .
Как отметил @Gian, во время операции вычитания может потребоваться осторожность, если тип длинный без знака.
Например, в случае, если у вас есть вопрос, это займет всего одну итерацию,
источник
C*D
A,B,C,D
хотя бы один из них отрицательный? Не будетE
илиF
будет еще больше тогда?Самое простое и наиболее общее решение состоит в том, чтобы использовать представление, которое не может переполниться, либо с помощью библиотеки длинных целых чисел (например, http://gmplib.org/ ), либо с помощью представления структуры или массива и реализации своего рода длинного умножения ( т.е. разделение каждого числа на две 32-битные половинки и выполнение умножения, как показано ниже:
Предполагая, что конечный результат умещается в 64 бита, вам на самом деле не нужно большинство битов R3 и ни одного из R4
источник
Обратите внимание, что это не является стандартным, поскольку оно основано на переполнении со знаком. (GCC имеет флаги компилятора, которые позволяют это.)
Но если вы просто выполните все вычисления
long long
, результат применения формулы напрямую:(A * B - C * D)
будет точным, если правильный результат вписывается вlong long
.Вот обходной путь, который опирается только на определяемое реализацией поведение приведения целого числа без знака к целому числу со знаком. Но сегодня можно ожидать, что это сработает практически во всех системах.
Это
unsigned long long
приводит к тому, что стандарт переполнения гарантирует, что поведение переполнения гарантируется. Возвращение к целому числу со знаком в конце - это часть, определяемая реализацией, но сегодня она будет работать практически во всех средах.Если вам нужно более педантичное решение, я думаю, что вы должны использовать «длинную арифметику»
источник
long long
.Это должно работать (я думаю):
Вот мой вывод:
источник
Вы могли бы рассмотреть вычисление как наибольший общий фактор для всех ваших значений, а затем разделить их на этот коэффициент, прежде чем выполнять арифметические операции, а затем снова умножить. Это предполагает , что такой фактор существует, однако (например, если
A
,B
,C
иD
случается быть относительно простыми, они не будут иметь общий фактор).Точно так же вы могли бы рассмотреть возможность работы с логарифмическими масштабами, но это будет немного страшно, учитывая числовую точность.
источник
long double
доступно. В этом случае может быть достигнут приемлемый уровень точности (и результат может быть округлен).Если результат помещается в long long int, тогда выражение A * BC * D нормально, поскольку оно выполняет арифметический мод 2 ^ 64 и даст правильный результат. Проблема в том, чтобы узнать, подходит ли результат в long long int. Чтобы обнаружить это, вы можете использовать следующий трюк с использованием double:
Проблема этого подхода заключается в том, что вы ограничены точностью мантиссы двойных чисел (54 бита?), Поэтому вам нужно ограничить произведения A * B и C * D до 63 + 54 бита (или, возможно, чуть меньше).
источник
затем
источник
Вы можете записать каждое число в массив, каждый элемент является цифрой и выполнять вычисления в виде полиномов . Возьмите получившийся полином, который является массивом, и вычислите результат, умножив каждый элемент массива на 10 на степень позиции в массиве (первая позиция является наибольшей, а последняя - нулем).
Число
123
может быть выражено как:для которого вы просто создаете массив
[1 2 3]
.Вы делаете это для всех чисел A, B, C и D, а затем умножаете их на полиномы. Получив полученный многочлен, вы просто восстанавливаете число по нему.
источник
Пока
signed long long int
не проведутA*B
, двое из них будут. Таким образом,A*B
можно разложить на три разных показателя степени, подходящих для любого из нихsigned long long int
.То же самое для
C*D
.Следуя прямому пути, вычитание может быть выполнено для каждой пары,
AB_i
аCD_i
также с использованием дополнительного бита переноса (точно 1-битное целое число) для каждой. Поэтому, если мы скажем E = A * BC * D, вы получите что-то вроде:Мы продолжаем, перенося верхнюю половину
E_10
вE_20
(сдвинуть на 32 и добавить, затем стереть верхнюю половинуE_10
).Теперь вы можете избавиться от бита для переноса
E_11
, добавив его с нужным знаком (полученным из части без переноса) вE_20
. Если это вызывает переполнение, результат не будет соответствовать.E_10
теперь достаточно места, чтобы взять верхнюю половинуE_00
(сдвиг, добавление, стирание) и бит переносаE_01
.E_10
может быть больше теперь снова, поэтому мы повторяем передачуE_20
.В этот момент
E_20
должен стать ноль, иначе результат не будет соответствовать. ВE_10
результате переноса верхняя половина также пуста.Последний шаг - перенести нижнюю половину
E_20
вE_10
снова.Если ожидание, которое
E=A*B+C*D
будет соответствовать ожиданиям, уsigned long long int
нас теперь естьисточник
Если вы знаете, что конечный результат представлен в целочисленном типе, вы можете быстро выполнить этот расчет, используя код ниже. Поскольку в стандарте C указано, что арифметика без знака является арифметикой по модулю и не переполняется, вы можете использовать тип без знака для выполнения вычислений.
В следующем коде предполагается, что существует неподписанный тип такой же ширины, и что подписанный тип использует все битовые шаблоны для представления значений (нет представлений ловушек, минимум подписанного типа является отрицательным от половины модуля беззнакового типа). Если это не выполняется в реализации C, для этого можно внести простые корректировки в процедуру ConvertToSigned.
Следующее использует
signed char
иunsigned char
для демонстрации кода. Для вашей реализации измените определениеSigned
наtypedef signed long long int Signed;
и определениеUnsigned
наtypedef unsigned long long int Unsigned;
.источник
Вы можете попробовать разбить уравнение на более мелкие компоненты, которые не переполняются.
Если компоненты все еще переполнены, вы можете рекурсивно разбить их на более мелкие компоненты, а затем рекомбинировать.
источник
K
аJ
почему быN
и нетM
. Кроме того, я думаю, что вы разбиваете уравнение на большие части. Так как ваш шаг 3 такой же, как вопрос ОП, за исключением более сложного(AK-CJ)
->(AB-CD)
Возможно, я не охватил все граничные случаи и не провел тщательного тестирования, но это реализует технику, которую я помню, использовал в 80-х годах при попытке выполнить 32-разрядное целочисленное вычисление на 16-разрядном процессоре. По сути, вы разбиваете 32 бита на два 16-битных блока и работаете с ними отдельно.
Печать:
который выглядит для меня, как будто он работает.
Бьюсь об заклад, я пропустил некоторые тонкости, такие как наблюдение за переполнением знака и т. Д., Но я думаю, что суть есть.
источник
Для полноты картины, поскольку никто не упомянул об этом, некоторые компиляторы (например, GCC) фактически предоставляют вам 128-битное целое число в настоящее время.
Таким образом, простое решение может быть:
источник
AB-CD = (AB-CD) * AC / AC = (B/C-D/A)*A*C
, НиB/C
ниD/A
может переполниться, поэтому не рассчитать(B/C-D/A)
первый. Поскольку окончательный результат не будет переполнен в соответствии с вашим определением, вы можете безопасно выполнить оставшиеся умножения и рассчитать,(B/C-D/A)*A*C
какой результат является требуемым.Обратите внимание: если ваш ввод также может быть очень маленьким ,
B/C
илиD/A
может переполниться. Если это возможно, могут потребоваться более сложные манипуляции в соответствии с входной проверкой.источник
Выберите
K = a big number
(напримерK = A - sqrt(A)
)Зачем?
Обратите внимание, что, поскольку A, B, C и D являются большими числами, следовательно,
A-C
иB-D
являются маленькими числами.источник
A-C+B-D
мало. Поскольку A, B, C и D - большие числа, таким образом, AC - небольшое число.A - sqrt(A)
:)