Dlaczego nie ma `int pow (int base, int exponent)` w standardowych bibliotekach C ++?

Czuję, że po prostu nie mogę go znaleźć. Czy jest jakiś powód, dla którego powfunkcja C ++ nie implementuje funkcji „power” dla niczego oprócz floats i doubles?

Wiem, że implementacja jest trywialna, po prostu czuję, że wykonuję pracę, która powinna znajdować się w standardowej bibliotece. Solidna funkcja potęgi (tj. Radzi sobie z przepełnieniem w jakiś spójny, wyraźny sposób) nie jest przyjemna do napisania.

Od dnia C++11do zestawu funkcji potęgowych (i innych) dodano przypadki specjalne. C++11 [c.math] /11stwierdza, po wypisaniu wszystkich float/double/long doubleprzeciążeń (moje podkreślenie i parafrazowanie):

Ponadto powinny istnieć dodatkowe przeciążenia wystarczające do zapewnienia, że jeśli jakikolwiek argument odpowiadający doubleparametrowi ma typ doublelub typ całkowity, to wszystkie argumenty odpowiadające doubleparametrom są skutecznie rzutowane na double.

Zasadniczo parametry całkowite zostaną zaktualizowane do podwojonych w celu wykonania operacji.

Przed C++11(czyli wtedy, gdy zadano Twoje pytanie) nie istniały żadne przeciążenia całkowitoliczbowe.

Ponieważ nie byłem ani blisko związany z twórcami, Cani C++w czasach ich powstania (choć jestem raczej stary), ani z członkami komitetów ANSI / ISO, które tworzyły normy, jest to koniecznie opinia z mojej strony. Chciałbym myśleć, że to przemyślana opinia, ale jak powie ci moja żona (często i bez potrzeby większej zachęty), wcześniej się myliłem :-)

Następuje przypuszczenie, ile to jest warte.

I podejrzewam , że powodem oryginału pre-ANSI Cnie mają tej funkcji, ponieważ to było zupełnie niepotrzebne. Po pierwsze, istniał już doskonale dobry sposób wykonywania potęg całkowitych (z podwójnymi, a następnie po prostu zamianą z powrotem na liczbę całkowitą, sprawdzaniem przepełnienia i niedomiaru liczb całkowitych przed konwersją).

Po drugie, inną rzeczą, o której musisz pamiętać, jest to, że pierwotnym zamiarem Cbyło stworzenie języka programowania systemów i wątpliwe jest, czy zmiennoprzecinkowy jest w ogóle pożądany na tej arenie.

Ponieważ jeden z jego początkowych przypadków użycia polegał na zakodowaniu systemu UNIX, zmiennoprzecinkowy byłby prawie bezużyteczny. BCPL, na którym oparto C, również nie miał zastosowania do potęg (w ogóle nie miał zmiennoprzecinkowych z pamięci).

Nawiasem mówiąc, integralny operator potęgowy prawdopodobnie byłby operatorem binarnym, a nie wywołaniem biblioteki. Nie dodajesz dwóch liczb całkowitych z, x = add (y, z)ale z x = y + z- częścią właściwego języka, a nie z biblioteki.

Po trzecie, ponieważ implementacja mocy integralnej jest stosunkowo trywialna, jest prawie pewne, że twórcy języka lepiej wykorzystaliby swój czas na dostarczanie bardziej przydatnych rzeczy (patrz poniżej komentarze dotyczące kosztów alternatywnych).

Dotyczy to również oryginału C++. Ponieważ oryginalna implementacja była właściwie tylko tłumaczem, który tworzył Ckod, zawierała wiele atrybutów C. Jego pierwotnym zamiarem było C-z-klasami, a nie C-z-klasami-plus-trochę-trochę-dodatkowych-matematycznych-rzeczy.

Jeśli chodzi o to, dlaczego nigdy wcześniej nie został dodany do standardów C++11, należy pamiętać, że organy ustanawiające normy mają określone wytyczne, których należy przestrzegać. Na przykład ANSI Cotrzymało szczególne zadanie kodyfikacji istniejącej praktyki, a nie tworzenia nowego języka. Inaczej mogliby oszaleć i dać nam Adę :-)

Późniejsze wersje tego standardu również mają określone wytyczne i można je znaleźć w dokumentach uzasadniających (uzasadnienie, dlaczego komitet podjął określone decyzje, a nie uzasadnienie samego języka).

