Kiến thức Blockchain, Lập trình Blockchain, Lập trình Smart Contract, Nâng cao Kiến thức

Hàm tính căn bậc 2 (Square root – Sqrt) hiệu quả trên Solidity theo phương pháp tìm kiếm nhị phân

Đã đăng Bởi Lập Trình Blockchain trong 2023-09-18 1 Bình luận

Hàm tính căn bậc 2 (Square root - Sqrt) hiệu quả trên Solidity theo phương pháp tìm kiếm nhị phân

Chia sẻ bài viết

Mục lục

Vai trò của hàm tính căn bậc 2 trên Solidity

Hàm tính căn bậc 2 (sqrt) sử dụng trong UniswapV3, ngoài ra nó sử dụng ở nhiều mảng:

Hợp đồng phái sinh tài chính : Trong DeFi, nhiều công cụ phái sinh tài chính yêu cầu tính căn bậc hai để xác định giá quyền chọn, độ biến động và các số liệu tài chính quan trọng khác. Hiệu quả của chức năng được đề xuất sqrt trong việc xử lý số lượng lớn hơn có thể mang lại lợi ích cao trong các hợp đồng như vậy.
Hợp đồng trò chơi : Trong nền tảng trò chơi và NFT dựa trên Ethereum, việc tính toán căn bậc hai thường được yêu cầu để tính toán số liệu trò chơi hoặc phân phối mã thông báo. Việc thực hiện đề xuất này có thể nâng cao hiệu suất và hiệu quả sử dụng khí đốt.
Hệ thống bỏ phiếu DAO : Biểu quyết căn bậc hai, trong đó quyền biểu quyết tỷ lệ thuận với căn bậc hai của số lượng token nắm giữ, đã được đề xuất như một cách để hạn chế ảnh hưởng của những người nắm giữ token lớn. Phương pháp được đề xuất có thể làm cho hệ thống bỏ phiếu như vậy hiệu quả hơn.

Hàm tính căn bậc 2 theo phương pháp Babylon

Hiên tại, hàm tính toán Căn bậc 2 trên Solidity được sử dụng rộng rãi là hàm tính toán dựa trên phương pháp Babylon (Dựa trên phương pháp của Newton). Chi tiết xem: Math.sol#L11. Nhưng hàm này khá tốn gas, đâu đó tầm 30000 với số nguyên lớn.

// Babylonian method
// https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
function sqrt(uint y) internal pure returns (uint z) {
    if (y > 3) {
        z = y;
        uint x = y / 2 + 1;
        while (x < z) {
            z = x;
            x = (y / x + x) / 2;
        }
    } else if (y != 0) {
        z = 1;
    }
}

Hàm tính căn bậc 2 hiệu quả theo phương pháp tìm kiếm nhị phân

Do đó chúng ta cần cài đặt hàm tính toán Căn bậc 2 mới hiệu quả hơn so với phương pháp Babylon ở trên. Trong bài viết EIP-7054: Gas Efficient Square Root Calculation with Binary Search Approach có giới thiệu một cách tiếp cận mới và hiệu quả hơn để tính căn bậc hai trong Solidity bằng thuật toán tìm kiếm nhị phân.

Cài đặt code như sau:

function sqrt(uint256 x) public pure returns (uint128) {
    if (x == 0) return 0;
    else{
        uint256 xx = x;
        uint256 r = 1;
        if (xx >= 0x100000000000000000000000000000000) { xx >>= 128; r <<= 64; }
        if (xx >= 0x10000000000000000) { xx >>= 64; r <<= 32; }
        if (xx >= 0x100000000) { xx >>= 32; r <<= 16; }
        if (xx >= 0x10000) { xx >>= 16; r <<= 8; }
        if (xx >= 0x100) { xx >>= 8; r <<= 4; }
        if (xx >= 0x10) { xx >>= 4; r <<= 2; }
        if (xx >= 0x8) { r <<= 1; }
        r = (r + x / r) >> 1;
        r = (r + x / r) >> 1;
        r = (r + x / r) >> 1;
        r = (r + x / r) >> 1;
        r = (r + x / r) >> 1;
        r = (r + x / r) >> 1;
        r = (r + x / r) >> 1;
        uint256 r1 = x / r;
        return uint128 (r < r1 ? r : r1);
    }
}

Nó tối ưu hóa số lần lặp cần thiết để tính toán, giúp giảm mức tiêu thụ khí đốt trong khi vẫn duy trì kết quả chính xác. Đề xuất nêu chi tiết việc triển khai thuật toán này trong Solidity, bao gồm các hoạt động khôn ngoan về bit và phân nhánh quyết định. Phương pháp này không chỉ cung cấp một cách tối ưu hơn cho việc tính toán căn bậc hai mà còn làm giảm độ phức tạp tính toán tổng thể, từ đó nâng cao hiệu suất và hiệu quả của các hợp đồng yêu cầu tính toán.

