Saya mencoba untuk mendapatkan jumlah 1 + 2 + ... + 1000000000
, tapi aku mendapatkan hasil yang lucu dalam PHP dan Node.js .
PHP
$sum = 0;
for($i = 0; $i <= 1000000000 ; $i++) {
$sum += $i;
}
printf("%s", number_format($sum, 0, "", "")); // 500000000067108992
Node.js
var sum = 0;
for (i = 0; i <= 1000000000; i++) {
sum += i ;
}
console.log(sum); // 500000000067109000
Jawaban yang benar dapat dihitung dengan menggunakan
1 + 2 + ... + n = n(n+1)/2
Jawaban yang benar = 500000000500000000 , jadi saya memutuskan untuk mencoba bahasa lain.
PERGILAH
var sum , i int64
for i = 0 ; i <= 1000000000; i++ {
sum += i
}
fmt.Println(sum) // 500000000500000000
Tapi itu bekerja dengan baik! Jadi apa yang salah dengan kode PHP dan Node.js saya?
Mungkin ini masalah bahasa yang ditafsirkan, dan itulah mengapa ia bekerja dalam bahasa yang dikompilasi seperti Go? Jika demikian, apakah bahasa yang ditafsirkan lain seperti Python dan Perl memiliki masalah yang sama?
Jawaban:
Python bekerja:
Atau:
Otomatis Python
int
mempromosikan ke Pythonlong
yang mendukung presisi sewenang-wenang. Ini akan menghasilkan jawaban yang benar pada platform 32 atau 64 bit.Ini dapat dilihat dengan menaikkan 2 ke daya yang jauh lebih besar dari lebar bit platform:
Anda dapat mendemonstrasikan (dengan Python) bahwa nilai yang salah yang Anda peroleh di PHP adalah karena PHP mempromosikan ke float ketika nilainya lebih dari 2 ** 32-1:
sumber
Kode Go Anda menggunakan bilangan bulat aritmatika dengan bit yang cukup untuk memberikan jawaban yang tepat. Tidak pernah menyentuh PHP atau Node.js, tetapi dari hasil saya menduga matematika dilakukan menggunakan angka floating point dan dengan demikian diharapkan tidak tepat untuk angka sebesar ini.
sumber
If PHP encounters a number beyond the bounds of the integer type, it will be interpreted as a float instead. Also, an operation which results in a number beyond the bounds of the integer type will return a float instead.
- php.net/manual/en/language.types.integer.phpAlasannya adalah bahwa nilai variabel integer Anda
sum
melebihi nilai maksimum. Dan yangsum
Anda dapatkan adalah hasil dari aritmatika float-point yang melibatkan pembulatan. Karena jawaban lain tidak menyebutkan batas pasti, saya memutuskan untuk mempostingnya.Nilai integer maks untuk PHP untuk:
Jadi itu berarti Anda menggunakan CPU 32 bit atau 32 bit OS atau versi 32 bit PHP yang dikompilasi. Itu dapat ditemukan menggunakan
PHP_INT_MAX
. Thesum
akan dihitung dengan benar jika Anda melakukannya pada mesin 64 bit.Nilai integer maks dalam JavaScript adalah 9007199254740992 . Nilai integral persis terbesar yang dapat Anda gunakan adalah 2 53 (diambil dari pertanyaan ini ). Itu
sum
melebihi batas ini.Jika nilai integer tidak melebihi batas ini, maka Anda baik. Kalau tidak, Anda harus mencari perpustakaan integer presisi sewenang-wenang.
sumber
Inilah jawaban dalam C, untuk kelengkapan:
Kunci dalam hal ini adalah menggunakan tipe data C99
long long
. Ini memberikan penyimpanan primitif terbesar yang dapat dikelola C dan beroperasi dengan sangat, sangat cepat. Itulong long
jenis juga akan bekerja pada hampir semua mesin 32 atau 64-bit.Ada satu peringatan: kompiler yang disediakan oleh Microsoft secara eksplisit tidak mendukung standar C99 yang berusia 14 tahun, sehingga menjalankan ini di Visual Studio adalah omong kosong.
sumber
long long
dalam standar C ++ 11. Sudah merupakan ekstensi MSVC ++ dan g ++ selama beberapa tahun.movabsq $500000000500000000, %rsi
gcc -O3
atauclang -O3
. Saya tidak tahu nama pengoptimalan spesifik. Pada dasarnya kompiler memperhatikan bahwa hasil dari loop tidak bergantung pada argumen apa pun, dan menghitungnya pada waktu kompilasi.Dugaan saya adalah bahwa ketika jumlah melebihi kapasitas asli
int
(2 31 -1 = 2.147.483.647), Node.js dan PHP beralih ke representasi titik mengambang dan Anda mulai mendapatkan kesalahan pembulatan. Bahasa seperti Go mungkin akan mencoba bertahan dengan bentuk integer (mis., Integer 64-bit) selama mungkin (jika, memang, itu tidak dimulai dengan itu). Karena jawabannya cocok dengan integer 64-bit, perhitungannya tepat.sumber
Script Perl memberi kami hasil yang diharapkan:
sumber
4.99999999067109e+017
pada Perl v5.16.1 MSWin32-x86.bignum
ataubigint
. Keduanya adalah modul inti, yaitu, mereka menginstal dengan Perl v5.8.0 atau lebih tinggi. Lihathttp://perldoc.perl.org/bignum.html
danhttp://perldoc.perl.org/bigint.html
Jawaban untuk ini "secara mengejutkan" sederhana:
Pertama - karena sebagian besar dari Anda mungkin tahu - bilangan bulat 32-bit berkisar dari 2.147.483.648 hingga 2.147.483.647 . Jadi, apa yang terjadi jika PHP mendapatkan hasil, yang LEBIH BESAR dari ini?
Biasanya, orang akan mengharapkan "Overflow" langsung, menyebabkan 2.147.483.647 +1 berubah menjadi −2.147.483.648 . Namun, itu BUKAN terjadi. JIKA PHP menemukan jumlah yang lebih besar, itu Mengembalikan FLOAT daripada INT.
http://php.net/manual/en/language.types.integer.php
Ini mengatakan, dan mengetahui bahwa implementasi PHP FLOAT mengikuti Format presisi ganda IEEE 754, berarti, PHP mampu menangani angka hingga 52 bit, tanpa kehilangan presisi. (Pada Sistem 32-bit)
Jadi, di Point, di mana jumlah Anda mencapai 9.007.199.254.740.992 (yang merupakan 2 ^ 53 ) Nilai Float yang dikembalikan oleh PHP Maths tidak lagi cukup akurat.
Contoh ini Shows the Point, di mana PHP kehilangan presisi. Pertama, bit signifikansi terakhir akan dihapus, menyebabkan 2 ekspresi pertama menghasilkan angka yang sama - yang tidak.
Mulai SEKARANG, seluruh matematika akan salah, saat bekerja dengan tipe data default.
Saya kira tidak. Saya pikir ini adalah masalah bahasa yang tidak memiliki keamanan jenis. Sementara Integer Overflow seperti yang disebutkan di atas AKAN terjadi di setiap bahasa yang menggunakan tipe data tetap, bahasa tanpa keamanan tipe mungkin mencoba untuk menangkap ini dengan tipe data lain. Namun, begitu mereka mencapai Perbatasan "alami" (yang diberikan Sistem) - mereka mungkin mengembalikan apa pun, tetapi hasilnya benar.
Namun, setiap bahasa dapat memiliki utas berbeda untuk Skenario semacam itu.
sumber
Jawaban lain sudah menjelaskan apa yang terjadi di sini (presisi floating point seperti biasa).
Salah satu solusinya adalah menggunakan tipe integer yang cukup besar, atau berharap bahasa akan memilih satu jika diperlukan.
Solusi lain adalah dengan menggunakan algoritma penjumlahan yang tahu tentang masalah presisi dan bekerja di sekitarnya. Di bawah ini Anda menemukan penjumlahan yang sama, pertama dengan integer 64 bit, kemudian dengan floating point 64 bit dan kemudian menggunakan floating point lagi, tetapi dengan algoritma penjumlahan Kahan .
Ditulis dalam C #, tetapi hal yang sama berlaku untuk bahasa lain juga.
Penjumlahan Kahan memberikan hasil yang indah. Tentu saja butuh waktu lebih lama untuk dihitung. Apakah Anda ingin menggunakannya tergantung a) pada kinerja Anda vs kebutuhan presisi, dan b) bagaimana bahasa Anda menangani tipe data integer vs floating point.
sumber
Jika Anda memiliki PHP 32-Bit, Anda dapat menghitungnya dengan bc :
Dalam Javascript Anda harus menggunakan pustaka angka arbitrer, misalnya BigInteger :
Bahkan dengan bahasa seperti Go dan Java Anda akhirnya harus menggunakan pustaka angka arbitrer, nomor Anda kebetulan cukup kecil untuk 64-bit tetapi terlalu tinggi untuk 32-bit.
sumber
Di Ruby:
Mencetak
500000000500000000
, tetapi membutuhkan 4 menit dengan baik pada Intel i7 2,6 GHz.Magnuss dan Jaunty memiliki lebih banyak solusi Ruby:
Untuk menjalankan tolok ukur:
sumber
Saya menggunakan simpul-bigint untuk hal-hal integer besar:
https://github.com/substack/node-bigint
Ini tidak secepat sesuatu yang dapat menggunakan hal-hal 64-bit asli untuk pengujian yang tepat ini, tetapi jika Anda masuk ke angka yang lebih besar dari 64-bit, ia menggunakan libgmp di bawah tenda, yang merupakan salah satu perpustakaan presisi cepat yang berubah-ubah di luar sana.
sumber
butuh waktu lama di ruby, tetapi memberikan jawaban yang benar:
sumber
Untuk mendapatkan hasil yang benar dalam php saya pikir Anda harus menggunakan operator matematika BC: http://php.net/manual/en/ref.bc.php
Inilah jawaban yang benar di Scala. Anda harus menggunakan Longs jika tidak, Anda melimpah nomornya:
sumber
Sebenarnya ada trik keren untuk masalah ini.
Asumsikan itu 1-100 sebagai gantinya.
1 + 2 + 3 + 4 + ... + 50 +
100 + 99 + 98 + 97 + ... + 51
= (101 + 101 + 101 + 101 + ... + 101) = 101 * 50
Rumus:
Untuk N = 100: Output = N / 2 * (N + 1)
Untuk N = 1e9: Output = N / 2 * (N + 1)
Ini jauh lebih cepat daripada perulangan melalui semua data itu. Prosesor Anda akan berterima kasih untuk itu. Dan di sini ada cerita menarik tentang masalah ini:
http://www.jimloy.com/algebra/gauss.htm
sumber
Ini memberikan hasil yang tepat dalam PHP dengan memaksa cast integer.
sumber
Common Lisp adalah salah satu bahasa * yang ditafsirkan tercepat dan menangani bilangan bulat besar yang sewenang-wenang secara default. Ini membutuhkan waktu sekitar 3 detik dengan SBCL :
sumber
Saya tidak memiliki reputasi yang cukup untuk mengomentari jawaban Common Lisp @ postfuturist, tetapi dapat dioptimalkan untuk diselesaikan dalam ~ 500ms dengan SBCL 1.1.8 pada mesin saya:
sumber
Racket v 5.3.4 (MBP; waktu dalam ms):
sumber
Bekerja dengan baik di Rebol:
Ini menggunakan Rebol 3 yang walaupun dikompilasi 32 bit namun menggunakan integer 64-bit (tidak seperti Rebol 2 yang menggunakan integer 32 bit)
sumber
Saya ingin melihat apa yang terjadi di CF Script
Saya mendapat 5.00000000067E + 017
Ini adalah eksperimen yang cukup rapi. Saya cukup yakin saya bisa membuat kode ini sedikit lebih baik dengan lebih banyak usaha.
sumber
ActivePerl v5.10.1 pada windows 32bit, intel core2duo 2.6:
hasil: 5.00000000067109e + 017 dalam 5 menit.
Dengan skrip "gunakan bigint" bekerja selama dua jam, dan akan bekerja lebih banyak, tetapi saya menghentikannya. Terlalu lambat.
sumber
Demi kelengkapan, di Clojure (cantik tapi tidak terlalu efisien):
sumber
AWK:
menghasilkan hasil yang salah sama seperti PHP:
Tampaknya AWK menggunakan floating point ketika angkanya benar-benar besar, jadi setidaknya jawabannya adalah urutan besarnya yang tepat.
Tes berjalan:
sumber
Kategori bahasa yang ditafsirkan lainnya:
Tcl:
Jika menggunakan Tcl 8.4 atau lebih tua itu tergantung apakah itu dikompilasi dengan 32 atau 64 bit. (8.4 adalah akhir kehidupan).
Jika menggunakan Tcl 8.5 atau lebih baru yang memiliki bilangan bulat besar sembarang, itu akan menampilkan hasil yang benar.
Saya meletakkan tes di dalam proc untuk mendapatkannya byte-compiled.
sumber
Untuk kode PHP, jawabannya ada di sini :
sumber
Pelabuhan:
Hasil dalam
500000000500000000
. (pada kedua windows / mingw / x86 dan osx / clang / x64)sumber
Erlang bekerja:
sumber
Lucunya, PHP 5.5.1 memberi 49999999950000000000 (dalam ~ 30s), sedangkan Dart2Js memberi 500000000067109000 (yang diharapkan, karena JS-lah yang dieksekusi). CLI Dart memberikan jawaban yang tepat ... secara instan.
sumber
Erlang memberikan hasil yang diharapkan juga.
sum.erl:
Dan menggunakannya:
sumber
Smalltalk:
sumber