V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Openbfdev
V2EX  ›  C

开源 C 库 bfdev: MPI 大数运算

  •  
  •   Openbfdev · 238 天前 · 741 次点击
    这是一个创建于 238 天前的主题,其中的信息可能已经有所发展或是发生改变。

    本文展示开源 C 库 bfdev 的大数运算模块。我们将分别在 x86 Linux 平台和 py32f030 为代表的嵌入式平台上分别进行演示,并进行性能测试。

    关于 bfdev 库,这是一个开源的 C 语言算法库, 它具有:良好的可移植性,面向对象的方法设计、安装部署简单等等优势。

    Github 仓库链接

    简介

    MPI 即 Multi precision integer (多精度整数),就是对很大的数进行一系列的运算。在数学中,数的大小是没有上限的,但是在计算机中,由于受 ALU 字长的限制,处理器无法对其进行直接计算,我们就需要用到多精度整数算法。

    使用

    我们先给出两个平台基于 MPI 使用 machin 公式 计算圆周率的测试代码,再进行说明。

    bfdev 仓库 示例

    #define MODULE_NAME "mpi-machin"
    #define bfdev_log_fmt(fmt) MODULE_NAME ": " fmt
    
    #include <stdio.h>
    #include <bfdev/mpi.h>
    #include <bfdev/log.h>
    #include "../time.h"
    #include "helper.h"
    
    #define TEST_LEN 10000
    #define TEST_SIZE (TEST_LEN / 4 + 1)
    #define TEST_LOOP (TEST_LEN / 1.39793 + 1)
    #define PRINT_RESULT 1
    
    int main(int argc, const char *argv[])
    {
        bfdev_mpi_t *vw, *vs, *vv, *vq;
        unsigned int k;
        int retval;
    
        if (!((vw = bfdev_mpi_create(NULL)) &&
              (vs = bfdev_mpi_create(NULL)) &&
              (vv = bfdev_mpi_create(NULL)) &&
              (vq = bfdev_mpi_create(NULL))))
            return 1;
    
        /**
         * Machin-like formula:
         *  PI = 16arctan(1/5) - 4arctan(1/239)
         *
         * These formulas are used in conjunction with Gregory's
         * series, the Taylor series expansion for arctangent:
         *  arctan(x) = x - (x^3)/3 + (x^5)/5 - (x^7)/7 + ...
         */
    
        if ((retval = bfdev_mpi_seti(vw, 16 * 5)) ||
            (retval = bfdev_mpi_seti(vv, 4 * 239)) ||
            (retval = bfdev_mpi_seti(vq, 10000)))
            return retval;
    
        for (k = 0; k < TEST_SIZE; ++k) {
            if ((retval = bfdev_mpi_mul(vw, vw, vq)) ||
                (retval = bfdev_mpi_mul(vv, vv, vq)))
                return retval;
        }
    
        bfdev_log_info("Convergence Machin %d:\n", TEST_LEN);
        EXAMPLE_TIME_STATISTICAL(
            for (k = 1; k <= TEST_LOOP; ++k) {
                if ((retval = bfdev_mpi_divi(vw, vw, vw, 5 * 5)) ||
                    (retval = bfdev_mpi_divi(vv, vv, vv, 239 * 239)) ||
                    (retval = bfdev_mpi_sub(vq, vw, vv)) ||
                    (retval = bfdev_mpi_divi(vq, vq, vq, 2 * k - 1)))
                    return retval;
    
                if (k & 1)
                    retval = bfdev_mpi_add(vs, vs, vq);
                else
                    retval = bfdev_mpi_sub(vs, vs, vq);
    
                if (retval)
                    return retval;
            }
            0;
        );
    
    #if PRINT_RESULT
        char *result;
    
        result = print_num(vs, 10);
        if (!result)
            return 1;
    
        printf("%c.", *result);
        puts(result + 1);
        free(result);
    #endif
    
        bfdev_mpi_destory(vw);
        bfdev_mpi_destory(vs);
        bfdev_mpi_destory(vv);
        bfdev_mpi_destory(vq);
    
        return 0;
    }
    

    以下是运算 pi 后 10000 位的结果,共使用了 0.36 秒。

    ❯ ./build/examples/mpi/mpi-machin
    [info] mpi-machin: Convergence Machin 10000:
    [info] mpi-machin:      real time: 0.360000
    [info] mpi-machin:      user time: 0.350000
    [info] mpi-machin:      kern time: 0.000000
    3.14159
    ...
    

    py32f030 平台 示例

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdint.h>
    #include <errno.h>
    #include <bfdev.h>
    
    #include "main.h"
    #include "py32f0xx_hal.h"
    
    #define TEST_LEN 100
    #define TEST_SIZE (TEST_LEN / 4 + 1)
    #define TEST_LOOP (TEST_LEN / 1.39793 + 1)
    
    int mpi_benchmark(void)
    {
        uint32_t start, time;
        bfdev_mpi_t *vw, *vs, *vv, *vq;
        unsigned int k;
        int retval;
    
        if (!((vw = bfdev_mpi_create(NULL)) &&
              (vs = bfdev_mpi_create(NULL)) &&
              (vv = bfdev_mpi_create(NULL)) &&
              (vq = bfdev_mpi_create(NULL))))
            return 1;
    
        if ((retval = bfdev_mpi_seti(vw, 16 * 5)) ||
            (retval = bfdev_mpi_seti(vv, 4 * 239)) ||
            (retval = bfdev_mpi_seti(vq, 10000)))
            return retval;
    
        for (k = 0; k < TEST_SIZE; ++k) {
            if ((retval = bfdev_mpi_mul(vw, vw, vq)) ||
                (retval = bfdev_mpi_mul(vv, vv, vq)))
                return retval;
        }
    
        bfdev_log_info("Convergence Machin %d:\n", TEST_LEN);
        start = HAL_GetTick();
        for (k = 1; k <= TEST_LOOP; ++k) {
            if ((retval = bfdev_mpi_divi(vw, vw, vw, 5 * 5)) ||
                (retval = bfdev_mpi_divi(vv, vv, vv, 239 * 239)) ||
                (retval = bfdev_mpi_sub(vq, vw, vv)) ||
                (retval = bfdev_mpi_divi(vq, vq, vq, 2 * k - 1)))
                return retval;
    
            if (k & 1)
                retval = bfdev_mpi_add(vs, vs, vq);
            else
                retval = bfdev_mpi_sub(vs, vs, vq);
    
            if (retval)
                return retval;
    
            iwdg_touch();
        }
    
        bfdev_mpi_destory(vw);
        bfdev_mpi_destory(vs);
        bfdev_mpi_destory(vv);
        bfdev_mpi_destory(vq);
        iwdg_touch();
    
        time = HAL_GetTick() - start;
        bfdev_log_notice("Total time: %lu.%lus\n", time / 1000, time % 1000);
    
        return 0;
    }
    

    以下是运算结果,由于 py32f030 只有 4KiB RAM ,我们这里只计算 100 位。

    [info] benchmark: Benchmark for PY32F0xx.
    [info] benchmark: Bfdev version: 1.0.1-devel
    [info] benchmark: This may take a few minutes...
    
    [info] Convergence Machin 100:
    [notice] Total time: 0.21s
    ...
    

    我们计算的大体流程如下:

    1. 首先使用 bfdev_mpi_create 创建 MPI 对象
    2. MPI 对象使用 bfdev_mpi_seti 方法赋值
    3. 使用计算方法进行运算
    4. 输出完成并退出

    bfdev 中,使用 MPI 需要引入 <bfdev/mpi.h> 头文件,或者引入 <bfdev.h> 顶层头文件也可以。

    这里要重点介绍一下 bfdev_mpi_create(alloc) 函数,它使用了 bfdev 的 allocator 兼容层,传入 NULL 将使用系统默认内存分配器,用户也可以使用自己的内存池为 MPI 分配内存。

    结语

    欢迎各位感兴趣的读者去访问 bfdev 仓库。

    bfdev 文档

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1323 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 23:37 · PVG 07:37 · LAX 16:37 · JFK 19:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.