Những gì bạn nên biết về float rounding
golang
39
White

huydx viết ngày 18/07/2017

Introduction

Mới đây tôi có đọc được một pull-request khá thú vị của golang: https://go-review.googlesource.com/c/43652/.
Pull request này nhằm giải quyết vấn đề khá thú vị tại https://golang.org/issue/20100 về việc: nên thêm hàm Round cho Float vào trong std của golang

Tóm tắt issue 20100 thì tác giả có nêu lên vấn đề là

Cần thêm hàm Round cho math library của golang. Hàm này sẽ nhận vào float64 và làm tròn xuống int hoặc uint. Khi đọc qua issue thì mình thấy khá bất ngờ bởi mình không nghĩ là golang lại không có hàm round (làm tròn) trong std, tuy nhiên khi đọc kĩ lại nội dung issue thì mình thấy hiểu biết về hàm round của mình khá hạn hẹp. Bạn nào thấy cần thiết có thể xem cụ thể các tranh luận trong issue, tuy nhiên cho ai lười đọc thì mình tóm tắt lại vài ý như sau:

  • Golang team không muốn có hàm round trong std, bởi hàm round có rất nhiều implementation khác nhau (mà mình sẽ nói cụ thể ở dưới), vì thế mà golang team muốn phó mặc việc implement hàm đó cho người dùng, thay vì việc cung cấp một implementation mà "dễ gây hiểu nhầm" (theo ý họ).
  • Tuy nhiên theo các user khác thì trong thực tế việc tự implement hàm round chứa nhiều nguy cơ hơn bởi việc implement hàm round "đúng" (thế nào là đúng thì mình sẽ nói kĩ hơn ở dưới). Core team của CockCroachDB có nói về khó khăn của họ trong việc tự implement hàm round tại comment này
  • Cuối cùng, golang team đồng ý là nên add hàm này (xem tại comment), với idea là nên add một hàm round giống như của C99 (C language, theo tiêu chuẩn ISO/IEC 9899:1999), hay nói một cách khác là hàm round theo phương pháp "halfway away from 0" (sẽ nói cụ thể hơn ở dưới)

Về thuật toán làm tròn (rounding) nói chung

Tại sao rounding quan trọng

Nói về rounding thì phải nói về floating point number trước. Floating point number (hay gọi tắt là float) sinh ra là để biểu diễn một cách "gần đúng" những số không thế biểu diễn chính xác được (số thực chẳng hạn). Việc này giải quyết bài toán biểu diễn những số như là $\sqrt(2)$ hay là $1/7$.

