Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   R.A.M. Exhaustion Program / The Havoc-Wrecking nature of NP Algorithms (http://www.go4expert.com/articles/ram-exhaustion-program-havoc-wrecking-t9797/)

rai_gandalf 6Apr2008 13:56

R.A.M. Exhaustion Program / The Havoc-Wrecking nature of NP Algorithms
 
1 Attachment(s)
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: C

/* 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

shabbir 1May2008 13:39

Re: R.A.M. Exhaustion Program / The Havoc-Wrecking nature of NP Algorithms
 
Nomination for article of the month of April

rai_gandalf 4May2008 21:24

Re: R.A.M. Exhaustion Program / The Havoc-Wrecking nature of NP Algorithms
 
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!

shabbir 24May2008 08:52

Re: R.A.M. Exhaustion Program / The Havoc-Wrecking nature of NP Algorithms
 
Voting for article of the month for Apr 2008


All times are GMT +5.5. The time now is 05:47.