integer terbesar yang bisa disimpan dalam dua kali lipat

225

Apa integer "no-floating" terbesar yang dapat disimpan dalam tipe ganda IEEE 754 tanpa kehilangan presisi?

Franck Freiburger
sumber

Jawaban:

506

Bilangan bulat terbesar / terbesar yang dapat disimpan dalam dua kali lipat tanpa kehilangan presisi adalah sama dengan nilai kemungkinan terbesar dari suatu ganda. Yaitu, DBL_MAXatau sekitar 1,8 × 10 308 (jika ganda Anda adalah ganda IEEE 754 64-bit). Itu bilangan bulat. Itu persis diwakili. Apa lagi yang kamu inginkan?

Ayo, tanya saya apa bilangan bulat terbesar, sehingga itu dan semua bilangan bulat yang lebih kecil dapat disimpan dalam ganda IEEE 64-bit tanpa kehilangan presisi. IEEE 64-bit double memiliki 52 bit mantissa, jadi saya pikir ini adalah 53 53 :

  • 2 53 + 1 tidak dapat disimpan, karena 1 di awal dan 1 di akhir memiliki terlalu banyak nol di antaranya.
  • Apa pun yang kurang dari 2 53 dapat disimpan, dengan 52 bit disimpan secara eksplisit di mantissa, dan kemudian eksponen yang berlaku memberi Anda satu lagi.
  • 2 53 jelas dapat disimpan, karena itu kekuatan kecil 2.

Atau cara lain untuk melihatnya: sekali bias telah diambil dari eksponen, dan mengabaikan bit tanda sebagai tidak relevan dengan pertanyaan, nilai yang disimpan oleh ganda adalah kekuatan 2, ditambah bilangan bulat 52-bit dikalikan dengan 2 eksponen - 52 . Jadi dengan eksponen 52 Anda dapat menyimpan semua nilai dari 2 52 hingga 2 53  - 1. Kemudian dengan eksponen 53, angka berikutnya yang dapat Anda simpan setelah 2 53 adalah 2 53 + 1 × 2 53 - 52 . Jadi kehilangan presisi pertama kali terjadi dengan 2 53 + 1.

Steve Jessop
sumber
126
+1 Pekerjaan bagus memperhatikan bahwa pertanyaan itu tidak benar-benar berarti apa yang dimaksudkan oleh si penanya dan memberikan kedua jawaban ("secara teknis benar" dan "mungkin diharapkan").
Pascal Cuoq
62
Atau "bermain-main" dan "berusaha membantu" seperti yang saya cenderung untuk memanggil mereka :-)
Steve Jessop
8
Saya tunduk pada Tony the Pony, dan tidak ada yang lain.
Steve Jessop
11
Maksud Anda bukan "semua bilangan bulat kecil", maksud Anda semua bilangan bulat dengan besaran yang sama atau lebih kecil. Karena ada banyak bilangan bulat negatif di bawah ini di bawah 2 ^ 53 dan tidak dapat direpresentasikan secara tepat dalam ganda.
Southern Hospitality
13
Maksud saya lebih kecil, dan itulah yang saya maksud ketika saya mengatakan lebih kecil :-) -1.000.000 kurang dari 1, tetapi tidak lebih kecil.
Steve Jessop
77

9007199254740992 (yaitu 9.007.199.254.740.992) tanpa jaminan :)

Program

#include <math.h>
#include <stdio.h>

int main(void) {
  double dbl = 0; /* I started with 9007199254000000, a little less than 2^53 */
  while (dbl + 1 != dbl) dbl++;
  printf("%.0f\n", dbl - 1);
  printf("%.0f\n", dbl);
  printf("%.0f\n", dbl + 1);
  return 0;
}

Hasil

