แฟกทอเรียลของจำนวนใหญ่ (Factorial of Large Number)

บทนำ

ในคอมพิวเตอร์ ตัวแปรถูกเก็บในหน่วยความจำ แต่ขนาดของหน่วยความจำคงที่ ดังนั้นเมื่อเราพยายามหาแฟกทอเรียลของค่าที่ใหญ่ขึ้น เช่น 15! หรือ 20! ค่าแฟกทอเรียลจะเกินขอบเขตหน่วยความจำและให้ผลลัพธ์ผิด

สำหรับการคำนวณจำนวนใหญ่ เราต้องใช้ Array เพื่อเก็บผลลัพธ์ แต่ละอิลิเมนต์ของ Array จะเก็บหลักต่างๆ ของผลลัพธ์ แตเราไม่สามารถคูณตัวเลขกับ Array โดยตรงได้ ต้องทำการคูณแบบมือ (Manual Multiplication) สำหรับทุกหลักของ Array ผลลัพธ์

อินพุตและเอาต์พุต

Input: จำนวนใหญ่: 50
Output: Factorial of given number is: 30414093201713378043612608166064768844377641568960512000000000000

อัลกอริทึม

multiply(x, multiplicand)

Input: ตัวเลข x, และ multiplicand ขนาดใหญ่ในรูป Array

Output: ผลลัพธ์หลังการคูณ

Begin
    carry := 0
    for ทุกหลัก i ของ multiplicand, do
        prod := i*x + carry
        i := prod mod 10
        carry := prod / 10
    done
    while carry ≠ 0, do
        insert (carry mod 10) ที่ท้าย multiplicand array
        carry := carry/10
    done
End

factorial(n)

Input: ตัวเลข n

Output: หาแฟกทอเรียลของ n

Begin
    กำหนด result array
    insert 1 ใน result
    for i := 2 to n, do
        multiply(i, result)
    done
    reverse the result
    return result
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void multiply(int x, vector& multiplicand) {
    // คูณ multiplicand ด้วย x
    int carry = 0;  // Initialize carry เป็น 0
    vector::iterator i;
    for (i = multiplicand.begin(); i != multiplicand.end(); i++) {
        // คูณ x กับทุกหลักของ multiplicand
        int prod = (*i) * x + carry;
        *i = prod % 10;  // ใส่เฉพาะหลักสุดท้ายของผลคูณ
        carry = prod/10;  // เพิ่มส่วนที่เหลือเข้า carry
    }
    while (carry) {
        // เมื่อยังมี carry
        multiplicand.push_back(carry%10);
        carry = carry/10;
    }
}

void factorial(int n) {
    vector result;
    result.push_back(1);  // เริ่มต้นเก็บ 1 เป็นผลลัพธ์
    for (int i=2; i<=n; i++)
        multiply(i, result);  // คูณเลข 1*2*3*......*n
    cout << "Factorial of given number is: " << endl;
    reverse(result.begin(), result.end());  // กลับลำดับผลลัพธ์
    vector::iterator it;
    for (it = result.begin(); it != result.end(); it++)
        cout << *it;
}

int main() {
    factorial(50);
}

ผลลัพธ์

Factorial of given number is: 30414093201713378043612608166064768844377641568960512000000000000