Mengapa `int pow (int base, int exponent)` tidak ada di pustaka C ++ standar?

116

Saya merasa seperti saya pasti tidak dapat menemukannya. Apakah ada alasan bahwa fungsi C ++ powtidak mengimplementasikan fungsi "daya" untuk apa pun kecuali floats dan doubles?

Saya tahu implementasinya sepele, saya hanya merasa seperti melakukan pekerjaan yang seharusnya ada di perpustakaan standar. Fungsi daya yang kuat (yaitu menangani luapan dengan cara yang konsisten dan eksplisit) tidak menyenangkan untuk ditulis.

Dan O
sumber
4
Ini pertanyaan yang bagus, dan menurut saya jawabannya tidak masuk akal. Eksponen negatif tidak berfungsi? Ambil int unsigned sebagai eksponen. Kebanyakan masukan menyebabkannya meluap? Hal yang sama berlaku untuk exp dan double pow, saya tidak melihat ada yang mengeluh. Jadi mengapa fungsi ini tidak standar?
static_rtti
2
@static_rtti: "Hal yang sama berlaku untuk exp dan double pow" benar-benar salah. Saya akan menguraikan jawaban saya.
Stephen Canon
11
Pustaka C ++ standar double pow(int base, int exponent)sejak C ++ 11 (§26.8 [c.math] / 11 butir poin 2)
Cubbi
Anda perlu memutuskan antara 'penerapannya sepele' dan 'tidak menyenangkan untuk ditulis'.
Marquis dari Lorne

Jawaban:

66

Pada C++11, kasus khusus ditambahkan ke rangkaian fungsi daya (dan lainnya). C++11 [c.math] /11menyatakan, setelah mencantumkan semua float/double/long doublekelebihan (penekanan saya, dan parafrase):

Selain itu, harus ada kelebihan beban tambahan yang cukup untuk memastikan bahwa, jika ada argumen yang sesuai dengan doubleparameter memiliki tipe doubleatau tipe bilangan bulat, maka semua argumen yang sesuai dengan doubleparameter secara efektif dikirim double.

Jadi, pada dasarnya, parameter integer akan ditingkatkan menjadi dua kali lipat untuk melakukan operasi.


Sebelumnya C++11(saat pertanyaan Anda diajukan), tidak ada kelebihan bilangan bulat.

Karena saya tidak terkait erat dengan pencipta Catau C++pada hari-hari penciptaan mereka (meskipun saya saya agak lama), juga bagian dari komite ANSI / ISO yang menciptakan standar, ini tentu pendapat di bagian saya. Saya ingin berpikir itu adalah opini yang diinformasikan tetapi, karena istri saya akan memberi tahu Anda (sering dan tanpa banyak dorongan yang dibutuhkan), saya pernah salah sebelumnya :-)

Anggapan, untuk apa nilainya, berikut.

Saya menduga bahwa alasan pra-ANSI asli Ctidak memiliki fitur ini adalah karena itu sama sekali tidak diperlukan. Pertama, sudah ada cara yang sangat baik untuk melakukan pangkat integer (dengan dua kali lipat dan kemudian hanya mengubahnya kembali ke integer, memeriksa overflow dan underflow integer sebelum mengonversi).

Kedua, hal lain yang harus Anda ingat adalah bahwa maksud asli dari Cadalah sebagai bahasa pemrograman sistem , dan itu dipertanyakan apakah floating point diinginkan di arena itu sama sekali.

Karena salah satu kasus penggunaan awalnya adalah untuk membuat kode UNIX, titik mengambang akan menjadi tidak berguna. BCPL, yang menjadi dasar C, juga tidak menggunakan kekuatan (tidak memiliki floating point sama sekali, dari memori).

Selain itu, operator daya integral mungkin akan menjadi operator biner daripada panggilan perpustakaan. Anda tidak menambahkan dua integer dengan x = add (y, z)but with x = y + z- bagian dari bahasa yang tepat daripada library.

Ketiga, karena penerapan kekuatan integral relatif sepele, hampir dapat dipastikan bahwa pengembang bahasa akan lebih baik menggunakan waktu mereka untuk menyediakan hal-hal yang lebih bermanfaat (lihat komentar di bawah tentang biaya peluang).

