ตรวจสอบปีอธิกสุรทินด้วยคำสั่งเพียง 3 คำสั่ง

 (hueffner.de)
13 คะแนน โดย GN⁺ 2025-05-16 | 2 ความคิดเห็น | แชร์ทาง WhatsApp
  • มีการสร้างฟังก์ชันสำหรับตรวจสอบปีอธิกสุรทินโดยใช้ คำสั่ง CPU เพียง 3 คำสั่ง
  • วิธีนี้ทำงานแบบไม่มีการแตกแขนงโดยอาศัยการดำเนินการบิตและการคูณ
  • วิธีนี้ ให้ผลถูกต้องในช่วงปี 0~102499
  • ผลการเบนช์มาร์กแสดงว่าให้ ประสิทธิภาพเร็วขึ้นราว 3.8 เท่า เมื่อเทียบกับวิธีเดิม

ภาพรวมและการตั้งปัญหา

  • สำหรับปีในช่วง 0 ถึง 102499 มีฟังก์ชันที่ใช้ คำสั่ง CPU เพียง 3 คำสั่งในการตรวจสอบปีอธิกสุรทิน
    • ฟังก์ชันที่ใช้จริงมีโครงสร้างเป็น ((y * 1073750999) & 3221352463) <= 126976
  • อธิบายหลักการ การทำงาน และประโยชน์เชิงปฏิบัติของเทคนิค bit-twiddling นี้

วิธีตรวจสอบปีอธิกสุรทินแบบดั้งเดิม

  • โดยทั่วไปการตรวจสอบปีอธิกสุรทินจะ ทำด้วยการหารเอาเศษ (modulo) และการแตกแขนงตามเงื่อนไข
    • ตรวจว่าหารด้วย 4 ลงตัวหรือไม่, ไม่หารด้วย 100 ลงตัว, หรือหารด้วย 400 ลงตัวหรือไม่
    • โค้ดตัวอย่าง: 
      if ((y % 4) != 0) return false  
if ((y % 100) != 0) return true  
if ((y % 400) == 0) return true  
return false

การปรับแต่งแนวทางมาตรฐานให้เหมาะสมขึ้น

  • สามารถแทนการตรวจ (y % 100) ด้วย (y % 25) และแทน (y % 400) ด้วย (y % 16) ได้
    • เหตุผลคือก่อนหน้านั้นมีการหารด้วย 4 ไปแล้ว จึงเปลี่ยนเป็นความสัมพันธ์ของการคูณ 25 และ 16 ได้
  • มีค่าคงที่มหัศจรรย์ที่ใช้แปลงการคำนวณ (y % 25) ให้เป็น การคูณและการเปรียบเทียบโดยไม่ต้องหาร
    • ตัวอย่าง: แปลงเป็น x * 3264175145 > 171798691 ได้
  • สามารถใช้บิตมาสก์เพิ่มเข้ามาเพื่อแทนการหารด้วย 4 หรือ 16 ผ่าน (y & 3) หรือ (y & 15)
  • คอมไพเลอร์สามารถทำการแปลงเหล่านี้โดยอัตโนมัติได้ แต่ก็สามารถนำไปใช้เองในภาษาอื่นได้เช่นกัน

วิธีทำแบบไม่มีการแตกแขนง (branchless)

  • ยังสามารถแปลงให้อยู่ในรูปแบบที่ไม่มีการแตกแขนงได้ด้วย: 
    return !(y & ((y % 25) ? 3 : 15))
  • แนวทางนี้เหมาะกับการย่อความยาวโค้ด เช่นใน code golf

การหาค่าคงที่มหัศจรรย์: แนวทางแบบ bit-twiddling

  • เพื่อทำให้สูตรตรวจปีอธิกสุรทิน เรียบง่ายยิ่งขึ้น จึงใช้การค้นหาเชิงจัดหมู่ร่วมกับ Z3 ซึ่งเป็น SMT Solver
    • รูปแบบคือ ((y * f) & m) <= t
  • ใช้ Z3 ค้นหาค่าคงที่ f, m, t ที่ตอบโจทย์
    • เพื่อให้ได้ผลลัพธ์ที่ถูกต้องในช่วง 0~102499
    • ผลลัพธ์สุดท้ายคือ (y * 1073750999) & 3221352463 <= 126976

