Kiểm tra năm nhuận chỉ với 3 lệnh

• Triển khai một hàm xác định năm nhuận chỉ với 3 lệnh CPU
• Phương pháp này hoạt động không cần nhánh truyền thống, sử dụng phép toán bit và phép nhân
• Cách làm này chính xác trong phạm vi từ năm 0 đến 102499
• Kết quả benchmark cho thấy hiệu năng nhanh hơn khoảng 3,8 lần so với phương pháp hiện có

---

Tổng quan và vấn đề đặt ra

• Với các năm từ 0 đến 102499, có một hàm kiểm tra năm nhuận chỉ dùng đúng 3 lệnh CPU
  • Hàm thực tế được dùng có dạng ((y * 1073750999) & 3221352463) <= 126976
• Bài viết giải thích nguyên lý, cách hoạt động và tính hữu ích thực tế của kỹ thuật bit-twiddling này

Cách kiểm tra năm nhuận truyền thống

• Thông thường, việc xác định năm nhuận được triển khai bằng phép chia lấy dư (modulo) và rẽ nhánh điều kiện
  • Kiểm tra có chia hết cho 4 hay không, không chia hết cho 100 hay không, và có chia hết cho 400 hay không
  • Mã ví dụ:

    if ((y % 4) != 0) return false  
    if ((y % 100) != 0) return true  
    if ((y % 400) == 0) return true  
    return false  
    

Tối ưu hóa cách tiếp cận chuẩn

• Có thể thay phép kiểm tra (y % 100) bằng (y % 25), và (y % 400) bằng (y % 16)
  • Lý do là trước đó đã chia theo 4, nên có thể chuyển thành quan hệ nhân với 25 và 16
• Có một hằng số ma thuật cho phép biến phép toán (y % 25) thành phép nhân và so sánh mà không cần chia
  • Ví dụ: có thể chuyển thành x * 3264175145 > 171798691
• Có thể thêm bitmask để thay thế phép chia cho 4 hoặc 16 bằng (y & 3) hay (y & 15)
• Trình biên dịch có thể tự động thực hiện các biến đổi này, nhưng cũng có thể áp dụng trực tiếp trong các ngôn ngữ khác

Cách triển khai không nhánh (branchless)

• Cũng có thể chuyển sang dạng không nhánh:

  return !(y & ((y % 25) ? 3 : 15))  
  

• Cách này phù hợp với các bài toán như code golf, nơi mục tiêu là rút ngắn độ dài mã

Tìm hằng số ma thuật: cách tiếp cận bit-twiddling

• Để làm công thức kiểm tra năm nhuận đơn giản hơn nữa, tác giả sử dụng tìm kiếm tổ hợp và Z3, một SMT Solver
  • Dạng công thức: ((y * f) & m) <= t
• Dùng Z3 để tìm các hằng số f, m, t thỏa mãn yêu cầu
  • Tìm ra các giá trị cho kết quả chính xác trong phạm vi 0~102499
  • Kết quả cuối cùng là (y * 1073750999) & 3221352463 <= 126976

Giải thích nguyên lý hàm và cấu trúc bên trong

• Phân tích các hằng số ở dạng nhị phân và chia chúng thành ba vùng bit chính: A, B, C
  • Trạng thái bit của từng vùng bao quát 3 điều kiện cần để xác định năm nhuận
• Phân rã logic của hàm:
  • Vùng A: kiểm tra điều kiện bội số của 4, bao gồm cả việc (y % 4) != 0
  • Vùng B: lọc điều kiện (y % 100) != 0 bằng nhiều mẫu khác nhau (ví dụ: hai chữ số cuối là 14, 57, 71, v.v.)
  • Vùng C: kiểm tra (y % 16) == 0, tức là bội số của 16
• Giải thích cách phép nhân thực sự kết hợp nhiều điều kiện mà không cần tính số dư
  • Khi nhân với hằng số ma thuật, các bội số của 100 tạo ra các mẫu bit đặc trưng
  • Ngoài ra còn có phân tích cấu trúc toán học bên trong, như sai số nhân và các mẫu chữ số nhiều hàng

Khả năng mở rộng phạm vi và độ rộng bit

• Khi mở rộng sang 64 bit, bài viết cũng đưa ra cách tìm tổ hợp hằng số ma thuật phù hợp
  • Có thể thử nhiều giá trị f, m, t khác nhau để tìm phạm vi dài nhất
  • Trên StackExchange cũng có các ví dụ chứng minh việc dùng Z3 và tổ hợp tối ưu

Benchmark và so sánh hiệu năng thực tế

• Kết quả benchmark:
  • Với các giá trị dễ đoán như năm 2025, chênh lệch hầu như không đáng kể ở mức 0,65~0,69ns
  • Với đầu vào ngẫu nhiên, is_leap_year_fast cho hiệu năng nhanh hơn khoảng 3,8 lần
  • Tùy theo mẫu đầu vào, cách dùng nhánh có thể khó dự đoán và khi đó phương pháp này có lợi thế đáng kể

Kết luận và khả năng ứng dụng thực tế

• Trong ứng dụng thực tế, nếu giá trị có thể dự đoán thì lợi ích không nhiều, nhưng rất hữu ích trong các tình huống có lượng lớn dữ liệu ngẫu nhiên
• Nếu muốn thay thế thư viện chuẩn trong Python hay C#, cần có benchmark toàn chương trình mang tính thực tế
• Bản thân ý tưởng và cách triển khai rất thú vị, và trong một số tình huống là một giải pháp hấp dẫn về mặt hiệu năng

[chickendreamtree]

Bài viết khiến tôi nhớ đến fast inverse sqrt

[GN⁺]

Ý kiến Hacker News