9007199254740991
9007199254740992
9007199254740992
pmg
sumber
7
Dengan asumsi itu akan 'dekat' tetapi kurang dari 2 ^ N, maka tes yang lebih cepat adalah double dbl = 1; while (dbl + 1 != dbl) dbl *= 2; while (dbl == --dbl);yang menghasilkan hasil yang sama
Seph
4
@ Apa apa ...? Tidak? while (dbl == --dbl)akan berulang selamanya atau tidak sama sekali. :) (dalam hal ini, tidak sama sekali, karena ini adalah 2 ^ N). Anda harus mendekatinya dari bawah. Ini memang juga akan menghasilkan satu kurang dari hasil yang diharapkan (karena yang memeriksa di while loop mengurangi dbl). Dan itu tergantung pada urutan eksekusi, jika pengurangan dilakukan sebelum atau setelah mengevaluasi sisi kiri (yang tidak ditentukan sejauh yang saya tahu). Jika yang pertama, itu akan selalu benar dan berulang selamanya.
falstro
10
Mungkin mengindikasikan bahwa 2 ^ 53 = 9.007.199.254.740.992 di suatu tempat.
Xonatron
1
Sulit untuk berdebat dengan ini! Percobaan yang bagus
MattM
Kelemahan untuk menggunakan while (dbl + 1 != dbl) dbl++;dalam yang dbl + 1 != dbldapat mengevaluasi menggunakan long doublematematika - pertimbangkan FLT_EVAL_METHOD == 2. Ini bisa berakhir dalam loop tak terbatas.
chux
25

Wikipedia mengatakan ini dalam konteks yang sama dengan tautan ke IEEE 754 :

Pada sistem komputer tipikal, angka biner floating-point 'presisi ganda' (64-bit) memiliki koefisien 53 bit (salah satunya tersirat), eksponen 11 bit, dan satu bit tanda.

2 ^ 53 lebih dari 9 * 10 ^ 15.

Carl Smotricz
sumber
@Steve Jessop kurang lebih, itulah yang saya katakan. Saya juga menemui sistem perangkat keras yang tidak memiliki FPU yang masih harus sesuai dengan IEEE, sehingga hal-hal "sistem biasa" tidak benar-benar membantu saya jika saya kembali ke sini 8 bulan kemudian dan memerlukan info yang sama untuk mikrokontroler berbasis 68K saya (dengan asumsi tidak memiliki FPU ... saya tidak ingat).
San Jacinto
14
@San Jacinto - "Ini tidak berguna" terlalu kasar. Jawabannya cukup berguna, hanya tidak berguna seperti seharusnya jika itu termasuk komentar bahwa sistem komputer memang menggunakan reprensentasi IEEE 754.
Stephen C. Steel
@Stephen C. Steel, sebenarnya Anda benar. Dalam skenario saya, kembali ke ini di lain waktu dan mencari IEEE max, sangat tidak mungkin untuk apa 'sistem tipikal' itu, tetapi masih ada kelebihan dalam jawaban selain keluhan ini.
San Jacinto
20

Bilangan bulat terbesar yang dapat direpresentasikan dalam IEEE 754 ganda (64-bit) adalah sama dengan nilai terbesar yang dapat diwakili oleh jenis tersebut, karena nilai itu sendiri merupakan bilangan bulat.

Ini direpresentasikan sebagai 0x7FEFFFFFFFFFFFFF, yang terdiri dari:

  • Tanda bit 0 (positif) daripada 1 (negatif)
  • Eksponen maksimum 0x7FE(2046 yang mewakili 1023 setelah bias dikurangi) daripada 0x7FF(2047 yang menunjukkan a NaNatau tak terbatas).
  • Mantra maksimum 0xFFFFFFFFFFFFFyaitu 52 bit semua 1.

Dalam biner, nilainya adalah implisit 1 diikuti oleh 52 yang lain dari mantissa, kemudian 971 nol (1023 - 52 = 971) dari eksponen.

Nilai desimal yang tepat adalah:

179769313486231570814527423731704356798070567525844996598917476803157260780028538760589558632766878171540458953514382464234321326889464182768467546703537516986049910576551282076245490090389328944075868508455133942304583236903222948165808559332123348274797826204144723168738177180919299881250404026184124858368

Ini sekitar 1,8 x 10 308 .

Simon Biber
sumber
Bagaimana dengan nilai terbesar yang dapat diwakilinya dengan semua nilai di antara itu dan nol yang dapat direpresentasikan secara berdekatan?
Aaron Franke
@AaronFranke Pertanyaannya tidak menanyakan tentang representasi yang berdekatan, tetapi jawaban untuk pertanyaan yang berbeda telah dimasukkan dalam sebagian besar jawaban lain di sini, atau bahkan diberikan secara salah sebagai jawaban yang sebenarnya. Ini 2⁵³ (2 pangkat 53).
Simon Biber
8