Na przykład C99dokument zawierający uzasadnienie zawiera w szczególności dwie z C89przewodnich zasad, które ograniczają to, co można dodać:

• Niech język będzie mały i prosty.
  
• Zapewnij tylko jeden sposób wykonania operacji.

Wytyczne (niekoniecznie te szczegółowe ) są ustanawiane dla poszczególnych grup roboczych, a zatem ograniczają również C++komitety (i wszystkie inne grupy ISO).

Ponadto organy ustanawiające normy zdają sobie sprawę, że każda podjęta przez nie decyzja wiąże się z kosztem alternatywnym (termin ekonomiczny oznaczający to, z czego musisz zrezygnować, aby podjąć decyzję). Na przykład koszt alternatywny zakupu automatu do gier o wartości 10 000 USD to serdeczne stosunki (lub prawdopodobnie wszystkie relacje) z drugą połową przez około sześć miesięcy.

Eric Gunnerson wyjaśnia to dobrze, wyjaśniając - 100 punktów, dlaczego rzeczy nie zawsze są dodawane do produktów Microsoft - w zasadzie funkcja zaczyna się od 100 punktów w dziurze, więc musi dodać sporo wartości, aby można ją było wziąć pod uwagę.

Innymi słowy, czy wolałbyś mieć zintegrowany operator potęgowy (który, szczerze mówiąc, każdy na wpół przyzwoity koder mógłby przyspieszyć w ciągu dziesięciu minut) lub wielowątkowość dodaną do standardu? Osobiście wolałbym mieć to drugie i nie musieć grzebać w różnych implementacjach w systemach UNIX i Windows.

Chciałbym również zobaczyć tysiące zbiorów w bibliotece standardowej (hashe, btrees, czerwono-czarne drzewa, słownik, dowolne mapy itp.), Ale jak podaje uzasadnienie:

Standard to umowa między implementatorem a programistą.

A liczba osób wdrażających w organach normalizacyjnych znacznie przewyższa liczbę programistów (lub przynajmniej tych programistów, którzy nie rozumieją kosztów alternatywnych). Gdyby to wszystko zostało dodane, następny standard C++byłby C++215xi prawdopodobnie zostałby w pełni zaimplementowany przez programistów kompilatorów trzysta lat później.

W każdym razie to moje (dość obszerne) przemyślenia na ten temat. Gdyby tylko głosy były przyznawane w oparciu o ilość, a nie jakość, wkrótce wywaliłbym wszystkich innych z wody. Dziękuję za słuchanie :-)

W przypadku dowolnego typu całkowego o stałej szerokości prawie wszystkie możliwe pary danych wejściowych i tak przepełniają typ. Jaki jest pożytek ze standaryzacji funkcji, która nie daje użytecznych wyników dla większości możliwych danych wejściowych?

Aby funkcja była użyteczna, musisz mieć typ dużej liczby całkowitej, a większość dużych bibliotek całkowitych zapewnia tę funkcję.

Edycja: W komentarzu do pytania static_rtti pisze: „Większość danych wejściowych powoduje przepełnienie? To samo dotyczy exp i podwójnej mocy, nie widzę nikogo narzekającego”. To jest niepoprawne.

Odłóżmy to na bok exp, bo to nie ma znaczenia (choć faktycznie wzmocniłoby to moją sprawę) i skupmy się na double pow(double x, double y). Dla jakiej części par (x, y) ta funkcja robi coś pożytecznego (tj. Nie jest po prostu przepełnieniem lub niedomiarem)?

Właściwie skupię się tylko na niewielkiej części par wejściowych, dla których powma to sens, ponieważ to wystarczy, aby udowodnić mój punkt widzenia: jeśli x jest dodatnie i | y | <= 1, to pownie powoduje przepełnienia ani niedomiaru. Obejmuje to prawie jedną czwartą wszystkich par zmiennoprzecinkowych (dokładnie połowa liczb zmiennoprzecinkowych innych niż NaN jest dodatnia, a tylko mniej niż połowa liczb zmiennoprzecinkowych innych niż NaN ma wielkość mniejszą niż 1). Oczywiście istnieje wiele innych par danych wejściowych, dla których można powuzyskać przydatne wyniki, ale ustaliliśmy, że jest to co najmniej jedna czwarta wszystkich danych wejściowych.

