Muszę obliczyć wyrażenie, które wygląda następująco:,
A*B - C*D
gdzie ich typy to: signed long long int A, B, C, D;
Każda liczba może być naprawdę duża (nie przepełniać swojego typu). Chociaż A*B
może spowodować przepełnienie, w tym samym czasie wyrażenieA*B - C*D
może być naprawdę małe. Jak mogę to poprawnie obliczyć?
Na przykład:, MAX * MAX - (MAX - 1) * (MAX + 1) == 1
gdzie in MAX = LLONG_MAX - n
- jakaś liczba naturalna.
c++
c
integer-overflow
NGix
źródło
źródło
A - C
może się przepełnić. Czy jest to kwestia do rozważenia, czy wiesz, że nie stanie się to z Twoimi danymi?Odpowiedzi:
Wydaje mi się, że to zbyt trywialne. Ale
A*B
to ten, który może się przepełnić.Możesz wykonać następujące czynności bez utraty precyzji
Ten rozkład można przeprowadzić dalej .
Jak zauważył @Gian, może być konieczne zachowanie ostrożności podczas operacji odejmowania, jeśli typ jest długi bez znaku.
Na przykład w przypadku, którego dotyczy pytanie, wystarczy jedna iteracja,
źródło
C*D
A,B,C,D
są negatywne? Nie będzieE
lubF
będzie jeszcze większa wtedy?Najprostszym i najbardziej ogólnym rozwiązaniem jest użycie reprezentacji, która nie może się przepełnić, albo za pomocą biblioteki długich liczb całkowitych (np. Http://gmplib.org/ ), albo reprezentując za pomocą struktury lub tablicy i implementując rodzaj długiego mnożenia ( tj. rozdzielenie każdej liczby na dwie 32-bitowe połowy i wykonanie mnożenia jak poniżej:
Zakładając, że wynik końcowy mieści się w 64 bitach, tak naprawdę nie potrzebujesz większości bitów R3 i żadnego R4
źródło
Zauważ, że nie jest to standardowe, ponieważ opiera się na zawijanym przepełnieniu ze znakiem. (GCC ma flagi kompilatora, które to umożliwiają.)
Ale jeśli wykonasz wszystkie obliczenia w programie
long long
, wynik bezpośredniego zastosowania wzoru:(A * B - C * D)
będzie dokładny, o ile poprawny wynik będzie pasował do along long
.Oto obejście, które polega tylko na zachowaniu zdefiniowanym przez implementację polegającym na rzutowaniu liczby całkowitej bez znaku na liczbę całkowitą ze znakiem. Ale dziś można oczekiwać, że zadziała to na prawie każdym systemie.
To rzutuje dane wejściowe do
unsigned long long
miejsca, w którym zachowanie przepełnienia jest gwarantowane jako zawijane przez standard. Rzutowanie z powrotem na podpisaną liczbę całkowitą na końcu jest częścią zdefiniowaną przez implementację, ale dziś będzie działać w prawie wszystkich środowiskach.Jeśli potrzebujesz bardziej pedantycznego rozwiązania, myślę, że musisz użyć „długiej arytmetyki”
źródło
long long
.To powinno działać (myślę):
Oto moje wyprowadzenie:
źródło
Możesz rozważyć obliczenie największego wspólnego współczynnika dla wszystkich wartości, a następnie podzielenie ich przez ten współczynnik przed wykonaniem operacji arytmetycznych, a następnie ponowne pomnożenie. Zakłada się, że taki czynnik istnieje jednak (na przykład w przypadku
A
,B
,C
iD
stało się względnie pierwsze, nie będą mieć wspólny czynnik).Podobnie możesz rozważyć pracę na skalach logarytmicznych, ale będzie to trochę przerażające, z zastrzeżeniem dokładności numerycznej.
źródło
long double
jest dostępne. W takim przypadku można osiągnąć akceptowalny poziom dokładności (a wynik można zaokrąglić).Jeśli wynik mieści się w długim długim int, to wyrażenie A * BC * D jest w porządku, ponieważ wykonuje arytmetyczną mod 2 ^ 64 i da prawidłowy wynik. Problem polega na tym, aby wiedzieć, czy wynik mieści się w długiej, długiej int. Aby to wykryć, możesz użyć następującej sztuczki, używając podwójnych:
Problem z tym podejściem polega na tym, że jesteś ograniczony precyzją mantysy podwójnych (54 bity?), Więc musisz ograniczyć iloczyn A * B i C * D do 63 + 54 bitów (lub prawdopodobnie trochę mniej).
źródło
następnie
źródło
Możesz zapisać każdą liczbę w tablicy, przy czym każdy element jest cyfrą i wykonywać obliczenia jako wielomiany . Weź wynikowy wielomian, który jest tablicą, i oblicz wynik, mnożąc każdy element tablicy przez 10 do potęgi pozycji w tablicy (pierwsza pozycja jest największa, a ostatnia zero).
Liczbę
123
można wyrazić jako:dla którego po prostu tworzysz tablicę
[1 2 3]
.Robisz to dla wszystkich liczb A, B, C i D, a następnie mnożysz je jako wielomiany. Gdy masz wynikowy wielomian, po prostu rekonstruujesz z niego liczbę.
źródło
Podczas gdy jeden
signed long long int
nie wytrzymaA*B
, dwóch z nich to zrobi.A*B
Można więc rozłożyć na trzy wyrażenia o różnych wykładnikach, z których każdy pasuje do jednegosigned long long int
.To samo dotyczy
C*D
.Idąc prostą drogą, można było dokonać subrakcji na każdej parze
AB_i
iCD_i
podobnie, używając dodatkowego bitu przenoszenia (dokładnie 1-bitowej liczby całkowitej) dla każdej. Więc jeśli powiemy E = A * BC * D, otrzymasz coś takiego:Kontynuujemy, przenosząc górną połowę
E_10
doE_20
(przesuń o 32 i dodaj, a następnie usuń górną połowęE_10
).Teraz możesz pozbyć się bitu przenoszonego
E_11
, dodając go z odpowiednim znakiem (uzyskanym z części nienoszonej) doE_20
. Jeśli spowoduje to przepełnienie, wynik również nie będzie pasował.E_10
teraz ma wystarczająco dużo miejsca, aby wziąć górną połowę zE_00
(przesuń, dodaj, wymaż) i przenoszoną częśćE_01
.E_10
może być teraz ponownie większy, więc powtarzamy transfer doE_20
.W tym momencie
E_20
musi wynosić zero, w przeciwnym razie wynik nie będzie pasował. W górnej połowieE_10
jest również pusta w wyniku przeniesienia.Ostatnim krokiem jest ponowne przeniesienie dolnej połowy
E_20
doE_10
.Jeśli oczekiwanie,
E=A*B+C*D
które pasowałoby dosigned long long int
blokad, mamy terazźródło
Jeśli wiesz, że wynik końcowy można przedstawić w typie liczby całkowitej, możesz szybko wykonać to obliczenie, korzystając z poniższego kodu. Ponieważ standard C określa, że arytmetyka bez znaku jest arytmetyką modulo i nie powoduje przepełnienia, można użyć typu bez znaku do wykonania obliczeń.
Poniższy kod zakłada, że istnieje typ bez znaku o tej samej szerokości i że typ ze znakiem wykorzystuje wszystkie wzorce bitowe do reprezentowania wartości (bez reprezentacji pułapek, minimum typu ze znakiem jest ujemną wartością połowy modułu typu bez znaku). Jeśli tak się nie stanie w implementacji C, można w tym celu wprowadzić proste poprawki w procedurze ConvertToSigned.
Poniższe zastosowania
signed char
iunsigned char
zademonstrowanie kodu. Na potrzeby swojej implementacji zmień definicjęSigned
totypedef signed long long int Signed;
i definicjęUnsigned
totypedef unsigned long long int Unsigned;
.źródło
Możesz spróbować rozbić równanie na mniejsze komponenty, które się nie przepełniają.
Jeśli komponenty nadal się przepełniają, możesz je rekurencyjnie podzielić na mniejsze komponenty, a następnie ponownie połączyć.
źródło
K
iJ
, dlaczego nieN
iM
. Myślę też, że rozbijasz równanie na większe części. Ponieważ twój krok 3 jest taki sam jak pytanie OP, z wyjątkiem bardziej skomplikowanych(AK-CJ)
->(AB-CD)
Być może nie omówiłem wszystkich przypadków skrajnych, ani nie przetestowałem tego rygorystycznie, ale implementuje to technikę, którą pamiętam z lat 80., kiedy próbowałem wykonywać 32-bitowe obliczenia liczb całkowitych na 16-bitowym procesorze. Zasadniczo dzielisz 32 bity na dwie 16-bitowe jednostki i pracujesz z nimi osobno.
Wydruki:
co wydaje mi się, że działa.
Założę się, że przegapiłem niektóre subtelności, takie jak obserwowanie przepełnienia znaków itp., Ale myślę, że istota jest tam.
źródło
Ze względu na kompletność, ponieważ nikt o tym nie wspomniał, niektóre kompilatory (np. GCC) obecnie dostarczają 128-bitową liczbę całkowitą.
Zatem prostym rozwiązaniem mogłoby być:
źródło
AB-CD = (AB-CD) * AC / AC = (B/C-D/A)*A*C
. Ani,B/C
ani nieD/A
mogą się przepełniać, więc(B/C-D/A)
najpierw oblicz . Ponieważ ostateczny wynik nie przepełni się zgodnie z twoją definicją, możesz bezpiecznie wykonać pozostałe mnożenia i obliczyć,(B/C-D/A)*A*C
który wynik jest wymagany.Uwaga, jeśli twój wkład może być również bardzo mały ,
B/C
lubD/A
może się przepełnić. Jeśli to możliwe, mogą być wymagane bardziej złożone manipulacje zgodnie z kontrolą wejściową.źródło
Wybierz
K = a big number
(np.K = A - sqrt(A)
)Czemu?
Zauważ, że ponieważ A, B, C i D są dużymi liczbami,
A-C
a więc iB-D
są małymi liczbami.źródło
A-C+B-D
jest mała liczba. Ponieważ A, B, C i D to duże liczby, więc AC to mała liczba.A - sqrt(A)