Intro & explanation
Although old, I see this question has had some edits recently and its still the first thing that came up on search engines for me when I was looking into this.
For that reason I wanted to share: if anyone comes to this looking for a simple (naive) solution that doesn't require pulling in a library, this is what I ended up using for my purpose.
Its a simple brute-force that first looks if 1/⌊1/x⌉
is a good approximation, if not it checks 2/⌊2/x⌉
, 3/⌊3/x⌉
and so on until the first result within the given error bound.
Code
function getFrac(x, maxErr){
let s = x<0?-1:1
x = Math.abs(x),
i = Math.floor(x),
d = x-i,
maxErr = maxErr ? maxErr : Math.pow(10,-6);
if(d<maxErr) return [i,1];
let n = 1,
nmax = Math.ceil(d*Math.min(
Math.pow(10,Math.ceil(Math.abs(Math.log10(maxErr)))),
Number.MAX_SAFE_INTEGER
)),
min = Infinity,
best = [0,0];
while(n <= nmax){
let err = Math.abs(d - n/Math.round(n/d));
if(err < maxErr) return [s*(n+i*Math.round(n/d)), Math.round(n/d)];
else if(err < min){
min = err;
best = [s*(n+i*Math.round(n/d)), Math.round(n/d)];
}
n++;
}
return best[1] == 0 ? false : best;
}
Example output:
getFrac(0) // [0, 1]
getFrac(0.28) // [7, 25]
getFrac(0.28282828) // [28, 99]
getFrac(2.56) // [64, 25]
getFrac(-1.33333333) // [-4, 3]
getFrac(Math.E) // [2721, 1001]
getFrac(Math.PI) // [355, 113]
getFrac(Math.PI, 0.01) // [22, 7]
getFrac(Math.PI, 0.001) // [201, 64]
getFrac(Math.PI, 10**-4) // [333, 106]
getFrac(Math.PI, 10**-12) // [4272943, 1360120]
Performance
Although this is the naive approach, it runs surprisingly well, fast enough for most needs. Both JSbench and tests in my console using performance.now()
indicate getFrac
takes ~4 microseconds to return on average when fed random input using the default error level of 6 decimal places. The linked JSBench was giving me a result of ~200 ops/sec on my machine when calling getFrac
1000 times each op. I include below the timer script I used in the console.
let N = 10000,
nums = new Array(N).fill(0).map(v=>Math.random()*(Math.random()<2/3?1:100)),
t = 0;
for(let n of nums){
const t0 = performance.now();
getFrac(n);
const t1 = performance.now();
t += t1-t0;
}
console.log((t/N)*1000,'micros'); // 4.039999999850989 micros