Bukan rahasia lagi bahwa informasi keuangan (akun, posting dan pembukuan lainnya) tidak terlalu ramah dengan angka floating point, dan banyak artikel merekomendasikan menggunakan aritmatika titik tetap. Di Java, format ini, pada kenyataannya, hanya diwakili oleh kelas BigDecimal, yang tidak selalu dapat digunakan karena alasan kinerja. Kami harus mencari alternatif. Artikel ini menjelaskan perpustakaan Java yang ditulis sendiri untuk melakukan operasi aritmatika pada angka presisi-tetap. Perpustakaan diciptakan untuk bekerja dalam aplikasi keuangan berkinerja tinggi dan memungkinkan Anda untuk bekerja dengan akurasi 9 desimal sambil mempertahankan kinerja yang dapat diterima. Tautan ke sumber dan tolok ukur diberikan di akhir artikel.

Aritmatika titik mengambang

Komputer modern dapat melakukan operasi aritmatika hanya dengan akurasi terbatas. Ini adalah perangkat diskrit yang mungkin tidak berfungsi dengan semua angka yang mungkin, tetapi hanya dengan sebagian himpunan bagiannya yang dapat dihitung. Format yang paling umum untuk bekerja dengan bilangan real dalam memori komputer adalah titik mengambang (biner) - titik mengambang (biner), ketika angka disimpan dalam bentuk M * 2 ^ E, di mana M dan E adalah bilangan bulat mantissa dan urutan bilangan. Tetapi beberapa angka, seperti 0,1, tidak dapat direpresentasikan secara akurat dalam format ini. Oleh karena itu, dalam proses perhitungan yang rumit, beberapa kesalahan pasti terakumulasi. Artinya, hasil perhitungan mesin, katakan 0,1 + 0,1 + 0,1, tidak bertepatan dengan 0,3 matematis yang benar. Mengingat hal di atas, saat pemrograman aritmatika kompleks, Anda dapat mengikuti beberapa strategi:

Strategi 1 - abaikan. Abaikan kesalahan, pertimbangkan semua operasi idealnya matematis dan berharap akurasi yang tersedia cukup untuk hasil yang dapat diterima. Opsi paling umum.

Strategi 2 - menghitung dengan cermat. Rumus untuk menghitung kesalahan mesin telah dikenal selama beberapa dekade. Mereka memungkinkan untuk memperkirakan kesalahan relatif dari operasi aritmatika dari atas. Mungkin, inilah yang harus Anda lakukan untuk simulasi numerik serius. Masalahnya adalah itu sangat memakan waktu. Faktanya, setiap + - * / karakter dalam kode harus disertai dengan perhitungan kesalahan. Anda harus memperhitungkan semua dependensi antara perhitungan dan ulangi prosedur setiap kali Anda mengubah kode.

Strategi 3 - gunakan titik desimal (floating desimal point) alih-alih biner. Artinya, simpan angka-angka dalam bentuk M * 10 ^ E. Ini tidak menyelesaikan masalah kesalahan (mantissa masih dibulatkan ke sejumlah digit signifikan), tetapi setidaknya semua angka "sederhana" untuk seseorang (seperti 1,1) kini secara akurat terwakili dalam memori. Pengembaliannya akan menjadi kinerja. Setiap normalisasi angka (yaitu, penurunan setara dalam mantra dan peningkatan urutan) memerlukan pembagian dengan kekuatan 10, yang tidak terlalu cepat, tidak seperti pembagian dengan kekuatan 2. Dan Anda harus menormalkan banyak - dengan setiap penambahan atau pengurangan dengan urutan yang berbeda.

Strategi 4 - gunakan titik tetap (titik desimal tetap). Penyederhanaan strategi 3, ketika kita memperbaiki urutan E. Dalam hal ini, normalisasi tidak diperlukan untuk penambahan / pengurangan. Selain itu, semua perhitungan akan memiliki kesalahan absolut yang sama. Artikel ini dikhususkan untuk strategi ini.

Aritmatika titik tetap

