Czuję, że po prostu nie mogę go znaleźć. Czy jest jakiś powód, dla którego pow
funkcja C ++ nie implementuje funkcji „power” dla niczego oprócz float
s i double
s?
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.
double pow(int base, int exponent)
od C ++ 11 (§26.8 [c.math] / 11 punktor 2)Odpowiedzi:
Od dnia
C++11
do zestawu funkcji potęgowych (i innych) dodano przypadki specjalne.C++11 [c.math] /11
stwierdza, po wypisaniu wszystkichfloat/double/long double
przeciążeń (moje podkreślenie i parafrazowanie):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,
C
aniC++
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
C
nie 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
C
był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).
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łC
kod, zawierała wiele atrybutówC
. 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 ANSIC
otrzymał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
C99
dokument zawierający uzasadnienie zawiera w szczególności dwie zC89
przewodnich zasad, które ograniczają to, co można dodać: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:
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łbyC++215x
i 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 :-)
źródło
to_string
i 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.pow
któ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.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ę nadouble 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
pow
ma to sens, ponieważ to wystarczy, aby udowodnić mój punkt widzenia: jeśli x jest dodatnie i | y | <= 1, topow
nie 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żnapow
uzyskać 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ą
n
szerokość bitów. Możemy łatwo określić część danych wejściowych, które mają znaczenie: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.
źródło
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.pow
to po prostu mała tablica przeglądowa. :-)Ponieważ i tak nie ma sposobu na przedstawienie wszystkich potęg całkowitych w int:
źródło
int pow(int base, unsigned int exponent)
ifloat pow(int base, int exponent)
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, lubbase >1 || base< -1
w takim przypadkuexponent<256
pod groźbą przepełnienia.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ść.pow_int(0,0)
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.
źródło
pow
między pływakami? Weź dwa duże pływaki, podnieś jeden do potęgi drugiego i masz Przepełnienie. Ipow(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.Krótka odpowiedź:
Specjalizacja
pow(x, n)
gdzien
jest liczbą naturalną jest często przydatna przy wykonywaniu zadań czasowych . Ale typowa biblioteka standardowapow()
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ącn
się 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ć wO(log(n))
czasie, ale gdyn
jest mała, prostsza wersja liniowa może być szybsza. Oto implementacje obu:(Wyszedłem
x
i wartość zwracana jako podwaja się, ponieważ wynikpow(double x, unsigned n)
będzie pasował do podwojenia mniej więcej tak często, jakpow(double, double)
będzie to możliwe).(Tak,
pown
jest rekurencyjny, ale zerwanie stosu jest absolutnie niemożliwe, ponieważ maksymalny rozmiar stosu będzie z grubsza równylog_2(n)
in
jest liczbą całkowitą. Jeślin
jest 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 zx
równą liczbą iteracji in
równą 10. W tym scenariuszupown_l
wygrałem. glibcpow()
zajmował 12,0 sekund użytkownika,pown
7,4 sekundy użytkownika ipown_l
tylko 6,5 sekundy użytkownika. Więc to nie jest zbyt zaskakujące. Spodziewaliśmy się tego mniej więcej.Następnie pozostawiam
x
stałą wartość (ustawiam ją na 2,5) i wykonuję pętlęn
od 0 do 19 sto milionów razy. Tym razem, dość nieoczekiwanie,pow
wygrał glibc , i to po miażdżąco! Zajęło to tylko 2,0 sekundy użytkownika. Mójpown
zajął 9,6 sekundy ipown_l
12,2 sekundy. Co tu się stało? Zrobiłem kolejny test, aby się dowiedzieć.Zrobiłem to samo, co powyżej, tylko z
x
równym milionem. Tym razempown
wygrał przy 9,6 s.pown_l
zajęło 12,2 s, a glibc pow 16,3 s. Teraz jest jasne! glibcpow
działa lepiej niż te trzy, gdyx
jest niski, ale gorzej, gdyx
jest wysoki. Kiedyx
jest wysoka,pown_l
działa najlepiej, gdyn
jest niska, ipown
działa najlepiej, gdyx
jest 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:O ile wartości stałe
x_expected
in_expected
są ustalane w czasie kompilacji, wraz z prawdopodobnie kilkoma innymi zastrzeżeniami, warty swojej soli kompilator optymalizujący automatycznie usunie całepown_auto
wywoł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.źródło
n
. godbolt.org/z/L9Kb98 . gcc i clang nie optymalizują rekurencyjnej definicji w prostą pętlę i faktycznie wykonują rozgałęzianie na każdym bicien
. (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)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.
źródło
Ś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:pown
funkcje, które ma liczbę zmiennoprzecinkową orazintmax_t
wykładnik.powr
funkcje, które ma dwa ruchome punkty liczby (x
iy
) i obliczyćx
na mocy
ze wzoremexp(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 .
źródło
pown
z wykładnikiem większym niżLONG_MAX
powinno dawać wartość inną niż użycieLONG_MAX
lub w których wartość mniejsza niżLONG_MIN
powinna dawać wartość inną niżLONG_MIN
? Zastanawiam się, jakie korzyści daje użycieintmax_t
wykładnika potęgi?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?
źródło
pow
. x86 may log2 x
instrukcję (fyl2x
), której można użyć jako pierwszej częścipow
funkcji, alepow
funkcja 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.Oto naprawdę prosta implementacja funkcji pow () O (log (n) ), która działa dla wszystkich typów liczbowych, w tym liczb całkowitych :
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ż:
źródło
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/powEDYCJA: puryści mogą twierdzić, że nie jest to poprawne, ponieważ w rzeczywistości używane jest typowanie „promowane”. Tak czy inaczej uzyskuje się poprawny
int
wynik lub błądint
parametrów.źródło
pow ( Arithmetic1 base, Arithmetic2 exp )
które zostanie rzutowanedouble
lublong double
jeś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. "pow(1.5f, 3)
=1072693280
butpow(1.5f, float(3))
=3.375
int pow(int, int)
, ale C ++ 11 zapewnia tylkodouble pow(int, int)
. Zobacz wyjaśnienie @phuclv.Bardzo prosty powód:
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.
źródło