So sánh hiệu quả của hai phương pháp

Tác giả đã thực hiện các test case, hai phương pháp đều cho cùng một kết quả, và phương pháp mới hiệu quả GAS hơn hẳn với số nguyên lớn.

So sánh GAS giữa 2 phương pháp tính căn bậc 2

Viết contract để test thử 2 hàm tính căn bậc 2 ở trên

Bây giờ chúng ta sẽ viết contract để test hai hàm tính căn bậc hai ở trên, qua đó kiểm tra tính hiệu quả. Viết SqrtComparison.sol như sau:

// SPDX-License-Identifier: No license
pragma solidity ^0.8.0;

// IERC20 interface
interface IERC20 {
    function name() external view returns (string memory);
    function symbol() external view returns (string memory);
    function decimals() external view returns (uint8);
    function totalSupply() external view returns (uint);
    function balanceOf(address owner) external view returns (uint);
    function allowance(address owner, address spender) external view returns (uint);

    function approve(address spender, uint value) external returns (bool);
    function transfer(address to, uint value) external returns (bool);
    function transferFrom(address from, address to, uint value) external returns (bool);
}

contract SqrtComparison {
    function sendToken(address token, address recipient, uint256 amount) public {
        IERC20(token).transfer(recipient, amount);
    }

    function sendToken1(address token, address recipient, uint256 amount) public {
        IERC20(token).transfer(recipient, BabylonianSquareRoot(amount));
    }

    function sendToken2(address token, address recipient, uint256 amount) public {
        IERC20(token).transfer(recipient, BinarySearchSquareRoot(amount));
    }

    function BinarySearchSquareRoot(uint256 x) public pure returns (uint256) {
        if (x == 0) return 0;
        else if (x==1) return 1;
        else {
            uint256 xx = x;
            uint256 r = 1;
            if (xx >= 0x100000000000000000000000000000000) { xx >>= 128; r <<= 64; }
            if (xx >= 0x10000000000000000) { xx >>= 64; r <<= 32; }
            if (xx >= 0x100000000) { xx >>= 32; r <<= 16; }
            if (xx >= 0x10000) { xx >>= 16; r <<= 8; }
            if (xx >= 0x100) { xx >>= 8; r <<= 4; }
            if (xx >= 0x10) { xx >>= 4; r <<= 2; }
            if (xx >= 0x8) { r <<= 1; }
            r = (r + x / r) >> 1;
            r = (r + x / r) >> 1;
            r = (r + x / r) >> 1;
            r = (r + x / r) >> 1;
            r = (r + x / r) >> 1;
            r = (r + x / r) >> 1;
            r = (r + x / r) >> 1;
            uint256 r1 = x / r;
            return (r < r1 ? r : r1);
        }
    }
    
    function BabylonianSquareRoot(uint256 y) public pure returns (uint256 z) {
        if (y > 3) {
            z = y;
            uint x = y / 2 + 1;
            while (x < z) {
                z = x;
                x = (y / x + x) / 2;
            }
        } else if (y != 0) {
            z = 1;
        }
    }
}

Tôi triển khai trên BSC-TESTNET được địa chỉ: 0xAF5b15D347a964cf4ecE2BE39716960062540918. Thử gọi 2 hàm BabylonianSquareRoot() và BinarySearchSquareRoot() thấy kết quả trả về như nhau. Thử 3 hàm transfer 0.1 USDT (0x7ef95a0fee0dd31b22626fa2e10ee6a223f8a684), tương đương 100000000000000000:

0xae389b932c3a6591036caa20baa44810c374b9764e6d14c1f1c66c6701ac095c: Giao dịch transfer bình thường => Gas Used = 38450
0x327f5f22a4cb2537c0a9d2df99047994ee72a0fd010587f888b547f0438da73a: Giao dịch transfer có sử dụng thêm hàm tính căn bậc 2 theo phương pháp Babylon => Gas Used = 46763 => Gas Used cho phần tính căn bậc 2 khoảng 8313
0x0abdc51478e3558b33519d8fca4afde1c83fd42946b3bc8922bfcc618ceb20ae: Giao dịch transfer có sử dụng thêm hàm tính căn bậc 2 mới => Gas Used = 39,888 => Gas Used cho phần tính căn bậc 2 khoảng 1438

Nếu bạn chuyển tiếp hàm tính căn bậc 2 này từ Solidity sang Assembly, Gas sẽ còn giảm nhiều nữa. Chi tiết xem thêm: Chuyển hàm tính căn bậc hai từ Solidity sang Assembly

Nguồn: EIP-7054: Gas Efficient Square Root Calculation with Binary Search Approach

Bài viết này có hữu ích với bạn?

Kích vào một biểu tượng ngôi sao để đánh giá bài viết!