summaryrefslogtreecommitdiff
path: root/lib/math/rational.c
diff options
context:
space:
mode:
authorAndy Shevchenko <andriy.shevchenko@linux.intel.com>2019-05-14 15:43:05 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2019-05-14 19:52:49 -0700
commit2c64e9cb0b6b858901e9a386860d7d929d1cbaeb (patch)
tree749da0ef8f5d478680a523c877fb0e16fc18409c /lib/math/rational.c
parentb5c56e0cdd62979dd538e5363b06be5bdf735a09 (diff)
lib: Move mathematic helpers to separate folder
For better maintenance and expansion move the mathematic helpers to the separate folder. No functional change intended. Note, the int_sqrt() is not used as a part of lib, so, moved to regular obj. Link: http://lkml.kernel.org/r/20190323172531.80025-1-andriy.shevchenko@linux.intel.com Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Signed-off-by: Mauro Carvalho Chehab <mchehab+samsung@kernel.org> Cc: Randy Dunlap <rdunlap@infradead.org> Cc: Thierry Reding <thierry.reding@gmail.com> Cc: Lee Jones <lee.jones@linaro.org> Cc: Daniel Thompson <daniel.thompson@linaro.org> Cc: Ray Jui <rjui@broadcom.com> [mchehab+samsung@kernel.org: fix broken doc references for div64.c and gcd.c] Link: http://lkml.kernel.org/r/734f49bae5d4052b3c25691dfefad59bea2e5843.1555580999.git.mchehab+samsung@kernel.org Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib/math/rational.c')
-rw-r--r--lib/math/rational.c65
1 files changed, 65 insertions, 0 deletions
diff --git a/lib/math/rational.c b/lib/math/rational.c
new file mode 100644
index 000000000000..ba7443677c90
--- /dev/null
+++ b/lib/math/rational.c
@@ -0,0 +1,65 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * rational fractions
+ *
+ * Copyright (C) 2009 emlix GmbH, Oskar Schirmer <oskar@scara.com>
+ *
+ * helper functions when coping with rational numbers
+ */
+
+#include <linux/rational.h>
+#include <linux/compiler.h>
+#include <linux/export.h>
+
+/*
+ * calculate best rational approximation for a given fraction
+ * taking into account restricted register size, e.g. to find
+ * appropriate values for a pll with 5 bit denominator and
+ * 8 bit numerator register fields, trying to set up with a
+ * frequency ratio of 3.1415, one would say:
+ *
+ * rational_best_approximation(31415, 10000,
+ * (1 << 8) - 1, (1 << 5) - 1, &n, &d);
+ *
+ * you may look at given_numerator as a fixed point number,
+ * with the fractional part size described in given_denominator.
+ *
+ * for theoretical background, see:
+ * http://en.wikipedia.org/wiki/Continued_fraction
+ */
+
+void rational_best_approximation(
+ unsigned long given_numerator, unsigned long given_denominator,
+ unsigned long max_numerator, unsigned long max_denominator,
+ unsigned long *best_numerator, unsigned long *best_denominator)
+{
+ unsigned long n, d, n0, d0, n1, d1;
+ n = given_numerator;
+ d = given_denominator;
+ n0 = d1 = 0;
+ n1 = d0 = 1;
+ for (;;) {
+ unsigned long t, a;
+ if ((n1 > max_numerator) || (d1 > max_denominator)) {
+ n1 = n0;
+ d1 = d0;
+ break;
+ }
+ if (d == 0)
+ break;
+ t = d;
+ a = n / d;
+ d = n % d;
+ n = t;
+ t = n0 + a * n1;
+ n0 = n1;
+ n1 = t;
+ t = d0 + a * d1;
+ d0 = d1;
+ d1 = t;
+ }
+ *best_numerator = n1;
+ *best_denominator = d1;
+}
+
+EXPORT_SYMBOL(rational_best_approximation);