Непредсказуемый SIGSEGV (ошибка времени выполнения) в коде

Question

Я написал код, который вычисляет число Фибоначчи, используя мои собственные функции произвольной точности для умножения и сложения.

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>

using namespace std;

#define max 3000

struct data_type{
   int string[max]; 
};

struct data_type mul(struct data_type a,struct data_type b) {
   struct data_type c;
   memset(c.string,0,sizeof(int)*max);
   int k;
   int i,j;
   for(i=max-1;i>0;i--) {
      int num=a.string[i];
      int carry=0;
      int rem=0;
      k=i;

      for(j=max-1;j>0;j--) {
         int n=b.string[j]*num + carry;
         int r=n%10;
         carry=n/10;
         int p=(c.string[k]+r+rem)%10;
         rem=(c.string[k]+r+rem)/10;
         c.string[k]=p;  
         k--;
      }
   }

   return c;
}

struct data_type add(struct data_type a,struct data_type b) {
   struct data_type c;
   memset(c.string,0,sizeof(int)*max);
   int carry=0;
   int i,j;
   int k=max-1;

   for(i=max-1,j=max-1;i>0 && j>0;i--,j--) {
      int res=(a.string[i] + b.string[j])+carry;
      carry=res/10;
      c.string[k--]=res%10;
   }

   return c;
}

void multiply(struct data_type f[2][2],struct data_type m[2][2]){

   struct data_type x,y,z,t;
   x=add(mul(f[0][0],m[0][0]),mul(f[0][1],m[1][0]));    
   y=add(mul(f[0][0],m[0][1]),mul(f[0][1],m[1][1]));    
   z=add(mul(f[1][0],m[0][0]),mul(f[1][1],m[1][0]));    
   t=add(mul(f[1][0],m[0][1]),mul(f[1][1],m[1][1]));    

   f[0][0]=x;
   f[0][1]=y;
   f[1][0]=z;
   f[1][1]=t;       
}

void power(struct data_type f[2][2],unsigned long long n){

   if((n==0)||(n==1))
      return ;
   struct data_type a,b;
   memset(a.string,0,sizeof(int)*max);
   memset(b.string,0,sizeof(int)*max);
   a.string[max-1]=1;
   b.string[max-1]=0;
   struct data_type m[2][2]={{a,a},{a,b}};  

   power(f,n/2);

   multiply(f,f);

   if(n%2 != 0)
       multiply(f,m);
   }

   struct data_type fib(unsigned long long n){
   struct data_type a,b;
   memset(a.string,0,sizeof(int)*max);
   memset(b.string,0,sizeof(int)*max);
   a.string[max-1]=1;
   b.string[max-1]=0;

   struct data_type f[2][2]={{a,a},{a,b}};

   if(n==0)
      return b;

   power(f,n-1);
   return f[0][0];
}

int main()
{   
   int t;
   cin>>t;

   for(int w=0;w<t;w++){
      unsigned long long n;
      cin>>n;
      struct data_type a,b,c;

      a=fib(n-1);
      b=fib(n+2);
      c=add(a,b);

      int ck=0;

      for(int i=0;i<max;i++) {
         if(c.string[i] && !ck)
            ck=1;

         if(ck)
            cout<<c.string[i];
      }

      cout<<"\n";
   }

   return 0;
}

Моя проблема в том, что он показывает SIGSEGV при запуске, но иногда работает правильно, например, я протестировал его на fib (50000) для max = 4000, но как только я изменяю max = 5000, он перестает работать. Я часами ломаю голову, но все еще не могу понять проблему.

Пожалуйста, скажите, что может быть не так с моим кодом.

Есть ли логическая ошибка в коде, которая вызывает ошибку во время выполнения?

Answer 1

Я думаю, что проблема в функции mul(), поскольку индекс k во внутреннем цикле for может стать отрицательным целым числом, а k используется для индексации массива.

k уменьшается max - 1 раз всегда, но устанавливается только max - 1 на первой итерации внешнего цикла for.В последующих итерациях внешнего цикла for ему присваивается значение меньше max - 1, в результате чего k становится отрицательным.

РЕДАКТИРОВАТЬ:

Я изменил внутренний forцикл:

for(j=max-1;j>0;j--){
    if (k < 0)
        std::cout << k << "\n";
    ...
}

и предоставляется 1 и 4 при отображении запроса во время выполнения и отображения множества отрицательных значений: так что это определенно одна проблема.

Answer 2

Ваша проблема с большими значениями для MAX может быть связана с тем, что вы создаете большие массивы в стеке, вызывая переполнение стека.

Попробуйте динамически распределить объекты с помощью new и посмотрите, исчезают ли ошибки SIGSEGV.