Berbeda dengan fisika, di mana kesalahan relatif adalah penting, hanya mutlak diperlukan dalam keuangan. Jika, setelah transaksi keuangan yang rumit, pelanggan ditagih $ 1.000.000,23 sementara dia mengharapkan $ 1.000.000, 18, maka beberapa kesulitan mungkin timbul. Penjelasan seperti "mengapa Anda perlu akurasi dalam 8 digit signifikan ??" mungkin tidak naik Dan intinya di sini bukan dalam 5 sen kerugian (untuk berbuat sebaliknya, "mendukung" klien tidak jauh lebih baik), tetapi dalam inkonsistensi dalam akuntansi. Oleh karena itu, aturan perhitungan dan pembulatan secara jelas ditentukan antara para pihak, dan artefak dari penggunaan variabel ganda dan mengambang terkadang menyulitkan kehidupan.

Java memiliki kelas standar untuk aritmatika titik tetap - BigDecimal. Ada dua masalah dengan itu: itu lambat (karena universalitasnya) dan tidak stabil. Ketidakstabilan berarti bahwa operasi apa pun mengalokasikan objek pada heap. Memilih dan melepaskan dalam hal suatu objek membutuhkan sedikit waktu, tetapi perhitungan intensif dalam kode "panas" membuat beban yang layak pada GC, yang dalam beberapa kasus tidak dapat diterima. Anda dapat mengandalkan analisis melarikan diri dan skalarisasi, tetapi mereka sangat tidak stabil dalam arti bahwa bahkan sedikit perubahan dalam kode atau JIT (seperti malas memuat implementasi antarmuka baru) dapat mengubah seluruh struktur inline terbalik, dan metode ini bekerja dengan baik beberapa menit yang lalu, tiba-tiba mulai mengalokasikan memori dengan marah.
UPD karena pertanyaan dalam komentar: Alasan utama untuk meninggalkan BigDecimal dan BigInteger sama sekali bukan kinerja komputasi yang rendah, tetapi kurangnya stabilitas dan pemilihan objek.

Perpustakaan yang dijelaskan adalah hasil dari bosan menulis ulang aritmatika non-memori titik-tetap dari awal untuk setiap perusahaan baru, dan saya memutuskan untuk menulis perpustakaan saya sendiri untuk insourcing berikutnya.

Saya akan segera menunjukkan contoh penggunaan sebelum beralih ke detail implementasi:

public class Sample { private final Decimal margin; private final Quantity cumQuantity = new Quantity(); private final Quantity contraQuantity = new Quantity(); private final Quantity cumContraQuantity = new Quantity(); private final Price priceWithMargin = new Price(); private final Price avgPrice = new Price(); public Sample(int marginBp) { // 1 + margin / 10000 this.margin = Decimal.create(marginBp).divRD(10000L).add(1); } public Price calculateAvgPrice(Quantity[] quantities, Price[] prices) { cumQuantity.set(0); contraQuantity.set(0); // avg = sum(q * p * margin) / sum(q) for (int i = 0; i < quantities.length; i++) { cumQuantity.add(quantities[i]); priceWithMargin.set(prices[i]).mulRD(margin); contraQuantity.set(quantities[i]).mulRD(priceWithMargin); cumContraQuantity.add(contraQuantity); } return avgPrice.quotientRD(cumContraQuantity, cumQuantity); } public static void main(String[] args) throws ParseException { Price p1 = Price.create("1.5"); Price p2 = Price.create(1.6); Quantity q1 = Quantity.create("100"); Quantity q2 = Quantity.create(200); // apply 0.05% margin to the prices Sample sample = new Sample(5); System.out.println(sample.calculateAvgPrice(new Quantity[]{q1, q2}, new Price[]{p1, p2})); } } 

Ide implementasi

Jadi, kita membutuhkan pembungkus yang bisa berubah dari integer primitive, lebih tepatnya, long'a, yang akan memberi kita hampir 19 digit signifikan (cukup untuk integer dan bagian fraksional). Panjang, yang kami maksud adalah N desimal. Misalnya, dengan N = 2, angka 2,56 disimpan sebagai 256 (biner 100000000). Nomor negatif disimpan sebagai standar, dalam kode tambahan:

-2,56
-256

(Selanjutnya, huruf miring menunjukkan angka dan perhitungan "matematis", dan dengan tebal representasi internal mereka)

Bagi saya bermanfaat juga untuk memasukkan NaN sebagai nilai terpisah, yang dikembalikan jika terjadi kesalahan aritmatika (bukan pengecualian atau sampah). NaN direpresentasikan secara internal sebagai Long.MIN_VALUE , "diperbanyak" melalui semua operasi dan memungkinkan untuk menentukan inversi tanda untuk semua angka yang tersisa.

Mari kita coba perkirakan algoritma operasi aritmatika untuk kasus ketika N = 2.

Penambahan dan pengurangan tidak membutuhkan gerakan tambahan, cukup gunakan nilai-nilainya seperti apa adanya:

1,20 + 2,30 = 3,50
120 + 230 = 350

Perkalian dan pembagian membutuhkan normalisasi tambahan, yaitu, perkalian / pembagian sebesar 10 ^ N (oleh 100 dalam contoh kita)

1.20 * 2.00 = 2.40
120 * 200/100 = 240

1.20 / 2.00 = 0.60
100 * 120/200 = 60

Divisi tambahan bukanlah operasi tercepat. Tetapi dalam kasus ini, ini adalah pembagian dengan konstanta, karena kami sebelumnya menetapkan N = 2 dan 10 ^ N = 100. Pembagian dengan konstanta, terutama oleh "cantik" (tipe 10), dioptimalkan secara intensif dalam CPU dan jauh lebih cepat daripada pembagian dengan angka acak. Kami melakukan banyak divisi dengan 10 setiap kali kami mengonversi angka apa pun menjadi string (misalnya, dalam log), dan produsen CPU mengetahuinya ( untuk rincian lebih lanjut tentang pengoptimalan, lihat "Pembagian dengan konstanta").

Untuk mengkonsolidasikan pemahaman tentang apa yang kita lakukan, saya akan memberikan satu operasi lagi: inversi nomor, yaitu 1 / x. Ini adalah kasus pembagian khusus, Anda hanya perlu mengirimkan 1,00 dalam format kami dan jangan lupa untuk menormalkan:

1,00 / 2,00 = 0,50
100 * 100/200 = 50

Nah, sementara semuanya cukup sederhana, mari kita coba menyelidiki detailnya.

Pembulatan

Mari kita coba menggambar nomor lain:

1,00 / 3,00 = 0,33
100 * 100/300 = 33

Hasil matematika yang jujur ​​terletak antara 0,33 dan 0,34, tetapi kita tidak dapat membayangkannya dengan tepat. Jalan mana yang harus dilalui? Biasanya dibulatkan menjadi 0, dan ini adalah cara tercepat (didukung perangkat keras). Tetapi, kembali ke masalah keuangan nyata, ini tidak selalu terjadi. Biasanya, saat memproses transaksi dengan klien, pembulatan adalah "mendukung klien." Artinya, harga dibulatkan jika pelanggan menjual, dan turun jika pelanggan membeli. Tetapi opsi lain mungkin diperlukan, misalnya, pembulatan aritmatika ke nomor terdekat dengan subtipe (setengah naik, setengah turun, setengah bahkan) untuk meminimalkan inkonsistensi akuntansi. Atau pembulatan ke ± tak terhingga untuk harga negatif (untuk beberapa instrumen keuangan). Java BigDecimal sudah berisi daftar mode pembulatan standar, dan perpustakaan yang dijelaskan mendukung semuanya. TIDAK PERLU mengembalikan NaN jika operasi secara tak terduga membutuhkan pembulatan.

Dalam mode round-up, perhitungan kami harus memberikan:

1,00 / 3,00 = 0,34
100 * 100/300 + 1 = 34

Bagaimana cara mengetahui apa yang Anda butuhkan untuk menambahkan sebuah unit? Anda membutuhkan sisa dari divisi 10.000% 300 = 100. Yang selambat divisi itu sendiri. Untungnya, jika Anda menulis berturut-turut dalam kode "a / b; a% b", maka JIT akan menyadari bahwa 2 divisi tidak diperlukan, hanya satu perintah assembler div yang mengembalikan 2 angka (hasil bagi dan sisa).

Opsi pembulatan lainnya sedikit lebih rumit, tetapi juga dapat dihitung berdasarkan sisanya dan pembagi.

Dalam API, saya sengaja menyebutkan pembulatan di mana pun itu terjadi, baik sebagai parameter atau sebagai akhiran R D ound D sendiri dalam metode yang defaultnya nol.

Overflow

Kita sampai pada bagian yang paling sulit. Ingat kembali penggandaan kita:

1.20 * 2.00 = 2.40
120 * 200/100 = 240

Sekarang bayangkan kita berada di tahun 1980-an dan kita memiliki prosesor 16-bit. Artinya, hanya kekurangan yang tersedia bagi kami dengan nilai maksimum 65535. Perkalian pertama akan melimpah dan akan sama dengan 240000 & 0xFFFF = 44392 (jika tidak ditandatangani, dengan tanda itu juga akan menjadi negatif), yang akan menghancurkan hasil bagi kami.

Itu tidak akan berhasil. Kami memiliki 2 argumen normal (sesuai dengan rentang nilai kami), dan hasil yang diharapkan normal yang sama, tetapi kami meluap di tengah jalan. Situasi yang sama persis mungkin dengan long'om 64-bit, hanya angka yang membutuhkan lebih banyak.

Pada 1980-an, kita membutuhkan multiplikasi yang memberikan hasil 32-bit. Hari ini kita membutuhkan perkalian dengan hasil 128-bit. Yang paling menjengkelkan adalah bahwa kedua perkalian tersedia di assembler 8086 dan x86-64, masing-masing, tetapi kita tidak dapat menggunakannya dari Jawa! JNI, bahkan dalam kasus peretasan dengan JavaCritical cepat, memberikan overhead puluhan nanodetik, memperkenalkan kesulitan dengan penyebaran dan kompatibilitas, membekukan GC selama durasi panggilan. Selain itu, kita bagaimanapun harus mengembalikan hasil 128-bit dari metode asli, dan menulis dengan referensi ke array (dalam memori) adalah penundaan tambahan.

Secara umum, saya harus menulis perkalian dan pembagian manual. Kolom Saya membutuhkan 2 operasi tambahan:

1. A (64) * B (64) = T (128); T (128) / N (32) = Q (64), R (32) - sebagai bagian dari titik tetap perkalian A * B
2. N (32) * A (64) = T (96); T (96) / B (64) = Q (64), R (64) - sebagai bagian dari divisi titik tetap A / B
   (dalam tanda kurung menunjukkan dimensi data dalam bit, T adalah variabel sementara yang tidak boleh meluap)

Kedua operasi mengembalikan hasil bagi dan sisanya (satu sebagai hasil dari metode, yang kedua di bidang objek). Mereka juga bisa meluap, tetapi hanya pada langkah terakhir, ketika ini tidak bisa dihindari. Berikut ini sebuah contoh (dari tahun 1980-an):

500,00 / 0,50 = 1000,00
100 * 50.000 / 50 = 100.000 - melimpah!

Pembagian kolom a la Knut bukan algoritma yang termudah. Plus, itu juga harus relatif cepat. Oleh karena itu, kode dari kedua operasi ini adalah ratusan baris bit magic yang agak berat, saya akan membutuhkan banyak waktu untuk mengingat kembali apa sebenarnya yang terjadi di sana. Saya menarik mereka ke kelas yang terpisah dan berkomentar sedetail mungkin.

Algoritma multiplikasi tidak terbatas pada menjalankan operasi 1, tetapi kode yang tersisa tidak begitu rumit dan hanya menambahkan dukungan untuk angka negatif, pembulatan, dan NaN.

Biasanya (kecuali dalam kasus khusus), kedua operasi mengandung 4 perkalian dan 2 divisi. Operasi 1 secara signifikan lebih cepat dari 2, karena di dalamnya pembagian ini konstan.

By the way, jika ada yang memperhatikan, N (32) adalah 10 ^ N kami untuk normalisasi. Ini adalah 32-bit, dari sini N dapat menjadi maksimum 9. Dalam aplikasi nyata yang saya lihat, 2, 4 atau 8 tempat desimal digunakan. Saya belum melihat lebih dari 9, jadi itu sudah cukup. Jika Anda membuat 10 ^ N 64-bit, kode menjadi lebih rumit (dan melambat) bahkan lebih.

Beberapa presisi berbeda

Kadang-kadang perlu untuk melakukan operasi pada argumen dengan jumlah desimal yang berbeda. Minimal, masukkan operasi yang melibatkan panjang biasa.

Sebagai contoh:

2.0000 (N = 4) + 3.00 (N = 2) = 5.0000 (N = 4)
20.000 + 300 * 100 = 50.000

3,00 (N = 2) + 2.0000 (N = 4) = 5.00 (N = 2)
300 + 20.000 / 100 = 500

Dalam hal ini, diperlukan normalisasi tambahan dari salah satu argumen. Perhatikan bahwa secara matematis kedua operasi adalah sama, tetapi karena akurasi hasil yang berbeda, mereka dihitung secara berbeda. Perlu juga dicatat bahwa operasi kedua umumnya membutuhkan pembulatan.

Jumlah tempat desimal TIDAK disimpan dalam objek. Sebagai gantinya, sebuah subclass terpisah diasumsikan untuk setiap presisi. Nama kelas dapat berorientasi bisnis, misalnya Harga (N = 8), Kuantitas (N = 2). Dan mereka dapat digeneralisasi: Decimal1, Decimal2, Decimal3, ... Semakin besar akurasi, semakin kecil rentang nilai yang disimpan, kisaran minimum memiliki Decimal9: ± 9223372036. Diasumsikan bahwa satu atau dua kelas akan cukup untuk mencakup fungsionalitas yang diperlukan, dalam hal ini metode getScale abstrak kemungkinan akan divirtualisasi dan sebaris. Subkelas (bukan bidang tambahan) memungkinkan Anda untuk secara ketat menentukan akurasi argumen dan hasil, serta sinyal tentang kemungkinan pembulatan pada tahap kompilasi.

Perpustakaan memungkinkan operasi dengan maksimum 2 (tetapi bukan 3) dengan akurasi berbeda. Artinya, keakuratan kedua argumen harus bersamaan, atau keakuratan salah satu argumen dan hasilnya. Sekali lagi, mendukung 3 presisi berbeda akan sangat memperlambat kode dan mempersulit API. Sebagai argumen, Anda dapat melewati panjang reguler, yang untuk itu akurasi N = 0 diasumsikan.

2.0000 / 3.0 = 0.6667 - ok (2 presisi berbeda)
2/3 = 0.6667 - ok (argumen panjang, hasil desimal)
2 / 3.0 = 0.6667 - tidak mungkin! (3 presisi berbeda)

Keuntungan dan kerugian

Jelas, komputasi bit tinggi yang dilakukan oleh perpustakaan lebih lambat daripada yang didukung perangkat keras. Namun, overhead tidak terlalu besar (lihat benchmark di bawah).

Selain itu, karena kurangnya kelebihan operator di Jawa, menggunakan metode bukannya operator aritmatika mempersulit persepsi kode.

Berdasarkan hal ini, perpustakaan biasanya digunakan di tempat-tempat di mana hilangnya keakuratan absolut sangat penting. Misalnya, menghitung statistik keuangan yang akurat, dengan mempertimbangkan indikator keuangan saat ini (posisi perdagangan, PnL, pesanan yang dieksekusi). Dalam pertukaran jaringan informasi keuangan antar sistem, juga lebih mudah menggunakan format dengan titik desimal (bukan biner).

Algoritma matematika yang kompleks (pemodelan, statistik, peramalan) biasanya lebih mudah dilakukan secara ganda, karena hasilnya dalam hal apapun tidak sepenuhnya akurat.

Kode dan tolok ukur

Kode

Secara umum, perkalian adalah 4 kali lebih cepat dari BigDecimal, pembagian 1,5. Tingkat pembagian sangat tergantung pada argumen, karenanya penyebaran nilai.