Itu juga relevan dengan aslinya C++. Karena implementasi asli secara efektif hanya penerjemah yang menghasilkan Ckode, itu membawa banyak atribut C. Maksud aslinya adalah C-dengan-kelas, bukan C-dengan-kelas-plus-sedikit-tambahan-matematika-barang.

Mengenai mengapa tidak pernah ditambahkan ke standar sebelumnya C++11, Anda harus ingat bahwa badan pembuat standar memiliki pedoman khusus untuk diikuti. Misalnya, ANSI Csecara khusus ditugaskan untuk menyusun praktik yang ada, bukan untuk membuat bahasa baru. Kalau tidak, mereka bisa jadi gila dan memberi kami Ada :-)

Iterasi selanjutnya dari standar itu juga memiliki pedoman khusus dan dapat ditemukan dalam dokumen rasional (alasan mengapa panitia membuat keputusan tertentu, bukan alasan bahasa itu sendiri).

Misalnya, C99dokumen dasar pemikiran secara khusus mengedepankan dua C89prinsip panduan yang membatasi apa yang dapat ditambahkan:

  • Pertahankan bahasanya kecil dan sederhana.
  • Sediakan hanya satu cara untuk melakukan suatu operasi.

Panduan (tidak harus yang spesifik ) ditetapkan untuk masing-masing kelompok kerja dan karenanya membatasi C++komite (dan semua kelompok ISO lainnya) juga.

Selain itu, badan-badan pembuat standar menyadari bahwa ada biaya peluang (istilah ekonomi yang berarti apa yang harus Anda tinggalkan untuk membuat keputusan) untuk setiap keputusan yang mereka buat. Misalnya, biaya peluang untuk membeli mesin game uber seharga $ 10.000 itu adalah hubungan baik (atau mungkin semua hubungan) dengan separuh lainnya selama sekitar enam bulan.

Eric Gunnerson menjelaskan hal ini dengan baik dengan penjelasan -100 poinnya tentang mengapa hal-hal tidak selalu ditambahkan ke produk Microsoft - pada dasarnya fitur memulai 100 poin di lubang sehingga harus menambahkan sedikit nilai untuk dipertimbangkan.

Dengan kata lain, apakah Anda lebih suka memiliki operator daya integral (yang, sejujurnya, pembuat kode setengah layak mana pun dapat menyiapkan dalam sepuluh menit) atau multi-threading ditambahkan ke standar? Bagi saya sendiri, saya lebih suka memiliki yang terakhir dan tidak perlu repot dengan implementasi yang berbeda di bawah UNIX dan Windows.

Saya juga ingin melihat ribuan dan ribuan koleksi perpustakaan standar (hashes, btree, pohon merah-hitam, kamus, peta sembarang, dan sebagainya), tetapi, seperti yang dinyatakan oleh alasan:

Standar adalah perjanjian antara pelaksana dan pemrogram.

Dan jumlah pelaksana di badan standar jauh lebih banyak daripada jumlah pemrogram (atau setidaknya pemrogram yang tidak memahami biaya peluang). Jika semua itu ditambahkan, standar berikutnya C++akan C++215xdan mungkin akan diimplementasikan sepenuhnya oleh pengembang kompilator tiga ratus tahun setelah itu.

Bagaimanapun, itu adalah pemikiran saya (yang agak banyak) tentang masalah ini. Andai saja suara diberikan berdasarkan kuantitas daripada kualitas, saya akan segera membuat semua orang tersingkir. Terima kasih untuk mendengarkan :-)

