Jawaban animal_magic benar bahwa Anda harus menambahkan angka dari terkecil ke terbesar, namun saya ingin memberikan contoh untuk menunjukkan alasannya.
Asumsikan kita sedang bekerja dalam format floating point yang memberi kita akurasi 3 digit. Sekarang kami ingin menambahkan sepuluh angka:
[1000, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Tentu saja jawaban pastinya adalah 1009, tetapi kami tidak dapat memperolehnya dalam format 3 digit. Membulatkan menjadi 3 digit, jawaban paling akurat yang kami dapatkan adalah 1010. Jika kami menambahkan terkecil ke terbesar, pada setiap loop yang kami dapatkan:
Loop Index s
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 1009 -> 1010
Jadi kami mendapatkan jawaban yang paling akurat untuk format kami. Sekarang mari kita asumsikan bahwa kita menambahkan dari yang terbesar ke yang terkecil.
Loop Index s
1 1000
2 1001 -> 1000
3 1001 -> 1000
4 1001 -> 1000
5 1001 -> 1000
6 1001 -> 1000
7 1001 -> 1000
8 1001 -> 1000
9 1001 -> 1000
10 1001 -> 1000
Karena angka floating point dibulatkan setelah setiap operasi, semua penambahan dibulatkan, meningkatkan kesalahan kami dari 1 menjadi 9 dari tepat. Sekarang bayangkan jika set angka yang Anda tambahkan memiliki 1000, dan kemudian seratus 1, atau satu juta. Perhatikan bahwa untuk menjadi benar-benar akurat, Anda ingin menjumlahkan dua angka terkecil, kemudian memasukkan hasilnya ke dalam set angka Anda.
Jawaban sebelumnya sudah membahas masalah ini secara luas dan memberikan nasihat, tetapi ada kekhasan tambahan yang ingin saya sebutkan. Pada sebagian besar arsitektur modern,
for
loop yang telah Anda uraikan akan tetap dilakukan dalam presisi diperluas 80-bit , yang menjamin akurasi tambahan, karena semua variabel sementara akan dimasukkan ke dalam register. Jadi, Anda sudah memiliki beberapa bentuk perlindungan dari kesalahan numerik. Namun, dalam loop yang lebih rumit, nilai-nilai perantara akan disimpan dalam memori di antara operasi, dan karenanya terpotong menjadi 64 bit. Saya rasa itucukup untuk mendapatkan presisi yang lebih rendah dalam penjumlahan Anda (!!). Jadi berhati-hatilah jika Anda ingin printf-debug kode Anda sambil memeriksa keakuratan.
Bagi yang berminat, makalah ini menjelaskan masalah dalam rutinitas numerik yang banyak digunakan (faktorisasi QR peringkat-peringkat Lapack) yang debugging dan analisisnya sangat rumit justru karena masalah ini.
sumber
Dari 2 opsi, menambahkan dari yang lebih kecil ke yang lebih besar akan menghasilkan lebih sedikit kesalahan numerik kemudian menambahkan dari yang lebih besar ke yang lebih kecil.
Namun,> 20 tahun yang lalu di kelas "Metode Numerik" saya, instruktur menyatakan ini dan terpikir oleh saya bahwa ini masih menimbulkan lebih banyak kesalahan daripada yang diperlukan karena perbedaan relatif dalam nilai antara akumulator dan nilai yang ditambahkan.
Secara logis, solusi yang lebih disukai adalah dengan menambahkan 2 angka terkecil dalam daftar, lalu memasukkan kembali nilai yang dijumlahkan ke dalam daftar yang diurutkan.
Untuk mendemonstrasikannya, saya membuat algoritma yang bisa melakukan itu secara efisien (dalam ruang dan waktu) dengan menggunakan ruang yang dibebaskan saat elemen dihapus dari array primer untuk membangun array sekunder dari nilai yang dijumlahkan yang secara inheren dipesan sejak penambahan adalah jumlah nilai yang selalu meningkat. Pada setiap iterasi, "tips" dari kedua array kemudian diperiksa untuk menemukan 2 nilai terkecil.
sumber
Karena Anda tidak membatasi tipe data yang akan digunakan, untuk mencapai hasil yang sangat akurat, cukup gunakan angka panjang arbitrer ... dalam hal ini urutannya tidak akan menjadi masalah. Ini akan jauh lebih lambat, tetapi mendapatkan kesempurnaan memang membutuhkan waktu.
sumber
Gunakan penambahan pohon biner, yaitu, Pilih rata-rata distribusi (nomor terdekat) sebagai akar dari pohon biner, dan buat pohon biner yang disortir dengan menambahkan nilai yang lebih rendah di sebelah kiri grafik dan yang lebih besar di sebelah kanan grafik dan seterusnya . Menambahkan semua simpul anak dari satu orangtua secara rekursif dalam pendekatan bottom-up. Ini akan efisien karena kesalahan rata-rata meningkat dengan jumlah penjumlahan dan dalam pendekatan pohon biner, jumlah penjumlahan berada dalam urutan log n pada basis 2. Oleh karena itu kesalahan rata-rata akan lebih rendah.
sumber
Apa yang dikatakan Hristo Iliev di atas tentang kompiler 64-bit yang lebih memilih instruksi SSE dan AVX daripada FPU (AKA NDP) benar-benar benar, setidaknya untuk Microsoft Visual Studio 2013. Namun, untuk operasi floating-point presisi ganda yang saya gunakan, saya menemukan sebenarnya lebih cepat, dan juga secara teori lebih akurat, untuk menggunakan FPU. Jika ini penting bagi Anda, saya sarankan menguji berbagai solusi terlebih dahulu, sebelum memilih pendekatan akhir.
Saat bekerja di Java, saya sangat sering menggunakan tipe data BigDecimal yang presisi-sewenang-wenang. Itu terlalu mudah, dan biasanya orang tidak menyadari kecepatannya menurun. Menghitung fungsi-fungsi transendental dengan deret tak terbatas dan sqrt menggunakan metode Newton dapat memakan waktu milidetik atau lebih, tetapi ini bisa dilakukan dan cukup akurat.
sumber
Saya hanya meninggalkan ini di sini /programming//a/58006104/860099 (ketika Anda pergi ke sana, klik untuk 'tunjukkan cuplikan kode' dan jalankan dengan tombol
Ini adalah contoh JavaScript yang jelas menunjukkan bahwa jumlah yang dimulai dari yang terbesar memberikan kesalahan yang lebih besar
sumber