Skip to content

Instantly share code, notes, and snippets.

@numinit
Created April 2, 2012 21:44
Show Gist options
  • Save numinit/2287454 to your computer and use it in GitHub Desktop.
Save numinit/2287454 to your computer and use it in GitHub Desktop.
Quadratic Solver
//
// QuadraticFormula.m
// MathTasksCode
//
// Created by Eric Li on 7/16/09. Edited by Morgan Jones.
// Copyright 2009 § Products. All rights reserved.
//
#import "QuadraticFormula.h"
#import "Fractions.h"
#import <ctype.h>
@implementation QuadraticFormula
+(void)QuadraticFormula:(NSString *)a:(NSString *)b:(NSString *)c {
if([a isEqualToString:@""] || [b isEqualToString:@""] || [c isEqualToString:@""])
return;
double A = [a doubleValue], B = [b doubleValue], C = [c doubleValue];
QuadraticSolution::SetPrecision( 0 );
if( A == 0 )
{
if( CheckString( a ) )
{
// "A" field is invalid
printf( "Invalid input: \"%s\"\n", [a cStringUsingEncoding:NSASCIIStringEncoding] );
return;
}
}
if( B == 0 )
{
if( CheckString( b ) )
{
// "B" field is invalid
printf( "Invalid input: \"%s\"\n", [b cStringUsingEncoding:NSASCIIStringEncoding] );
return;
}
}
if( C == 0 )
{
if( CheckString( c ) )
{
// "C" field is invalid
printf( "Invalid input: \"%s\"\n", [c cStringUsingEncoding:NSASCIIStringEncoding] );
return;
}
}
if( A == 0 )
{
// There will be a divide by zero error right now, so catch it
printf( "Divide By Zero\n" );
return;
}
if( A == HUGE_VAL || B == HUGE_VAL || C == HUGE_VAL || A == -HUGE_VAL || B == -HUGE_VAL || C == -HUGE_VAL )
{
// Handle an overflow here
printf( "Overflow\n" );
return;
}
QuadraticSolution solution = QuadraticSolution::SolveQuadratic( A, B, C );
if( solution.Error() != QUADRATIC_NOERROR )
{
if( solution.Error() == QUADRATIC_UNINITIALIZED )
printf( "Uninitialized quadratic equation\n" );
else if( solution.Error() == QUADRATIC_MEMORY )
printf( "Out of memory!\n" );
}
else
{
if( !solution.IsImaginary() && !solution.IsDoubleRoot() )
printf( "Real Roots: %s (%.*f and %.*f)\n", solution.String(), QuadraticSolution::Precision(), solution.X1(), QuadraticSolution::Precision(), solution.X2() );
else if( solution.IsImaginary() && !solution.IsDoubleRoot() )
printf( "Imaginary Roots: %s\n", solution.String() );
else if( !solution.IsImaginary() && solution.IsDoubleRoot() )
printf( "Double Root: %.*f\n", QuadraticSolution::Precision(), solution.X1() );
// It is mathematically impossible to have a pair of double imaginary roots. We don't need to check for it.
}
}
@end
/* Quadratic and Fraction library
* Morgan Jones 2010
* THIS CODE IS HORRIFYING
*/
#import <cmath>
#import <cstdlib>
#import <cstring>
#include "Quadratic.h"
Fraction::Fraction()
{
// Set the fraction
Set( 0, 1 );
// Allocate memory to start out with
const_append_num = (char *)calloc( 2, sizeof( char ) );
if(!const_append_num)
return;
const_append_denom = (char *)calloc( 2, sizeof( char ) );
if(!const_append_denom)
return;
}
Fraction::Fraction(long int num, long int denom)
{
// Set the fraction
Set( num, denom );
// Allocate memory to start out with
const_append_num = (char *)calloc( 2, sizeof( char ) );
if(!const_append_num)
return;
const_append_denom = (char *)calloc( 2, sizeof( char ) );
if(!const_append_denom)
return;
}
Fraction::~Fraction()
{
Destroy();
}
long int Fraction::Numerator()
{
return numerator;
}
long int Fraction::Denominator()
{
return denominator;
}
double Fraction::Approximation()
{
return (double)Numerator() / (double)Denominator();
}
void Fraction::Set(long int num, long int denom)
{
// Sanitize it
sanitize( num, denom );
// Assign vars
numerator = num;
denominator = denom;
}
void Fraction::Simplify()
{
Simplify( numerator, denominator );
}
void Fraction::Simplify(long int &numerator, long int &denominator)
{
long int divisor = gcd( numerator, denominator );
while( divisor != 1 )
{
numerator /= divisor;
denominator /= divisor;
divisor = gcd( numerator, denominator );
}
sanitize( numerator, denominator );
}
void Fraction::AppendConstantToNumerator(const char * constant)
{
if( !const_append_num || strlen( (const char*)const_append_num ) == 0 )
{
const_append_num = (char *)realloc( const_append_num, strlen( constant ) + 1 );
if(!const_append_num)
return;
strcpy( const_append_num, constant );
}
else
{
const_append_num = (char *)realloc( const_append_num, strlen( constant ) + strlen( const_append_num ) + 1 );
if(!const_append_num)
return;
strcat( const_append_num, constant );
}
}
void Fraction::AppendConstantToDenominator(const char * constant)
{
if( !const_append_denom || strlen( (const char*)const_append_denom ) == 0 )
{
const_append_denom = (char *)realloc( const_append_denom, strlen( constant ) + 1 );
if(!const_append_denom)
return;
strcpy( const_append_denom, constant );
}
else
{
const_append_denom = (char *)realloc( const_append_denom, strlen( constant ) + strlen( const_append_denom ) + 1 );
if(!const_append_denom)
return;
strcat( const_append_denom, constant );
}
}
char * Fraction::String(QuadraticError & errorlevel)
{
return String( "/", errorlevel );
}
char * Fraction::String(const char * divider, QuadraticError & errorlevel)
{
/* First, watch for divides by 0. */
if( denominator == 0 )
{
errorlevel = QUADRATIC_DIVIDEBYZERO;
return NULL;
}
/* Is the whole thing 0 if the denominator isn't? */
if( numerator == 0 )
{
char * ret = (char *)calloc( 2, sizeof( char ) );
strcpy( ret, "0" );
errorlevel = QUADRATIC_NOERROR;
return ret;
}
/* Set up these all-important variables */
char num[25];
char denom[25];
sprintf( num, "%ld", numerator );
sprintf( denom, "%ld", denominator );
/* Set up length vars */
size_t num_len = strlen( num ), denom_len = strlen( denom ), num_const_len = strlen( const_append_num ), denom_const_len = strlen( const_append_denom ), divider_len = strlen( divider );
/* Allocate some memory for the return variable */
char * ret = (char *)calloc( num_len + denom_len + num_const_len + denom_const_len + divider_len + 1, sizeof( char ) );
if( ret == NULL )
{
errorlevel = QUADRATIC_MEMORY;
return NULL;
}
/* Build the string. */
// If there is a numerator constant and the numerator isn't 1 or -1
if( num_const_len > 0 && numerator != 1 && numerator != -1 )
{
strncat( ret, (const char *)num, num_len );
strncat( ret, (const char *)const_append_num, num_const_len );
}
// Constant present and numerator = 1
else if( num_const_len > 0 && numerator == 1 )
strncat( ret, (const char *)const_append_num, num_const_len );
// Negative 1 numerator with constant
else if( num_const_len > 0 && numerator == -1 )
{
strncat( ret, "-", 1 );
strncat( ret, (const char *)const_append_num, num_const_len );
}
// No constant and any numerator
else
strncat( ret, (const char *)num, num_len );
// If there's a divider and the denominator is not 1 or -1, put it there.
if( divider_len > 0 && denominator != 1 && denominator != -1 )
strncat( ret, divider, divider_len );
// If there is a denominator constant and the denominator isn't 1 or -1
if( denom_const_len > 0 && denominator != 1 )
{
strncat( ret, (const char *)denom, denom_len );
strncat( ret, (const char *)const_append_denom, denom_const_len );
}
// Constant present and denominator = 1
else if( denom_const_len > 0 && denominator == 1 )
strncat( ret, (const char *)const_append_denom, denom_const_len );
// No constant and any denominator but 1
else if( denominator != 1 )
strncat( ret, (const char *)denom, denom_len );
// Terminate with a NULL
strncat( ret, "\0", 1 );
/* Finally, return the string. */
errorlevel = QUADRATIC_NOERROR;
return ret;
}
void Fraction::Destroy()
{
numerator = 0;
denominator = 1;
if( const_append_num )
free( const_append_num );
if( const_append_denom )
free( const_append_denom );
const_append_num = NULL;
const_append_denom = NULL;
}
long int Fraction::gcd(long int a, long int b)
{
if ( b == 0 )
return a;
return gcd( b, a % b );
}
void Fraction::sanitize(long int &num, long int &denom)
{
if( ( denom < 0 && num < 0 ) || ( denom < 0 && num > 0 ) )
{
num *= -1;
denom *= -1;
}
}
const char * Fraction::Version()
{
return VERSION;
}
/* Default to six significant digits */
int QuadraticSolution::precision = PRECISION;
QuadraticSolution::QuadraticSolution()
{
formatted_string = NULL;
x1 = x2 = 0;
imaginary = double_root = false;
error_level = QUADRATIC_UNINITIALIZED;
}
QuadraticSolution::~QuadraticSolution()
{
Destroy();
}
char * QuadraticSolution::String()
{
return formatted_string;
}
double QuadraticSolution::X1()
{
return x1;
}
double QuadraticSolution::X2()
{
return x2;
}
bool QuadraticSolution::IsImaginary()
{
return imaginary;
}
bool QuadraticSolution::IsDoubleRoot()
{
return double_root;
}
void QuadraticSolution::SimplifyRoot(long int & multiple, long int & radicand)
{
long int power;
for( long int a = floor( sqrt( radicand ) ); a > 0; a-- )
{
power = pow( a, 2 );
if( radicand % power == 0 )
{
multiple = a;
radicand /= power;
break;
}
}
}
QuadraticError QuadraticSolution::Error()
{
return error_level;
}
void QuadraticSolution::Destroy()
{
if( formatted_string )
free( formatted_string );
formatted_string = NULL;
x1 = x2 = 0;
imaginary = double_root = false;
error_level = QUADRATIC_UNINITIALIZED;
}
QuadraticSolution QuadraticSolution::SolveQuadratic(double a, double b, double c)
{
// Fractions and the solution
Fraction frac1, frac2;
QuadraticSolution ret;
// Nicely formatted string
char * str = NULL;
// Discriminant
double d = pow( b, 2 ) - (4 * a * c);
bool i = d < 0;
ret.imaginary = i;
// d2 is the decimal value of the sqrt of the discriminant
// fractpart is its fractional part
// intpart is its integral part
double old_intpart, fractpart, d2 = sqrt( fabs( d ) );
long int intpart;
fractpart = modf( d2, &old_intpart );
intpart = floor( old_intpart );
bool a_hasdecimal = modf( a, &old_intpart ) != 0;
bool b_hasdecimal = modf( b, &old_intpart ) != 0;
bool c_hasdecimal = modf( c, &old_intpart ) != 0;
bool d_hasdecimal = modf( d, &old_intpart ) != 0;
bool whole_root = fractpart == 0;
// The root is a whole number and there are no decimal values - perfect
if( !a_hasdecimal && !b_hasdecimal && !c_hasdecimal && !d_hasdecimal && whole_root )
{
frac1.Set( -floor( b ), 2 * floor( a ) );
frac2.Set( intpart, 2 * floor( a ) );
frac1.Simplify();
frac2.Simplify();
if( i )
frac2.AppendConstantToNumerator( "i" );
else
{
double y = frac1.Approximation();
double z = frac2.Approximation();
ret.x1 = y + z;
ret.x2 = y - z;
if( ret.X1() == ret.X2() )
ret.double_root = true;
}
QuadraticError error1, error2;
char * string1 = frac1.String( error1 );
char * string2 = frac2.String( error2 );
if( string1 && string2 && error1 == QUADRATIC_NOERROR && error2 == QUADRATIC_NOERROR )
{
str = (char *)calloc( strlen( string1 ) + strlen( string2 ) + 5, sizeof( char ) );
if( frac1.Approximation() != 0 )
{
strcat( str, string1 );
strcat( str, " " );
}
if( frac2.Approximation() != 0 )
{
strcat( str, "\xc2\xb1 " );
strcat( str, string2 );
}
if( string1 )
free( string1 );
if( string2 )
free( string2 );
}
else
{
if( string1 )
free( string1 );
if( string2 )
free( string2 );
ret.error_level = error1;
return ret;
}
}
// Otherwise, this is not a whole number root, but the discriminant is whole, so write it as a simplified expression
else if( !a_hasdecimal && !b_hasdecimal && !c_hasdecimal && !d_hasdecimal && !whole_root )
{
long int multiple, radicand = abs( floor( d ) );
SimplifyRoot( multiple, radicand );
frac1.Set( -( floor( b ) ), 2 * floor( a ) );
frac2.Set( multiple, 2 * floor( a ) );
frac1.Simplify();
frac2.Simplify();
if( i )
{
char buffer[50];
if( frac2.Numerator() == 1 )
sprintf( buffer, "i\xe2\x88\x9a%ld", radicand );
else
sprintf( buffer, "(i\xe2\x88\x9a%ld)", radicand );
frac2.AppendConstantToNumerator( buffer );
}
else
{
char buffer[50];
if( frac2.Numerator() == 1 )
sprintf( buffer, "\xe2\x88\x9a%ld", radicand );
else
sprintf( buffer, "(\xe2\x88\x9a%ld)", radicand );
frac2.AppendConstantToNumerator( buffer );
double y = frac1.Approximation();
double z = frac2.Approximation() * sqrt( radicand );
ret.x1 = y + z;
ret.x2 = y - z;
if( ret.X1() == ret.X2() )
ret.double_root = true;
}
QuadraticError error1, error2;
char * string1 = frac1.String( error1 );
char * string2 = frac2.String( error2 );
if( string1 && string2 && error1 == QUADRATIC_NOERROR && error2 == QUADRATIC_NOERROR )
{
str = (char *)calloc( strlen( string1 ) + strlen( string2 ) + 5, sizeof( char ) );
if( frac1.Approximation() != 0 )
{
strcat( str, string1 );
strcat( str, " " );
}
if( frac2.Approximation() != 0 )
{
strcat( str, "\xc2\xb1 " );
strcat( str, string2 );
}
if( string1 )
free( string1 );
if( string2 )
free( string2 );
}
else
{
if( string1 )
free( string1 );
if( string2 )
free( string2 );
ret.error_level = error1;
return ret;
}
}
// The third case? There is a decimal, so skip the radical sign or fractions altogether.
else if( a_hasdecimal || b_hasdecimal || c_hasdecimal || ( d_hasdecimal && !whole_root ) )
{
char buffer[50];
int size = 0;
if( i )
size = sprintf( buffer, "%.*f \xc2\xb1 %.*fi", QuadraticSolution::Precision(), (-b) / (2 * a), QuadraticSolution::Precision(), d2 / (2 * a) );
else
{
double y = (-b) / (2 * a);
double z = d2 / (2 * a);
ret.x1 = y + z;
ret.x2 = y - z;
if( ret.X1() == ret.X2() )
ret.double_root = true;
size = sprintf( buffer, "%.*f \xc2\xb1 %.*f", QuadraticSolution::Precision(), y, QuadraticSolution::Precision(), z );
}
str = (char *)calloc( size + 1, sizeof( char ) );
strcpy( str, buffer );
}
ret.formatted_string = str;
ret.error_level = QUADRATIC_NOERROR;
return ret;
}
int QuadraticSolution::Precision()
{
return precision;
}
void QuadraticSolution::SetPrecision(int new_precision)
{
if( new_precision < MIN_PRECISION || new_precision > MAX_PRECISION )
return;
precision = new_precision;
}
/* Quadratic and Fraction library
* Morgan Jones 2010
* THIS CODE IS HORRIFYING
*/
#ifndef QUADRATIC_H
#define QUADRATIC_H
/*
* Change this to whatever precision you want in the outputs as default.
* Note that this will NOT affect the actual value of the decimal.
* It only affects the output of the string. Use QuadraticSolution::SetPrecision(int)
* to set it. QuadraticSolution::Precision() returns the current precision.
*/
#define PRECISION 6
#define MIN_PRECISION 5
#define MAX_PRECISION 9
#define VERSION "1.1.3"
typedef enum { QUADRATIC_NOERROR, QUADRATIC_UNINITIALIZED, QUADRATIC_DIVIDEBYZERO, QUADRATIC_MEMORY } QuadraticError;
class Fraction {
public:
Fraction();
Fraction(long int num, long int denom);
~Fraction();
long int Numerator();
long int Denominator();
double Approximation();
void Set(long int num, long int denom);
void Simplify();
static void Simplify(long int &numerator, long int &denominator);
void AppendConstantToNumerator(const char * constant);
void AppendConstantToDenominator(const char * constant);
char * String(QuadraticError & errorlevel);
char * String(const char * divider, QuadraticError & errorlevel);
static const char * Version();
private:
void Destroy();
static void sanitize(long int &num, long int &denom);
static long int gcd(long int a, long int b);
long int numerator, denominator;
char * const_append_num, *const_append_denom;
};
class QuadraticSolution {
public:
QuadraticSolution();
~QuadraticSolution();
char * String();
double X1();
double X2();
bool IsImaginary();
bool IsDoubleRoot();
QuadraticError Error();
static QuadraticSolution SolveQuadratic(double a, double b, double c);
static int Precision();
static void SetPrecision(int new_precision);
private:
void Destroy();
static void SimplifyRoot(long int & multiple, long int & radicand);
QuadraticError error_level;
char * formatted_string;
double x1, x2;
bool imaginary, double_root;
static int precision;
};
#endif // QUADRATIC_H
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment