0

Con un amigo hicimos una implementación de la criba de Eratóstenes, funciona bien, pero ahora que la reviso un poco más de cerca, en el primer for de la función para generarla, él colocó en la condición mientras i sea menor o igual a n, que es el tamaño del arreglo de booleanos, pero si llama a la posición [n] de la criba, no estaría llamando a una posición inválida, lo cual es un segmentation fault?

#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>

using namespace std;

const long long int n=1000000;
bool criba[n];

void gencriba(){
    memset(criba,true,sizeof(criba));
    criba[0]=criba[1]=false;
    for(long long int i=2;i<=n;++i){ ///Aquí es donde usa <=
        if(criba[i]){
            for(long long int j=i;j<=n/i;++j){
                criba[j*i]=false;
            }
        }
    }
}

int main()
{
    gencriba();
    int c;
    cin>>c;
    cout<<criba[c]<<endl;
    return 0;
}
1

2 respuestas 2

1

En esta sección creas un array de n elementos:

const long long int n=1000000;
bool criba[n];

... elementos que serán accesibles en el rango (0,n-1):

criba[0] = false;   // primer elemento
criba[n-1] = false; // ultimo elemento

Pero por otro lado tus bucles violan este rango de forma sistemática:

for(long long int i=2;i<=n;++i){ // (1)
    if(criba[i]){
        for(long long int j=i;j<=n/i;++j){ // (2)
            criba[j*i]=false; // (3)
        }
    }
}
  1. Este bucle itera en el rango (2,n). Nota que n, por lo que te he explicado antes, no reresenta un índice válido.
  2. Sucede lo mismo que en (1). Lo he duplicado para que no pienses que me he equivocado al elaborar la respuesta
  3. Teniendo en cuenta los rangos de las iteraciones i y j, i*j será igual o mayor que n con suma facilidad. (n/4)*(n/4)>n, por ponerte un ejemplo

Escribir fuera del rango puede tener dos posibles efectos:

  • Sobreescribes valores de otras variables (o incluso de otros programas!!!!)
  • El sistema operativo detecta el acceso a regiones de memoria que no te pertenecen y mata el proceso para evitar que corrompa la memoria

Vas a tener que replantearte el algoritmo porque, como ves, no hay por dónde cogerlo.

0

Si llama a la posición [n]siendo n igual al tamaño del arreglo」de la criba, ¿no estaría llamando a una posición inválida?.

No exactamente, la posición sería válida (por ello accesible) pero fuera del rango del arreglo. Si consultamos el estándar de C++ en el apartado de Indexado (traducción y resaltado míos):

5.2.1 Indexado

  1. Una expresión sufijo seguida de una expresión en corchetes es una expresión de indexado. Una de las expresiones debe tener el tipo “arreglo de T” o “puntero a T” y la otra debe ser un tipo enumerado sin contexto o integral. El resultado es de tipo “T”. El tipo “T” debe ser un tipo completamente definido. La expresión E1[E2] es idéntica (por definición) a *((E1)+(E2)).

Así pues, la expresión criba[i] equivale a *((criba)+(i)) que no es más que sumar i a la posición de criba o dicho de otra manera, avanzar i veces el tamaño del tipo apuntado (en este caso bool) lo cuál siempre devuelve una posición válida aunque ésta no sea "legal" por no pertenecer al rango del arreglo.

¿Es un segmentation fault?

Para responder a esta pregunta, consultaremos de nuevo el estándar de C++ en el apartado de Operadores Unarios (traducción y resaltado míos):

5.3.1 Operadores Unarios

  1. El operador unario * realiza una indirección: la expresión sobre la que es aplicado debe ser un puntero a un tipo objeto, o un puntero a un tipo función y el resultado será un valor izquierdo referenciando al objeto o función al que la expresión apunta. Si el tipo de la expresión es “puntero a T,” el tipo del resultado es “T.”

El estándar no indica que indireccionar un puntero fuera de rango provoque segmentation fault1, así que consultemos de nuevo el estándar de C++ esta vez sobre el otro operador relacionado con el indexado (traducción y resaltado míos):

5.7 Operadores aditivos

  1. Cuando una expresión que tiene tipo integral se suma o resta a un puntero, el resultado tiene el tipo del operando puntero. Si el operando puntero apunta a un elemento del objeto arreglo, y el arreglo es suficientemente grande, el resultado apunta al elemento desplazado desde el elemento original de manera que la diferencia entre los índices de los elementos del arreglo resultante y original equivalga a la expresión integral. En otras palabras, si la expresión P apunta al elemento i-ésimo de un objeto arreglo, las expresiones (P)+N (equivalente a N+(P)) y (P)-N (en que N tiene el valor n) apuntan a, respectivamente, el i+n-ésimo y al i-n-ésimo elemento de un objeto arreglo, la expresión (P)+1 apunta a un elemento después del último elemento del objeto arreglo, y si la expresión Q apunta a un elemento después del último elemento del objeto arreglo, la expresión (Q)-1 apunta al último elemento del objeto arreglo. Si tanto el operando puntero y el resultado apuntan a elementos del mismo objeto arreglo, o uno después del último elemento del objeto arreglo, la operación no producirá un desbordamiento; en otros casos el comportamiento es indefinido.

Así pues, tras analizar las notas del estándar de C++, vemos que el código incurre en comportamiento indefinido, esto significa que podría no apreciarse ningún efecto en el programa, provocar una violación de segmento, la tercera guerra mundial o invocar demonios en tus fosas nasales.


1De hecho el estándar no hace referencia alguna a segmentation fault.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.