/*=======================================================================*/
#define PROGRAMMER "SOLUTIONS, Nofrills"
#define PROG_CODE  "SOLN"
#define COURSE     "ECE-1021"
#define YEAR       (2004)
#define TERM       "Fall"
#define SECTION    (0)
#define ASSIGNMENT "HW7"
#define REVISION   (0)
#define TITLE      "Custom Math Functions - npown(), nlogn()"
#define SUBTITLE   "Last Modified on 23 OCT 04"
#define EMAIL      "ece1021@eas.uccs.edu"
#define FILENAME   "7_0SOLN0.c"
/*=======================================================================*/

/*=======================================================================*/
/* WAIVED COMPILER WARNINGS                                              */
/*=======================================================================*/
/*
	Linker Warning: No module definition file specified: using defaults
	Reason for Waiver: Can't suppress. Does not have adverse impact.
*/
/*=======================================================================*/
/* NOTES TO THE USER/GRADER                                              */
/*=======================================================================*/
/*
*/
/*=======================================================================*/
/* PROBLEM STATEMENT                                                     */
/*=======================================================================*/
/*
	Write and test the functions npown() and nlog()

	Prototypes:

	double npown(double v, int mode);
	double nlogn(double v, int mode);

	Description:
	-----------------------------------------------------------------
	double npown(double x, int mode);

	mode = TRUE :  return value is y such that y = x^x
	mode = FALSE:  return value is y such that x = y^y
	-----------------------------------------------------------------
	double nlogn(double x, int mode);

	mode = TRUE :  return value is y such that y = xln(x)
	mode = FALSE:  return value is y such that x = yln(y)
	-----------------------------------------------------------------
*/
/*=======================================================================*/
/* DEVELOPMENT NOTES                                                     */
/*=======================================================================*/
/*
	Each function is actually two problems - the forward (mode = TRUE) and
	the reverse (mode = FALSE). So we will tackle each case separately:

	The forward functions (mode = TRUE) are trivial given the functions
	available in math.h:

		npown(): if (mode) then return pow(x,x);
		nlogn(): if (mode) then return x * log(x);

	The reverse functions (mode = FALSE) are more challenging.

	In the case of npown(), we are looking for y such that:

		x = y^y

	Taking the natural log of both sides, we have:

		ln(x) = y*ln(y)

	But this is the basic problem statement we have for the reverse
	function of nlogn() meaning that:

		npown(): if (!mode) then return nlogn(log(x), FALSE);

	Hence, of our original four problems, only one is left that has any
	real meat to it - namely the reverse version of nlogn().

	As discussed in the reading material, this is a non-algebraic function
	that we will need to solve iteratively. Since nlogn(x) is monotonically
	increasing for x > 1 and is positive for value of x > 1, we know that
	if we are asked to find the value of y such that nlogn(y) is equal to
	a specific value of x that is positive, that y is positive and greater
	than 1.

	We can therefore use the method whereby we first walk up the number
	line looking for a set of values that bound the answer and then cut
	the bounds in half each time until we find an answer that is close
	enough.

	Since we are working with values of type double, we will consider the
	answer close enough when the range we are working with is less than
	the change representable by a value of type double.

*/
/*=======================================================================*/
/* PSEUDOCODE                                                            */
/*=======================================================================*/
/*
	Since the first argument of both functions is supposed to always be
	positive, we will check for negative arguments and simply return a
	value of -1 if we detect this.

	for npown(x, mode):
	1) IF: x <= 0.0
		1) RETURN -1
	2) IF: mode is TRUE
		1) RETURN: pow(x,x)
	3) RETURN: nlogn(log(x), FALSE)

	for nlogn(x, mode):
	1) IF: x <= 0.0
		1) RETURN -1
	2) IF: mode is TRUE
		1) RETURN: x * log(x)
	3) TASK: Find y such that x = y*ln(y) = nlogn(y, TRUE)
		1) TASK: Find initial set of bounds
			1) SET: y = 1
			2)	WHILE: x > nlogn(y, TRUE)
				1) SET: y = 2y
		2) TASK: Set initial increment size and final limit
			1) SET: inc = y / 4
			2) SET: limit = (y/2)*DBL_EPSILON
		3) TASK: Iterate in on final value
			1) WHILE: inc > limit
				1) IF: x > nlogn(y, TRUE)
					1) SET: y - inc
				2) ELSE:
					1) SET: y + inc
				3) SET: inc = inc/2
	4) RETURN: y
*/
/*=======================================================================*/
/* DEVIATIONS FROM SUBMITTED PSEUDOCODE                                  */
/*=======================================================================*/
/*
*/
/*=======================================================================*/
/*=======================================================================*/
/* CODE SECTION                                                          */
/*=======================================================================*/
/*=======================================================================*/

