🙅🏼 👨🏽‍🤝‍👨🏼 🔎 Aritmatika presisi sewenang-wenang di Erlang 🙆🏽 ⛑️ 💈

@rawpixel

Bahkan anak sekolah sadar akan adanya berbagai sistem bilangan dan fakta bahwa tidak setiap pecahan desimal terbatas adalah pecahan terbatas dalam sistem bilangan biner. Hanya sedikit orang berpikir bahwa karena fakta ini, operasi pada float dan double tidak tepat.

Jika kita berbicara tentang Erlang, maka, seperti banyak bahasa lain, ia mengimplementasikan standar IEEE754 untuk float, sedangkan tipe Integer standar di Erlang diimplementasikan menggunakan aritmatika presisi sewenang-wenang. Namun, saya ingin memiliki tidak hanya bigint, tetapi juga kemampuan untuk beroperasi dengan angka-angka yang rasional, kompleks dan mengambang dengan akurasi yang diperlukan.

Artikel ini memberikan tinjauan minimal teori pengkodean angka floating-point dan contoh paling menonjol dari efek yang muncul. Solusi yang memberikan akurasi operasi yang diperlukan melalui transisi ke representasi titik tetap dirancang sebagai perpustakaan EAPA (Erlang Arbitrary Precision Arithmetic), yang dirancang untuk memenuhi kebutuhan aplikasi keuangan yang dikembangkan pada Erlang / Elixir.

Standar, standar, standar ...

Saat ini, standar utama untuk aritmatika titik-mengambang biner adalah IEEE754, yang banyak digunakan dalam rekayasa dan pemrograman. Ini mendefinisikan empat format presentasi:

presisi tunggal 32 bit
presisi ganda 64 bit
single-extended precision> = 43 bit (jarang digunakan)
double-extended precision> = 79 bit (biasanya 80 bit digunakan)
dan empat mode pembulatan:
Pembulatan, cenderung ke keseluruhan terdekat.
Pembulatan cenderung ke nol.
Pembulatan cenderung ke + ∞
Pembulatan menuju -∞

Sebagian besar mikroprosesor modern diproduksi dengan implementasi perangkat keras dari representasi variabel nyata dalam format IEEE754. Format presentasi membatasi batas ukuran suatu angka, dan mode pembulatan memengaruhi akurasi. Pemrogram seringkali tidak dapat mengubah perilaku perangkat keras dan mengimplementasikan bahasa pemrograman. Misalnya, implementasi Erlang resmi menyimpan float dalam 3 kata pada mesin 64-bit dan dalam 4 kata pada 32-bit.

Seperti disebutkan di atas, angka-angka dalam format IEEE754 adalah himpunan terbatas ke mana serangkaian bilangan real yang tak terbatas dipetakan, sehingga angka asli dapat disajikan dalam format IEEE754 dengan kesalahan.

Sebagian besar angka ketika ditampilkan pada himpunan terbatas memiliki kesalahan relatif stabil dan kecil. Jadi, untuk float adalah 11.920928955078125e-6%, dan untuk double - 2.2204460492503130808472633361816e-14%. Dalam kehidupan programmer, sebagian besar tugas sehari-hari yang harus diselesaikan memungkinkan kami mengabaikan kesalahan ini, meskipun harus dicatat bahwa bahkan dalam tugas sederhana Anda dapat menginjak penggaruk, karena besarnya kesalahan absolut masing-masing dapat mencapai 10 ³¹ dan 10 ²⁹² untuk float dan double, masing-masing, menyebabkan kesulitan dalam perhitungan.

Ilustrasi efek

Dari informasi umum hingga bisnis. Mari kita coba mereproduksi efek yang muncul di Erlang.

Semua contoh di bawah ini dirancang sebagai ct-test.

Pembulatan dan hilangnya keakuratan

Mari kita mulai dengan klasik - penambahan dua angka: 0,1 + 0,2 = ?:

t30000000000000004(_)-> ["0.30000000000000004"] = io_lib:format("~w", [0.1 + 0.2]).

