diff options
author | Linus Torvalds <torvalds@linux-foundation.org> | 2019-12-05 09:46:26 -0800 |
---|---|---|
committer | Linus Torvalds <torvalds@linux-foundation.org> | 2019-12-05 09:46:26 -0800 |
commit | 5ecc9d15f73b82c748526350d5602c94fdd65cac (patch) | |
tree | 686ae55a0de4be8bad9e2248b019e459525cb109 /lib/math/rational.c | |
parent | 2f13437b8917627119d163d62f73e7a78a92303a (diff) | |
parent | f949286c668aed5aa24acdb5838be9cfd9513bd3 (diff) |
Merge branch 'akpm' (patches from Andrew)
Merge more updates from Andrew Morton:
"Most of the rest of MM and various other things. Some Kconfig rework
still awaits merges of dependent trees from linux-next.
Subsystems affected by this patch series: mm/hotfixes, mm/memcg,
mm/vmstat, mm/thp, procfs, sysctl, misc, notifiers, core-kernel,
bitops, lib, checkpatch, epoll, binfmt, init, rapidio, uaccess, kcov,
ubsan, ipc, bitmap, mm/pagemap"
* akpm: (86 commits)
mm: remove __ARCH_HAS_4LEVEL_HACK and include/asm-generic/4level-fixup.h
um: add support for folded p4d page tables
um: remove unused pxx_offset_proc() and addr_pte() functions
sparc32: use pgtable-nopud instead of 4level-fixup
parisc/hugetlb: use pgtable-nopXd instead of 4level-fixup
parisc: use pgtable-nopXd instead of 4level-fixup
nds32: use pgtable-nopmd instead of 4level-fixup
microblaze: use pgtable-nopmd instead of 4level-fixup
m68k: mm: use pgtable-nopXd instead of 4level-fixup
m68k: nommu: use pgtable-nopud instead of 4level-fixup
c6x: use pgtable-nopud instead of 4level-fixup
arm: nommu: use pgtable-nopud instead of 4level-fixup
alpha: use pgtable-nopud instead of 4level-fixup
gpio: pca953x: tighten up indentation
gpio: pca953x: convert to use bitmap API
gpio: pca953x: use input from regs structure in pca953x_irq_pending()
gpio: pca953x: remove redundant variable and check in IRQ handler
lib/bitmap: introduce bitmap_replace() helper
lib/test_bitmap: fix comment about this file
lib/test_bitmap: move exp1 and exp2 upper for others to use
...
Diffstat (limited to 'lib/math/rational.c')
-rw-r--r-- | lib/math/rational.c | 63 |
1 files changed, 50 insertions, 13 deletions
diff --git a/lib/math/rational.c b/lib/math/rational.c index ba7443677c90..31fb27db2deb 100644 --- a/lib/math/rational.c +++ b/lib/math/rational.c @@ -3,6 +3,7 @@ * rational fractions * * Copyright (C) 2009 emlix GmbH, Oskar Schirmer <oskar@scara.com> + * Copyright (C) 2019 Trent Piepho <tpiepho@gmail.com> * * helper functions when coping with rational numbers */ @@ -10,6 +11,7 @@ #include <linux/rational.h> #include <linux/compiler.h> #include <linux/export.h> +#include <linux/kernel.h> /* * calculate best rational approximation for a given fraction @@ -33,30 +35,65 @@ void rational_best_approximation( 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/d is the starting rational, which is continually + * decreased each iteration using the Euclidean algorithm. + * + * dp is the value of d from the prior iteration. + * + * n2/d2, n1/d1, and n0/d0 are our successively more accurate + * approximations of the rational. They are, respectively, + * the current, previous, and two prior iterations of it. + * + * a is current term of the continued fraction. + */ + unsigned long n, d, n0, d0, n1, d1, n2, d2; 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; - } + unsigned long dp, a; + if (d == 0) break; - t = d; + /* Find next term in continued fraction, 'a', via + * Euclidean algorithm. + */ + dp = d; a = n / d; d = n % d; - n = t; - t = n0 + a * n1; + n = dp; + + /* Calculate the current rational approximation (aka + * convergent), n2/d2, using the term just found and + * the two prior approximations. + */ + n2 = n0 + a * n1; + d2 = d0 + a * d1; + + /* If the current convergent exceeds the maxes, then + * return either the previous convergent or the + * largest semi-convergent, the final term of which is + * found below as 't'. + */ + if ((n2 > max_numerator) || (d2 > max_denominator)) { + unsigned long t = min((max_numerator - n0) / n1, + (max_denominator - d0) / d1); + + /* This tests if the semi-convergent is closer + * than the previous convergent. + */ + if (2u * t > a || (2u * t == a && d0 * dp > d1 * d)) { + n1 = n0 + t * n1; + d1 = d0 + t * d1; + } + break; + } n0 = n1; - n1 = t; - t = d0 + a * d1; + n1 = n2; d0 = d1; - d1 = t; + d1 = d2; } *best_numerator = n1; *best_denominator = d1; |