time vs memory

i am creating a double linked list of prime numbers ( 2 to 1,000,000 ). one way to do it is add nodes as each prime is found by dividing each new number by all the nodes on the list (slow). The other way is start with a list with just the odd numbers and 2 (2- 999999) and remove the nodes that are not prime. which turns out to be nearly 5 times quicker however takes a big chunk of memory at the beginning.

which way is best

Time/space tradeoffs are common in programming. People are usually more concerned about time. However, if you were really concerned about space you wouldn't be storing primes in a linked list!

I suspect that something else is going on to make your first program so much slower. Post both of the programs so I can see exactly what you are doing.

i just use block comments to comment out the different bits of main

Code:

---

#include <stdio.h>
#include <stdlib.h>

#define Limit 1000000

typedef struct Numbers
{

    int Num;
    struct Numbers *Next;
    struct Numbers *Previous;

} Number;

Number * GetMemory();
void CreateHead( Number *, int );
Number * CreateNode( Number *, Number *, int );
Number * AppendtoList( Number *, Number *, int );
void ReadList( Number * );
Number * SearchList( Number *, Number *, int, int );
void DeleteNode( Number *, int * );
void DestroyList( Number * );

int CheckPrime( Number *, int );

int main()
{
    Number *Head = NULL, *Tail = NULL;
/*
    Head = AppendtoList( Head, Tail, 2 );
    Tail = Head;

    for ( int i = 3; i < Limit; i += 2 )
    {
        if ( CheckPrime( Head, i ) == 1 )
        {
            Tail = AppendtoList( Head, Tail, i );
        }
    }
//*/
//*
    Head = AppendtoList( Head, Tail, 2 );
    Tail = Head;

    int RecNum = 1;

    for ( int i = 3; i < Limit; i += 2 )
    {
        Tail = AppendtoList( Head, Tail, i ); // add all the odd numbers to the list
        RecNum++;
    }

    for ( int i = 3; i < 1000; i += 2)
    {
        for ( Number *Node = Head->Next; Node->Num < Limit - 1; Node = Node->Next )
        {
            if ( Node->Num != i && Node->Num % i == 0 )
            {
                Number *tmpNode = Node;
                Node = Node->Next;
                DeleteNode( tmpNode, &RecNum );
            }

            if (Node->Next == NULL)
                break;
        }
    }

    Number *tmpTail = Tail;
    Tail = Tail->Previous;
    Tail->Next = NULL;
    free (tmpTail);
//*/
    ReadList( Head );
    DestroyList( Tail );

    return 0;
}

Number * GetMemory()
{
    return ( Number * ) malloc ( sizeof( Number ) );
}

void CreateHead( Number *Tmpptr, int x )
{
    Tmpptr->Num = x;
    Tmpptr->Next = NULL;
    Tmpptr->Previous = NULL;
}

Number * CreateNode( Number *TmpPtr, Number *TPtr, int x )
{
    TmpPtr->Previous = TPtr;
    TPtr->Next = TmpPtr;
    TmpPtr->Next = NULL;
    TmpPtr->Num = x;

    return TmpPtr;
}

Number * AppendtoList( Number *HPtr, Number *TPtr, int x )
{
    if ( HPtr == NULL )
    {
        HPtr = GetMemory();
        if ( HPtr != NULL )
        {
            CreateHead( HPtr, x );
            TPtr = HPtr;
            return HPtr;
        }
        else
        {
            printf("error getting memory!\n");
            exit(0);//will improve this
        }
    }
    else
    {
        Number *tmpNode = NULL;

        tmpNode = GetMemory();
        if ( tmpNode != NULL )
        {
            TPtr = CreateNode(tmpNode, TPtr, x);
            return TPtr;
        }
        else
        {
            printf("error getting memory!  Record not created \n");
            return NULL;
        }
    }
}

void ReadList( Number * CurrentRecord) //passed head pointer
{
    int countrec = 0;

    while ( CurrentRecord != NULL )
    {
        printf("%d\n", CurrentRecord->Num);
        CurrentRecord = CurrentRecord->Next;
        countrec++;
    }

    printf("%d records displayed\n", countrec);
}