Hasil penambahan sedikit berbeda dari yang diharapkan secara intuitif, dan tes berhasil. Mari kita coba mencapai hasil yang tepat. Tulis ulang tes menggunakan EAPA:

 t30000000000000004_eapa(_)-> %% prec = 1 symbols after coma X = eapa_int:with_val(1, <<"0.1">>), Y = eapa_int:with_val(1, <<"0.2">>), <<"0.3">> = eapa_int:to_float(1, eapa_int:add(X, Y)).

Tes ini juga berhasil, menunjukkan bahwa masalahnya telah teratasi.
Mari kita lanjutkan eksperimen, tambahkan nilai yang sangat kecil ke 1.0:

 tiny(_)-> X = 1.0, Y = 0.0000000000000000000000001, 1.0 = X + Y.

Seperti yang Anda lihat, peningkatan kami tidak diperhatikan. Kami sedang mencoba untuk memperbaiki masalah, secara simultan mengilustrasikan salah satu fitur perpustakaan - penskalaan otomatis:

 tiny_eapa(_)-> X1 = eapa_int:with_val(1, <<"1.0">>), X2 = eapa_int:with_val(25, <<"0.0000000000000000000000001">>), <<"1.0000000000000000000000001">> = eapa_int:to_float(eapa_int:add(X1, X2)).

Bit Grid Overflow

Selain masalah yang terkait dengan jumlah kecil, melimpah adalah masalah yang jelas dan signifikan.

 float_overflow(_) -> 1.0 = 9007199254740991.0 - 9007199254740990.0, 1.0 = 9007199254740992.0 - 9007199254740991.0, 0.0 = 9007199254740993.0 - 9007199254740992.0, 2.0 = 9007199254740994.0 - 9007199254740993.0.

Seperti yang dapat Anda lihat dari tes, pada titik tertentu perbedaannya tidak lagi sama dengan 1,0, yang jelas merupakan masalah. EAPA juga memecahkan masalah ini:

 float_overflow_eapa(_)-> X11 = eapa_int:with_val(1, <<"9007199254740992.0">>), X21 = eapa_int:with_val(1, <<"9007199254740991.0">>), <<"1.0">> = eapa_int:to_float(1, eapa_int:sub(X11, X21)), X12 = eapa_int:with_val(1, <<"9007199254740993.0">>), X22 = eapa_int:with_val(1, <<"9007199254740992.0">>), <<"1.0">> = eapa_int:to_float(1, eapa_int:sub(X12, X22)), X13 = eapa_int:with_val(1, <<"9007199254740994.0">>), X23 = eapa_int:with_val(1, <<"9007199254740993.0">>), <<"1.0">> = eapa_int:to_float(1, eapa_int:sub(X13, X23)).

Pengurangan berbahaya

Tes berikut menunjukkan terjadinya reduksi yang berbahaya. Proses ini disertai dengan penurunan katastropik dalam akurasi perhitungan dalam operasi di mana nilai yang dihasilkan jauh lebih sedikit daripada input. Dalam kasus kami, hasil pengurangan 1.

Kami menunjukkan bahwa di Erlang masalah ini ada:

 reduction(_)-> X = float(87654321098765432), Y = float(87654321098765431), 16.0 = XY. %% has to be 1.0

Ternyata 16.0 bukannya 1.0 yang diharapkan. Mari kita coba untuk memperbaiki situasi ini:

 reduction_eapa(_)-> X = eapa_int:with_val(1, <<"87654321098765432">>), Y = eapa_int:with_val(1, <<"87654321098765431">>), <<"1.0">> = eapa_int:to_float(eapa_int:sub(X, Y)).

Fitur lain dari aritmatika floating point di Erlang

Mari kita mulai dengan mengabaikan nol negatif.

 eq(_)-> true = list_to_float("0.0") =:= list_to_float("-0.0").

Hanya ingin mengatakan bahwa EAPA mempertahankan perilaku ini:

 eq_eapa(_)-> X = eapa_int:with_val(1, <<"0.0">>), Y = eapa_int:with_val(1, <<"-0.0">>), true = eapa_int:eq(X, Y).

karena ini valid. Erlang tidak memiliki sintaks yang jelas dan pemrosesan NaN dan infinitas, yang memunculkan sejumlah fitur, misalnya, ini:

 1> math:sqrt(list_to_float("-0.0")). 0.0

