mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-04 07:29:47 +08:00
86d333ee94
* chore: Switch to Node 20 + Vitest * chore: migrate to vitest mock functions * chore: code style (switch to prettier) * test: re-enable long-running test Seems the switch to Node 20 and Vitest has vastly improved the code's and / or the test's runtime! see #1193 * chore: code style * chore: fix failing tests * Updated Documentation in README.md * Update contribution guidelines to state usage of Prettier * fix: set prettier printWidth back to 80 * chore: apply updated code style automatically * fix: set prettier line endings to lf again * chore: apply updated code style automatically --------- Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com> Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>
51 lines
1.3 KiB
JavaScript
51 lines
1.3 KiB
JavaScript
/*
|
|
* Reference: https://en.wikipedia.org/wiki/Farey_sequence
|
|
* Inspiration: https://www.youtube.com/watch?v=7LKy3lrkTRA
|
|
*
|
|
* Farey Approximation algorithm is an algorithm to
|
|
* approximate a reduced fraction value for a certain
|
|
* decimal number x where 0 < x < 1.
|
|
*
|
|
* The algorithm works by keeping two fractional upper and
|
|
* lower bounds which start at 0 / 1 and 1 / 1. These values
|
|
* are then used to find the "mediate" which is a value between
|
|
* the two fractions.
|
|
*
|
|
* For any two fractions a / b and c / d,
|
|
* mediate = a + c / b + d
|
|
*
|
|
* Then it is checked if the decimal is greater than or less
|
|
* than the mediate and then the lower or the upper value is
|
|
* set to be the mediate respectively.
|
|
*
|
|
* This is repeated for n times and then the mediate is
|
|
* returned.
|
|
*
|
|
* This is explained in a greater detail in the "Inspiration"
|
|
* link.
|
|
*/
|
|
|
|
function fareyApproximation(decimal, repeat = 20) {
|
|
let a = 0
|
|
let b = 1
|
|
let c = 1
|
|
let d = 1
|
|
let numerator
|
|
let denominator
|
|
|
|
for (let i = 0; i < repeat; i++) {
|
|
numerator = a + c
|
|
denominator = b + d
|
|
|
|
if (decimal > numerator / denominator) {
|
|
;[a, b] = [numerator, denominator]
|
|
} else {
|
|
;[c, d] = [numerator, denominator]
|
|
}
|
|
}
|
|
|
|
return { numerator, denominator }
|
|
}
|
|
|
|
export { fareyApproximation }
|