Tuy nhiên, từ phía ngược lại, việc biểu diễn "gần đúng" sẽ dẫn đến bài toán là một số khi vượt quá số bit có thể biểu diễn được nó, hoặc là số thực vô hạn (như ví dụ trên $\sqrt(2)$ thì sẽ cần biến nó về số có thể biểu diễn được dưới dạng float, gần nó nhất. Do đó sẽ có nhu cầu về việc "làm tròn", ví dụ (ví dụ này sai, nhưng vì dễ hiểu nên mình dùng tạm): ví dụ giá trị floating point của $1/10$ giả sử là $0.0989999$ thì việc làm tròn sẽ giúp chúng ta có giá trị chính xác là $0.1$. Ngoài ra thì kĩ thuật làm tròn cũng rất quan trọng trong việc tính toán (các phép toán cộng / trừ với floating point).

Trong các kĩ thuật làm tròn nói chung (float về float) thì việc làm tròn float về int khá quan trọng, trong việc xử lý các bài toán không cần chính xác lắm, hoặc trong các nhu cầu tính toán thông thường mà sử dụng int. Trong issue của golang thì bài toàn nói đến là làm tròn float về int.

Tại sao rounding lại khó?

Có 3 điểm chính khiến rounding khá đau đầu:

  • Rounding phục vụ chính cho float, và bạn nào muốn biết float phức tạp ra sao, hãy đọc bài viết này.
  • Có quá nhiều phương pháp rounding (mà sẽ nói rõ hơn ở dưới)
  • Có nhiều edge case (với f là số cần làm tròn thì : f == 0, f âm, f dương, f > MAX_FLOAT, f < MIN_FLOAT...) có thể khiến các implementation tưởng chừng như đúng sẽ không chính xác

Những phương pháp float rounding nào hiện có

Có 5 phương pháp chính để round một số float thành int gồm có:

  • Round down : làm tròn xuống (r(1.6) = 1)
  • Round up : làm tròn lên (r(1.6) = 2)
  • Round towards zero : phần integer của float (mà không có fraction)
  • Round away from zero : nếu f là int thì round(f) = f, nếu không thì round(f) = số int q gần 0 nhất mà f nằm giữa 0 và q (vừa là round up trong case f dương và cũng là round down trong case f âm)
  • Round to nearest làm tròn về số int gần nhất. Trong trường hợp f nằm đúng giữa (0.5 chẳng hạn) thì phải theo rule "Tie breaking" ở dưới.

Tie breaking rules

Đây là các rule nhằm phân định khi làm tròn một số nằm "đúng ở giữa" như là 0.5, thì nên theo hướng nào.

  • Round half down (23.5 thành 24 và -23.5 thành 23)
  • Round half up (23.5 -> 23, và −23.5 -> −24)
  • Round half towards zero (23.5 -> 23, và −23.5 -> −23)
  • Round half away from zero (23.5 -> 24, and −23.5 -> −24)
  • Round half to even (23.5 và 24.5 đều round thành 24)
  • Round half to odd (22.5 và 23.5 đều round thành 23)

Phù, mệt quá, nói chung chắc các bạn chả nhớ gì đâu, nên mình cứ để đây để các bạn thấy số lượng lựa chọn khổng lồ chỉ để "làm tròn". Trong thực tế thì thường default mode của rounding là "(Round to nearest) halfway away from 0". (Tức là làm tròn đến số int gần nhất, và tie breaking rule là Half away from zero)

Vậy vấn đề là implement thuật toán làm tròn trên như thế nào?

Thuật toán này có thể được implement bằng một loạt các hàm condition (nếu phần dư > 0.5 thì ..., nếu phần dư < 0.5 thì ..., nếu phần dư == 0.5 thì...).
Tuy nhiên để làm việc này cũng không dễ với yêu cầu là "performance". Tuy nhiên rất may mắn là đã có người pull request cho implementation này rồi, mình khá tò mò nên đã xem thử họ làm thế nào, thì thấy implementation không hề đơn giản, chúng ta hãy xem cụ thể ở dưới nhé.

Implement của https://go-review.googlesource.com/c/43652/

const (
    mask     = 0x7FF // exponent mask
    shift    = 64 - 11 - 1 // mantissa bit num
    bias     = 1023
)

// test code for https://go-review.googlesource.com/c/43652/4/src/math/floor.go#b52
func Round(x float64) float64 {
    const (
        signMask = 1 << 63
        fracMask = (1 << shift) - 1
        halfMask = 1 << (shift - 1)
        one      = bias << shift
    )
    bits := math.Float64bits(x)
    e := uint(bits>>shift) & mask

    switch {
    case e < bias:
        // Round abs(x)<1 including denormals.
        bits &= signMask // +-0
        if e == bias-1 {
            bits |= one // +-1
        }
    case e < bias+shift:
        // Round any abs(x)>=1 containing a fractional component [0,1).
        e -= bias
        bits += halfMask >> e
        bits &^= fracMask >> e
    }

    return math.Float64frombits(bits)
}


func main() {
    fmt.Println(Round(122.22) // 122
    fmt.Println(Round(-122.22) // -122    
}

Để hiểu được implement ở trên thì chúng ta phải quay lại: Float có bit layout thế nào. Đây là phần mà chắc chắn bạn nào cũng đã học ở đại học, nếu bạn vẫn nhớ :v.

Một số float 64bit (hay còn gọi là double) gồm có 64 bit cạnh nhau, với layout như dưới đây:

S EEEEEEE EEEE MMMM MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM

Ở đây S là bit dấu (sign bit) (S == 1 thì là số âm, S == 0 thì là số dương)
Tiếp theo là 11 bit exponent , được tiếp nối bởi 52 bit fraction (hay còn gọi là mantissa)

Idea của floating point là: bất kì một số thực F nào cũng sẽ biểu diễn được dưới dạng:

$F = (-1)^S * 2^E * 1.M$

từ công thức trên bạn có thể hiểu sơ qua là:

  • S biểu diễn cho dấu
  • Exponent biểu diễn cho độ lớn: (E có thể đến 12 bit tức là F có thể có độ lớn đến $2^{11}$ (thực ra là $2^{10}$ nếu normalize mà sẽ được nói rõ hơn ở dưới) và có thể nhỏ đến $2^{-12}$).
  • Mantissa biểu diễn cho số có thể biểu diễn "sau dấu phẩy", hay còn gọi là "độ chính xác" (tức là mantissa bit càng to, thì số có thể biểu diễn được càng phong phú)

Một số điểm mà có thể các bạn không biết về biểu diễn thực tế của float:

Normalized exponent

  • Phần exponent (E) có thể được "normalize", tức là để biểu diễn được cả E âm, thì thay vì dùng sign bit như bình thường, thì chúng ta "giả định" rằng biểu diễn này sẽ luôn trừ đi 1 số X, tức là thực tến nó sẽ biểu diễn E-X. Với float64 thì X có giá trị là 1023 (tức là 2^10 - 1). Trong thực tế X được gọi là "bias"

Để hiểu rõ hơn phần này, hãy làm một ví dụ nhỏ: biểu diễn 1.0 dưới dạng bit array

$ gore> fmt.Sprintf("%2b", math.Float64bits(1.0))
011111111110000000000000000000000000000000000000000000000000000

Như bạn thấy ở trên thì về lý thuyết theo công thức $F = (-1)^S * 2^E * 1.M$ thì

  • để biểu diễn 1 thì S (sign bit) phải bằng 0 (đúng rồi)
  • Exponent phải bằng $2^0$ tức là có LSB (least significant bit) hay là bit ngoài cùng bên phải là 1 (hay là 00000...1)
  • và Mantissa phải bằng 0 (đúng rồi)

Tuy nhiên nhìn ví dụ trên thì bạn thấy exponent thay vì 000....1 thì lại là 111111...0. Việc đó mô phỏng chính xác cái mình đã nói ở trên về bias: 1023 có giá trị bằng 111111...0, và trừ đi chính nó sẽ có giá trị là 0, tức là $2^0 == 1$

Hiểu rõ về thuật toán làm tròn ở trên

Idea của thuật toán khá thú vị (có lẽ trong IEEE754 có mô tả về việc này nhưng tôi chưa thử đọc lại mô tả IEEE754, bạn nào đọc kĩ rồi thì comment lại dưới đây nhé). Trước khi đi vào cụ thể thì hãy đi vào một số thứ "dễ hiểu trước"

Đầu tiên input X sẽ được đưa về biểu diễn dưới dạng bit array thông qua hàm

    bits := math.Float64bits(x)

Sau đó có một câu lệnh switch đó dành để mô tả 2 trường hợp:

  • $-1 < x < 1$ thì sẽ làm tròn x về ($+0$ hoặc là $-0$) tuỳ vào sign bit
  • $x > 1$ thì sẽ làm tròn x về "số int gần nhất"

Điểm thú vị nằm trong trường hợp thứ 2 $x > 1$: làm thế nào để làm tròn X về "số int gần nhất", thế nào là "số int gần nhất". Hãy lấy một vài ví dụ đơn giản

  • Làm tròn 4.6 thành 5

alt text

  • Làm tròn 2.9 thành 3

alt text

Từ 2 trường hợp ở trên tôi "dự đoán" việc làm tròn lên đều có một rule là:

  • Từ một offset E nào đó của mantissa thì toàn bộ các bit sau E sẽ bị clear
  • Bit tại offset E sẽ được cộng thêm 1

Vậy với làm tròn xuống thì sao

  • Làm tròn 3.1 thành 3 alt text

Rule của làm tròn xuống gần tương tự với làm tròn lên :

  • Từ một offset E nào đó của mantissa thì toàn bộ các bit sau E sẽ bị clear

Nhìn lại đoạn code thì chúng ta sẽ thấy đoạn code mô tả đúng cho rule mà tôi đã dự đoán ở trên (khi |x| > 1), điều đó thể hiện ở 2 dòng

    bits += halfMask >> e
    bits &^= fracMask >> e

Quay lại, halfMask với fracMask là gì:

  • Biến shift chính là số mantisssa (ở đây là 52)
  • halfMask mô tả 1 << (shift - 1) tức là 51 bit mà bắt đầu bằng bit 1, còn lại là 0 (10000....0) (50 số 0)
  • fracMask mô tả (1 << shift) - 1 tức là 51 bit 1 liên tiếp 1111....11 (51 số 1)

Áp 2 mô tả này vào phép toán

bits += halfMask >> e

có nghĩa là biến mantissa tại offset e sẽ được cộng thêm 1, phù hợp với rule tôi đã nói ở trên

còn phép toán

bits &^= fracMask >> e

có nghĩa là clear toàn bộ bit từ sau offset e (phép toán &^ có nghĩa là AND với NOT 11111, có mục đích clear bit)

Như vậy chúng ta chỉ còn lại 2 câu hỏi:

  • offset E có ý nghĩa thế nào
  • Tại sao thao tác + 1 và clear bit tại offset E lại giúp tìm số int gần nhất so với X

Hãy bắt đầu từ câu hỏi: offset E có ý nghĩa thế nào? Quay lại đoạn code

e := uint(bits>>shift) & mask
e -= bias

Ở đây

  • mask là 0x7FF (tức là 10 bit 1), tương đương với bias
  • Và nhớ lại là ở trên chúng ta vừa có : Biến shift chính là số mantisssa (ở đây là 52).

Nhìn thì có vẻ phức tạp, tuy nhiên xem lại những kiến thức về exponent normalize ở trên thì có thể rút ra : e chính là phần exponent, biểu diễn theo số int (tức là 1024 thì là 10).
Vậy chúng ta cần chưng minh là, với offset e bằng số exponent, thì việc +1 tại offset đó và clear toàn bộ phần bit sau E của mantissa sẽ giúp làm tròn về số int gần nhất.

Quay trở lại biểu diễn float

$F = (-1)^S * 2^E * 1.M$

thì chúng ta có thể thấy nếu bỏ qua phần normalize, thì nếu trong trường hợp dưới đây

alt text

Tức là khi offset từ điểm giao giữa exponent (e) đến bit gần nhất của exponent và mantissa là bằng nhau (ví dụ ở trên là 3), thì chuyện gì sẽ xảy ra? Chúng ta sẽ có

$2^{3} * 1.2^{-3}$

hay chính là 1 !!!!

Điều đó có nghĩa là, nếu lấy e là số exponent theo int, và + offset của mantissa tại e thêm 1, đồng thời clear hết bit của phần đắng sau đi thì chúng ta sẽ có một số int (tại sao lại chắc chắn nó là int thì các bạn thử comment xem nhé ), với sai số là 1 so với input X, hay nói cách khác chính là số int, "gần X nhất".

Như vậy là chúng ta đã chứng minh được là, thuật toán được sử dụng trong PR của golang là đúng đắn, và hợp lý, tại sao họ nghĩ ra thuật toán này thì tôi chịu :v.

Để hiểu thêm về float cũng như rounding, các bạn có thể tham khảo thêm reference dưới đây:

Reference

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

huydx

115 bài viết.
858 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
135 8
Introduction (Link) là một cuộc thi ở Nhật, và cũng chỉ có riêng ở Nhật. Đây là một cuộc thi khá đặc trưng bởi sự thú vị của cách thi của nó, những...
huydx viết hơn 1 năm trước
135 8
White
109 14
Happy programmer là gì nhỉ, chắc ai đọc xong title của bài post này cũng không hiểu ý mình định nói đến là gì :D. Đầu tiên với cá nhân mình thì hap...
huydx viết gần 3 năm trước
109 14
White
86 10
(Ảnh) Mở đầu Chắc nhiều bạn đã nghe đến khái niệm oauth. Về cơ bản thì oauth là một phương thức chứng thực, mà nhờ đó một web service hay một ap...
huydx viết hơn 2 năm trước
86 10
Bài viết liên quan
White
17 0
Crawl dữ liệu Crawl là một vấn đề hay gặp trong quá trình làm software. Ví dụ lấy tin tức, tin giảm giá, vé xem phim... là những dạng của crawl. Mộ...
Thach Le viết gần 2 năm trước
17 0
White
40 7
Là một người thường xuyên đọc Quora, có một điểm cá nhân tôi thấy rất ấn tượng ở quora chính là khả năng autocomplete với tốc độ ánh sáng. (Ảnh) ...
huydx viết 2 tháng trước
40 7
White
7 2
Makefile thực hiện một số thao tác thường dùng trong Go Khi làm project Go mình thường tạo một file Makefile dạng này: Lưu ý nhớ thay thành tên m...
Huy Trần viết hơn 1 năm trước
7 2
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
115 bài viết.
858 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!