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

116

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.

Dan O
źródło
4
To dobre pytanie i nie sądzę, by odpowiedzi miały sens. Ujemne wykładniki nie działają? Jako wykładniki potraktuj liczby int bez znaku. Większość wejść powoduje przepełnienie? To samo dotyczy exp i podwójnej mocy, nie widzę nikogo narzekającego. Dlaczego więc ta funkcja nie jest standardem?
static_rtti,
2
@static_rtti: "To samo dotyczy exp i double pow" jest całkowicie fałszywe. Opiszę swoją odpowiedź.
Stephen Canon,
11
Standardowa biblioteka C ++ ma double pow(int base, int exponent)od C ++ 11 (§26.8 [c.math] / 11 punktor 2)
Cubbi
Musisz zdecydować między „implementacja jest trywialna” a „niezbyt przyjemne do napisania”.
Markiz Lorne

Odpowiedzi:

66

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 :-)

paxdiablo
źródło
2
FWIW, nie sądzę, by C ++ następowało po „Zapewnij tylko jeden sposób wykonania operacji” jako ograniczenie. Słusznie, ponieważ na przykład to_stringi lambdy są wygodami dla rzeczy, które można już zrobić. Przypuszczam, że można by bardzo luźno zinterpretować „tylko jeden sposób wykonania operacji”, aby zezwolić na oba te sposoby , a jednocześnie pozwolić na prawie każde powielenie funkcjonalności, jakie można sobie wyobrazić, mówiąc „aha! Nie! jest to nieco inna operacja niż dokładnie równoważna, ale bardziej rozwlekła alternatywa! ”. Co z pewnością jest prawdą w przypadku lambd.
Steve Jessop
@Steve, tak, to było źle sformułowane z mojej strony. Bardziej trafne jest stwierdzenie, że istnieją wytyczne dla każdej komisji, a nie wszystkie komisje stosują się do tych samych wytycznych. Dostosowano odpowiedź na clarifyl
paxdiablo,
2
Tylko jeden punkt (z kilku): „każda małpa kodu może się przygotować w dziesięć minut”. Jasne, a jeśli 100 małp kodowych (przy okazji, fajnie obraźliwy termin) robi to każdego roku (prawdopodobnie niski szacunek), tracimy 1000 minut. Bardzo wydajne, nie sądzisz?
Jürgen A. Erhard
1
@ Jürgen, to nie miało być obraźliwe (ponieważ tak naprawdę nie przypisałem etykiety nikomu konkretnemu), to była tylko wskazówka, powktóra tak naprawdę nie wymaga dużych umiejętności. Z pewnością wolałbym mieć średnia dostarczyć coś, co będzie wymagało wiele umiejętności i spowodować wiele bardziej zmarnowane minuty jeśli wysiłek musiał być duplikowane.
paxdiablo
2
@ eharo2, po prostu zamień „w połowie przyzwoity koder” w bieżącym tekście na „małpa kodu”. Nie sądziłem, że to obraźliwe, ale uważałem, że najlepiej będzie zachować ostrożność i, szczerze mówiąc, obecne sformułowanie dotyczy tego samego pomysłu.
paxdiablo
41

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.

Stephen Canon
źródło
8
W każdym razie to wszystko jest dyskusyjne. Tylko dlatego, że funkcja nie jest poprawna dla niektórych lub wielu danych wejściowych, nie czyni jej mniej użyteczną.
static_rtti,
2
@static_rtti: pow(x,y)nie niedomiar do zera dla żadnego x jeśli | y | <= 1. Istnieje bardzo wąskie pasmo danych wejściowych (duże x, y bardzo blisko -1), dla których występuje niedomiar, ale wynik jest nadal znaczący w tym zakresie.
Stephen Canon,
2
Po dokładniejszym przemyśleniu zgadzam się na niedomiar. Nadal uważam, że to nie ma znaczenia dla pytania.
static_rtti,
7
@ybungalobill: Dlaczego wybrałeś to jako powód? Osobiście wolałbym użyteczność w przypadku dużej liczby problemów i programistów, możliwość tworzenia zoptymalizowanych pod kątem oprogramowania wersji, które są szybsze niż naiwne implementacje, które prawdopodobnie napisze większość programistów, i tak dalej. Twoje kryterium wydaje się całkowicie arbitralne i, szczerze mówiąc, zupełnie bezcelowe.
static_rtti
5
@StephenCanon: Z drugiej strony, twój argument pokazuje, że oczywiście poprawna i optymalna implementacja liczby całkowitej powto po prostu mała tablica przeglądowa. :-)
R .. GitHub STOP HELPING ICE
11

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

