Dopuszczalny zakres wartości w zmiennych przekazywanych do funkcji
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

Dopuszczalny zakres wartości w zmiennych przekazywanych do funkcji

AutorWiadomość
Temat założony przez niniejszego użytkownika
Dopuszczalny zakres wartości w zmiennych przekazywanych do funkcji
» 2020-11-18 18:43:24

Czysto teoretycznie napisałem prostą funkcję, która nie działa prawidłowo

C/C++
#include <iostream>
bool a_b_lessthan_c_d( int a, int b, int c, int d ) {
    return a * b < c * d;
}

int main() {
    std::cout << a_b_lessthan_c_d( 2147483647, 2, 2147483647, 1 ) << std::endl;
    system( "pause" );
    return;
}

Rozumiem, że to przez przekręcenie zmiennej (tak to się nazywa?)
Z drugiej strony gdy się wykorzystuje już istniejącą funkcję raczej powinien nas interesować sam typ (w tym jej pełen zakres), a nie ograniczenia wynikające z ciała funkcji.
W jaki sposób obchodzić się z takimi problemami? Da się takie funkcje udoskonalić, żeby działały na pełnym zakresie wartości (bez uciekania się do dzielenia, nie chcę tracić na precyzji)
Obliczanie przedziału dopuszczalnych wartości i pisanie assertów też raczej dobrym pomysłem nie jest.

Dzięki za każdą sugestię
P-177720
» 2020-11-18 19:50:26
1. Zakres wartości jakie mogą przyjmować zmienne typów podstawowych znajdziesz w kursie:
http://cpp0x.pl/kursy/Kurs-C++​/Poziom-1​/Pojecie-zmiennej-i-podstawowe​-typy-danych​/11

2. Jeżeli chciałbyś mieć 'rozwiązanie', które 'nie ma' ograniczeń, to musiałbyś napisać sobie bibliotekę wykonującą obliczenia na liczbach przekazywanych jako tekst LUB użyć istniejącej biblioteki.
Istnieje np. biblioteka taka jak libtommath, która umożliwia wykonywanie obliczeń liczbach całkowitych o nielimitowanej długości:
https://github.com/libtom​/libtommath

Dokumentację do tej biblioteki możesz sobie wygooglać. Przykład:
http://www.gtoal.com/src/mobi​/clit18/libtommath-0.41/bn.pdf

Jak sobie przeczytasz fragmenty dokumentacji tej biblioteki to zapewne dojdziesz do wniosku, że jest to za trudne i prawdopodobnie zadowolisz się ograniczeniami podstawowych typów danych (i w praktyce będzie to słuszna decyzja, bo rzadko kiedy będziesz miał realne przypadki użycia, w których podstawowe typy danych dla liczb całkowitych okażą się niewystarczające).

Tu masz jeszcze trochę informacji o tej bibliotece:
https://www.libtom.net​/LibTomMath/
P-177721
» 2020-11-18 20:37:13
Dodam jeszcze, że zakres zmiennej typu
int
 bywa różny, więc jeśli chcesz pisać kod, który wymaga konkretnych zakresów wartości, to warto skorzystać z
#include <cstdint>
 i używać odpowiednio typów od
std::int8_t
 do
std::int64_t
. Przy liczbach większych niż 64-bitowe zwykle trzeba albo użyć jakiejś biblioteki, albo samodzielnie poskładać większe inty z tych mniejszych.