Przyjrzyjmy się teraz funkcji potęgowej o stałej szerokości (tj. Innej niż bignum). Na jaką porcję nakładów po prostu się nie przepełnia? Aby zmaksymalizować liczbę znaczących par wejściowych, podstawa powinna być podpisana, a wykładnik pozbawiony znaku. Załóżmy, że podstawa i wykładnik mają nszerokość bitów. Możemy łatwo określić część danych wejściowych, które mają znaczenie:

• Jeśli wykładnik wykładniczy 0 lub 1, wtedy każda podstawa ma znaczenie.
• Jeśli wykładnik jest 2 lub większy, wówczas żadna podstawa większa niż 2 ^ (n / 2) nie daje sensownego wyniku.

Zatem z 2 ^ (2n) par wejściowych mniej niż 2 ^ (n + 1) + 2 ^ (3n / 2) daje znaczące wyniki. Jeśli spojrzymy na prawdopodobnie najczęściej używane 32-bitowe liczby całkowite, oznacza to, że coś rzędu 1/1000 jednego procenta par wejściowych nie jest po prostu przepełnione.

Ponieważ i tak nie ma sposobu na przedstawienie wszystkich potęg całkowitych w int:

>>> print 2**-4
0.0625

Właściwie to interesujące pytanie. Jednym z argumentów, których nie znalazłem w dyskusji, jest prosty brak oczywistych wartości zwracanych dla argumentów. Policzmy, w jaki sposób int pow_int(int, int)funkcja hipotetyczna może zawieść.

1. Przelewowy
2. Wynik niezdefiniowany pow_int(0,0)
3. Nie można przedstawić wyniku pow_int(2,-1)

Funkcja ma co najmniej 2 tryby awarii. Liczby całkowite nie mogą reprezentować tych wartości, zachowanie funkcji w takich przypadkach musiałoby być zdefiniowane przez standard - a programiści musieliby być świadomi, jak dokładnie funkcja obsługuje te przypadki.

Ogólnie rzecz biorąc, wykluczenie funkcji wydaje się jedyną rozsądną opcją. Programista może zamiast tego użyć wersji zmiennoprzecinkowej z całym raportowaniem błędów.

Krótka odpowiedź:

Specjalizacja pow(x, n)gdzie njest liczbą naturalną jest często przydatna przy wykonywaniu zadań czasowych . Ale typowa biblioteka standardowa pow()nadal działa całkiem (o dziwo! ) Dobrze w tym celu i absolutnie krytyczne jest włączenie jak najmniejszej ilości do standardowej biblioteki C, aby można ją było uczynić tak przenośną i tak łatwą do wdrożenia, jak to tylko możliwe. Z drugiej strony, to wcale nie przeszkadza mu być w standardowej bibliotece C ++ lub STL, którego jestem prawie pewien, że nikt nie planuje używać na jakiejś wbudowanej platformie.

A teraz długa odpowiedź.

pow(x, n)w wielu przypadkach można znacznie przyspieszyć, specjalizując nsię w liczbach naturalnych. Musiałem używać własnej implementacji tej funkcji dla prawie każdego programu, który piszę (ale piszę wiele programów matematycznych w języku C). Specjalistyczną operację można wykonać w O(log(n))czasie, ale gdy njest mała, prostsza wersja liniowa może być szybsza. Oto implementacje obu:

    // Computes x^n, where n is a natural number.
    double pown(double x, unsigned n)
    {
        double y = 1;
        // n = 2*d + r. x^n = (x^2)^d * x^r.
        unsigned d = n >> 1;
        unsigned r = n & 1;
        double x_2_d = d == 0? 1 : pown(x*x, d);
        double x_r = r == 0? 1 : x;
        return x_2_d*x_r;
    }
    // The linear implementation.
    double pown_l(double x, unsigned n)
    {
        double y = 1;
        for (unsigned i = 0; i < n; i++)
            y *= x;
        return y;
    }

(Wyszedłem xi wartość zwracana jako podwaja się, ponieważ wynik pow(double x, unsigned n)będzie pasował do podwojenia mniej więcej tak często, jak pow(double, double)będzie to możliwe).

(Tak, pownjest rekurencyjny, ale zerwanie stosu jest absolutnie niemożliwe, ponieważ maksymalny rozmiar stosu będzie z grubsza równy log_2(n)i njest liczbą całkowitą. Jeśli njest to 64-bitowa liczba całkowita, daje to maksymalny rozmiar stosu wynoszący około 64. Żaden sprzęt nie ma tak ekstremalnych możliwości ograniczenia pamięci, z wyjątkiem niektórych podejrzanych PIC ze stosami sprzętowymi, które sięgają tylko 3 do 8 wywołań funkcji głęboko.)

