/*
 * Copyright (c) 2008 James Dow Allen
 *
 * NB: because of strtold(), this must be compiled with
 *	-std=c99
 */
#include	<stdio.h>
#include	<stdlib.h>
#include	<string.h>

#define	TINY	0.000000000000000000000001
typedef	unsigned long long Number;
#define	MAXLENG	100
Number	Arr[MAXLENG], Num[MAXLENG], Den[MAXLENG];

Number findfact(Number x)
{
	Number  y;

	if (x % 2 == 0) return 2;
	if (x % 3 == 0) return 3;
	if (x % 5 == 0) return 5;
	for (y = 6; y * y < x; y += 6) {
		if (x % (y + 1) == 0) return y + 1;
		if (x % (y + 5) == 0) return y + 5;
	}
	return x;
}

void fizion(Number x, char *ob)
{
	Number	y, prm;
	int	cnt;

	strcpy(ob, "1");
	prm = cnt = 0;
	while (1) {
		y = findfact(x);
		if (y != prm) {
			if (cnt > 1)
				sprintf(ob + strlen(ob), "^%d", cnt);
			if (y < 2)
				return;
			if (prm)
				sprintf(ob + strlen(ob), "*%Ld", y);
			else
				sprintf(ob, "%Ld", y);
			prm = y;
			cnt = 0;
		}
		++cnt;
		x /= y;
	}
}

int main(int argc, char **argv)
{
	long double	x, origx, error, minerr = 9;
	int	i, j, maxi;
	Number	nxt, num, den;
	char	fiz1[3000], fiz2[3000];

	if (argc != 2) {
		fprintf(stderr,
	"Usage: cf #F\n\t-- show #F as continued fraction\n");
		exit(1);
	}
	origx = x = strtold(argv[1], (char **)0);
	if (x < TINY)
		exit(1);
	printf("%25.22Lf rendered as\n\tCF = ", x);
	for (i = 0; i < MAXLENG; i++) {
		Arr[i] = x;
		den = 1;
		num = 0;
		for (j = i; j; j--) {
			nxt = Arr[j] * den + num;
			num = den;
			den = nxt;
		}
		Den[i] = den;
		Num[i] = num + den * Arr[0];
		error = origx - Num[i] / (long double)Den[i];
		if (error < 0)
			error = -error;
		if (error < minerr - 1000 * TINY)
			minerr = error;
		else
			break;
		printf("%d ", (int)x);
		x = 1 / (x - (int)x) - TINY;
	}
	maxi = i;
	printf("\nLeading to the approximations:\n");
	for (i = 1; i < maxi; i++) {
		fizion(Num[i], fiz1);
		fizion(Den[i], fiz2);
		printf(" %Ld / %Ld =\n\t%s / %s =\n\t%22.19Lf\n",
				Num[i], Den[i], fiz1, fiz2,
				Num[i] / (long double)Den[i]);
	}
	exit(0);
}