paxdiablo
sumber
2
FWIW, saya tidak berpikir C ++ mengikuti "Sediakan hanya satu cara untuk melakukan operasi" sebagai kendala. Memang benar, karena misalnya to_stringdan lambda adalah kemudahan untuk hal-hal yang sudah dapat Anda lakukan. Saya kira orang dapat menafsirkan "hanya satu cara untuk melakukan suatu operasi" dengan sangat longgar untuk memungkinkan keduanya, dan pada saat yang sama memungkinkan hampir semua duplikasi fungsi yang dapat dibayangkan, dengan mengatakan "aha! Tidak! Karena kemudahan membuat itu operasi yang sedikit berbeda dari alternatif yang persis sama tetapi lebih bertele-tele! ". Yang benar tentang lambda.
Steve Jessop
@ Steve, ya, itu adalah kata-kata yang buruk di pihak saya. Lebih akurat untuk mengatakan bahwa ada pedoman untuk setiap komite daripada semua komite mengikuti pedoman yang sama. Jawaban yang disesuaikan untuk klarifikasi
paxdiablo
2
Hanya satu poin (dari sedikit): "kode apa pun yang dapat dibuat monyet dalam sepuluh menit". Tentu, dan jika 100 kode monyet (istilah menghina yang bagus, BTW) melakukan itu setiap tahun (mungkin perkiraan yang rendah), kami memiliki 1000 menit yang terbuang. Sangat efisien, bukan?
Jürgen A. Erhard
1
@ Jürgen, itu tidak dimaksudkan untuk menghina (karena saya tidak benar-benar menganggap label itu untuk orang tertentu), itu hanya indikasi yang powtidak benar-benar membutuhkan banyak keterampilan. Tentu saja saya lebih suka standar menyediakan sesuatu yang akan membutuhkan banyak keterampilan, dan menghasilkan lebih banyak menit terbuang percuma jika usaha itu harus diduplikasi.
paxdiablo
2
@ eharo2, cukup ganti "pembuat kode setengah yang layak" dalam teks saat ini dengan "kode monyet". Saya juga tidak berpikir itu menghina tetapi saya pikir yang terbaik adalah berhati-hati dan, sejujurnya, kata-kata saat ini menyampaikan ide yang sama.
paxdiablo
41

Untuk tipe integral dengan lebar tetap, hampir semua pasangan input yang memungkinkan melimpah tipe tersebut. Apa gunanya standarisasi fungsi yang tidak memberikan hasil yang berguna untuk sebagian besar kemungkinan inputnya?

Anda perlu memiliki tipe integer yang besar untuk membuat fungsi tersebut berguna, dan sebagian besar library integer menyediakan fungsinya.


Edit: Dalam komentar pada pertanyaan, static_rtti menulis "Sebagian besar input menyebabkannya meluap? Hal yang sama berlaku untuk exp dan double pow, saya tidak melihat ada yang mengeluh." Ini salah

Mari kita kesampingkan exp, karena itu tidak penting (meskipun itu sebenarnya akan membuat kasus saya lebih kuat), dan fokuslah double pow(double x, double y). Untuk bagian mana dari pasangan (x, y) fungsi ini melakukan sesuatu yang berguna (yaitu, tidak hanya meluap atau meluap)?

Saya sebenarnya akan fokus hanya pada sebagian kecil dari pasangan input yang powmasuk akal, karena itu akan cukup untuk membuktikan poin saya: jika x positif dan | y | <= 1, maka powtidak overflow atau underflow. Ini terdiri dari hampir seperempat dari semua pasangan floating-point (tepatnya setengah dari bilangan floating-point non-NaN adalah positif, dan hanya kurang dari separuh bilangan floating-point non-NaN yang besarnya kurang dari 1). Jelas, ada banyak pasangan masukan lain yang memberikan powhasil berguna, tetapi kami telah memastikan bahwa setidaknya seperempat dari semua masukan.

Sekarang mari kita lihat fungsi bilangan bulat dengan lebar tetap (yaitu non-bignum). Untuk bagian apa masukan tidak meluap begitu saja? Untuk memaksimalkan jumlah pasangan input yang berarti, basis harus ditandatangani dan eksponen tidak ditandatangani. Misalkan basis dan eksponen keduanya memiliki nlebar bit. Kita bisa dengan mudah mendapatkan batasan pada porsi input yang berarti:

  • Jika eksponen 0 atau 1, maka basis apa pun berarti.
  • Jika eksponennya 2 atau lebih besar, maka tidak ada basis yang lebih besar dari 2 ^ (n / 2) yang memberikan hasil yang berarti.

Jadi, dari 2 ^ (2n) pasangan masukan, kurang dari 2 ^ (n + 1) + 2 ^ (3n / 2) menghasilkan hasil yang berarti. Jika kita melihat kemungkinan penggunaan paling umum, bilangan bulat 32-bit, ini berarti bahwa sesuatu di urutan 1/1000 dari satu persen pasangan input tidak meluap begitu saja.