Jak sobie przeczytasz fragmenty dokumentacji tej biblioteki to zapewne dojdziesz do wniosku, że jest to za trudne i prawdopodobnie zadowolisz się ograniczeniami podstawowych typów danych
Nie no, bez przesady, to zależy od operacji, które na tych liczbach mają być wykonywane. Najprostszą implementację na stringach można spokojnie napisać nawet po tutejszym kursie. Znając dodawanie, odejmowanie, mnożenie i dzielenie pisemne można spokojnie to zrozumieć i tak to właśnie zaimplementować (chyba nawet na SPOJ-u było takie zadanie). Poza tym, używając wyłącznie choćby takiego
std::uint64_t
 jako "pojemnika na bity", też można spokojnie napisać implementację większych intów w kodzie U2, czyli uzupełnień do dwóch:
  • przy dodawaniu xor składników daje wynik, zaś and przesunięty o jeden daje przeniesienia, których można użyć jako kolejnego składnika sumy, dorzucając tutaj pętlę z odpowiednim warunkiem można dość prosto to napisać, przykład był nawet w tutejszym kursie;
  • odejmowanie w kodzie U2 to tylko dodawanie liczby ujemnej, a do odwrócenia znaku liczby wystarczy jedynie negacja wszystkich bitów i inkrementacja wyniku;
  • żeby pomnożyć dwie liczby, wystarczy brać bity z jednej z nich i dodawać do wyniku drugą, przesuniętą o odpowiednią liczbę bitów w lewo (lub też ją pomijać, jeśli trafimy na zero);
  • dzielenie jest już nieco bardziej zakręcone, ale też do ogarnięcia, znając dzielenie pisemne też można to względnie łatwo napisać, wystarczy najpierw upewnić się, że nie dzielimy przez zero, później przesunąć dzielnik w lewo tak długo, aż pierwsza jedynka zrówna się z pierwszą jedynką w dzielnej, a dalej wykonywać odejmowanie tak samo, jak przy dzieleniu pisemnym i analogicznie obliczać reszty z kolejnych odejmowań, aż do uzyskania ostatecznego wyniku (gdzieś chyba też widziałem jakiś sprytny sposób z przesunięciami bitowymi, ale teraz już tego nie pamiętam).
P-177722
Temat założony przez niniejszego użytkownika
» 2020-11-23 14:35:54
Obawiam się, że pytanie zostało źle zrozumiane :|
Mam pełną świadomość, że są biblioteki do obliczeń na DUŻYCH liczbach (choćby GMP z GNU)
Nie chodzi mi tutaj o obliczenia na liczbach o nieskończonym zakresie, tylko o dobrą praktykę co powinno się robić, żeby zasięg zmiennej nie był ograniczany przez ciało funkcji.

Tzn. w tym przykładzie co podałem teoretycznie jakbyśmy chcieli działać na zmiennych typu int(4bajty)
to maksymalna wartość int(4bajty) = 2147483647 czyli int*int = 4611686014132420609
maksymalna wartość long long(8bajtow) = 9223372036854775807
także wniosek, że w typie long long mieści się iloczyn dwóch intów ( dla ujemnych też można to wykazać)
.. i dalej przedstawiam poprawiony przykład, który obsługuje pełen zakres zmiennych wejściowych.

C/C++
#include <iostream>
bool a_b_lessthan_c_d( int a, int b, int c, int d ) {
    long long ab =( long long ) a *( long long ) b;
    long long cd =( long long ) c *( long long ) d;
    return ab < cd;
}

int main() {
    std::cout << a_b_lessthan_c_d( 2147483647, 2, 2147483647, 1 ) << std::endl;
    system( "pause" );
    return;
}

(Specjalnie nie zmieniałem tutaj nic w deklaracji ani wywołaniu funkcji)
Czy są metody które umożliwiają kontrolę nad tego typu błędami?


P-177735
» 2020-11-23 17:59:07
Czy są metody które umożliwiają kontrolę nad tego typu błędami?
Przekroczenie zakresu zmiennej nie oznacza że w funkcji jest błąd. Funkcja która dosłownie nazywa się a_b_lessthan_c_d powinna wykonywać taką operację w sposób poprawny dla każdego przypadku - inaczej nie ma sensu mieć takiej funkcji. W ogólnym przypadku zwykle wiesz na jakich rzędach wielkości operujesz i masz stosowny margines bezpieczeństwa. Pisanie kodu mission-critical jest skomplikowane i w takiej sytuacji miałbyś dowód poprawności dla każdej krytycznej procedury. Nie ma sensu tak postępować w każdym przypadku, bo kod pisałbyś całą wieczność, a potem kod wykonywałby się całą wieczność przez ogromny narzut związany z kontrolą błędów na tak niskim poziomie.

także wniosek, że w typie long long mieści się iloczyn dwóch intów ( dla ujemnych też można to wykazać)
Drugie wyjście to nie mnożyć tych liczb przez siebie. Na architekturze mającej liczby co najwyżej 32-bitowe taki kod też by zadziałał, bo kompilator jakoś by te operacje 64-bitowe zaimplementował z tym co ma. Możesz zrobić to samo, jakoś sprytnie przekształcić samą nierówność, rozbić na konkretne przypadki i tak dalej. Pomyśl co by było jakbyś miał na wejściu już argumenty 64-bitowe.
P-177737
« 1 »
 Strona 1 z 1