1

したがって、明らかに数字 399137 自体はセグメンテーション違反を引き起こしませんが、私のプログラムは同じ計算で一貫してクラッシュします。これは、2 から指定された制限 (デフォルトは 1,000,000) までのオイラーの totient ( phi function ) の値を計算します。これは、オイラーの totient の以前に計算された値から線形に順序付けられた素数のリストを保持することによって行われます。33791 番目の素数 (339137) を素数のリストに追加しようとすると、セグメンテーション違反が発生します。この計算ではメモリが再割り当てされないことに注意してください。を使用して問題を特定しようとしgdbたところ、リストに素数が追加された行が示されました (以下を参照)。

8192*10*4100 万未満のすべての素数を格納するには、私のプログラムはバイトを動的に割り当てます(320KB)。それだけ多くの連続したメモリを必要とすることは、私には問題にならないようです。

では、素数のリストに 339137 を追加しようとすると、プログラムで一貫してセグメンテーション違反が発生するのはなぜですか? このセグメンテーション違反の原因は何ですか?

C Code:

#include <math.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

uint32_t phi       (uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size);
uint32_t gcd_bin   (uint32_t u, uint32_t v);
uint32_t isPrime   (uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size);
void     addPrime  (uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size);
uint32_t isInArr   (uint32_t n, uint32_t *primes, uint32_t count);
uint32_t expand_arr(uint32_t **arr, uint32_t *size);
void     print_arr (uint32_t  *arr, uint32_t count);
uint32_t print_help(char* str);

int main(int argc, char* argv[]) {
  uint32_t z=1000000;         //default
  uint32_t count=0,size = 10; //default
  uint32_t i,n;
//  uint32_t x,y; //max numerator & denominator of ratio
  uint32_t *primes = malloc(size * sizeof(uint32_t));

  if(argc > 1 && !strcmp(argv[1],"--help")) { return print_help(argv[0]); }
  if(argc > 1) {  sscanf(argv[1],"%u",&z); }

  uint32_t old=size;
  for(i=2,/*x=y=1,*/count=0; i<=z; ++i) {
    n = phi(i,primes,&count,&size);
    fprintf(stderr,"\ni=%u phi(i)=%u\t: c=%u s=%u ",i,n,count,size);
  }
//  printf("%u/%u\n",x,y);
  return 0;
}

uint32_t phi(uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size) {
  uint32_t i,bound;
  // Base case
  if(n < 2)
    return 0;
  // Is Prime? (Lehmer's conjecture)
  if(isPrime(n,primes,count,size))
    return n-1;
  // Even number?
  if((n & 1) == 0 ) {
    int m = n >> 1;
    return ~m & 1 ? phi(m,primes,count,size)<<1 : phi(m,primes,count,size);
  }
  // Find (smallest) prime factor using list of primes
  for(i=0,bound=(uint32_t)sqrt(n); primes[i] < bound && i<*count && (n%primes[i])!=0; ++i);
  uint32_t m = primes[i];
  uint32_t o = n/m;
  uint32_t d = gcd_bin(m, o);
  return d==1 ? phi(m,primes,count,size)*phi(o,primes,count,size)
              : phi(m,primes,count,size)*phi(o,primes,count,size)*(d/phi(d,primes,count,size));
}

uint32_t isPrime(uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size) {
  uint32_t i,prime,bound;
  for(i=0,prime=1,bound=(uint32_t)sqrt(n)+1; prime && i<*count && primes[i]<=bound; ++i)
    prime = n%primes[i];
  if(prime)
    addPrime(n,primes,count,size);
  return prime;
}

void addPrime(uint32_t n, uint32_t *primes, uint32_t *count, uint32_t *size) {
  if(*count >= *size) {
    if(!expand_arr(&primes,size)) {
      fprintf(stderr,"dying gracefully!");
      exit(1); //realloc failure
    }
  }
  if(!isInArr(n,primes,*count))
    primes[(*count)++] = n; /* ERROR IS HERE APPARENTLY */
}

uint32_t expand_arr(uint32_t **primes, uint32_t *size) {
  *size  *= 2;
  *primes = realloc(*primes, *size * sizeof(uint32_t));
  return *primes!=NULL;
}

uint32_t isInArr(uint32_t n, uint32_t *primes, uint32_t count) {
  uint32_t hi,low,mid,val;
  low = 0; hi = count; // set bounds
  while(low < hi) {    // binary search
    mid = low/2 + hi/2;
    val = primes[mid];
    if(val == n) return  1;
    if(val >  n) hi  = mid;
    if(val <  n) low = mid+1;
  }
  return 0;
}

void print_arr(uint32_t *arr, uint32_t count) {
  uint32_t i;
  for(i=0; i<count; ++i)
    printf("%u,",arr[i]);
  printf("\n");
}

uint32_t gcd_bin(uint32_t u, uint32_t v) {
    /* simple cases (termination) */
    if(u == v)  return u;
    if(u == 0)  return v;
    if(v == 0)  return u;
    /* look for even numbers  */
    if( ~u & 1) {
      if(v & 1) return gcd_bin(u >> 1, v);           /* u is even, v is odd  */
      else      return gcd_bin(u >> 1, v >> 1) << 1; /* u is even, v is even */
    }
    if( ~v & 1) return gcd_bin(u, v >> 1);           /* u is odd,  v is even */
    /* reduce larger argument */                     /* u is odd,  v is odd  */
    return (u > v) ? gcd_bin((u - v) >> 1, v)
                   : gcd_bin((v - u) >> 1, u);
}

uint32_t print_help(char* str) {
  printf("  Usage: %s <limit> \n",str);
  printf("  Calculates the values of euler's totient (phi fnction) \n");
  printf("  from 2 to <limit> inclusively\n");
  printf("  * limit : a decimal number\n");
  printf("          : default = 1000000\n");
  return 0;
}
4

1 に答える 1