Stephen Canon
sumber
8
Bagaimanapun semua ini bisa diperdebatkan. Hanya karena suatu fungsi tidak valid untuk beberapa atau banyak input tidak membuatnya kurang berguna.
static_rtti
2
@static_rtti: pow(x,y)tidak mengalir ke nol untuk sembarang x jika | y | <= 1. Ada pita input yang sangat sempit (besar x, y hampir -1) yang menyebabkan underflow, tetapi hasilnya masih berarti dalam kisaran itu.
Stephen Canon
2
Setelah memikirkannya lebih lanjut, saya setuju dengan arus bawah. Saya masih berpikir ini tidak relevan dengan pertanyaan itu.
static_rtti
7
@ybungalobill: Mengapa Anda memilih itu sebagai alasan? Secara pribadi, saya lebih menyukai kegunaan untuk sejumlah besar masalah dan pemrogram, kemungkinan untuk membuat versi yang dioptimalkan untuk harware yang lebih cepat daripada implementasi naif yang mungkin akan ditulis oleh sebagian besar pemrogram, dan seterusnya. Kriteria Anda tampaknya sepenuhnya sewenang-wenang, dan, sejujurnya, tidak ada gunanya.
static_rtti
5
@StephenCanon: Sisi baiknya, argumen Anda menunjukkan bahwa implementasi integer yang jelas-benar-dan-optimal powhanyalah tabel pencarian kecil. :-)
R .. GitHub STOP HELPING ICE
11

Karena tidak ada cara untuk merepresentasikan semua pangkat integer dalam int:

>>> print 2**-4
0.0625
Ignacio Vazquez-Abrams
sumber
3
Untuk tipe numerik berukuran terbatas, tidak ada cara untuk merepresentasikan semua kekuatan tipe itu di dalam tipe itu karena luapan. Tetapi pendapat Anda tentang kekuatan negatif lebih valid.
Chris Lutz
1
Saya melihat eksponen negatif sebagai sesuatu yang dapat ditangani oleh implementasi standar, baik dengan mengambil int unsigned sebagai eksponen atau mengembalikan nol ketika eksponen negatif diberikan sebagai input dan int adalah output yang diharapkan.
Dan O
3
atau pisahkan int pow(int base, unsigned int exponent)danfloat pow(int base, int exponent)
Ponkadoodle
4
Mereka bisa saja mendeklarasikannya sebagai perilaku tidak terdefinisi untuk meneruskan bilangan bulat negatif.
Johannes Schaub - litb
2
Pada semua implementasi modern, apapun di luar int pow(int base, unsigned char exponent)itu agak tidak berguna. Entah basisnya adalah 0, atau 1, dan eksponennya tidak penting, itu -1, dalam hal ini hanya eksponen bit terakhir yang penting, atau base >1 || base< -1dalam kasus ini exponent<256pada penalti luapan.
MSalters
9

Itu sebenarnya pertanyaan yang menarik. Satu argumen yang belum saya temukan dalam diskusi adalah kurangnya nilai pengembalian yang jelas untuk argumen tersebut. Mari kita hitung bagaimana int pow_int(int, int)fungsi hypthetical bisa gagal.

  1. Meluap
  2. Hasil tidak ditentukan pow_int(0,0)
  3. Hasil tidak dapat direpresentasikan pow_int(2,-1)

Fungsi ini memiliki setidaknya 2 mode kegagalan. Bilangan bulat tidak dapat mewakili nilai-nilai ini, perilaku fungsi dalam kasus ini perlu ditentukan oleh standar - dan pemrogram perlu mengetahui bagaimana sebenarnya fungsi tersebut menangani kasus-kasus ini.

Secara keseluruhan, meninggalkan fungsi sepertinya satu-satunya pilihan yang masuk akal. Programmer dapat menggunakan versi floating point dengan semua pelaporan kesalahan tersedia.

phoku
sumber
Tapi bukankah dua kasus pertama berlaku untuk powpelampung di antara juga? Ambil dua pelampung besar, naikkan satu dengan kekuatan yang lain dan Anda memiliki Overflow. Dan pow(0.0, 0.0)akan menyebabkan masalah yang sama seperti poin ke-2 Anda. Poin ketiga Anda adalah satu-satunya perbedaan nyata antara menerapkan fungsi daya untuk integer vs float.
numbermaniac
7

Jawaban singkat:

