Как обойти двоичную погрешность JavaScript
Есть такая задача:
Имеется n кг металлического сплава. Из него изготавливают заготовки массой k кг каждая.
После этого из каждой заготовки вытачиваются детали массой m кг каждая (из каждой заготовки вытачивают максимально возможное количество деталей).
Если от заготовок после этого что-то остается, то этот материал возвращают к началу производственного цикла и сплавляют с тем, что осталось при изготовлении заготовок. Если того сплава, который получился, достаточно для изготовления хотя бы
одной заготовки, то из него снова изготавливают заготовки, из них — детали и т.д.
Напишите программу, которая вычислит, какое количество деталей может быть получено по этой технологии из исходного n кг сплава
function calcMetall(n, k, m, sum = 0) {
console.log(n, 'кг металлического сплава');
console.log(k, 'кг масса одной заготовки');
console.log(m, 'кг масса одной детали');
console.log('');
const kPieces = Math.trunc(n / k);
const kBalance = n - kPieces * k;
console.log(kPieces, 'заготовок');
console.log(kBalance, 'Остаток сплава от заготовок');
console.log('');
// Я предполагаю, что заготовку стругают и из неё всегда получается деталь, оставшийся мусор пускают на следующий цикл переработки
const mPieces = kPieces;
const mBalance = k * kPieces - m * mPieces;
console.log(mPieces, 'деталей');
console.log(mBalance, 'Остаток сплава от деталей');
const balance = kBalance + mBalance;
console.log(balance, 'Общий остаток');
sum = sum + mPieces;
console.log('----------------------------------');
if (balance > k) {
return calcMetall(balance, k, m, sum);
}
return sum;
}
const sum = calcMetall(2, 0.3, 0.2);
console.log(sum);
console.log(0.1 + 0.2 == 0.3); // false
console.log(0.3); // 0.30000000000000004
console.log(2 - 6*0.3); // 0.20000000000000018
Я не понимаю, как мне обойти эту погрешность, чтобы моя программа работала правильно при разных входных данных
UPD:
Не понимаю, почему здесь опять появляется неточность
function toTochno(n) {
if (n > 1 / Math.pow(10, 15)) {
return Math.round(n * Math.pow(10, 15)) / Math.pow(10, 15);
} else {
return n;
}
}
function calcMetall(n, k, m, sum = 0) {
console.log(n, 'кг металлического сплава');
console.log(k, 'кг масса одной заготовки');
console.log(m, 'кг масса одной детали');
console.log('');
const kPieces = Math.trunc(n / k);
const kBalance = toTochno(n - kPieces * k);
console.log(kPieces, 'заготовок');
console.log(kBalance, 'Остаток сплава от заготовок');
console.log('');
const mPieces = toTochno(Math.trunc(k / m) * kPieces);
const mBalance = toTochno(k * kPieces - m * mPieces);
console.log(mPieces, 'деталей');
console.log(mBalance, 'Остаток сплава от деталей');
const balance = toTochno(kBalance + mBalance);
console.log(balance, 'Общий остаток');
sum = sum + mPieces;
console.log('----------------------------------');
if (balance > k) {
return calcMetall(balance, k, m, sum);
}
return sum;
}
const sum = calcMetall(100, 0.3, 0.2);
console.log(sum);
Ответы (2 шт):
По большому счету кг можно выразить в граммах, микрограммах, нанограммах. Тогда удастся избежать неточностей. Если максимальное число в JS ~9e15, то в нанограммах можно выразить до 9 тонн без всяких нецелых чисел.
Если позволяет точность до нанограмма:
function toTochno(n) {
return Math.round(n * Math.pow(10, 12)) / Math.pow(10, 12);
}
function calcMetall(n, k, m, sum = 0) {
console.log(n, 'кг металлического сплава');
console.log(k, 'кг масса одной заготовки');
console.log(m, 'кг масса одной детали');
console.log('');
const kPieces = Math.trunc(n / k);
const kBalance = toTochno(n - kPieces * k);
console.log(kPieces, 'заготовок');
console.log(kBalance, 'Остаток сплава от заготовок');
console.log('');
const mPieces = toTochno(Math.trunc(k / m) * kPieces);
const mBalance = toTochno(k * kPieces - m * mPieces);
console.log(mPieces, 'деталей');
console.log(mBalance, 'Остаток сплава от деталей');
const balance = toTochno(kBalance + mBalance);
console.log(balance, 'Общий остаток');
sum = sum + mPieces;
console.log('----------------------------------');
if (balance > k) {
return calcMetall(balance, k, m, sum);
}
return sum;
}
const sum = calcMetall(100, 0.3, 0.2);
console.log(sum);
Еще проще если использовать граммы!!!:
function calcMetall(n, k, m, sum = 0) {
console.log(n, 'г металлического сплава');
console.log(k, 'г масса одной заготовки');
console.log(m, 'г масса одной детали');
console.log('');
const kPieces = Math.trunc(n / k);
const kBalance = n - kPieces * k;
console.log(kPieces, 'заготовок');
console.log(kBalance, 'Остаток сплава от заготовок');
console.log('');
const mPieces = Math.trunc(k / m) * kPieces;
const mBalance = k * kPieces - m * mPieces;
console.log(mPieces, 'деталей');
console.log(mBalance, 'Остаток сплава от деталей');
const balance = kBalance + mBalance;
console.log(balance, 'Общий остаток');
sum = sum + mPieces;
console.log('----------------------------------');
if (balance > k) {
return calcMetall(balance, k, m, sum);
}
return sum;
}
const sum = calcMetall(100000, 300, 200);
console.log(sum);
Проблема
Когда вы получили числа n, k и m в вещественном формате, бой уже проигран. Большая часть дробей не представима точно как вещественное число, их значения немного округлились. Следовательно деление с остатком будет иногда ошибаться. Да можно играть с округлениями, это поможет с небольшими десятичными дробями. Но что вы будете делать с n = 1, m = k = 0.14285714285714285? Второе значение это 1/7 слегка округлённая в вещественном формате. Тут округлением к десятичной дроби не обойдёшься.
Ещё пример: n = 1.4142135623730951, k = 0.14142135623730953, m = 0.014142135623730952. Можно догадаться что n ≈ √2, k ≈ √2/10, m ≈ √2/100 и ответ должен быть сто. Но округления превращают простую задачу в проблему.
Задача
Отложим проблему в сторону и посмотрим на саму задачу.
Пусть d(n, k, m) - количество деталей, которое в конце концов будет изготовлено. Из n сплава можно сделать ⌊n/k⌋ заготовок. Из одной заготовки можно сделать ⌊k/m⌋ деталей. Тогда
d(n, k, m) = 0, если m > k. Нельзя делать детали, если они тяжелее заготовок.
d(n, k, m) = 0, если k > m. Нельзя делать заготовки, если на них не хватает материала. А если нет заготовок, то не будет и деталей.
d(n, k, m) = ⌊n/k⌋·⌊k/m⌋ + d(n - ⌊n/k⌋·⌊k/m⌋·m, k, m), если k > m. За один подход можно изготовить ⌊n/k⌋ заготовок. Из каждой заготовки - ⌊k/m⌋ деталей. После изготовления деталей количество материала уменьшиться на ⌊n/k⌋·⌊k/m⌋·m. Из оставшего материала продолжаем делать детали.
Видно что умножение параметров на общий положительный коэффициент сохраняет значение d: d(n, k, m) = d(cn, ck, cm). Другими словами ответ в задаче зависит не от абсолютных значений параметров, а только от пропорций между ними. Раз так, то будем решать приведённую задачу: d(n, k, m) = d(1, k/n, m/n).
Компенсация ошибок
Можно восстановить исходную дробь по её приближённому вещественному значению. Сперва вещественое число преобразуется в дробь, в знаменателе которой степень двойки. Затем по этой дроби строится непрерывная дробь. По непрерывной дроби строится последовательность обыкновенных дробей, которые сходятся к вещественному значению. Из этих обыкновенных дробей выбирается первая, которая в машинной арифметике достаточно близка к вещественному значению. Подробности в этом ответе.
"Достаточно близка" требует уточнения. Мы восстанавливаем дробь для значения вида a/b, где a, b уже были машинными вещественными числами, то есть, уже содержали в себе ошибку округления. Примем что их относительная ошибка не превосходит Number.EPSILON / 2. Оценка точности отношения тогда есть сумма ошибок аргументов (два раза по Number.EPSILON / 2) и округления после деления (ещё раз Number.EPSILON / 2). Общую точность отношения удобно оценить в Number.EPSILON * 2. Здесь опущено множество делалей, чтобы не отходить далеко в сторону. Точность вещественных чисел - отдельная большая интересная тема.
Решение
binRatio(x) - возвращает дробь n/d, значение которой точно равно x. Например 0.3 = 5404319552844595/18014398509481984.
continuedFraction(n, d) - возвращает непрерывную дробь для дроби обыкновенной. Например: 5404319552844595/18014398509481984 → [0; 3, 2, 1, 900719925474098, 2]. Функция так устроена, что её можно вызывать для нецелых аргументов: 0.3/1 → [0; 3, 2, 1, 900719925474098, 2].
ratio(x, relativeError) - возвращает самую "простую" обыкновенную дробь, которая в машинной арифметика близка к x. Для этого она строит непрерывную дробь, а из неё подходящие обыкновенные дроби. Например: 0.3 → [0; 3, 2, 1, 900719925474098, 2] →
| итерация | подходящая дробь | значение подходящей дроби |
|---|---|---|
| 1 | [0; ] | 0/1 = 0 |
| 2 | [0; 3] | 1/3 = 0.3333333333333333 |
| 3 | [0; 3, 2] | 2/7 = 0.2857142857142857 |
| 4 | [0; 3, 2, 1] | 3/10 = 0.3 |
| 5 | [0; 3, 2, 1, 900719925474098] | 2702159776422296/9007199254740987 = 0.3 |
| 6 | [0; 3, 2, 1, 900719925474098, 2] | 5404319552844595/18014398509481984 = 0.3 |
scaleToInts(a) приводит массив дробей к общему знаменателю и отбрасывает знаменатель. Например [1/1, 3/20, 1/10] → [20, 3, 2].
countDetails(n, k, m) считает детали. Все параметры целые, расчёт точный.
const binRatio = x => {
// n / d === x
let n = x;
let d = 1;
while (!Number.isInteger(n)) {
n *= 2;
d *= 2;
}
return [n, d];
};
const continuedFraction = (n, d) => {
const f = [];
while (d != 0) {
f.push(Math.floor(n / d));
[n, d] = [d, n % d];
}
return f;
};
const ratio = (x, relativeError) => {
const minX = x * (1 - relativeError);
const maxX = x * (1 + relativeError);
const f = continuedFraction(x, 1);
for (let i = 1; i <= f.length; ++i) {
let [n, d] = [1, 0];
for (let j = i - 1; j >= 0; --j) {
[n, d] = [f[j] * n + d, n];
}
const x_ = n / d;
if (minX <= x_ && x_ <= maxX) {
return [n, d];
}
}
return binRatio(x);
};
const gcd2 = (a, b) => (b === 0) ? a : gcd2(b, a % b);
const lcm = a => a.reduce((a, b) => a * (b / gcd2(a, b)));
const scaleToInts = a => {
const cd = lcm(a.map(([, d]) => d));
return a.map(([n, d]) => n * (cd / d));
};
const countDetails = (n, k, m) => {
let d = 0;
while (true) {
const dd = Math.floor(n / k) * Math.floor(k / m);
if (dd === 0) {
break;
}
d += dd;
n -= dd * m;
}
return d;
};
(() => {
const rl = require('readline').createInterface({input: process.stdin});
rl.on('line', line => {
const floats = line.trim().split(' ').map(x => parseFloat(x));
const relations = floats.map(x => x / floats[0]);
const fractions = relations.map(x => ratio(x, 2 * Number.EPSILON));
const integers = scaleToInts(fractions);
console.log(countDetails(...integers));
});
})();
$ echo 2 0.3 0.2 | node countDetails.js 9 $ echo 100 0.3 0.2 | node countDetails.js 499 $ echo 1.4142135623730951 0.14142135623730953 0.014142135623730952 | node countDetails.js 100