Как обойти двоичную погрешность 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 шт):

Автор решения: Leonid

По большому счету кг можно выразить в граммах, микрограммах, нанограммах. Тогда удастся избежать неточностей. Если максимальное число в 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);

→ Ссылка
Автор решения: Stanislav Volodarskiy

Проблема

Когда вы получили числа 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
→ Ссылка