Spesialisasi pow(x, n)ke mana nbilangan asli sering berguna untuk kinerja waktu . Tetapi generik pustaka standar pow()masih berfungsi dengan baik ( mengejutkan! ) Untuk tujuan ini dan sangat penting untuk menyertakan sesedikit mungkin dalam pustaka C standar sehingga dapat dibuat portabel dan semudah mungkin diimplementasikan. Di sisi lain, itu tidak menghentikannya sama sekali dari berada di pustaka standar C ++ atau STL, yang saya cukup yakin tidak ada yang berencana menggunakannya dalam beberapa jenis platform tertanam.

Sekarang, untuk jawaban panjangnya.

pow(x, n)dalam banyak kasus dapat dibuat lebih cepat dengan mengkhususkan diri npada bilangan asli. Saya harus menggunakan implementasi saya sendiri dari fungsi ini untuk hampir setiap program yang saya tulis (tetapi saya menulis banyak program matematika dalam C). Operasi khusus dapat dilakukan O(log(n))tepat waktu, tetapi bila nkecil, versi linier yang lebih sederhana dapat lebih cepat. Berikut implementasi keduanya:


    // 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;
    }

(Saya pergi xdan nilai kembaliannya berlipat ganda karena hasil dari pow(double x, unsigned n)akan masuk ganda sesering pow(double, double)mungkin.)

(Ya, pownitu rekursif, tetapi memecahkan tumpukan sama sekali tidak mungkin karena ukuran tumpukan maksimum kira-kira akan sama log_2(n)dan nmerupakan bilangan bulat. Jika nadalah bilangan bulat 64-bit, itu memberi Anda ukuran tumpukan maksimum sekitar 64. Tidak ada perangkat keras yang sedemikian ekstrim keterbatasan memori, kecuali untuk beberapa PIC cerdik dengan tumpukan perangkat keras yang hanya melakukan panggilan fungsi 3 hingga 8 dalam.)

Mengenai kinerja, Anda akan terkejut dengan kemampuan berbagai taman pow(double, double). Saya menguji seratus juta iterasi pada IBM Thinkpad saya yang berusia 5 tahun dengan xangka iterasi yang nsama dan sama dengan 10. Dalam skenario ini, pown_lmenang. glibc pow()membutuhkan 12,0 detik pengguna, pown7,4 detik pengguna, dan pown_lhanya 6,5 ​​detik pengguna. Jadi itu tidak terlalu mengejutkan. Kami kurang lebih mengharapkan ini.

Kemudian, saya biarkan xkonstan (saya setel menjadi 2,5), dan saya mengulang ndari 0 hingga 19 seratus juta kali. Kali ini, secara tidak terduga, glibc powmenang, dan dengan telak! Hanya butuh 2.0 detik pengguna. Saya pownmengambil 9,6 detik, dan pown_lmengambil 12,2 detik. Apa yang terjadi disini? Saya melakukan tes lain untuk mencari tahu.

Saya melakukan hal yang sama seperti di atas hanya dengan xsetara dengan satu juta. Kali ini, pownmenang di 9,6s. pown_lmengambil 12.2s dan glibc pow mengambil 16.3s. Sekarang, sudah jelas! glibc powberkinerja lebih baik daripada ketiganya saat xrendah, tetapi terburuk saat xtinggi. Saat xtinggi, pown_lberkinerja terbaik saat nrendah, dan pownberkinerja terbaik saat xtinggi.

Jadi, inilah tiga algoritme berbeda, masing-masing mampu berkinerja lebih baik daripada yang lain dalam situasi yang tepat. Jadi, pada akhirnya, mana yang akan digunakan kemungkinan besar tergantung pada bagaimana Anda berencana menggunakan pow, tetapi menggunakan versi yang tepat itu sepadan, dan memiliki semua versi itu bagus. Bahkan, Anda bahkan dapat mengotomatiskan pilihan algoritme dengan fungsi seperti ini:

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);
}

Selama x_expecteddan n_expectedmerupakan konstanta yang diputuskan pada waktu kompilasi, bersama dengan kemungkinan beberapa peringatan lainnya, kompiler pengoptimalan yang bernilai garamnya akan secara otomatis menghapus seluruh pown_autopemanggilan fungsi dan menggantinya dengan pilihan yang sesuai dari ketiga algoritme. (Sekarang, jika Anda benar-benar akan mencoba menggunakan ini, Anda mungkin harus sedikit bermain-main dengannya, karena saya tidak benar-benar mencoba menyusun apa yang saya tulis di atas.;))

