Continued fractions: convert real numbers to approximate fractions, such as 0.33 to 1/3 and π to 22/7.

continued fractions.m

@import Foundation;

#define ENABLE_LOGGING 1

#if ENABLE_LOGGING
#define DHLog(__FORMAT__, ...) NSLog((__FORMAT__), ##__VA_ARGS__)
#else
#define DHLog(...) do { } while (0)
#endif

typedef struct {
	int numerator;
	int denominator;
} DHFraction;

DHFraction DHFractionMake(int numerator, int denominator)
{
	DHFraction fraction;
	
	fraction.numerator = numerator;
	fraction.denominator = denominator;
	
	return fraction;
}

DHFraction DHFractionAdd(int integer, DHFraction fraction)
{
	DHFraction newFraction;
	
	newFraction.numerator = fraction.numerator + integer * fraction.denominator;
	newFraction.denominator = fraction.denominator;
	
	return newFraction;
}

NSString *DHStringFromFraction(DHFraction fraction)
{
	return [NSString stringWithFormat:@"%d/%d", fraction.numerator, fraction.denominator];
}

DHFraction continuedFraction(float number, float tolerance, int iterationLimit)
{
	int integralComponent = floorf(number);
	float fractionalComponent = number - integralComponent;
	
#if ENABLE_LOGGING
	DHLog(@"%d + %f", integralComponent, fractionalComponent);
#endif
	
	if (ABS(1 - fractionalComponent) < tolerance) {
		DHLog(@"%f ~ 1", fractionalComponent);
		++integralComponent;
		fractionalComponent = 0;
		DHLog(@"%d + %f *", integralComponent, fractionalComponent);
	}
	
	if (fractionalComponent < tolerance || iterationLimit <= 1) {
		if (fractionalComponent < tolerance) {
			DHLog(@"%f ~ 0", fractionalComponent);
		}
		else {
			DHLog(@"Reached iteration limit");
		}
		return DHFractionMake(integralComponent, 1);
	}
	
	float reciprocal = 1 / fractionalComponent;
	
	DHFraction nextFraction = continuedFraction(reciprocal, tolerance, iterationLimit - 1);
	return DHFractionAdd(integralComponent, DHFractionMake(nextFraction.denominator, nextFraction.numerator));
}

int main(int argc, const char * argv[]) {
	@autoreleasepool {
		
		float target = 0.33;
		float tolerance = 0.1;
		
		DHFraction fraction = continuedFraction(target, tolerance, 10);
		NSLog(@"%f = %@ %+g", target, DHStringFromFraction(fraction), target - ((float)fraction.numerator / fraction.denominator));
	}
	return 0;
}