Таким образом, очевидно, что число 399137 само по себе не вызывает ошибки сегментации, но моя программа постоянно падает при одном и том же вычислении. Он вычисляет значения коэффициента Эйлера (фи-функции) от 2 до заданного предела (по умолчанию 1 000 000). Он делает это, сохраняя линейно упорядоченный список простых чисел из ранее вычисленных значений Эйлера. При попытке добавить 33791-е простое число (339137) в список простых чисел возникает ошибка сегментации. Обратите внимание, что при этом вычислении память не перераспределяется. Я попытался использовать gdb
, чтобы найти проблему, и он указал на строку, где простое число добавляется в список (см. ниже).
Чтобы сохранить все простые числа меньше 1 миллиона, моя программа динамически выделяла 8192*10*4
байт (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;
}
valgrind
для запуска вашего приложения. Он показывает 605 ошибок в 59 контекстах. Думаю, тебе есть что пожевать. - person Bryan Olivier   schedule 11.06.2013if(~n & 1) return 0;
, чтобы пропустить 2 как простое число. Программа вылетает, когда счетчик достигает 337991; пытаясь вычислить 33792-е простое число (399149). - person recursion.ninja   schedule 11.06.2013valgrind
и заметил многоinvalid read
, есть предложения, в чем может быть проблема? - person recursion.ninja   schedule 11.06.2013assert
кажется одним из инструментов, который может быть вам полезен... - person autistic   schedule 11.06.2013