[recipes/rational-approximation: 1/4] Display doubles as mixed fractions too

[Matthias Clasen <matthiasc src gnome org>]

commit 360535697b9709b4e9d3208ca3c528f52d641669
Author: Matthias Clasen <mclasen redhat com>
Date:   Sat Jun 24 15:47:42 2017 -0400

    Display doubles as mixed fractions too
    
    Use rational approximation using continued fractions.

 src/gr-number.c |  114 +++++++++++++++++++++++++++++++++++++++++++-----------
 1 files changed, 90 insertions(+), 24 deletions(-)
---
diff --git a/src/gr-number.c b/src/gr-number.c
index dc7157e..d1e22e0 100644
--- a/src/gr-number.c
+++ b/src/gr-number.c
@@ -20,6 +20,7 @@
 
 #include <glib/gi18n.h>
 #include <gio/gio.h>
+#include <math.h>
 
 #include "gr-number.h"
 #include "gr-utils.h"
@@ -44,6 +45,61 @@ gcd (int m, int n)
         return m;
 }
 
+static gboolean
+rational_approximation (double  input,
+                        int     max_denom,
+                        int    *num,
+                        int    *denom)
+{
+        long m[2][2];
+        double x, n0, d0, n1, d1;
+        long ai;
+
+        x = input;
+
+        m[0][0] = m[1][1] = 1;
+        m[0][1] = m[1][0] = 0;
+
+        while (m[1][0] * (ai = (long)x) + m[1][1] <= max_denom) {
+                long t;
+
+                t = m[0][0] * ai + m[0][1];
+                m[0][1] = m[0][0];
+                m[0][0] = t;
+                t = m[1][0] * ai + m[1][1];
+                m[1][1] = m[1][0];
+                m[1][0] = t;
+
+                if (x == (double)ai)
+                        break;
+
+                x = 1 / (x - (double)ai);
+
+                if (x > (double)0x7fffffff)
+                        break;
+        }
+
+        n0 = (double)m[0][0];
+        d0 = (double)m[1][0];
+
+        ai = (max_denom - m[1][1]) / m[1][0];
+        m[0][0] = m[0][0] * ai + m[0][1];
+        m[1][0] = m[1][0] * ai + m[1][1];
+
+        n1 = (double)m[0][0];
+        d1 = (double)m[1][0];
+
+        if (fabs (input - n0 / d0) < fabs (input - n1 / d1)) {
+                *num = (int)n0;
+                *denom = (int)d0;
+        } else {
+                *num = (int)n1;
+                *denom = (int)d1;
+        }
+
+        return TRUE;
+}
+
 void
 gr_number_set_fraction (GrNumber *number,
                         int       num,
@@ -308,47 +364,57 @@ append_digits (GString    *s,
 }
 
 static char *
-format_fraction (int num, int denom)
+format_fraction (int integral, int num, int denom)
 {
         int i;
         GString *s;
 
-        for (i = 0; i < G_N_ELEMENTS (fractions); i++) {
-                if (fractions[i].num == num && fractions[i].denom == denom)
-                        return g_strdup (fractions[i].ch);
-        }
+        if (denom == 0)
+                return g_strdup ("");
+
+        integral += num / denom;
+        num = num % denom;
 
         s = g_string_new ("");
 
+        if (integral != 0)
+                g_string_append_printf (s, "%d", integral);
+
+        if (num == 0)
+                goto out;
+
+        g_string_append (s, " ");
+
+        for (i = 0; i < G_N_ELEMENTS (fractions); i++) {
+                if (fractions[i].num == num && fractions[i].denom == denom) {
+                        g_string_append (s, fractions[i].ch);
+                        goto out;
+                }
+        }
+
         append_digits (s, sup, num);
         g_string_append (s, "⁄");
         append_digits (s, sub, denom);
 
+out:
         return g_string_free (s, FALSE);
 }
 
 char *
 gr_number_format (GrNumber *number)
 {
-        if (number->fraction) {
-                if (number->denom == 1)
-                        return g_strdup_printf ("%d", number->num);
-                else {
-                        int integral;
-                        g_autofree char *fraction = NULL;
-
-                        if (number->denom == 0)
-                                return g_strdup ("");
-
-                        integral = number->num / number->denom;
-                        fraction = format_fraction (number->num % number->denom, number->denom);
-                        if (integral == 0)
-                                return g_strdup_printf ("%s", fraction);
-                        else
-                                return g_strdup_printf ("%d %s", integral, fraction);
-                }
-        }
+        if (number->fraction)
+                return format_fraction (0, number->num, number->denom);
         else {
-                return g_strdup_printf ("%g", number->value);
+                double integral, rem;
+                int num, denom;
+
+                integral = floor (number->value);
+                rem = number->value - integral;
+
+                if (rational_approximation (rem, 20, &num, &denom))
+                        return format_fraction ((int)integral, num, denom);
+                else
+                        return g_strdup_printf ("%g", number->value);
         }
 }