อธิบายหลักการของฟังก์ชันและโครงสร้างภายใน

  • วิเคราะห์ค่าคงที่ในรูปเลขฐานสอง และแบ่งออกเป็น 3 บริเวณบิตหลักคือ A, B, C
    • สถานะบิตของแต่ละบริเวณครอบคลุมเงื่อนไขการตรวจปีอธิกสุรทินทั้ง 3 ข้อ
  • การแยกองค์ประกอบเชิงตรรกะของฟังก์ชัน:
    • บริเวณ A: ตรวจเงื่อนไขการเป็นพหุคูณของ 4 รวมถึงกรณี (y % 4) != 0
    • บริเวณ B: กรองกรณี (y % 100) != 0 ด้วยแพตเทิร์นหลากหลายแบบ (เช่น ลงท้ายด้วย 14, 57, 71 เป็นต้น)
    • บริเวณ C: ตรวจ (y % 16) == 0 หรือก็คือการเป็นพหุคูณของ 16
  • อธิบายหลักการที่การคูณสามารถ รวมหลายเงื่อนไขเข้าด้วยกันได้โดยไม่ต้องคำนวณเศษโดยตรง
    • เมื่อคูณด้วยค่าคงที่มหัศจรรย์ จะเกิดแพตเทิร์นบิตเฉพาะสำหรับกรณีอย่างพหุคูณของ 100
    • นอกจากนี้ยังมีการวิเคราะห์โครงสร้างทางคณิตศาสตร์ภายใน เช่น ความคลาดเคลื่อนจากการคูณและแพตเทิร์นของตัวเลขหลายหลัก

ความเป็นไปได้ในการขยายช่วงและความกว้างบิต

  • หากขยายเป็น 64 บิต ก็มีการเสนอวิธีค้นหาชุดค่าคงที่มหัศจรรย์ที่เหมาะสมเช่นกัน
    • สามารถลองปรับค่า f, m, t ได้หลายแบบเพื่อหาช่วงที่รองรับได้ยาวที่สุด
    • บน StackExchange ก็มีตัวอย่างการพิสูจน์ชุดค่าที่เหมาะสมและการใช้ Z3 เช่นกัน

เบนช์มาร์กและการเปรียบเทียบประสิทธิภาพจริง

  • ผลเบนช์มาร์ก:
    • สำหรับค่าที่คาดเดาได้ เช่น ปี 2025 ความต่างแทบไม่มี โดยอยู่ที่ 0.65~0.69ns
    • เมื่ออินพุตเป็นแบบสุ่ม is_leap_year_fast ให้ ประสิทธิภาพเร็วขึ้นราว 3.8 เท่า
    • หากแพตเทิร์นอินพุตทำให้การแตกแขนง (branching) คาดเดาได้ยาก วิธีนี้จะมีข้อได้เปรียบอย่างมาก

บทสรุปและความเหมาะสมในการใช้งานจริง

  • ในงานจริง หากค่ามีรูปแบบที่คาดเดาได้ ประโยชน์อาจไม่มากนัก แต่ในสถานการณ์ที่มี ข้อมูลสุ่มจำนวนมาก จะมีประโยชน์อย่างยิ่ง
  • หากจะนำไปแทนที่ไลบรารีมาตรฐานจริงใน Python หรือ C# ก็ยังจำเป็นต้องมี การเบนช์มาร์กระดับทั้งโปรแกรมในสภาพจริง
  • ทั้งแนวคิดและวิธีการนำไปใช้มีความน่าสนใจ และในบางสถานการณ์ก็เป็นโซลูชันที่น่าดึงดูดในด้านประสิทธิภาพ

บทความที่เกี่ยวข้อง

2 ความคิดเห็น

 
chickendreamtree 2025-05-19

บทความที่ชวนให้นึกถึง Fast inverse sqrt
 
GN⁺ 2025-05-16
ความคิดเห็นจาก Hacker News
  • รู้สึกทึ่งที่คอมไพเลอร์รุ่นใหม่อย่าง gcc หรือ clang สามารถปรับโค้ดแบบ is_leap_year1 ให้เป็นแบบ is_leap_year2 ได้อัตโนมัติ เลยคิดว่าในระดับซอร์ส C อาจไม่จำเป็นต้องมานั่งปรับแต่งเองมากนัก แต่กับภาษาอื่นก็อาจยังมีประโยชน์อยู่ โดยเฉพาะอย่างยิ่งประทับใจกับการที่ซอร์สโค้ดของ cal เวอร์ชันล่าสุดจัดการการตรวจปีอธิกสุรทินได้อย่างเรียบง่ายมาก
    • ชอบที่โค้ดของ Linux กลับเงื่อนไขต่อเนื่องสามครั้งทุกครั้ง และไม่ใช้การคืนค่าปริยาย ทำให้อ่านเข้าใจง่ายกว่ามาก เจอโครงสร้างโค้ดซับซ้อนแบบนี้ตอนดีบักทีไรแทบเป็นบ้าทุกที
  • ไม่แปลกใจเลยที่คำอธิบายว่าโค้ด ((y * 1073750999) & 3221352463) <= 126976 ทำงานอย่างไรจะต้องซับซ้อน เพราะมันก็เป็นเรื่องธรรมดาอยู่แล้ว
  • ชอบเทคนิคการปรับแต่งด้วย magic number ที่เข้าใจยากแบบนี้มาก เห็นทีไรก็อดสงสัยไม่ได้ว่าสมัยก่อนตอนเขียน inner loop ด้วยแอสเซมบลีพลาดเทคนิคปรับแต่งไปมากแค่ไหน ถ้ามีคอลเลกชันที่รวมเทคนิคพวกนี้ไว้ก็อยากให้ช่วยแชร์
    • มีการแชร์ลิงก์รวมทริกการจัดการบิตหลายแบบ, มาโคร CMP(X, Y) ที่มีประสิทธิภาพสำหรับการเปรียบเทียบสไตล์ UNIX, ตัวอย่างการปรับแต่งฟังก์ชัน signum, ลิงก์ตัวอย่างโค้ดแอสเซมบลีสำหรับ Motorola 68000, ชุด bit macro ที่มาจาก OpenSolaris และเทคนิคการปรับแต่งอีกหลากหลายแบบ พร้อมบ่นเสียดายว่าบล็อก Open Solaris หายไปแล้ว และแนะนำสำหรับคนที่สนใจการปรับแต่งโค้ด
    • แนะนำหนังสือ "Hacker's Delight" ที่เต็มไปด้วย bit trick และเทคนิคการปรับแต่งระดับล่างหลากหลายแบบ
    • มีข้อเสนอให้ไปค้นหาเทคนิค supercompilation
    • สมัยก่อนเราไม่ได้พลาดเทคนิคพวกนี้หรอก แต่ตอนนั้นการคูณมีราคาแพงมาก ดังนั้นของแบบนี้นั่นแหละคือการปรับแต่ง
  • ไม่เคยคิดเลยว่าการเช็กปีอธิกสุรทินจะน่าสนใจได้ขนาดนี้ อาจเป็นไปได้ว่าโปรแกรมเมอร์สาย low-level เจอทริกพวกนี้กันมาตั้งนานแล้วแต่ไม่ได้บันทึกไว้ เลยให้ความรู้สึกว่าอาจยังมีของแบบนี้ซ่อนอยู่ในโค้ดเก่า ๆ จนอยากได้คอลเลกชันมานั่งสำรวจจริงจัง
    • สมัยยุค 80 เคยเรียนรู้เองที่บ้านกับ z80 อยู่บ้าง แต่ตอนนี้ลืมไปเกือบหมดแล้ว บางครั้งพอเอาไปให้ลูกวัยยี่สิบดูจะรู้สึกเหมือนกำลังเล่นมายากล
  • ถ้าจำเป็นต้องรู้ปีอธิกสุรทินก่อนปี 6000 ก็มีคนทำเครื่องคิดเลขแบบโต้ตอบและเครื่องมือแสดงภาพไว้ให้ใช้ แม้จะใช้จำนวนคำสั่งเครื่องมากกว่าเล็กน้อย แต่คำนวณได้เร็วมากเป็นหลักพันครั้ง และทริกทางคณิตศาสตร์ก็น่าทึ่งเช่นกัน
  • ตอนอ่านบทเกี่ยวกับการจัดการบิตก็นึกขึ้นมาว่า "หรือจะใช้ solver ได้ไหม" แล้วก็ตกใจที่ผู้เขียนใช้วิธีนั้นจริง ๆ รู้สึกพอใจกับแนวทางที่ละเอียดรอบคอบ
  • มีข้อเสนอว่าควรเพิ่มฟังก์ชันตรวจปีอธิกสุรทินแบบนี้เข้าไปใน current-time-api
  • เวลามองตัวเลขเป็นเลขฐานสองจะเห็นแพตเทิร์นที่น่าสนใจ เคยรู้สึกว่าน่าสนใจที่จำนวนเฉพาะทุกตัว ยกเว้น 2 ลงท้ายด้วย 1
    • แม้อาจจะดูน่าสนุก แต่จำนวนคี่ทุกตัวก็ลงท้ายด้วย 1 อยู่แล้ว และโดยธรรมชาติแล้วจำนวนเฉพาะยกเว้น 2 จะเป็นจำนวนคู่ไม่ได้ จึงมีคนตั้งคำถามว่าไม่ได้รู้สึกว่ามันมีความหมายอะไรเป็นพิเศษ
  • มีคนทักขึ้นมาว่าในปัญหาปีอธิกสุรทินไม่มีเลข 0 จริง ๆ แล้วไม่มี "ปี 0" เพราะจาก 1 BC ข้ามไป 1 AD เลย ดังนั้นการเช็ก 0 จึงไม่มีความหมาย
    • ถ้าอ่านตอนต้นของบทความจะอธิบายว่าข้อสมมติของการออกแบบอัลกอริทึมปีอธิกสุรทินคือใช้ปฏิทินเกรกอเรียนแบบ proleptic และใช้ปีแบบดาราศาสตร์ หากไม่มีเงื่อนไขนี้ การเช็กปีอธิกสุรทินจะซับซ้อนต่างกันไปตาม locale
    • ถ้าใช้การนับปีแบบดาราศาสตร์ก็จะมีปี 0 และสำหรับการจัดการปี/เดือน การทำแบบนั้นกลับสะอาดกว่าเสียอีก โดยเสนอให้ใช้รูปแบบดาราศาสตร์ในข้อมูลภายใน แล้วค่อยแปลงเป็น BCE/CE ตอนแสดงผลภายนอก
    • ปฏิทินก่อนการนำเกรกอเรียนมาใช้มีเกณฑ์ที่คลุมเครือและแตกต่างกันไปตามแต่ละพื้นที่ ในปี 1582 ยังมีการ "ลบ 10 วัน" ด้วย ดังนั้นการคำนวณวันที่ก่อนหน้านั้นจึงเชื่อถือไม่ได้ อีกทั้งนักบวชสมัยโรมันยังเคยปรับปีอธิกสุรทินตามอำเภอใจเพราะความเชื่อหรือสินบน ทำให้ยิ่งซับซ้อนขึ้น
    • มาตรฐาน ISO8601 อนุญาตให้มีปี 0 และในปฏิทินดาราศาสตร์ ปี 0 หมายถึง 1 BC โดยปีแบบ BCE ทั้งหมดจะถูกออฟเซ็ตไป -1
  • ไม่ค่อยมีบ่อยนักที่ซอร์สโค้ดจะทำให้หลุดหัวเราะออกมาจริง ๆ เลยเป็นประสบการณ์ที่สนุกมาก