diff options
Diffstat (limited to 'src/services/quick-answers/math.c')
| -rw-r--r-- | src/services/quick-answers/math.c | 437 |
1 files changed, 291 insertions, 146 deletions
diff --git a/src/services/quick-answers/math.c b/src/services/quick-answers/math.c index e813808..69219e2 100644 --- a/src/services/quick-answers/math.c +++ b/src/services/quick-answers/math.c @@ -3,6 +3,16 @@ #include "services/quick-answers/math.h" #include <math.h> +// +// FoobarMathExpression: +// +// A fully parsed mathematical expression which can be evaluated, for example "sin(pi) - 3" would be represented as: +// - Operation: SUB +// - Function: SIN +// - Constant: PI +// - Value: 3 +// + struct _FoobarMathExpression { FoobarMathExpressionType type; @@ -34,6 +44,29 @@ struct _FoobarMathExpression }; }; +// +// FoobarMathValue: +// +// Representation of a value. The goal of this memory structure is to store the value as an integer for as long as +// possible. Because of this, there is a "decimal_places" field, so the actual value of an integer is +// $v * 10^(-decimal_places)$. +// +// If absolutely necessary (for example, because we use a function like sin), the value is converted to a floating-point +// value. +// +// Note that we use GMP to store the integer value to allow for arbitrarily large values. Because of this, the structure +// should always be freed using foobar_math_value_free. +// + +// --------------------------------------------------------------------------------------------------------------------- +// Expressions +// --------------------------------------------------------------------------------------------------------------------- + +// +// Helper to allocate a new FoobarMathExpression representing a value. +// +// Ownership of "value" is transferred to the new expression. +// FoobarMathExpression* foobar_math_expression_new_value( FoobarMathValue value ) { FoobarMathExpression* res = g_new0( FoobarMathExpression, 1 ); @@ -42,6 +75,12 @@ FoobarMathExpression* foobar_math_expression_new_value( FoobarMathValue value ) return res; } +// +// Helper to allocate a new FoobarMathExpression representing a function to be evaluated with another expression as its +// parameter. +// +// Ownership of "input" is transferred to the new expression. +// FoobarMathExpression* foobar_math_expression_new_function( FoobarMathFunction function, FoobarMathExpression* input ) @@ -53,6 +92,9 @@ FoobarMathExpression* foobar_math_expression_new_function( return res; } +// +// Helper to allocate a new FoobarMathExpression representing a known constant. +// FoobarMathExpression* foobar_math_expression_new_constant( FoobarMathConstant constant ) { FoobarMathExpression* res = g_new0( FoobarMathExpression, 1 ); @@ -61,6 +103,12 @@ FoobarMathExpression* foobar_math_expression_new_constant( FoobarMathConstant co return res; } +// +// Helper to allocate a new FoobarMathExpression representing an operation to be evaluated with two expressions as its +// parameters. +// +// Ownership of "lhs" and "rhs" is transferred to the new expression. +// FoobarMathExpression* foobar_math_expression_new_operation( FoobarMathOperation operation, FoobarMathExpression* lhs, @@ -74,6 +122,9 @@ FoobarMathExpression* foobar_math_expression_new_operation( return res; } +// +// Release the memory associated with a mathematical expression, along with the expressions it owns. +// void foobar_math_expression_free( FoobarMathExpression* expression ) { if ( expression ) @@ -101,6 +152,12 @@ void foobar_math_expression_free( FoobarMathExpression* expression ) } } +// +// Print a tree representation of a mathematical expression. +// +// This is mainly useful for debugging. "indentation" describes the current indentation level for the recursive call +// (should be 0 initially). +// void foobar_math_expression_print( FoobarMathExpression const* expr, gint indentation ) @@ -213,6 +270,158 @@ void foobar_math_expression_print( } } +// +// Evaluate an expression, producing a value. +// +// On success (indicated by the return value TRUE), the value should be freed using foobar_math_value_free. +// +gboolean foobar_math_evaluate( + FoobarMathExpression const* expr, + FoobarMathValue* out_value ) +{ + switch ( expr->type ) + { + case FOOBAR_MATH_EXPRESSION_VALUE: + foobar_math_value_copy( expr->value.v, out_value ); + return TRUE; + case FOOBAR_MATH_EXPRESSION_CONSTANT: + switch ( expr->constant.c ) + { + case FOOBAR_MATH_CONSTANT_PI: + foobar_math_value_from_float( M_PIl, out_value ); + return TRUE; + case FOOBAR_MATH_CONSTANT_E: + foobar_math_value_from_float( M_El, out_value ); + return TRUE; + default: + g_warn_if_reached( ); + return FALSE; + } + case FOOBAR_MATH_EXPRESSION_FUNCTION: + { + FoobarMathValue input = { 0 }; + if ( !foobar_math_evaluate( expr->function.input, &input ) ) { return FALSE; } + + if ( expr->function.f == FOOBAR_MATH_FUNCTION_NEGATE ) + { + *out_value = input; + foobar_math_value_negate( out_value ); + return TRUE; + } + + long double input_float = foobar_math_value_to_float( input ); + foobar_math_value_free( input ); + + long double result = NAN; + switch ( expr->function.f ) + { + case FOOBAR_MATH_FUNCTION_SIN: + result = sinl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_COS: + result = cosl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_SEC: + result = 1.L / cosl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_CSC: + result = 1.L / sinl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_TAN: + result = tanl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_COT: + result = 1.L / tanl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCSIN: + result = asinl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCCOS: + result = acosl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCSEC: + result = acosl( 1.L / input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCCSC: + result = asinl( 1.L / input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCTAN: + result = atanl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCCOT: + result = atanl( 1.L / input_float ); + break; + case FOOBAR_MATH_FUNCTION_EXP: + result = expl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_SQRT: + result = sqrtl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_NEGATE: + default: + g_warn_if_reached( ); + return FALSE; + } + + if ( isnanl( result ) || isinfl( result ) ) { return FALSE; } + + foobar_math_value_from_float( result, out_value ); + return TRUE; + } + case FOOBAR_MATH_EXPRESSION_OPERATION: + { + FoobarMathValue lhs = { 0 }; + if ( !foobar_math_evaluate( expr->operation.lhs, &lhs ) ) { return FALSE; } + FoobarMathValue rhs = { 0 }; + if ( !foobar_math_evaluate( expr->operation.rhs, &rhs ) ) + { + foobar_math_value_free( lhs ); + return FALSE; + } + + gboolean success = FALSE; + switch ( expr->operation.o ) + { + case FOOBAR_MATH_OPERATION_ADD: + success = foobar_math_value_add( &lhs, &rhs, out_value ); + break; + case FOOBAR_MATH_OPERATION_SUB: + success = foobar_math_value_sub( &lhs, &rhs, out_value ); + break; + case FOOBAR_MATH_OPERATION_MUL: + success = foobar_math_value_mul( &lhs, &rhs, out_value ); + break; + case FOOBAR_MATH_OPERATION_DIV: + success = foobar_math_value_div( &lhs, &rhs, out_value ); + break; + case FOOBAR_MATH_OPERATION_POW: + success = foobar_math_value_pow( &lhs, &rhs, out_value ); + break; + default: + g_warn_if_reached( ); + break; + } + + foobar_math_value_free( lhs ); + foobar_math_value_free( rhs ); + + return success; + } + default: + g_warn_if_reached( ); + return FALSE; + } +} + +// --------------------------------------------------------------------------------------------------------------------- +// Values +// --------------------------------------------------------------------------------------------------------------------- + +// +// Initialize a new integer value to zero. +// +// After this, the structure should be freed using foobar_math_value_free. +// void foobar_math_value_new_int( FoobarMathValue* out_value ) { out_value->type = FOOBAR_MATH_VALUE_INT; @@ -220,6 +429,24 @@ void foobar_math_value_new_int( FoobarMathValue* out_value ) out_value->int_value.decimal_places = 0; } +// +// Initialize a new value from its floating point representation. +// +// Although technically not necessary, you should still call foobar_math_value_free on the returned value. +// +void foobar_math_value_from_float( + long double value, + FoobarMathValue* out_value ) +{ + out_value->type = FOOBAR_MATH_VALUE_FLOAT; + out_value->float_value.v = value; +} + +// +// Parse a value from its string representation. This will always return an integer representation. +// +// On success (return value TRUE), the structure should be freed using foobar_math_value_free. +// gboolean foobar_math_value_from_string( gchar const* input, gsize input_length, @@ -251,14 +478,11 @@ gboolean foobar_math_value_from_string( return TRUE; } -void foobar_math_value_from_float( - long double value, - FoobarMathValue* out_value ) -{ - out_value->type = FOOBAR_MATH_VALUE_FLOAT; - out_value->float_value.v = value; -} - +// +// Create a copy of a value, allocating necessary memory. +// +// After this, the structure should be freed using foobar_math_value_free. +// void foobar_math_value_copy( FoobarMathValue value, FoobarMathValue* out_value ) @@ -278,6 +502,11 @@ void foobar_math_value_copy( } } +// +// Release memory associated with a value. +// +// This is necessary because the integer representation is stored using GMP, which can store arbitrarily large values. +// void foobar_math_value_free( FoobarMathValue value ) { switch ( value.type ) @@ -293,6 +522,13 @@ void foobar_math_value_free( FoobarMathValue value ) } } +// --------------------------------------------------------------------------------------------------------------------- +// Operations +// --------------------------------------------------------------------------------------------------------------------- + +// +// Operation equivalent to "value *= -1". +// void foobar_math_value_negate( FoobarMathValue* value ) { switch ( value->type ) @@ -309,6 +545,11 @@ void foobar_math_value_negate( FoobarMathValue* value ) } } +// +// Operation setting "out_value = lhs + rhs". +// +// After this, the result value should be freed using foobar_math_value_free. +// gboolean foobar_math_value_add( FoobarMathValue* lhs, FoobarMathValue* rhs, @@ -328,6 +569,11 @@ gboolean foobar_math_value_add( return TRUE; } +// +// Operation setting "out_value = lhs - rhs". +// +// After this, the result value should be freed using foobar_math_value_free. +// gboolean foobar_math_value_sub( FoobarMathValue* lhs, FoobarMathValue* rhs, @@ -347,6 +593,11 @@ gboolean foobar_math_value_sub( return TRUE; } +// +// Operation setting "out_value = lhs * rhs". +// +// After this, the result value should be freed using foobar_math_value_free. +// gboolean foobar_math_value_mul( FoobarMathValue* lhs, FoobarMathValue* rhs, @@ -366,6 +617,11 @@ gboolean foobar_math_value_mul( return TRUE; } +// +// Operation setting "out_value = lhs / rhs". +// +// After this, the result value should be freed using foobar_math_value_free. +// gboolean foobar_math_value_div( FoobarMathValue* lhs, FoobarMathValue* rhs, @@ -400,6 +656,11 @@ gboolean foobar_math_value_div( return TRUE; } +// +// Operation setting "out_value = lhs ^ rhs". +// +// After this, the result value should be freed using foobar_math_value_free. +// gboolean foobar_math_value_pow( FoobarMathValue* lhs, FoobarMathValue* rhs, @@ -425,6 +686,14 @@ gboolean foobar_math_value_pow( return TRUE; } +// +// Ensure that two integer values have the same number of decimal places. +// +// This may change the in-memory-representation of a value, but not its actual value. It only increases the precision of +// one value +// +// If either a or b is not stored as an integer, this will return FALSE. +// gboolean foobar_math_value_unify_integers( FoobarMathValue* a, FoobarMathValue* b ) @@ -457,6 +726,15 @@ gboolean foobar_math_value_unify_integers( return TRUE; } +// --------------------------------------------------------------------------------------------------------------------- +// Conversions +// --------------------------------------------------------------------------------------------------------------------- + +// +// Format a value as a string. +// +// The result is a null-terminated string which should be freed using g_free. +// gchar* foobar_math_value_to_string( FoobarMathValue value ) { switch ( value.type ) @@ -538,6 +816,11 @@ gchar* foobar_math_value_to_string( FoobarMathValue value ) } } +// +// Convert a value to its floating-point representation. +// +// This may be a lossy conversion and should only be done if absolutely necessary. +// long double foobar_math_value_to_float( FoobarMathValue value ) { switch ( value.type ) @@ -566,141 +849,3 @@ long double foobar_math_value_to_float( FoobarMathValue value ) return 0; } } - -gboolean foobar_math_evaluate( - FoobarMathExpression const* expr, - FoobarMathValue* out_value ) -{ - switch ( expr->type ) - { - case FOOBAR_MATH_EXPRESSION_VALUE: - foobar_math_value_copy( expr->value.v, out_value ); - return TRUE; - case FOOBAR_MATH_EXPRESSION_CONSTANT: - switch ( expr->constant.c ) - { - case FOOBAR_MATH_CONSTANT_PI: - foobar_math_value_from_float( M_PIl, out_value ); - return TRUE; - case FOOBAR_MATH_CONSTANT_E: - foobar_math_value_from_float( M_El, out_value ); - return TRUE; - default: - g_warn_if_reached( ); - return FALSE; - } - case FOOBAR_MATH_EXPRESSION_FUNCTION: - { - FoobarMathValue input = { 0 }; - if ( !foobar_math_evaluate( expr->function.input, &input ) ) { return FALSE; } - - if ( expr->function.f == FOOBAR_MATH_FUNCTION_NEGATE ) - { - *out_value = input; - foobar_math_value_negate( out_value ); - return TRUE; - } - - long double input_float = foobar_math_value_to_float( input ); - foobar_math_value_free( input ); - - long double result = NAN; - switch ( expr->function.f ) - { - case FOOBAR_MATH_FUNCTION_SIN: - result = sinl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_COS: - result = cosl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_SEC: - result = 1.L / cosl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_CSC: - result = 1.L / sinl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_TAN: - result = tanl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_COT: - result = 1.L / tanl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_ARCSIN: - result = asinl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_ARCCOS: - result = acosl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_ARCSEC: - result = acosl( 1.L / input_float ); - break; - case FOOBAR_MATH_FUNCTION_ARCCSC: - result = asinl( 1.L / input_float ); - break; - case FOOBAR_MATH_FUNCTION_ARCTAN: - result = atanl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_ARCCOT: - result = atanl( 1.L / input_float ); - break; - case FOOBAR_MATH_FUNCTION_EXP: - result = expl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_SQRT: - result = sqrtl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_NEGATE: - default: - g_warn_if_reached( ); - return FALSE; - } - - if ( isnanl( result ) || isinfl( result ) ) { return FALSE; } - - foobar_math_value_from_float( result, out_value ); - return TRUE; - } - case FOOBAR_MATH_EXPRESSION_OPERATION: - { - FoobarMathValue lhs = { 0 }; - if ( !foobar_math_evaluate( expr->operation.lhs, &lhs ) ) { return FALSE; } - FoobarMathValue rhs = { 0 }; - if ( !foobar_math_evaluate( expr->operation.rhs, &rhs ) ) - { - foobar_math_value_free( lhs ); - return FALSE; - } - - gboolean success = FALSE; - switch ( expr->operation.o ) - { - case FOOBAR_MATH_OPERATION_ADD: - success = foobar_math_value_add( &lhs, &rhs, out_value ); - break; - case FOOBAR_MATH_OPERATION_SUB: - success = foobar_math_value_sub( &lhs, &rhs, out_value ); - break; - case FOOBAR_MATH_OPERATION_MUL: - success = foobar_math_value_mul( &lhs, &rhs, out_value ); - break; - case FOOBAR_MATH_OPERATION_DIV: - success = foobar_math_value_div( &lhs, &rhs, out_value ); - break; - case FOOBAR_MATH_OPERATION_POW: - success = foobar_math_value_pow( &lhs, &rhs, out_value ); - break; - default: - g_warn_if_reached( ); - break; - } - - foobar_math_value_free( lhs ); - foobar_math_value_free( rhs ); - - return success; - } - default: - g_warn_if_reached( ); - return FALSE; - } -} |