>>> print 2**-4
0.0625
Ignacio Vazquez-Abrams
źródło
3
W przypadku typu liczbowego o skończonej wielkości nie ma możliwości reprezentowania wszystkich potęg tego typu w tym typie z powodu przepełnienia. Ale twoja uwaga dotycząca negatywnych mocy jest bardziej aktualna.
Chris Lutz,
1
Postrzegam ujemne wykładniki jako coś, co może obsłużyć standardowa implementacja, albo przyjmując wartość int bez znaku jako wykładnik, albo zwracając zero, gdy jako dane wejściowe podano wykładnik ujemny, a wartość int jest oczekiwanym wynikiem.
Dan O
3
lub mieć osobne int pow(int base, unsigned int exponent)ifloat pow(int base, int exponent)
Ponkadoodle
4
Mogliby po prostu zadeklarować to jako niezdefiniowane zachowanie, aby przekazać ujemną liczbę całkowitą.
Johannes Schaub - litb
2
We wszystkich nowoczesnych implementacjach wszystko poza tym i tak int pow(int base, unsigned char exponent)jest nieco bezużyteczne. Podstawa jest równa 0 lub 1, a wykładnik nie ma znaczenia, jest to -1, w którym to przypadku liczy się tylko ostatni bit wykładnika, lub base >1 || base< -1w takim przypadku exponent<256pod groźbą przepełnienia.
MSalters
9

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.

phoku
źródło
Ale czy dwa pierwsze przypadki nie miałyby zastosowania również do powmiędzy pływakami? Weź dwa duże pływaki, podnieś jeden do potęgi drugiego i masz Przepełnienie. I pow(0.0, 0.0)spowodowałoby ten sam problem, co twój drugi punkt. Twój trzeci punkt jest jedyną rzeczywistą różnicą między implementacją funkcji potęgowej dla liczb całkowitych a zmiennoprzecinkowymi.
numbermaniac
7

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.

enigmatyczny fizyk
źródło
Myślę, że jeśli pozbędziesz się rekurencji, zaoszczędzisz czas potrzebny na przydzielenie stosu. I tak, mieliśmy sytuację, w której pow wszystko spowalniał i musimy zaimplementować własny pow.
Sambatyon
„Nikt nie ma tak skrajnych ograniczeń pamięciowych” jest fałszem. PIC często mają ograniczony stos wywołań dla maksymalnie 3 (na przykład PIC10F200) do 8 (na przykład 16F722A) wywołań (PIC używa stosu sprzętowego do wywołań funkcji).
12431234123412341234123
och, stary, to brutalne lol. OK, więc to nie zadziała na tych PIC.
enigmaticPhysicist
W przypadku liczby całkowitej, a także potęgi, jak to dotyczy pytania, kompilatory (gcc i clang) z łatwością utworzą bezgałęziową pętlę z iteracyjnej (zamiast rekurencyjnej) implementacji. Pozwala to uniknąć błędnych prognoz gałęzi z każdego bitu n. godbolt.org/z/L9Kb98 . gcc i clang nie optymalizują rekurencyjnej definicji w prostą pętlę i faktycznie wykonują rozgałęzianie na każdym bicie n. (Ponieważ pown_iter(double,unsigned)nadal rozgałęziają się, ale bezgałęziowa implementacja SSE2 lub SSE4.1 powinna być możliwa w asm x86 lub z elementami wewnętrznymi C. Ale nawet to lepsze niż rekursja)
Peter Cordes
Cholera, teraz muszę powtórzyć testy porównawcze z wersją opartą na pętli, aby mieć pewność. Pomyślę o tym.
enigmaticPhysicist
6

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.

Bo Persson
źródło
3

Ś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 .