/*== INCLUDE FILES ======================================================*/
#include <stdio.h> /* stdout, stdin, putc(), printf(), getc(), ungetc*() */
#include <math.h>  /* pow(), log() */

/*== MACRO DEFINITIONS (OBJECT-LIKE) ====================================*/
#define FALSE (0)
#define TRUE (!FALSE)
#define BLANKLINE printf("\n")
#define MARGIN (2)                       /* Left Margin in PrintHeader() */
#define INDENT_SIZE (2)                  /* Indent relative to           */

#define LMARG printc(' ', MARGIN)        /* Print Left Margin            */
#define INDENT printc(' ', INDENT_SIZE)  /* Indent relative to margin    */
#define EMPTYLOOP {}

#define SIZE (11)

/*== EXIT CODE DEFINITIONS ==============================================*/
#define EXIT_PASS (0)
#define EXIT_FAIL (1)

/*== MACRO DEFINITIONS (FUNCTION-LIKE) ==================================*/
#define PutC(c)  (putc((char)(c),stdout))
#define PutD(d)  (PutC( (char) ((d)<10)?('0'+(d)):('A'+(d)-10) ))
#define GetC()   (getc(stdin))

/*=======================================================================*/
/* SUPPORT FUNCTIONS ( functions not called directly by main() )         */
/*=======================================================================*/

int printc(char c, int n)
{
	while ( (n--) && (c == putc(c, stdout)) ); /* EMPTY LOOP */
	return n;
}

int PutV_u(unsigned int n)
{
	unsigned int m;
	int i, count;

	/* Set m to the largest power or ten <= n */
	for (m = 1; n/m >=10; m*=10)
		/* EMPTYLOOP */;

	/* Print out the digits in n one-by-one */
	for (count = 0; m > 0; m /= 10)
	{
		for(i = 0; n >= m; i++)
			n -= m;
		PutD(i);
		count++;
	}

	return count;
}

int PutV_i(int n)
{
	if (n < 0)
	{
		PutC('-');
		return 1 + PutV_u(-n);
	}

	return PutV_u(n);
}

#define LEASTSIGDIGIT (1e-6)

int PutV_lf(double n)
{
	double m;
	int i, count;

	/* Take care of sign and convert to absolute value */
	count = 0;
	if (n < 0)
	{
		PutC('-');
		count++;
		n = -n;
	}

	/* Add 0.5 Least Sig Digit to perform rounding */
	n += 0.5*LEASTSIGDIGIT;

	/* Set m to the largest power or ten <= n */
	for (m = 1; n/m >=10; m*=10)
		/* EMPTYLOOP */;

	/* Print out the digits in n (left of decimal point) one-by-one */
	while (m > 0.5)
	{
		for(i = 0; n >= m; i++)
			n -= m;
		PutD(i);
		count++;
		m /= 10;
	}

	/* Print out decimal point */
	PutC('.');
	count++;

	/* Print out the digits in n (right of decimal point) one-by-one */
	while (m > 0.5*LEASTSIGDIGIT)
	{
		for(i = 0; n >= m; i++)
			n -= m;
		PutD(i);
		count++;
		m /= 10;
	}

	return count;
}


int PutS(const char *s)
{
	int i;

	for(i = 0; '\0' != s[i]; i++)
		PutC(s[i]);

	return i;
}

int isspace(int c)
{
	switch(c)
	{
		case ' ':
		case '\t':
		case '\n':
		case '\f':
		case '\b':
		case '\v':
		case '\r':
			return TRUE;
	}

	return FALSE;
}

int isdigit(int c)
{
	return ( ('0' <= c) && (c <= '9') );
}

