R.A.M. Exhaustion Program / The Havoc-Wrecking nature of NP Algorithms

Discussion in 'C' started by rai_gandalf, Apr 6, 2008.

  1. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    The other day, I just had this thought of exhausting the R.A.M. of my ailing, old P.C. in the hopes that it may trigger off a cataclysmic crash which would render it useless :happy: (so that I finally get that brand new mega-system P.C. which I so yearn! :D )

    So I set out to write this program in C, making use of a standard Algorithm to a very well-known problem taught to Computer Science students (I implore you to guess what Algorithm it is), which has got Exponential Time Complexity, i.e. O(2^n) - otherwise also referred to as an NP Algorithm (Non-Deterministic Polynomial complexity on Turing Machines)

    Within this Exponential complexity algorithm, I called a routine 'computeRandom()', in a manner that it would be called exponential no. of times. This routines basically performs some computations using math library function 'random()' in a manner that is extremely C.P.U. intensive (CPU Utilization goes upto 80% in some cases)

    The computeRandom() routine in turns call a function 'memAlloc()', which for each call, dynamically allocates one instance of a structure MemLoad & assigns it to a loose pointer (with no self-referential mechanism like a Linked List). The structure MemLoad has been designed in a manner that an instance acts as a significant memory load on the system.

    By the time the exponential algorithm finishes, the system's CPU utilization has shot through the roof & the system's R.A.M. is severely close to exhaustion. On my system, with a value of about n = 20 to 24, the amount of free R.A.M. touched a low of 0.8 MB!! (and btw I have a 512MB R.A.M. system). At which point, the O.S. (Windows XP SP2) proved to be a saviour & probably started swapping a portion of the load into the Virtual Memory, because the free R.A.M. climbed to about 7MB.

    Some in this forum might feel this article/program is frivolous, but its meant to be! It is just a quirky, esoteric pursuit of curious programmers like me, who are fascinated by NP Algorithms and how real-life computational machines deal with them (and how they are nearly defeated by them).

    So if you have similar esoteric curiosities or simply want to try wrecking your PC, try this program out! And, comment the printf statements if you want to have a faster execution.

    And btw, please do try guessing the Algorithm behind in expRec() routine - it ain't that difficult, in fact it is pretty simple.


    Code:
    /* Program for causing Intense CPU Utilization & Severe Exhaustion of system's R.A.M. */
    
    #include <stdio.h>
    #include <conio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <time.h>
    
    #define NULL 0
    
    /* Symbolic Constants*/
    const long unsigned int MAXVAL = 100 , MINVAL = 10;
    //const unsigned int NULL = 0;
    
    /* Global Variables */
    long unsigned int step = 0;
    
    /* Structure Declarations */
    struct MemoryLoad
    {
      long int x[MAXVAL];
      float y[MAXVAL];
      double z[MAXVAL];
    };
    
    /* Function Prototype Declarations */
    void expRecursion(unsigned int,char,char,char);
    void computeRandom(void);
    void memAlloc(void);
    
    void main()
    {
      unsigned int n;
      clrscr();
    
      printf("Enter the Number whose exponential recursion is to be carried out :  ");
      scanf("%d",&n);
    
      randomize();
      expRecursion(n,'X','Z','Y');
      getch();
    
      clrscr();
      printf("\n\n\aEXP RECURSION SOLVED in %d STEPS!! Press Enter to Exit .... ",step);
      getch();
    }
    
    void expRecursion(unsigned int n , char s , char t , char a)
    {
      if(n == 1)
      {
        computeRandom();
        return;
      }
    
      expRecursion(n-1,s,a,t);
      computeRandom();
      expRecursion(n-1,a,t,s);
    }
    
    void computeRandom(void)
    {
      long unsigned int i,j,k;
      
      step++;
      printf("\n\nSTEP %d:",step);
      printf("\n\nLooping Begins - Press any key to continue ....");
      //getch();
      for(i=0 ; i<MAXVAL ; i++)
      {
        printf("\n\n\n\ni Loop:  i = %d",i);
        //getch();
        i += random(MINVAL);
        for(j=0 ; j<MAXVAL ; j++)
        {
          printf("\n\nj Loop:  j = %d",j);
          //getch();
          i += random(MINVAL);
          for(k=0; k<MAXVAL ; k++)
          {
            printf("\nk Loop:  k = %d",k);
            i += random(MINVAL);
            memAlloc();
          }
        }
      }
    
      step++;
      printf("\n\nSTEP %d: \t i = %d",step,i);
    }
    
    void memAlloc(void)
    {
      struct MemoryLoad *pnode;
    
      pnode = (struct MemoryLoad*)malloc(sizeof(MemoryLoad));
      if(pnode == NULL)
      {
        printf("\n\n\apnode = %x",pnode);
        printf("\n\n\aMEMORY UNAVAILABLE!! Prog Terminates!!\a\n\n");
        getch();
        exit(1);
      }
    }
    Wikipedia's Entry on NP Complexity
    Wikipedia's Page on TuringMachine
    Wikipedia's Page on Deterministic Automaton
     

    Attached Files:

  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  3. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    Hey thanks Shabbir for the nomination! Nice to receive some acknowledgement!

    Now to the matter of the identity of the exponential algorithm used - it seems no-one has hazarded a guess so far! I am a little disappointed to find no one responding in a programming forum as big as this!

    Please do take guesses! Like I said before, it ain't all that difficult!
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice