1 | *// SPDX-License-Identifier: GPL-2.0* |

2 | */** |

3 | * * rational fractions* |

4 | * ** |

5 | * * Copyright (C) 2009 emlix GmbH, Oskar Schirmer <oskar@scara.com>* |

6 | * ** |

7 | * * helper functions when coping with rational numbers* |

8 | * */* |

9 | |

10 | __#include <linux/rational.h>__ |

11 | __#include <linux/compiler.h>__ |

12 | __#include <linux/export.h>__ |

13 | |

14 | */** |

15 | * * calculate best rational approximation for a given fraction* |

16 | * * taking into account restricted register size, e.g. to find* |

17 | * * appropriate values for a pll with 5 bit denominator and* |

18 | * * 8 bit numerator register fields, trying to set up with a* |

19 | * * frequency ratio of 3.1415, one would say:* |

20 | * ** |

21 | * * rational_best_approximation(31415, 10000,* |

22 | * * (1 << 8) - 1, (1 << 5) - 1, &n, &d);* |

23 | * ** |

24 | * * you may look at given_numerator as a fixed point number,* |

25 | * * with the fractional part size described in given_denominator.* |

26 | * ** |

27 | * * for theoretical background, see:* |

28 | * * http://en.wikipedia.org/wiki/Continued_fraction* |

29 | * */* |

30 | |

31 | *void* rational_best_approximation( |

32 | *unsigned* *long* given_numerator, *unsigned* *long* given_denominator, |

33 | *unsigned* *long* max_numerator, *unsigned* *long* max_denominator, |

34 | *unsigned* *long* *best_numerator, *unsigned* *long* *best_denominator) |

35 | { |

36 | *unsigned* *long* n, d, n0, d0, n1, d1; |

37 | n = given_numerator; |

38 | d = given_denominator; |

39 | n0 = d1 = `0`; |

40 | n1 = d0 = `1`; |

41 | **for** (;;) { |

42 | *unsigned* *long* t, a; |

43 | **if** ((n1 > max_numerator) || (d1 > max_denominator)) { |

44 | n1 = n0; |

45 | d1 = d0; |

46 | **break**; |

47 | } |

48 | **if** (d == `0`) |

49 | **break**; |

50 | t = d; |

51 | a = n / d; |

52 | d = n % d; |

53 | n = t; |

54 | t = n0 + a * n1; |

55 | n0 = n1; |

56 | n1 = t; |

57 | t = d0 + a * d1; |

58 | d0 = d1; |

59 | d1 = t; |

60 | } |

61 | *best_numerator = n1; |

62 | *best_denominator = d1; |

63 | } |

64 | |

65 | EXPORT_SYMBOL(rational_best_approximation); |

66 | |