Number * SearchList( Number *FirstRec, Number *LastRec, int Goal, int NumRec )
{
    if ( NumRec == 0 )
        return NULL;

    int MidRecNum = 1;
    Number *MidRec = FirstRec;
    for ( ; MidRecNum < NumRec / 2; ++MidRecNum )
        MidRec = MidRec->Next;

    if ( MidRec == NULL )
        return NULL;

    if ( MidRec->Num == Goal )
        return MidRec;

    return Goal < MidRec->Num
        ? SearchList( FirstRec,    MidRec->Previous, Goal, MidRecNum-1 )
        : SearchList( MidRec->Next, LastRec,          Goal, NumRec-MidRecNum );
}

void DeleteNode( Number *CurrentRecord, int *x )
{
    if ( CurrentRecord != NULL )
    {
        if (CurrentRecord->Next == NULL) //tail
        {
            //printf("Tail Record DONT delete\n");
        }
        else
        {
            Number *NextNode = NULL, *PrevNode = NULL;

            NextNode = CurrentRecord->Next;
            PrevNode = CurrentRecord->Previous;

            CurrentRecord->Next->Previous = PrevNode;
            CurrentRecord->Previous->Next = NextNode;

            free ( CurrentRecord );
            *x -= 1;
            //printf("Record deleated\n");
        }
    }
    else
    {
        //printf("Deleation failed! Record not found\n");
    }
}


void DestroyList( Number *CurrentTail ) //passed tail pointer
{
    int countrec = 0;
    while ( CurrentTail != NULL )
    {
        Number *tmpTail =NULL;
        tmpTail = CurrentTail;
        CurrentTail = CurrentTail->Previous;
        free (tmpTail);
        countrec++;
    }

    printf("%d records distroyed\n", countrec);
}

int CheckPrime( Number *CurrentRecord, int x )
{
    while ( CurrentRecord != NULL )
    {
        if ( x % CurrentRecord->Num == 0 )
        {
            return -1;
        }

        CurrentRecord = CurrentRecord->Next;
    }

    return 1;
}

---

the one un-commented is the faster one but obviously uses a lot more memory.

the other version of main

Code:

---

int main()
{
    Number *Head = NULL, *Tail = NULL;
//*
    Head = AppendtoList( Head, Tail, 2 );
    Tail = Head;

    for ( int i = 3; i < Limit; i += 2 )
    {
        if ( CheckPrime( Head, i ) == 1 )
        {
            Tail = AppendtoList( Head, Tail, i );
        }
    }
//*/
/*
    Head = AppendtoList( Head, Tail, 2 );
    Tail = Head;

    int RecNum = 1;

    for ( int i = 3; i < Limit; i += 2 )
    {
        Tail = AppendtoList( Head, Tail, i ); // add all the odd numbers to the list
        RecNum++;
    }

    for ( int i = 3; i < 1000; i += 2)
    {
        for ( Number *Node = Head->Next; Node->Num < Limit - 1; Node = Node->Next )
        {
            if ( Node->Num != i && Node->Num % i == 0 )
            {
                Number *tmpNode = Node;
                Node = Node->Next;
                DeleteNode( tmpNode, &RecNum );
            }

            if (Node->Next == NULL)
                break;
        }
    }

    Number *tmpTail = Tail;
    Tail = Tail->Previous;
    Tail->Next = NULL;
    free (tmpTail);
//*/
    ReadList( Head );
    DestroyList( Tail );

    return 0;
}

---

Try changing CheckPrime to:

Code:

---

int CheckPrime( Number *CurrentRecord, int x )
{
    while ( CurrentRecord )
    {
        if ( CurrentRecord->Num * CurrentRecord->Num > x ) // don't bother checking beyond the square root
            return 1;
        if ( x % CurrentRecord->Num == 0 )
            return -1;
        CurrentRecord = CurrentRecord->Next;
    }
    return 1;
}

---

thanks.....

Do i approach things logically or do you get the impression that i am thrashing around fighting it. i Feel that its like when i first started driving wagons i would strap everything up to an inch of its life so that the sides of the trailer looked like a Victorian in a corset and the dang product would still move /fall over.

It's just a matter of experience.
In the other version you knew not to go above the square root of a million (your test loop only went up to 1000).
You just forgot about it in this version.