บวกเลข 128 บิต

เมื่อวานหลังจากสอนวิชา comp arch ซึ่งกำลังพูดถึงเรื่อง computer arithmetic ก็มีนักศึกษา (ที่ยังไม่ได้ถามว่าเจ้าตัวอยากจะให้ออกนามหรือเปล่า) สงสัยว่า ถ้าเราต้องการบวกเลขที่มีขนาดใหญ่กว่า 64 บิต ซึ่งเป็นขนาดที่คอมพิวเตอร์ปัจจุบันรองรับ จะทำย้งไง หลังจากอธิบายไปจนคิดว่าคนถามน่าจะเข้าใจแล้ว ก็เกิดอาการคันไม้คันมือเล็กน้อย เลยลองเขียนฟังก์ชันบวกเลขขนาด 128 บิต
ฟังก์ชันนี้ทำงานง่ายๆ คือ เก็บข้อมูลจำนวนเต็มขนาด 128 บิต โดยใช้ข้อมูลจำนวนเต็มขนาด 64 บิต 2 ตัวต่อกัน (เรียกเป็นครึ่งบน กับครึ่งล่างละกัน) เวลาจะบวกกัน ก็แค่ เอาครึ่งล่างบวกกัน เอาครึ่งบนบวกกัน แล้วถ้ามีทดจากครึ่งล่างก็ให้เอาไปบวกเพิ่มที่ครึ่งบนด้วย แค่นี้แหละ

#include <stdio.h>
#include <stdint.h>

typedef struct {
    int64_t hi;
    int64_t lo;
} int128_t;

int128_t add128(int128_t x, int128_t y) {
    int128_t z = {0,0};
    
    z.hi = x.hi + y.hi;
    z.lo = x.lo + y.lo;
    if (z.lo < x.lo) {
        z.hi++;
    }
    
    return z;
}

int main(int argc, const char * argv[])
{
    int128_t a = {0x0000000000000001, 0xffffffffffffffff};
    int128_t b = {0x0000000000000000, 0x0000000000000005};
    int128_t c;
    
    c = add128(a, b);
    
    printf("0x%016llx %016llx", c.hi, c.lo);
    
    return 0;
}

จากโปรแกรมนี้ จะได้ c = a+b โดยที่ทั้งหมดเป็นจำนวนเต็มขนาด 128 บิต ซึ่งเก็บในลักษณะ struct ประกอบด้วย hi กับ lo เป็นจำนวนเต็มขนาด 64 บิตทั้งคู่

จุดสำคัญของฟังก์ชันนี้ คือ การทดสอบว่าเกิดการทดเลขจากครึ่งล่างหรือไม่ โดยปกติ processor จะมี carry flag เอาไว้สำหรับเก็บค่าตัวทดหลังจากการบวกเลข แต่ภาษา C มีจุดอ่อนที่ไม่สามารถเรียกใช้ค่า carry flag ได้โดยตรง ถ้าจะทำแบบนั้นก็ต้องเขียน assembly ซึ่งดูไม่สะดวก ผมจึงใช้วิธีการตรวจสอบว่าเกิด overflow ขึ้นในการบวกเลขครึ่งล่างหรือไม่ ถ้าเกิด overflow ก็แสดงว่าจะต้องทดเลข หรือบวก 1 เข้าไปที่ผลบวกของครึ่งบน ตามลิงก์นี้ และต้องขอบคุณ @cutiening ที่ช่วยแสดงวิธี prove ว่า เมื่อ a+b แล้วเกิด overflow จะได้ว่าผลที่ได้ c < a และ c < b เสมอ ก็เลยได้ if statement ตามโปรแกรม เป็นอันเสร็จสิ้นการละเล่นแต่เพียงเท่านี้

ที่นี้บวกเลข 128 บิตได้แล้ว แต่ละแสดงผลลัพธ์ออกมาเป็นเลขฐานสิบได้ยังไง ก็ต้องเป็นคำถามต่อไป