Tại sao việc thay đổi thứ tự tổng lại trả về một kết quả khác?

300
Marlon Bernardes 2013-11-07 08:50.

Tại sao việc thay đổi thứ tự tổng lại trả về một kết quả khác?

23.53 + 5.88 + 17.64 = 47.05

23.53 + 17.64 + 5.88 = 47.050000000000004

Cả JavaJavaScript đều trả về kết quả giống nhau.

Tôi hiểu rằng, do cách biểu diễn số dấu phẩy động trong hệ nhị phân, một số số hữu tỉ ( như 1/3 - 0,333333 ... ) không thể được biểu diễn chính xác.

Tại sao chỉ cần thay đổi thứ tự của các phần tử lại ảnh hưởng đến kết quả?

6 answers

277
Jon Skeet 2013-11-07 08:56.

Có thể câu hỏi này là ngu ngốc, nhưng tại sao chỉ cần thay đổi thứ tự của các phần tử lại ảnh hưởng đến kết quả?

Nó sẽ thay đổi các điểm mà tại đó các giá trị được làm tròn, dựa trên độ lớn của chúng. Như một ví dụ về loại mà chúng ta đang thấy, hãy giả sử rằng thay vì dấu phẩy động nhị phân, chúng tôi đang sử dụng loại dấu phẩy động thập phân với 4 chữ số có nghĩa, trong đó mỗi phép cộng được thực hiện ở độ chính xác "vô hạn" và sau đó làm tròn thành số đại diện gần nhất. Đây là hai tổng:

1/3 + 2/3 + 2/3 = (0.3333 + 0.6667) + 0.6667
                = 1.000 + 0.6667 (no rounding needed!)
                = 1.667 (where 1.6667 is rounded to 1.667)

2/3 + 2/3 + 1/3 = (0.6667 + 0.6667) + 0.3333
                = 1.333 + 0.3333 (where 1.3334 is rounded to 1.333)
                = 1.666 (where 1.6663 is rounded to 1.666)

Chúng tôi thậm chí không cần các số không phải là số nguyên vì đây là một vấn đề:

10000 + 1 - 10000 = (10000 + 1) - 10000
                  = 10000 - 10000 (where 10001 is rounded to 10000)
                  = 0

10000 - 10000 + 1 = (10000 - 10000) + 1
                  = 0 + 1
                  = 1

Điều này có thể chứng minh rõ ràng hơn rằng phần quan trọng là chúng ta có một số lượng giới hạn các chữ số có nghĩa - không phải là một số lượng giới hạn các chữ số thập phân . Nếu chúng ta luôn có thể giữ cùng một số chữ số thập phân, thì với phép cộng và trừ ít nhất, chúng ta sẽ ổn (miễn là các giá trị không bị tràn). Vấn đề là khi bạn chuyển đến số lớn hơn, thông tin nhỏ hơn sẽ bị mất - 10001 được làm tròn thành 10000 trong trường hợp này. (Đây là một ví dụ về vấn đề mà Eric Lippert đã lưu ý trong câu trả lời của mình .)

Điều quan trọng cần lưu ý là các giá trị trên dòng đầu tiên của phía bên phải là giống nhau trong mọi trường hợp - vì vậy, mặc dù điều quan trọng là phải hiểu rằng các số thập phân của bạn (23,53, 5,88, 17,64) sẽ không được biểu thị chính xác dưới dạng doublegiá trị, đó là chỉ có một vấn đề vì các vấn đề hiển thị ở trên.

52
rgettman 2013-11-07 09:40.

Đây là những gì đang xảy ra trong hệ nhị phân. Như chúng ta đã biết, một số giá trị dấu phẩy động không thể được biểu diễn chính xác dưới dạng nhị phân, ngay cả khi chúng có thể được biểu diễn chính xác dưới dạng thập phân. 3 con số này chỉ là ví dụ minh chứng cho thực tế đó.

Với chương trình này, tôi xuất ra các biểu diễn thập lục phân của mỗi số và kết quả của mỗi phép cộng.

public class Main{
   public static void main(String args[]) {
      double x = 23.53;   // Inexact representation
      double y = 5.88;    // Inexact representation
      double z = 17.64;   // Inexact representation
      double s = 47.05;   // What math tells us the sum should be; still inexact

      printValueAndInHex(x);
      printValueAndInHex(y);
      printValueAndInHex(z);
      printValueAndInHex(s);

      System.out.println("--------");

      double t1 = x + y;
      printValueAndInHex(t1);
      t1 = t1 + z;
      printValueAndInHex(t1);

      System.out.println("--------");

      double t2 = x + z;
      printValueAndInHex(t2);
      t2 = t2 + y;
      printValueAndInHex(t2);
   }

   private static void printValueAndInHex(double d)
   {
      System.out.println(Long.toHexString(Double.doubleToLongBits(d)) + ": " + d);
   }
}

Các printValueAndInHexphương pháp chỉ là một helper hex-in.

Kết quả như sau:

403787ae147ae148: 23.53
4017851eb851eb85: 5.88
4031a3d70a3d70a4: 17.64
4047866666666666: 47.05
--------
403d68f5c28f5c29: 29.41
4047866666666666: 47.05
--------
404495c28f5c28f6: 41.17
4047866666666667: 47.050000000000004

4 số đầu tiên là x, y, z, và s's đại diện thập lục phân. Trong biểu diễn dấu phẩy động IEEE, các bit 2-12 đại diện cho số mũ nhị phân , tức là tỷ lệ của số. (Bit đầu tiên là bit dấu và các bit còn lại cho phần định trị .) Số mũ được biểu diễn thực sự là số nhị phân trừ đi 1023.

Số mũ của 4 số đầu tiên được trích ra:

    sign|exponent
403 => 0|100 0000 0011| => 1027 - 1023 = 4
401 => 0|100 0000 0001| => 1025 - 1023 = 2
403 => 0|100 0000 0011| => 1027 - 1023 = 4
404 => 0|100 0000 0100| => 1028 - 1023 = 5

Bộ bổ sung đầu tiên

Số thứ hai ( y) có độ lớn nhỏ hơn. Khi cộng hai số này để có được x + y, 2 bit cuối cùng của số thứ hai ( 01) bị dịch chuyển ra khỏi phạm vi và không được đưa vào phép tính.

Phép cộng thứ hai thêm bớt x + yvà cộng zhai số cùng tỉ lệ.

Bộ bổ sung thứ hai

Ở đây, x + zxảy ra đầu tiên. Chúng có cùng quy mô, nhưng chúng mang lại một con số cao hơn về quy mô:

404 => 0|100 0000 0100| => 1028 - 1023 = 5

Phép cộng thứ hai thêm x + zy, và bây giờ 3 bit được loại bỏ yđể thêm các số ( 101). Ở đây, phải có một vòng trở lên, vì kết quả là số dấu phẩy động tiếp theo tăng lên: 4047866666666666đối với tập bổ sung đầu tiên so với 4047866666666667tập bổ sung thứ hai. Lỗi đó đủ đáng kể để hiển thị trong bản in của tổng số.

Kết luận, hãy cẩn thận khi thực hiện các phép toán trên số IEEE. Một số biểu diễn không chính xác, và chúng càng trở nên thiếu chính xác hơn khi các thang đo khác nhau. Cộng và trừ các số có tỷ lệ tương tự nếu bạn có thể.

44
Eric Lippert 2013-11-07 09:44.

Câu trả lời của Jon tất nhiên là đúng. Trong trường hợp của bạn, lỗi không lớn hơn lỗi bạn sẽ tích lũy khi thực hiện bất kỳ phép toán dấu chấm động đơn giản nào. Bạn có một tình huống trong đó trong một trường hợp, bạn không gặp lỗi và trong một trường hợp khác, bạn gặp một lỗi nhỏ; đó không thực sự là một kịch bản thú vị. Một câu hỏi hay là: có những trường hợp nào mà việc thay đổi thứ tự tính toán đi từ một lỗi nhỏ thành một lỗi lớn (tương đối) không? Câu trả lời rõ ràng là có.

Hãy xem xét ví dụ:

x1 = (a - b) + (c - d) + (e - f) + (g - h);

vs

x2 = (a + c + e + g) - (b + d + f + h);

vs

x3 = a - b + c - d + e - f + g - h;

Rõ ràng trong số học chính xác chúng sẽ giống nhau. Thật thú vị khi cố gắng tìm các giá trị cho a, b, c, d, e, f, g, h sao cho các giá trị của x1 và x2 và x3 khác nhau một lượng lớn. Xem nếu bạn có thể làm như vậy!

10
Compass 2013-11-07 09:06.

Điều này thực sự bao gồm nhiều thứ hơn là chỉ Java và Javascript, và có thể sẽ ảnh hưởng đến bất kỳ ngôn ngữ lập trình nào sử dụng float hoặc double.

Trong bộ nhớ, dấu chấm động sử dụng một định dạng đặc biệt dọc theo các dòng của IEEE 754 (bộ chuyển đổi cung cấp lời giải thích tốt hơn nhiều so với tôi có thể).

Dù sao, đây là công cụ chuyển đổi float.

http://www.h-schmidt.net/FloatConverter/

Vấn đề về thứ tự của các hoạt động là "độ mịn" của hoạt động.

Dòng đầu tiên của bạn mang lại 29,41 từ hai giá trị đầu tiên, cho chúng ta 2 ^ 4 dưới dạng số mũ.

Dòng thứ hai của bạn cho kết quả là 41,17 cho chúng ta 2 ^ 5 dưới dạng số mũ.

Chúng ta đang mất một con số đáng kể khi tăng số mũ, điều này có khả năng thay đổi kết quả.

Hãy thử đánh dấu vào bit cuối cùng ở ngoài cùng bên phải bật và tắt cho 41,17 và bạn có thể thấy rằng một thứ gì đó "không đáng kể" như 1/2 ^ 23 của số mũ sẽ đủ để gây ra sự khác biệt dấu phẩy động này.

Chỉnh sửa: Đối với những người bạn nhớ những con số quan trọng, điều này sẽ thuộc danh mục đó. 10 ^ 4 + 4999 với con số có nghĩa là 1 sẽ là 10 ^ 4. Trong trường hợp này, con số có ý nghĩa nhỏ hơn nhiều, nhưng chúng ta có thể thấy kết quả với .00000000004 gắn liền với nó.

9
jbx 2013-11-07 08:57.

Số dấu chấm động được biểu diễn bằng định dạng IEEE 754, định dạng này cung cấp kích thước cụ thể của các bit cho phần định trị (ý nghĩa và). Thật không may, điều này cung cấp cho bạn một số 'khối xây dựng phân số' cụ thể để chơi với và một số giá trị phân số nhất định không thể được biểu diễn chính xác.

Những gì đang xảy ra trong trường hợp của bạn là trong trường hợp thứ hai, việc bổ sung có thể đang gặp phải một số vấn đề về độ chính xác do thứ tự các phần bổ sung được đánh giá. Tôi chưa tính toán các giá trị, nhưng có thể ví dụ như 23,53 + 17,64 không thể được biểu diễn chính xác, trong khi 23,53 + 5,88 có thể.

Thật không may, đó là một vấn đề đã biết mà bạn phải đối phó.

7
hotforfeature 2013-11-07 08:53.

Tôi tin rằng nó liên quan đến trình tự trốn chạy. Trong khi tổng tự nhiên giống nhau trong thế giới toán học, trong thế giới nhị phân thay vì A + B + C = D, nó

A + B = E
E + C = D(1)

Vì vậy, có bước thứ hai mà số dấu phẩy động có thể bắt đầu.

Khi bạn thay đổi thứ tự,

A + C = F
F + B = D(2)

Related questions

MORE COOL STUFF

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett đã bất chấp những lời khuyên hẹn hò điển hình khi cô gặp chồng mình.

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Michael Sheen là một diễn viên phi lợi nhuận nhưng chính xác thì điều đó có nghĩa là gì?

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Ngôi sao của Hallmark Colin Egglesfield chia sẻ về những cuộc gặp gỡ với người hâm mộ ly kỳ tại RomaDrama Live! cộng với chương trình INSPIRE của anh ấy tại đại hội.

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Bạn sẽ phải phủi sạch đầu đĩa Blu-ray hoặc DVD để xem tại sao Northern Exposure trở thành một trong những chương trình nổi tiếng nhất của thập niên 90.

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

8 công dụng tuyệt vời của Baking Soda và Giấm

8 công dụng tuyệt vời của Baking Soda và Giấm

Bạn biết đấy, hai sản phẩm này là nguồn điện để làm sạch, riêng chúng. Nhưng cùng với nhau, chúng có một loạt công dụng hoàn toàn khác.

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Thủy điện rất cần thiết cho lưới điện của Hoa Kỳ, nhưng nó chỉ tạo ra năng lượng khi có nước di chuyển. Bao nhiêu nhà máy thủy điện có thể gặp nguy hiểm khi các hồ và sông cạn kiệt?

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Tóc tỉa từ các tiệm và các khoản quyên góp cá nhân có thể được tái sử dụng như những tấm thảm thấm dầu và giúp bảo vệ môi trường.

Làm thế nào để xây dựng một quả địa cầu từ Scratch

Làm thế nào để xây dựng một quả địa cầu từ Scratch

Thời gian, sự kiên nhẫn, thời gian, sự cống hiến và thời gian chỉ là một vài trong số những thứ mà Peter Bellerby cần để thành lập và sau đó điều hành Bellerby & Co. Globemakers, một trong những công ty duy nhất trên Trái đất vẫn sản xuất các quả địa cầu bằng tay.

Năm giai đoạn đau buồn sau khi mất việc làm

Năm giai đoạn đau buồn sau khi mất việc làm

Đó là một ngày thứ Bảy, máy bay của tôi hạ cánh, và tôi đã sẵn sàng để thư giãn trong một kỳ nghỉ cuối tuần ngắn ngủi, khi một email đến trên điện thoại của tôi. Tôi đã mất việc.

Giữ an toàn cho danh tính của bạn với một cảnh báo đóng băng hoặc gian lận tín dụng

Giữ an toàn cho danh tính của bạn với một cảnh báo đóng băng hoặc gian lận tín dụng

Nếu bạn đã từng bị đánh cắp danh tính của mình, bạn biết đó là một trải nghiệm đáng sợ và căng thẳng. Một cách không phổ biến để ngăn chặn nó? Tín dụng bị đóng băng.

Buổi ra mắt phần 3 của The Good Place có một học sinh mới: Khán giả

Buổi ra mắt phần 3 của The Good Place có một học sinh mới: Khán giả

Eleanor (Kristen Bell) dường như đã tình nguyện cho chúng tôi làm vật tưởng nhớ. NBC's The Good Place là một chương trình thích thử thách tốt.

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Rothschild's luggage got lost, but luckily she has an incredible closet to shop: Sister Paris Hilton's!

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa. Từ Hollywood đến New York và mọi nơi ở giữa, hãy xem các ngôi sao yêu thích của bạn đang làm gì!

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

Các nhà điều tra đang xem xét liệu nhóm và nghi phạm có biết nhau trước vụ tấn công hay không

Thanh thiếu niên, Gia đình Florida Hội đồng quản trị trường học về Luật 'Không nói đồng tính': 'Buộc chúng tôi tự kiểm duyệt'

Thanh thiếu niên, Gia đình Florida Hội đồng quản trị trường học về Luật 'Không nói đồng tính': 'Buộc chúng tôi tự kiểm duyệt'

Vụ kiện, nêu tên một số học khu, lập luận rằng dự luật "Không nói đồng tính" được ban hành gần đây của Florida "có hiệu quả im lặng và xóa bỏ học sinh và gia đình LGBTQ +"

Đường băng hạ cánh

Đường băng hạ cánh

Cuối hè đầu thu là mùa hoài niệm. Những chiếc đèn đường chiếu ánh sáng của chúng qua những con đường đẫm mưa, và những chiếc lá dưới chân - màu đỏ cam tắt trong bóng chạng vạng - là lời nhắc nhở về những ngày đã qua.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Vào năm 2021, tôi khuyến khích bạn suy nghĩ lại mọi thứ bạn biết về khách hàng mà bạn phục vụ và những câu chuyện bạn kể cho họ. Lùi lại.

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Vào ngày sinh nhật thứ 9 của Felix The Cat, tôi nhớ về một trong những mất mát lớn nhất trong cuộc đời trưởng thành của tôi - Sophie của tôi vào năm 2013. Tôi đã viết bài luận này và chia sẻ nó trên nền tảng này một thời gian ngắn vào năm 2013.

Khi bạn không thể trở thành người mà Internet muốn bạn trở thành

Khi bạn không thể trở thành người mà Internet muốn bạn trở thành

Tôi ghét từ "tàu đắm". Mọi người cảm thấy thoải mái trong la bàn đạo đức của riêng mình, và khi làm như vậy, họ thấy mình vượt qua sự phán xét.

Language