Jeśli chodzi o wydajność, będziesz zaskoczony, do czego pow(double, double)zdolna jest odmiana ogrodowa . Przetestowałem sto milionów iteracji na moim 5-letnim IBM Thinkpad z xrówną liczbą iteracji i nrówną 10. W tym scenariuszu pown_lwygrałem. glibc pow()zajmował 12,0 sekund użytkownika, pown7,4 sekundy użytkownika i pown_ltylko 6,5 sekundy użytkownika. Więc to nie jest zbyt zaskakujące. Spodziewaliśmy się tego mniej więcej.

Następnie pozostawiam xstałą wartość (ustawiam ją na 2,5) i wykonuję pętlę nod 0 do 19 sto milionów razy. Tym razem, dość nieoczekiwanie, powwygrał glibc , i to po miażdżąco! Zajęło to tylko 2,0 sekundy użytkownika. Mój pownzajął 9,6 sekundy i pown_l12,2 sekundy. Co tu się stało? Zrobiłem kolejny test, aby się dowiedzieć.

Zrobiłem to samo, co powyżej, tylko z xrównym milionem. Tym razem pownwygrał przy 9,6 s. pown_lzajęło 12,2 s, a glibc pow 16,3 s. Teraz jest jasne! glibc powdziała lepiej niż te trzy, gdy xjest niski, ale gorzej, gdy xjest wysoki. Kiedy xjest wysoka, pown_ldziała najlepiej, gdy njest niska, i powndziała najlepiej, gdy xjest wysoka.

Oto trzy różne algorytmy, z których każdy może działać lepiej niż inne w odpowiednich okolicznościach. Ostatecznie więc, który z nich najprawdopodobniej zależy od tego, jak planujesz używać pow, ale użycie właściwej wersji jest tego warte, a posiadanie wszystkich wersji jest przyjemne. W rzeczywistości możesz nawet zautomatyzować wybór algorytmu za pomocą takiej funkcji:

double pown_auto(double x, unsigned n, double x_expected, unsigned n_expected) {
    if (x_expected < x_threshold)
        return pow(x, n);
    if (n_expected < n_threshold)
        return pown_l(x, n);
    return pown(x, n);
}

O ile wartości stałe x_expectedi n_expectedsą ustalane w czasie kompilacji, wraz z prawdopodobnie kilkoma innymi zastrzeżeniami, warty swojej soli kompilator optymalizujący automatycznie usunie całe pown_autowywołanie funkcji i zastąpi je odpowiednim wyborem spośród trzech algorytmów. (Teraz, jeśli rzeczywiście zamierzasz tego użyć , prawdopodobnie będziesz musiał się trochę bawić, ponieważ nie próbowałem dokładnie skompilować tego, co napisałem powyżej.;))

Z drugiej strony, glibc pow działa, a glibc jest już wystarczająco duży. Standard C ma być przenośny, w tym na różne urządzenia wbudowane (w rzeczywistości deweloperzy oprogramowania wbudowanego na całym świecie ogólnie zgadzają się, że glibc jest już dla nich za duży) i nie może być przenośny, jeśli dla każdej prostej funkcji matematycznej musi zawierać wszystkie alternatywny algorytm, który może być przydatny. Dlatego właśnie nie jest w standardzie C.

przypis: Podczas testowania wydajności w czasie dałem moim funkcjom stosunkowo duże flagi optymalizacji ( -s -O2), które prawdopodobnie będą porównywalne, jeśli nie gorsze, z tym, co prawdopodobnie zostało użyte do kompilacji glibc w moim systemie (archlinux), więc wyniki są prawdopodobnie targi. Aby uzyskać bardziej rygorystyczny test, musiałbym sam skompilować glibc i naprawdę nie mam na to ochoty. Kiedyś używałem Gentoo, więc pamiętam, ile czasu to zajmuje, nawet jeśli zadanie jest zautomatyzowane . Wyniki są dla mnie wystarczająco rozstrzygające (lub raczej niejednoznaczne). Oczywiście możesz to zrobić samodzielnie.

Runda bonusowa: specjalizacja pow(x, n)wszystkich liczb całkowitych ma znaczenie instrumentalne, jeśli wymagana jest dokładna liczba całkowita, co się zdarza. Rozważ przydzielenie pamięci dla tablicy N-wymiarowej z elementami p ^ N. Usunięcie p ^ N nawet o jeden spowoduje prawdopodobnie przypadkowe wystąpienie błędu.