Di sisi lain, glibc pow berfungsi dan glibc sudah cukup besar. Standar C seharusnya portabel, termasuk ke berbagai perangkat yang disematkan (pada kenyataannya pengembang yang disematkan di mana-mana umumnya setuju bahwa glibc sudah terlalu besar untuk mereka), dan itu tidak bisa portabel jika untuk setiap fungsi matematika sederhana perlu menyertakan setiap algoritma alternatif yang mungkin bisa digunakan. Jadi, itulah mengapa tidak ada dalam standar C.

catatan kaki: Dalam pengujian kinerja waktu, saya memberikan fungsi saya tanda pengoptimalan yang relatif murah hati ( -s -O2) yang cenderung sebanding dengan, jika tidak lebih buruk dari, apa yang mungkin digunakan untuk mengkompilasi glibc di sistem saya (archlinux), jadi hasilnya mungkin adil. Untuk tes yang lebih ketat, aku harus mengkompilasi glibc diri saya dan saya reeeally tidak merasa seperti melakukan hal itu. Saya dulu menggunakan Gentoo, jadi saya ingat berapa lama waktu yang dibutuhkan, bahkan ketika tugasnya otomatis . Hasilnya cukup meyakinkan (atau agak tidak meyakinkan) bagi saya. Anda tentu saja dipersilakan untuk melakukannya sendiri.

Putaran bonus: Spesialisasi dari pow(x, n)semua bilangan bulat sangat penting jika diperlukan keluaran bilangan bulat yang tepat, yang memang terjadi. Pertimbangkan mengalokasikan memori untuk larik berdimensi-N dengan elemen p ^ N. Mendapatkan p ^ N off bahkan satu akan menghasilkan kemungkinan segfault yang terjadi secara acak.

enigmaticPhysicist
sumber
Saya kira jika Anda menyingkirkan rekursi, Anda akan menghemat waktu yang diperlukan untuk alokasi tumpukan. Dan ya, kami memiliki situasi di mana pow memperlambat segalanya dan kami harus menerapkan kekuatan kami sendiri.
Sambatyon
"Tidak ada yang memiliki keterbatasan memori yang ekstrim" adalah salah. PIC sering memiliki tumpukan panggilan terbatas untuk maksimum 3 (contoh adalah PIC10F200) hingga 8 (contoh adalah 16F722A) panggilan (PIC menggunakan tumpukan perangkat keras untuk panggilan fungsi).
12431234123412341234123
oh, man itu brutal lol. Oke, jadi ini tidak akan berfungsi pada PIC tersebut.
enigmaticPhysicist
Untuk basis integer dan juga power, seperti pertanyaan yang ditanyakan, kompiler (gcc dan clang) akan dengan mudah menghasilkan loop tanpa cabang dari implementasi iteratif (bukan rekursif). Ini untuk menghindari kesalahan prediksi cabang dari setiap bit n. godbolt.org/z/L9Kb98 . gcc dan clang gagal mengoptimalkan definisi rekursif Anda menjadi loop sederhana, dan sebenarnya melakukan branch pada setiap bit n. (Karena pown_iter(double,unsigned)mereka masih bercabang, tetapi implementasi SSE2 atau SSE4.1 tanpa cabang harus dimungkinkan di x86 asm atau dengan intrinsik C. Tetapi bahkan itu lebih baik daripada rekursi)
Peter Cordes
Sial, sekarang saya harus melakukan tolok ukur lagi dengan versi berbasis loop hanya untuk memastikan. Saya akan berpikir tentang hal ini.
enigmaticPhysicist
6

Salah satu alasan C ++ agar tidak memiliki kelebihan beban tambahan adalah agar kompatibel dengan C.

C ++ 98 memiliki fungsi seperti double pow(double, int), tetapi ini telah dihapus di C ++ 11 dengan argumen bahwa C99 tidak menyertakannya.

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

Mendapatkan hasil yang sedikit lebih akurat juga berarti mendapatkan hasil yang sedikit berbeda .

Bo Persson
sumber
3

Dunia terus berkembang dan begitu pula bahasa pemrogramannya. Bagian keempat dari desimal C TR ¹ menambahkan beberapa fungsi lagi <math.h>. Dua kelompok fungsi ini mungkin menarik untuk pertanyaan ini:

  • The pownfungsi, yang mengambil sejumlah floating point dan intmax_teksponen.
  • The powrfungsi, yang mengambil dua poin angka floating ( xdan y) dan menghitung xdengan kekuatan ydengan rumus exp(y*log(x)).

Tampaknya orang-orang standar pada akhirnya menganggap fitur-fitur ini cukup berguna untuk diintegrasikan ke dalam pustaka standar. Namun, rasionalnya adalah bahwa fungsi ini direkomendasikan oleh standar ISO / IEC / IEEE 60559: 2011 untuk bilangan floating point biner dan desimal. Saya tidak dapat mengatakan dengan pasti "standar" apa yang diikuti pada saat C89, tetapi evolusi masa depan <math.h>mungkin akan sangat dipengaruhi oleh evolusi masa depan ISO / IEC / IEEE 60559 .

Perhatikan bahwa bagian keempat dari TR desimal tidak akan disertakan dalam C2x (revisi C mayor berikutnya), dan mungkin akan disertakan nanti sebagai fitur opsional. Belum ada niat apa pun yang saya ketahui untuk menyertakan bagian TR ini dalam revisi C ++ mendatang.


¹ Anda dapat menemukan beberapa dokumentasi pekerjaan yang sedang berlangsung di sini .

Morwenn
sumber
Apakah ada implementasi yang masuk akal di mana penggunaan powndengan eksponen lebih besar dari yang LONG_MAXseharusnya menghasilkan nilai yang berbeda dari penggunaan LONG_MAX, atau di mana nilai yang lebih kecil dari LONG_MINseharusnya menghasilkan nilai yang berbeda LONG_MIN? Saya ingin tahu manfaat apa yang didapat dari menggunakan intmax_teksponen?
supercat
@supercat Tidak tahu, maaf.
Morwenn
Mungkin ada baiknya untuk menyebutkan bahwa, melihat Standard, tampaknya juga mendefinisikan fungsi "crpown" opsional yang akan, jika ditentukan, menjadi versi yang benar dari "pown"; Standar sebaliknya tidak menentukan tingkat akurasi yang diperlukan. Menerapkan "pown" yang cepat dan cukup presisi itu mudah, tetapi memastikan pembulatan yang benar di semua kasus cenderung jauh lebih mahal.
supercat
2

Mungkin karena ALU prosesor tidak mengimplementasikan fungsi seperti itu untuk bilangan bulat, tetapi ada instruksi FPU seperti itu (seperti yang ditunjukkan Stephen, sebenarnya ini adalah pasangan). Jadi sebenarnya lebih cepat untuk melakukan cast menjadi double, memanggil kekuatan dengan double, lalu menguji overflow dan cast back, daripada menerapkannya menggunakan aritmatika integer.

(untuk satu hal, logaritma mengurangi pangkat menjadi perkalian, tetapi logaritma bilangan bulat kehilangan banyak akurasi untuk sebagian besar input)

Stephen benar bahwa pada prosesor modern ini tidak lagi benar, tetapi standar C ketika fungsi matematika dipilih (C ++ baru saja menggunakan fungsi C) sekarang berapa, 20 tahun?

Ben Voigt
sumber
5
Saya tidak tahu arsitektur apa pun saat ini dengan instruksi FPU untuk pow. x86 memiliki sebuah y log2 xinstruksi ( fyl2x) yang dapat digunakan sebagai bagian pertama dari sebuah powfungsi, tetapi sebuah powfungsi yang ditulis dengan cara tersebut membutuhkan ratusan siklus untuk dieksekusi pada perangkat keras saat ini; rutinitas eksponensial integer yang ditulis dengan baik beberapa kali lebih cepat.
Stephen Canon
Saya tidak tahu bahwa "ratusan" itu akurat, tampaknya sekitar 150 siklus untuk fyl2x kemudian f2xm1 pada sebagian besar CPU modern dan itu sejalan dengan instruksi lain. Tetapi Anda benar bahwa implementasi integer yang disetel dengan baik seharusnya jauh lebih cepat (hari ini) karena IMUL telah dipercepat lebih banyak daripada instruksi floating-point. Kembali ketika standar C ditulis, IMUL cukup mahal dan menggunakannya dalam satu lingkaran mungkin membutuhkan waktu lebih lama daripada menggunakan FPU.
Ben Voigt
2
Mengubah suara saya karena koreksi; Namun, perlu diingat (a) bahwa standar C mengalami revisi besar (termasuk perluasan besar pustaka matematika) pada tahun 1999, dan (b) bahwa standar C tidak ditulis untuk arsitektur prosesor tertentu - kehadiran atau tidak adanya instruksi FPU pada x86 pada dasarnya tidak ada hubungannya dengan fungsionalitas apa yang dipilih oleh komite C untuk distandarisasi.
Stephen Canon
Ini tidak terkait dengan arsitektur apa pun, benar, tetapi biaya relatif dari interpolasi tabel pencarian (umumnya digunakan untuk implementasi floating point) dibandingkan dengan penggandaan integer telah berubah cukup banyak untuk semua arsitektur yang saya kira.
Ben Voigt
1