• Khá ngạc nhiên khi các trình biên dịch mới như gcc hay clang có thể tự động tối ưu đoạn mã như is_leap_year1 thành dạng như is_leap_year2, nên có cảm giác không thật sự cần tự tay tối ưu ở cấp mã nguồn C, dù điều này vẫn có thể hữu ích trong các ngôn ngữ khác, đặc biệt là cách phiên bản mới nhất của mã nguồn cal xử lý việc kiểm tra năm nhuận cực kỳ ngắn gọn rất ấn tượng
  • Tôi thích việc mã của Linux dễ hiểu hơn nhiều vì nó đảo ba điều kiện liên tiếp mỗi lần và không dùng kiểu trả về giá trị mặc định, gặp cấu trúc mã phức tạp như vậy khi debug đúng là phát điên
• Hoàn toàn không ngạc nhiên khi lời giải thích về cách đoạn mã ((y * 1073750999) & 3221352463) <= 126976 hoạt động lại phức tạp đến vậy, thậm chí điều đó là hiển nhiên
• Rất thích các kỹ thuật tối ưu bằng magic number khó hiểu như thế này; mỗi lần thấy lại tự hỏi ngày xưa khi viết vòng lặp trong bằng assembly mình đã bỏ lỡ bao nhiêu mẹo tối ưu, nếu có bộ sưu tập nào tổng hợp các kỹ thuật như vậy thì mong được chia sẻ
  • Chia sẻ các liên kết về nhiều mẹo tối ưu khác nhau như bộ sưu tập bit-twiddling tricks, macro CMP(X, Y) hiệu quả cho kiểu so sánh phong cách UNIX, ví dụ tối ưu hàm signum, ví dụ mã assembly cho Motorola 68000, và bộ macro bit có nguồn gốc từ OpenSolaris, đồng thời cũng tiếc là blog Open Solaris đã biến mất; rất đáng xem với những ai quan tâm đến tối ưu mã
  • Gợi ý cuốn sách "Hacker's Delight", chứa đầy các bit trick và kỹ thuật tối ưu mức thấp
  • Đề xuất tìm hiểu kỹ thuật supercompilation
  • Không phải ngày xưa người ta bỏ lỡ những kỹ thuật này, mà thời đó phép nhân quá đắt đỏ nên chính những thứ như vậy mới là tối ưu
• Không ngờ việc kiểm tra năm nhuận lại thú vị đến thế; có lẽ các lập trình viên mức thấp đã tìm ra các mẹo này từ lâu nhưng không ghi chép lại, và có cảm giác những thứ như vậy có thể vẫn còn ẩn trong mã cũ, thật muốn khám phá nếu có bộ sưu tập các kỹ thuật kiểu này
  • Hồi những năm 80 từng tự học mấy thứ này trên z80 ở nhà nhưng giờ quên gần hết, thỉnh thoảng đem ra cho các con ngoài 20 xem thì cứ như đang làm ảo thuật
• Nếu cần biết năm nào là năm nhuận trước năm 6000, hãy dùng máy tính tương tác và công cụ trực quan hóa do tác giả tự làm; dù số lệnh máy có hơi nhiều hơn nhưng vẫn có thể xử lý hàng nghìn phép tính rất nhanh, và các mẹo toán học cũng rất đáng nể
• Khi đọc chương về bit manipulation, đã nảy ra ý nghĩ "hay là dùng solver được không", và khá bất ngờ khi tác giả thực sự dùng đúng cách đó, rất hài lòng với cách tiếp cận tỉ mỉ này
• Có đề xuất nên thêm một hàm kiểm tra năm nhuận như thế này vào current-time-api
• Khi nhìn các con số ở dạng nhị phân sẽ thấy những mẫu hình thú vị; việc mọi số nguyên tố, trừ 2, đều kết thúc bằng 1 trông khá hấp dẫn
  • Có thể trông vui thật, nhưng mọi số lẻ đều kết thúc bằng 1, mà số nguyên tố về bản chất thì ngoài 2 ra không thể là số chẵn, nên cũng có ý kiến rằng điều này chẳng mang nhiều ý nghĩa
• Có người chỉ ra rằng trong bài toán năm nhuận không có số 0; thật ra không có "năm 0", mà từ 1 TCN chuyển thẳng sang 1 SCN, nên kiểm tra 0 là vô nghĩa
  • Nếu xem phần đầu bài viết thì tiền đề khi thiết kế thuật toán năm nhuận là dùng lịch Gregory kéo dài và cách đánh số năm thiên văn, và nếu không có điều kiện này thì việc kiểm tra năm nhuận sẽ trở nên phức tạp tùy theo từng locale
  • Nếu dùng cách đánh số năm thiên văn thì sẽ xuất hiện năm 0, và trong quản lý năm/tháng thì cách đó lại gọn gàng hơn; đề xuất dùng biểu diễn thiên văn cho dữ liệu nội bộ và chỉ chuyển sang BCE/CE khi hiển thị ra ngoài
  • Lịch trước khi Gregorian được đưa vào sử dụng vốn đã mơ hồ về chính tiêu chuẩn của nó và lại khác nhau theo từng vùng; năm 1582 còn có chuyện "xóa 10 ngày" khi nhảy qua mười ngày trong một đêm, nên các phép tính với ngày tháng trước đó là không đáng tin, chưa kể các giáo sĩ thời La Mã còn tùy tiện điều chỉnh năm nhuận vì mê tín hoặc hối lộ nên càng phức tạp hơn
  • Trong tiêu chuẩn ISO8601, năm 0 được cho phép, và trong lịch thiên văn thì năm 0 có nghĩa là 1 TCN, các năm BCE đều bị dịch đi -1
• Hiếm khi mã nguồn thực sự khiến người ta bật cười thành tiếng, nên đây là một trải nghiệm rất vui