Jednym z powodów, dla których C ++ nie ma dodatkowych przeciążeń, jest kompatybilność z C.

C ++ 98 ma funkcje takie jak double pow(double, int), ale zostały one usunięte w C ++ 11 z argumentem, że C99 ich nie zawiera.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3286.html#550

Uzyskanie nieco dokładniejszego wyniku oznacza również uzyskanie nieco innego wyniku.

Świat stale się rozwija, podobnie jak języki programowania. Czwarta część C TR dziesiętnych ¹ dodaje nieco więcej funkcje <math.h>. W tym pytaniu interesujące mogą być dwie rodziny tych funkcji:

• Te pownfunkcje, które ma liczbę zmiennoprzecinkową oraz intmax_twykładnik.
• Te powrfunkcje, które ma dwa ruchome punkty liczby ( xi y) i obliczyć xna moc yze wzorem exp(y*log(x)).

Wygląda na to, że standardowi użytkownicy ostatecznie uznali te funkcje za wystarczająco przydatne, aby można je było zintegrować ze standardową biblioteką. Jednak racjonalne jest to, że te funkcje są zalecane przez normę ISO / IEC / IEEE 60559: 2011 dla binarnych i dziesiętnych liczb zmiennoprzecinkowych. Nie mogę powiedzieć na pewno, jaki „standard” był przestrzegany w czasie C89, ale przyszłe ewolucje <math.h>będą prawdopodobnie pod silnym wpływem przyszłej ewolucji normy ISO / IEC / IEEE 60559 .

Zauważ, że czwarta część dziesiętnego TR nie zostanie uwzględniona w C2x (następna główna wersja C) i prawdopodobnie zostanie dołączona później jako funkcja opcjonalna. Nie było żadnego zamiaru, o którym wiem, aby włączyć tę część TR w przyszłej wersji C ++.

¹ można znaleźć dokumentację work-in-progress tutaj .

Być może dlatego, że jednostka ALU procesora nie zaimplementowała takiej funkcji dla liczb całkowitych, ale jest taka instrukcja FPU (jak podkreśla Stephen, to właściwie para). Tak więc w rzeczywistości szybsze było rzutowanie na podwojenie, wywoływanie pow z podwójnymi, a następnie testowanie przepełnienia i rzutowanie z powrotem, niż zaimplementowanie tego za pomocą arytmetyki liczb całkowitych.

(po pierwsze, logarytmy redukują potęgi do mnożenia, ale logarytmy liczb całkowitych tracą dużo dokładności dla większości danych wejściowych)

Stephen ma rację, że na nowoczesnych procesorach nie jest to już prawdą, ale standard C, kiedy wybrano funkcje matematyczne (C ++ właśnie używał funkcji C), ma teraz 20 lat?

Oto naprawdę prosta implementacja funkcji pow () O (log (n) ), która działa dla wszystkich typów liczbowych, w tym liczb całkowitych :

template<typename T>
static constexpr inline T pown(T x, unsigned p) {
    T result = 1;

    while (p) {
        if (p & 0x1) {
            result *= x;
        }
        x *= x;
        p >>= 1;
    }

    return result;
}

Jest lepsza niż implementacja O (log (n)) enigmaticPhysicist, ponieważ nie używa rekurencji.

Jest również prawie zawsze szybszy niż jego liniowa implementacja (o ile p> ~ 3), ponieważ:

• nie wymaga dodatkowej pamięci
• wykonuje tylko ~ 1,5 raza więcej operacji na pętlę
• robi tylko ~ 1,25x więcej aktualizacji pamięci na pętlę

W rzeczywistości tak.

Od C ++ 11 istnieje szablonowa implementacja pow(int, int)--- i jeszcze bardziej ogólnych przypadków, patrz (7) w http://en.cppreference.com/w/cpp/numeric/math/pow

EDYCJA: puryści mogą twierdzić, że nie jest to poprawne, ponieważ w rzeczywistości używane jest typowanie „promowane”. Tak czy inaczej uzyskuje się poprawny intwynik lub błąd intparametrów.

Bardzo prosty powód:

5^-2 = 1/25

Wszystko w bibliotece STL jest oparte na najbardziej dokładnych i solidnych rzeczach, jakie można sobie wyobrazić. Jasne, int powróciłoby do zera (od 1/25), ale byłaby to niedokładna odpowiedź.

Zgadzam się, w niektórych przypadkach to dziwne.