Berikut adalah implementasi O (log (n)) yang sangat sederhana dari pow () yang bekerja untuk semua tipe numerik, termasuk integer :

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;
}

Ini lebih baik daripada implementasi O (log (n)) enigmaticPhysicist karena tidak menggunakan rekursi.

Ini juga hampir selalu lebih cepat daripada implementasi liniernya (selama p> ~ 3) karena:

  • itu tidak membutuhkan memori tambahan
  • itu hanya melakukan ~ 1.5x lebih banyak operasi per loop
  • itu hanya melakukan ~ 1.25x lebih banyak pembaruan memori per loop
serg06
sumber
-2

Faktanya, memang demikian.

Sejak C ++ 11 ada implementasi template dari pow(int, int)--- dan bahkan kasus yang lebih umum, lihat (7) di http://en.cppreference.com/w/cpp/numeric/math/pow


EDIT: para puritan mungkin berpendapat ini tidak benar, karena sebenarnya ada pengetikan "yang dipromosikan" yang digunakan. Dengan satu atau lain cara, seseorang mendapatkan inthasil yang benar , atau kesalahan, pada intparameter.

Dima Pasechnik
sumber
2
ini tidak benar. (7) kelebihan beban pow ( Arithmetic1 base, Arithmetic2 exp )yang akan dilemparkan ke doubleatau long doublejika Anda telah membaca deskripsi: "7) Satu set kelebihan beban atau template fungsi untuk semua kombinasi argumen jenis aritmatika tidak tercakup oleh 1-3). Jika ada argumen memiliki tipe integral, itu diubah menjadi ganda. Jika ada argumen yang panjangnya dobel, maka tipe kembalian Dipromosikan juga ganda panjang, jika tidak tipe kembaliannya selalu ganda. "
phuclv
apa yang salah di sini? Saya hanya mengatakan bahwa saat ini (sejak C ++ 11) pow templated ( , ) ada di perpustakaan standar, yang tidak terjadi pada tahun 2010.
Dima Pasechnik
5
Tidak, tidak. Templeates mempromosikan jenis ini menjadi double atau long double. Jadi itu bekerja pada ganda di bawahnya.
Trismegistos
1
@Trismegistos Ini masih mengizinkan parameter int. Jika template ini tidak ada di sana, meneruskan parameter int menyebabkannya menafsirkan bit di int sebagai float, menyebabkan hasil yang tidak diharapkan secara arbitrer. Hal yang sama terjadi dengan nilai masukan campuran. eg pow(1.5f, 3)= 1072693280but pow(1.5f, float(3))=3.375
Mark Jeronimus
2
OP meminta int pow(int, int), tetapi C ++ 11 hanya menyediakan double pow(int, int). Lihat penjelasan @phuclv.
xuhdev
-4

Alasan yang sangat sederhana:

5^-2 = 1/25

Segala sesuatu di perpustakaan STL didasarkan pada hal-hal paling akurat dan kuat yang bisa dibayangkan. Tentu, int akan kembali ke nol (dari 1/25) tetapi ini akan menjadi jawaban yang tidak akurat.

Saya setuju, itu aneh dalam beberapa kasus.

Jason A.
sumber
3
Membutuhkan argumen kedua yang tidak ditandatangani jelas diperlukan. Ada banyak aplikasi yang hanya membutuhkan pangkat integer non-negatif.
enigmaticPhysicist