C中的分割故障11由较大的操作数字引起

Question

我知道，当使用segmentation fault 11遇到时，这意味着该程序已尝试访问不允许访问的内存区域。

在这里，我尝试使用以下代码来计算傅立叶变换。

当nPoints = 2^15（或当然要少点）时，它运行良好，但是当我将点进一步增加到2^16时，它会损坏。我想知道，这是由于占据太多记忆而引起的吗？但是我没有注意到操作过程中的记忆职业太多。尽管它使用递归，但它会在就地改变。我认为它不会占据那么多的记忆。然后，问题在哪里？

预先感谢

ps：我忘了说的一件事是，上面的结果是在最大OS（8G内存）上。

当我在Windows（16G内存）上运行代码时，它会在nPoints = 2^14时损坏。因此，这使我感到困惑是否是由内存分配引起的，因为Windows PC具有更大的内存（但很难说，因为两个操作系统使用不同的内存策略）。

#include <stdio.h>
#include <tgmath.h>
#include <string.h>
// in place FFT with O(n) memory usage
long double PI;
typedef long double complex cplx;
void _fft(cplx buf[], cplx out[], int n, int step)
{
  if (step < n) {
    _fft(out, buf, n, step * 2);
    _fft(out + step, buf + step, n, step * 2);
    for (int i = 0; i < n; i += 2 * step) {
      cplx t = exp(-I * PI * i / n) * out[i + step];
      buf[i / 2]     = out[i] + t;
      buf[(i + n)/2] = out[i] - t;
    }
  }
}
void fft(cplx buf[], int n)
{
  cplx out[n];
  for (int i = 0; i < n; i++) out[i] = buf[i];
  _fft(buf, out, n, 1);
}

int main()
{
  const int nPoints = pow(2, 15);
  PI = atan2(1.0l, 1) * 4;
  double tau = 0.1;
  double tSpan = 12.5;
  long double dt = tSpan / (nPoints-1);
  long double T[nPoints];
  cplx At[nPoints];
  for (int i = 0; i < nPoints; ++i)
  {
    T[i] = dt * (i - nPoints / 2);
    At[i] = exp( - T[i]*T[i] / (2*tau*tau));
  }
    fft(At, nPoints);
  return 0;
}

Answer 1

1. 您不能在堆栈中分配非常大的数组。MACOS上的默认堆栈大小为8 MIB。cplx类型的大小为32个字节，因此2 ¹⁶ cplx elements的数组为2 MIB，您有两个（一个在main中，一个在fft中），因此是4 MIB。这很适合堆栈，但是，在此大小时，我尝试使用该程序就可以完成。在2 ¹⁷ 时，它失败了，这是有道理的，因为那时该程序有两个阵列在堆栈上取8个MIB。分配如此大数组的正确方法是包括<stdlib.h>并使用cmplx *At = malloc(nPoints * sizeof *At);，然后使用if (!At) { /* Print some error message about being unable to allocate memory and terminate the program. */ }。您应该为At，T和out做到这一点。另外，当您使用每个数组时，您应该将其释放，例如free(At);。

2. 要计算两个整数功率，请使用整数操作1 << power，而不是浮点操作pow(2, 16)。我们在MACOS上设计了pow，但是，在其他系统上，即使可能确切的结果，它也可能返回近似值。近似结果可能略低于确切的整数值，因此将其转换为整数截断为错误的结果。如果可能是两个大于适合int的功率，则使用(type) 1 << power，其中type是合适的整数类型。

Answer 2

以下，仪器，代码清楚地表明，OPS代码反复更新out[]数组中的相同位置，并且实际上并未更新该数组中的大多数位置。

#include <stdio.h>
#include <tgmath.h>
#include <assert.h>

// in place FFT with O(n) memory usage
#define N_POINTS  (1<<15)
double T[N_POINTS];
double At[N_POINTS];
double PI;

// prototypes
void _fft(double buf[], double out[], int step);
void fft( void );

int main( void )
{
    PI = 3.14159;
    double tau = 0.1;
    double tSpan = 12.5;
    double dt = tSpan / (N_POINTS-1);
    for (int i = 0; i < N_POINTS; ++i)
    {
        T[i]  = dt * (i - (N_POINTS / 2));
        At[i] = exp( - T[i]*T[i] / (2*tau*tau));
    }
    fft();
    return 0;
}

void fft()
{
    double out[ N_POINTS ];
    for (int i = 0; i < N_POINTS; i++)
        out[i] = At[i];
    _fft(At, out, 1);
}

void _fft(double buf[], double out[], int step)
{
    printf( "step: %dn", step );
    if (step < N_POINTS)
    {
        _fft(out, buf, step * 2);
        _fft(out + step, buf + step, step * 2);
        for (int i = 0; i < N_POINTS; i += 2 * step)
        {
            double t = exp(-I * PI * i / N_POINTS) * out[i + step];
            buf[i / 2]     = out[i] + t;
            buf[(i + N_POINTS)/2] = out[i] - t;
            printf( "index: %d buf update: %d, %dn", i, i/2, (i+N_POINTS)/2 );
        }
    }
}

建议通过（ untitled1是可执行文件的名称和Linux上的名称）

./untitled1 > out.txt
less out.txt

out.txt文件是8630880字节

对该文件的检查表明缺乏覆盖范围，并表明任何一个条目不是前两个条目的总和，所以我怀疑这不是有效的傅立叶变换，