unsigned int GetV_u(unsigned int *ptr)
{
	unsigned int value;
	int c;

	while (isspace(c = GetC())) /* Skip leading whitespace */
		EMPTYLOOP;

	for ( value = 0; isdigit(c); c = GetC() ) /* convert integer */
		value = 10*value + (c - '0');

	ungetc(c, stdin); /* Return unused character to stream buffer */

	if (NULL != ptr)  /* write to memory only if valid pointer */
		*ptr = value;

	return value;
}

int GetV_i(int *ptr)
{
	int value;
	int c;

	while (isspace(c = GetC())) /* Skip leading whitespace */
		EMPTYLOOP;

	value = 1;

	if ( '-' == c )             /* Found a negative sign */
		value = -1;
	else
		ungetc(c, stdin);        /* found something else - push it back */

	value *= GetV_u(NULL);

	if (NULL != ptr)            /* write to memory only if valid pointer */
		*ptr = value;

	return value;
}
/* ======================================================================*/
/* Copied Directly from Lesson #7 (removed ellipsis following #define */
#define SIGFIGS (16)

double arc_xlogx(double y)
{
	 double x, inc;

	 /* TASK: Find the appropriate general range */
	 x = 1.0;
	 while (y > x*log(x))
		  x *= 2.0;

	 /* TASK: Zero in on the actual value */
	 inc = 0.5*x;
	 while ( log10(x/inc) < SIGFIGS )
	 {
		  if (y > x*log(x))
				x += inc;
		  else
				x -= inc;
		  inc *= 0.5;
	 }
	 return x;
}
/* ======================================================================*/

double nlogn(double x, int mode)
{
	if (x < 0.0)
		return -1.0;
	if (mode)
		return x * log(x);
	return arc_xlogx(x);
}

double npown(double x, int mode)
{
	if (x < 0.0)
		return -1.0;
	if (mode)
		return pow(x,x);
	return nlogn(log(x), FALSE);
}

/*=======================================================================*/
/* PRIMARY FUNCTIONS ( functions called directly by main() )             */
/*=======================================================================*/

/*== FUNCTION PROTOTYPES (to Document Support Functions) ================*/
int printc(char c, int n);
int PutV_i(int n);
int PutS(const char *);

/*== PRIMARY FUNCTIONS ==================================================*/
void PrintHeader(void)
{
	LMARG; printc('=', (78 - MARGIN)); putc('\n', stdout);
	LMARG; printf("Course....... %s-%i (%s %i)\n",COURSE,SECTION,TERM,YEAR);
	LMARG; printf("Programmer... %s (%s)\n", PROGRAMMER, PROG_CODE);
	LMARG; printf("Assignment... %s (Rev %i)", ASSIGNMENT, REVISION);
	LMARG; printf("(Source Code in %s)\n", FILENAME);
	LMARG; printf("Description.. %s\n", TITLE);
	LMARG; printf("              %s\n", SUBTITLE);
	LMARG; printc('=', (78 - MARGIN)); putc('\n', stdout);
}

/*=======================================================================*/
/* MAIN FUNCTION                                                         */
/*=======================================================================*/

/*== FUNCTION PROTOTYPES (to Document Primary Functions) ================*/
void PrintHeader(void);

int main(void)
{
	double x;

	PrintHeader();
	BLANKLINE;

	PutS("Test of npown()\n");
	PutS("   x  npown(x, TRUE)  npown(npown(x, TRUE), FALSE)\n");
	for (x = 1.0; x <= 5.0; x += 0.5)
	{
		PutV_lf(x);
		PutS("     ");
		PutV_lf(npown(x, TRUE));
		PutS("     ");
		PutV_lf(npown(npown(x, TRUE), FALSE));
		PutS("\n");
	}

	BLANKLINE;
	PutS("Test of nlogn()\n");
	PutS("   x  nlogn(x, TRUE)  nlogn(nlogn(x, TRUE), FALSE)\n");
	for (x = 1.0; x <= 5.0; x += 0.5)
	{
		PutV_lf(x);
		PutS("     ");
		PutV_lf(nlogn(x, TRUE));
		PutS("     ");
		PutV_lf(nlogn(nlogn(x, TRUE), FALSE));
		PutS("\n");
	}

	return EXIT_PASS;
}

/*=======================================================================*/
/* END OF SOURCE CODE FILE                                               */
/*=======================================================================*/