Anda perlu melihat ukuran mantissa. Nomor floating point IEEE 754 64 bit (yang memiliki 52 bit, ditambah 1 tersirat) dapat mewakili integer dengan nilai absolut kurang dari atau sama dengan 2 ^ 53.

Lumba-lumba
sumber
8
Persis dapat mewakili 2 ^ 53, juga :-)
Steve Jessop
6

1.7976931348623157 × 10 ^ 308

http://en.wikipedia.org/wiki/Double_precision_floating-point_format

Jay
sumber
2
jawaban ini akan jauh lebih baik dengan kutipan.
San Jacinto
2
@Carl baik, jika bilangan bulat memiliki angka nol di sebelah kiri, maka itu disimpan dengan tepat.
Wilhelm
4
@ semua Anda downvoters: 1.7976931348623157 × 10 ^ 308 adalah bilangan bulat yang tepat. Apakah Anda semua harus menghadiri kelas matematika perbaikan atau sesuatu ??
Dan Moulding
6
Kita sampai pada semantik di sini dalam pembahasan tentang jawaban yang tak ada harapan ini. Benar, angka itu dapat diwakili secara tepat dan dengan demikian memenuhi surat pertanyaan. Tetapi kita semua tahu itu adalah pulau kecil dengan ketelitian di samudera nyaris celaka, dan sebagian besar dari kita dengan benar menginterpolasi pertanyaan yang berarti "jumlah terbesar di luar ketepatan yang sia-sia." Ah, bukankah luar biasa kalau CompSci adalah ilmu pasti? :)
Carl Smotricz
2
@DanMoulding 1,7976931348623157 × 10 ^ 308 adalah bilangan bulat yang tepat, tapi saya cukup yakin bilangan bulat khusus ini tidak dapat disimpan tepat dalam dua kali lipat.
Pascal Cuoq
2

DECIMAL_DIGdari <float.h>harus memberikan setidaknya perkiraan yang masuk akal itu. Karena itu berkaitan dengan angka desimal, dan itu benar-benar disimpan dalam biner, Anda mungkin dapat menyimpan sesuatu yang sedikit lebih besar tanpa kehilangan presisi, tetapi seberapa banyak yang sulit dikatakan. Saya kira Anda harus bisa mengetahuinya FLT_RADIXdan DBL_MANT_DIG, tapi saya tidak yakin saya sepenuhnya percaya hasilnya.

Jerry Coffin
sumber
Ini tidak memberikan jawaban untuk pertanyaan itu. Untuk mengkritik atau meminta klarifikasi dari penulis, tinggalkan komentar di bawah posting mereka.
MichaelChirico
@MichaelChirico: Ini menjawab pertanyaan yang ingin dia tanyakan, sebagaimana ada ketika jawabannya ditulis. Untuk melihat riwayat edit pertanyaan, klik tautan "edit 19 Juni 14 jam 11:40" di bagian bawah pertanyaan.
Jerry Coffin
jawaban Anda berbunyi seperti komentar karena tampaknya kurang percaya diri / otoritatif bahwa jawaban harus memiliki ("harus memberikan setidaknya yang masuk akal ..." "persis berapa ... sulit untuk mengatakan" "Saya kira ... "). Saya tidak memiliki keahlian pada pertanyaan yang diajukan atau jawabannya, jadi saya mungkin salah; hanya memasukkan dua sen saya mengingat saya dikirim ke sini dari antrian ulasan (yang saya kira berarti pengguna lain menandai jawaban Anda).
MichaelChirico
1
@MichaelChirico: Mereka mungkin memiliki - Anda jauh dari satu-satunya yang tidak tahu tentang masalah pokok; Apa yang membuat Anda tidak biasa adalah Anda menyadari bahwa Anda tidak mengetahui hal itu. Sebagian besar jawaban yang terdengar otoritatif tentang ketepatan angka floating point dalam C hanya salah. Sebagai contoh, banyak (kebanyakan) dari mereka di atas didasarkan pada asumsi yang salah bahwa doubleberhubungan langsung dengan jenis IEEE tertentu, tetapi itu tidak diperlukan, dan ketika jawaban ini ditulis, pertanyaannya tidak menyebutkan jenis IEEE tertentu juga.
Jerry Coffin
mengerti. Saya mungkin menyarankan menambahkan info itu ke jawabannya.
MichaelChirico