Poin berikutnya adalah fitur pemrosesan angka besar dan kecil. Mari kita coba mereproduksi untuk anak kecil:

 2> list_to_float("0."++lists:duplicate(322, $0)++"1"). 1.0e-323 3> list_to_float("0."++lists:duplicate(323, $0)++"1"). 0.0

dan untuk jumlah besar:

 4> list_to_float("1"++lists:duplicate(308, $0)++".0"). 1.0e308 5> list_to_float("1"++lists:duplicate(309, $0)++".0"). ** exception error: bad argument

Berikut beberapa contoh untuk jumlah kecil:

 6> list_to_float("0."++lists:duplicate(322, $0)++"123456789"). 1.0e-323 7> list_to_float("0."++lists:duplicate(300, $0)++"123456789"). 1.23456789e-301

 8> 0.123456789e-100 * 0.123456789e-100. 1.524157875019052e-202 9> 0.123456789e-200 * 0.123456789e-200. 0.0

Contoh di atas mengkonfirmasi kebenaran untuk proyek Erlang: uang tidak dapat dihitung dalam IEEE754.

EAPA (Erlang Arbitrary-Precision Arithmetic)

EAPA adalah ekstensi NIF yang ditulis dalam Rust. Saat ini, repositori EAPA menyediakan antarmuka eapa_int yang paling sederhana dan nyaman untuk bekerja dengan angka titik tetap. Fitur-fitur eapa_int termasuk yang berikut:

Kurangnya efek pengkodean IEEE754
Dukungan angka besar
Akurasi yang dapat dikonfigurasi hingga 126 tempat desimal. (dalam implementasi saat ini)
Autoscaling
Dukungan untuk semua operasi dasar pada angka
Kurang lebih pengujian lengkap, termasuk berbasis properti.

Antarmuka eapa_int :

with_val/2 - terjemahan angka floating-point ke representasi tetap, yang dapat digunakan, termasuk dengan aman, di json, xml.
to_float/2 - terjemahan nomor titik tetap menjadi angka titik mengambang dengan akurasi yang diberikan.
to_float/1 - menerjemahkan angka titik tetap ke angka titik mengambang.
add/2 - jumlah dari dua angka
sub/2 - perbedaan
mul/2 - perkalian
divp/2 - divisi
min/2 - angka minimum
max/2 - jumlah maksimal
eq/2 - periksa kesetaraan angka
lt/2 - periksa apakah angkanya kurang
lte/2 - memeriksa kurang dari sama
gt/2 - periksa apakah angkanya lebih besar
gte/2 - memeriksa lebih dari sama

Kode EAPA dapat ditemukan di repositori https://github.com/Vonmo/eapa

Kapan Anda harus menggunakan eapa_int? Misalnya, jika aplikasi Anda berfungsi dengan uang atau Anda perlu dengan mudah dan akurat melakukan operasi komputasi pada angka-angka seperti 92233720368547758079223372036854775807.92233720368547758079223372036854775807, Anda dapat menggunakan EAPA dengan aman.

Seperti solusi apa pun, EAPA adalah kompromi. Kami mendapatkan akurasi yang diperlukan dengan mengorbankan memori dan kecepatan komputasi. Uji kinerja dan statistik yang dikumpulkan pada sistem nyata menunjukkan bahwa sebagian besar operasi dilakukan dalam kisaran 3-30 μs. Poin ini juga harus dipertimbangkan ketika memilih antarmuka titik tetap EAPA.

Kesimpulan

Tentu saja, itu jauh dari selalu perlu untuk memecahkan masalah seperti pada Erlang atau Elixir, tetapi ketika masalah muncul dan alat yang sesuai tidak ditemukan, Anda harus menemukan solusi.
Artikel ini adalah upaya untuk berbagi dengan komunitas alat dan pengalaman, dengan harapan bahwa bagi sebagian orang perpustakaan ini akan berguna dan membantu menghemat waktu.
Apa pendapat Anda tentang uang di Erlang?

PS Bekerja dengan bilangan rasional dan kompleks, serta akses asli ke Integer, Float, Complex, jenis-jenis rasional akurasi arbitrer akan dibahas dalam publikasi berikut. Jangan beralih!

Bahan terkait:

Aritmatika presisi sewenang-wenang di Erlang