Morwenn
źródło
Czy są jakieś wiarygodne implementacje, w których użycie pownz wykładnikiem większym niż LONG_MAXpowinno dawać wartość inną niż użycie LONG_MAXlub w których wartość mniejsza niż LONG_MINpowinna dawać wartość inną niż LONG_MIN? Zastanawiam się, jakie korzyści daje użycie intmax_twykładnika potęgi?
supercat
@supercat Nie mam pojęcia, przepraszam.
Morwenn
Warto wspomnieć, że patrząc na Standard, wydaje się, że definiuje on również opcjonalną funkcję „crpown”, która, gdyby została zdefiniowana, byłaby poprawnie zaokrągloną wersją „pown”; poza tym norma nie określa wymaganego stopnia dokładności. Wdrożenie szybkiego i średnio precyzyjnego „pown” jest łatwe, ale zapewnienie prawidłowego zaokrąglania we wszystkich przypadkach może być znacznie droższe.
supercat
2

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?

Ben Voigt
źródło
5
Nie znam żadnej obecnej architektury z instrukcją FPU dla pow. x86 ma y log2 xinstrukcję ( fyl2x), której można użyć jako pierwszej części powfunkcji, ale powfunkcja napisana w ten sposób wymaga setek cykli do wykonania na bieżącym sprzęcie; dobrze napisana procedura potęgowania liczb całkowitych jest kilka razy szybsza.
Stephen Canon,
Nie wiem, czy „setki” jest dokładne, wydaje się, że wynosi około 150 cykli dla fyl2x, a następnie f2xm1 na większości nowoczesnych procesorów, i to jest potokowane z innymi instrukcjami. Ale masz rację, że dobrze dostrojona implementacja liczb całkowitych powinna być znacznie szybsza (obecnie), ponieważ IMUL został znacznie przyspieszony niż instrukcje zmiennoprzecinkowe. Jednak kiedy pisano standard C, IMUL był dość drogi i użycie go w pętli prawdopodobnie trwało dłużej niż użycie FPU.
Ben Voigt
2
Zmieniłem swój głos w świetle poprawki; należy jednak pamiętać, że (a) standard C przeszedł poważną rewizję (w tym duże rozszerzenie biblioteki matematycznej) w 1999 r. oraz (b) standard C nie został napisany do żadnej określonej architektury procesora - obecność lub brak instrukcji FPU na x86 nie ma w zasadzie nic wspólnego z funkcjonalnością, którą komitet C wybrał do standaryzacji.
Stephen Canon
Nie jest to związane z żadną architekturą, to prawda, ale względny koszt interpolacji tabeli przeglądowej (zwykle używanej w implementacji zmiennoprzecinkowej) w porównaniu z mnożeniem liczb całkowitych zmienił się prawie jednakowo dla wszystkich architektur.
Ben Voigt
1

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ę
serg06
źródło
-2

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.

Dima Pasechnik
źródło
2
to jest niepoprawne. Przeciążenie (7) jest tym, na pow ( Arithmetic1 base, Arithmetic2 exp )które zostanie rzutowane doublelub long doublejeśli przeczytałeś opis: "7) Zestaw przeciążeń lub szablon funkcji dla wszystkich kombinacji argumentów typu arytmetycznego nie objętych 1-3). Jeśli jakikolwiek argument ma typ całkowity, jest rzutowany na podwójny. Jeśli jakikolwiek argument jest typu long double, to typ zwracany Promoted również jest typu long double, w przeciwnym razie typ zwracany jest zawsze double. "
phuclv
co tu jest nie tak? Powiedziałem tylko, że obecnie (od C ++ 11) szablon pow ( , ) znajduje się w standardowej bibliotece, co nie miało miejsca w 2010 roku.
Dima Pasechnik
5
Nie, nie ma. Templeates promują te typy do podwójnego lub długiego podwójnego. Więc działa na dubletach pod spodem.
Trismegistos
1
@Trismegistos Nadal dopuszcza parametry int. Gdyby tego szablonu nie było, przekazanie parametrów int powoduje zinterpretowanie bitów w int jako liczby zmiennoprzecinkowej, powodując dowolne nieoczekiwane wyniki. To samo dzieje się z mieszanymi wartościami wejściowymi. np. pow(1.5f, 3)= 1072693280but pow(1.5f, float(3))=3.375
Mark Jeronimus
2
OP poprosił int pow(int, int), ale C ++ 11 zapewnia tylko double pow(int, int). Zobacz wyjaśnienie @phuclv.
xuhdev
-4

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.

Jason A.
źródło
3
Wymaganie drugiego argumentu bez znaku jest oczywiście konieczne. Istnieje wiele aplikacji, które wymagają tylko nieujemnych liczb całkowitych.
enigmaticPhysicist