通过 GMP 使用 Malloc 处理大量数据

Question

已解决：

我觉得自己好傻。 GMP 很好，这是我的疏忽。使用 size_t mpz_sizeinbase (const mpz_t op, int base) 后，我意识到我用来复制结果的字符数组太小了。增加它的大小解决了它。感谢您的帮助！

我的任务是写一个C程序计算斐波那契数列从第1024个元素到第1048576个元素（从2的10次方到2的20次方，以2的次方递增） .为此，我使用 GMP 库来处理数字。问题是，在2的17次方附近，这个数字太大了，连GMP都处理不了，这意味着我应该使用malloc().

这是我的 main()（我修改了粘贴的代码，删除了不必要的部分，例如写入文件和时间测量，这些部分将用于程序的另一部分） :

int main(){
    int powersOfTwo[11];
    char res[10000];
    char *c;
    c = res;

    for(int i = 0; i < 11; i++){
        powersOfTwo[i] = normalPower(2,i+10);
    }
    for(int i = 0; i < 11; i++){
        fibo(c, powersOfTwo[i]);
        printf("The %d th element of Fibonacci is %s\n",powersOfTwo[i],res);
        memset(res, 0, sizeof res);
    }

    return 0;
}

现在这里是简单的 normalPower 函数（为了清楚起见，实际上与问题没有任何关系）：

int normalPower(int n1, int n2){
    if(n2 == 0){
        return 1;
    }else{
        int temp = n1;
        for(int i = 1; i < n2; i++){
            temp *= n1;
        }
        return temp;
    }
}

现在的问题是 fibo 函数：

void fibo(char *c, int n){
    mpz_t *fib1;
    mpz_t *fib2;
    mpz_t *temp;

    fib1 = (mpz_t *) malloc(101000000 * sizeof(mpz_t));
    fib2 = (mpz_t *) malloc(101000000 * sizeof(mpz_t));
    temp = (mpz_t *) malloc(101000000 * sizeof(mpz_t));

    if (NULL == fib1 || NULL == fib2 || NULL == temp){
      printf("ERROR: Out of memory\n");
    }
    mpz_init(*fib1);
    mpz_init(*fib2);
    mpz_init(*temp);

    mpz_set_str(*fib1,"0",10);
    mpz_set_str(*fib2,"1",10);

    int i;
    if(n == 0){
      char *d = mpz_get_str(NULL,10,*fib1);
      strcpy(c,d);
    }

    if(n == 1){
      char *d = mpz_get_str(NULL,10,*fib2);
      strcpy(c,d);
    }

    if(n > 1){
      for(i = 1; i < n; i++){
          mpz_set(*temp, *fib2);
          mpz_add(*fib2, *fib1, *fib2);
          mpz_set(*fib1,*temp);

      }
      char *d = mpz_get_str(NULL,10,*fib2);
      strcpy(c,d);
    }

    free(fib1);
    free(fib2);
    free(temp); 
}

最初我只使用 mpz_t-s，初始化它们并在最后 mpz_clear()-ing 它们，没有指针和 malloc()，但这导致了 分段错误(core dumped) 计算 2 的 17(-ish) 元素的幂后出现错误。这是我在 Internet 上找到的解决方案，这几乎是我可以分配的最大数量，仍然没有任何变化，程序在同一点停止并显示相同的错误消息。我还尝试使用 mp_set_memory_functions() 并创建自定义 mallocWrapper() 并为其提供 GMP，但这并没有似乎也有效。当然，我有 99% 的把握，这是因为我是 GMP 的新手，也是使用 malloc() 的新手，所以我的代码可能让你们中的大多数人现在都抓狂了对此我深表歉意。

所以基本上我的问题是：我应该如何使用 malloc() 来为数字获取足够的内存？

提前感谢大家的帮助！

Answer 1

如果 GMP 库无法处理它，请考虑在您的算法中使用 char* 来处理数字。您可以轻松完成 GMP 支持的任何事情。

Answer 2

这些行：

mpz_t *fib1;
mpz_t *fib2;
mpz_t *temp;

fib1 = (mpz_t *) malloc(101000000 * sizeof(mpz_t));
fib2 = (mpz_t *) malloc(101000000 * sizeof(mpz_t));
temp = (mpz_t *) malloc(101000000 * sizeof(mpz_t));

我觉得很不对（而且你的整个源代码闻起来很糟糕，你应该放弃它）。看来你要分配101000000个不同的bignum，我不明白你为什么需要那么多。

仔细阅读 GMPlib and the definition of Fibonnaci numbers. You only need a few mpz_t (very probably you need less than half a dozen of mpz_t variables), not many millions of them. Think about the mathematic definition of Fibonacci before coding your program. Notice that if you know Fib(10000) and Fib(10001) computing Fib(10002) is easy with GMPlib and then you don't need Fib(10000) any more and you can print Fib(10002) as soon as it has been computed. Be aware that you can use mpz_set 的文档以分配 GMP 大整数。

^{（你真的应该在对数学进行思考之后开始重写你的程序；你可以转储你现有的代码）}

不要忘记初始化每个变量，以适当地调用 mpz_init。

编译所有警告和调试信息 (gcc -Wall -Wextra -g)。 使用调试器 (gdb) 和valgrind and perhaps -fsanitize= debugging options

据我了解，您甚至不需要在代码中对 malloc 进行单个显式调用（当然，GMPlib 在内部使用 malloc).

^{（顺便说一句，作为一名学生，假设你的练习很容易完成是有帮助的）}

通过 GMP 使用 Malloc 处理大量数据

Using Malloc to handle large numbers with GMP

c

memory

malloc

gmp

dynamic-memory-allocation

已解决：