Run Do...While Calculations Until Condition Is Met

user_15192669 0
Viewed 132

I am writing a simple do...while statement using Javascript that's meant to look at the length of a decimal of a given input num and if the length of the decimal is greater than or equals to 1, to take the num and added it onto itself until the decimal length is equal to 0. Currently, it works for decimals with the length of 1, but anything greater, it stops.

The expected output, for example, when num is 8.75, should be 35, not 17.5.

The series should take 4 steps to reach 35.

8.75

17.5

26.25

35

Here's my code:

const num = 8.75;
var decimalLength = num.toString().split(".")[1].length;
let result = "";
let i = num;

do {
  i = i + num;
  result = result + num;
  newLength = decimalLength;
} while (newLength < 0);

console.log(i);
do-while conditional-statements javascript
4 Answers

You can use some fancy maths to get a more definitive answer that doesn't loop over and over again:

const num = 8.75;
var decimal = num % 1 //Decimal part
var decimalPlaces = num.toString().split(".")[1] ?.length || 0; //Get decimal places

//GCD function
const gcd = (x, y) => (!y ? x : gcd(y, x % y));

//GCD between decimal and 1, need to make it whole number to get multiplier, so multiply each with 10^[decimal places]
//Get what's remaining when divided by 10^[decimal places] as well, to see what to multiply by to get whole number
var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * 10 ** decimalPlaces)

//Use log change of base property to get value in power of 2
var outputExponent = Math.log(multiplier) / Math.log(2)
//Multiply number by multiplier
var outputValue = num * multiplier

console.log(outputExponent) //Power of 2 to multiply by to get whole number
console.log(outputValue) //The whole number itself

user_142657490

This version uses a recursive function and a tolerance to deal with floating point rounding errors.

const firstIntMultiple = (n, tol=1e-6, c = 1) =>
  Math.abs(n * c - Math.floor(n * c)) < tol ? n * c : firstIntMultiple (n, tol, c + 1)

console .log (firstIntMultiple (8.75))               //  35/4
console .log (firstIntMultiple (8.333333333333334))  //  25/3
console .log (firstIntMultiple (14.058823529411764)) //  239/17

It finds the correct version by multiplication by successive integers instead of successive additions, but it's the same idea.

We can easily replace the recursive version by an iterative approach, which might be useful for numbers which don't have a good rational approximation. (Right now, passing Math.PI will run into recursion limits.)

That might look like this:

const firstIntMultiple = (n, tol=1e-6) => {
  let c = 1;
  while (Math.abs(n * c - Math.floor(n * c)) > tol) {
    c += 1
  }
  return n * c
}

and for Math.PI, that would return 4272943.0000005495, the first multiple of pi that is within 1e-6 of an integer. And you can adjust the tolerance as needed.

Update -- an entirely different technique

Another technique would take advantage of the fact that continued fractions offer a straightforward way to find the best rational approximations to a number. We can use this to find the ten best rational approximations to pi, for instance like this:

bestApprox (Math.PI, 1, 10) .map (({n, d}) => `${n}/${d}`)
// => ["3/1", "22/7", "333/106", "355/113", "103993/33102", "104348/33215", 
//     "208341/66317", "312689/99532", "833719/265381", "1146408/364913"]

And then, using those approximations, we can find the first one that is within some small distance from our target value.

The code might look like this:

const contFrac = (n, d = 1, count = Infinity) =>
  count < 1 || d == 0
    ? []
    : [Math .floor (n / d)] .concat (contFrac (d, n % d, count - 1))

const bestApprox = (n, d = 1, c) =>
  contFrac(n, d, c)
    .reduce ((a, n, i) => [
      ...a, 
      {
        n: a [i] .n + n * a [i + 1] .n, 
        d: a [i] .d + n * a [i + 1] .d
      }
    ], [{n: 0, d: 1}, {n: 1, d: 0}])
    .slice (2)

const firstIntMultiple = (x, ε = 1e-6) => 
  bestApprox (x, 1) 
    .find (({n, d}, i, a) => i == a.length - 1 || Math.abs (n / d - x) < ε) 
    .n


console .log (firstIntMultiple (8.75))               //  35/4
console .log (firstIntMultiple (8.333333333333334))  //  25/3
console .log (firstIntMultiple (14.058823529411764)) //  239/17
console .log (firstIntMultiple (Math.PI))            //  353/113
console .log (firstIntMultiple (Math.PI, 1e-8))      //  103993/33102

I haven't tested for performance, but this should be reasonably good, especially for those number whose continued fractions contain large integers early. (pi for instance is <3; 7, 15, 1, 292,...> That 292 implies that 3 + (1 / (7 + (1 / (15 + 1 / 1)))) or 355 / 113 is an excellent approximation to pi, and in fact, it's good to six decimal places.

I don't know how helpful this is to the OP, but it shows that ancient math classes might one day come in handy!. ;-)

Update 2 - Now With More Explanation!

This version cleans up the issue in the second approach with small values, by checking not if the test value is within epsilon of the original value but if the ratio of the the test value to the original value is within epsilon of 1. It also has some minor clean-up and a smaller value for the default epsilon:

const contFrac = (n, d = 1, count = Infinity) =>
  count < 1 || d == 0
    ? []
    : [Math .floor (n / d)] .concat (contFrac (d, n % d, count - 1))

const bestApprox = (n, d = 1, count = Infinity) =>
  contFrac(n, d, count)
    .reduce ((a, n, i) => [
      ...a, 
      {
        n: a [i] .n + n * a [i + 1] .n, 
        d: a [i] .d + n * a [i + 1] .d
      }
    ], [{n: 0, d: 1}, {n: 1, d: 0}])
    .slice (2)

const isClose = (x, y, ε) =>
  y == 0 ? x < ε : (x / y > 1 - ε && x / y < 1 + ε)

const firstIntMultiple = (x, ε = 1e-8) => 
  bestApprox (x, 1) 
    .find (({n, d}, i, a) => i == a.length - 1 || isClose (n / d, x, ε)) 
    .n


console .log (firstIntMultiple (8.75))               //  35/4
console .log (firstIntMultiple (8.333333333333334))  //  25/3
console .log (firstIntMultiple (14.058823529411764)) //  239/17
console .log (firstIntMultiple (Math.PI))            //  103993/33102
console .log (firstIntMultiple (Math.PI, 1e-6))      //  353/113
console .log (firstIntMultiple (13.000000221))       //  58823532/4524887
console .log (firstIntMultiple (1.0000003333))       //  3000301/3000300
console .log (firstIntMultiple (1234/987654321))     //  6/4802209
.as-console-wrapper {min-height: 100% !important; top: 0}

Explanation

The main function here is still firstIntMultiple, and it's fairly simple, just searching the results of bestApprox for a rational approximation that is close enough to our target number and then returning the numerator of that result. "Close enough" is determined by isClose, which checks if the ratio of the two numbers is between 1 - ε and 1 + ε, where ε is an optional parameter that defaults to 1e-8.

So the question is how bestApprox works. For that, we need to discuss Continued Fractions. I cannot do them justice here, but hopefully I can describe enough to give a feel for them.

Here is a repeating infinite simple continued fraction:

                    1
1 + ---------------------------------
                      1
     2 + ----------------------------
                        1
          2 + ---------------------
                          1
                2 + ---------------
                            1
                      2 + ---------
                                 
                            2 + ...

It's a continued fraction because we keep nesting fractions in the denominators of other fractions. It's infinite because... well because it continues on infinitely - in an obvious manner. It's simple because all the numerators are 1s.

It's not hard to show with a little algebra that this represents the square root of 2.

This will usually be abbreviated with a notation like:

<1; 2, 2, 2, 2, ...>

where all the values are integers, and after the first one, all are positive.

These have a few advantages. All rational numbers have a finite representation as a continued fraction, and all quadratic numbers have a repeating infinite pattern. But more importantly, the prefixes of these continued fractions contain the best rational approximations to a number. (The proof is not terribly difficult, and should be something non-mathematicians can follow. But I won't try it here.)

By this, I mean that these numbers:

<1;>            //=> 1
<1; 2>          //=> 3/2
<1; 2, 2>       //=> 7/5
<1; 2, 2, 2>    //=> 17/12
<1; 2, 2, 2, 2> //=> 41/29
...

Are successively better approximations to sqrt(2), and there are no better approximations available except with higher denominators. That is, for example, among denominators greater than 12 and less than 29, there are not better approximations to sqrt(2).

So by calculating the partial continued fraction for a number, we can find all the best approximations, and eventually find one that gets the multiple we're looking for.

Now we need to know how to calculate these continued fractions and then how to turn them their partials into rational numbers. Luckily, both are pretty easy.

To find the elements of a continued fraction, all we need to do is find the floor of the number, add that to our list, then continue with the reciprocal of the remainder.

If we started with 27/11, then the first element would be floor(27/11) or 2; the remainder is 5/11, which has the reciprocal of 11/5, The next digit would be the floor of that, which is 2, with a remainder of 1/5, whose reciprocal is 5 with no remainder. And so 27/11 can be written as <2; 2, 5>.

If we started with pi, then our first element would be 3, then we'd continue with the reciprocal of 0.14159265358979312, which is 7.062513305931052, and the next element would be 7. Taking the reciprocal of the remainder, we get 15.996594406684103, and the next element is 15. The reciprocal of that remainder is 1.0034172310150002, so the next element is 1. Then the reciprocal of the remainder gets much larger, at 292.63459087501246. We could continue to get a result like:

<3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 3, 3, 2, 1, ...>

which has no obvious pattern. But the high value of 292 tells us that <3; 7, 15, 1>, or 355/113 is an excellent approximation for pi.

The function contFrac does this algorithm just as described.

Now, to turn the partials into rational numbers, we can use a simple recursion. In <a_0; a_1, a_2, a_3, ...>, the first approximation is a_0, which we write as a_0/1. The second one is a_0 + (1 / a_1) or (a_0 * a_1) / a_1. After that, we can find the (k + 2)nd value by this simple formulas: n_(k + 2) = a_(k + 2) * n_(k + 1) + n_k, and d_(k + 2) = a_(k + 2) * d_(k + 1) + d_k.

So for <3; 7, 15, 1>, we start with 3/1 then 22/7, then our next value is (15 * 22 + 3) / (15 * 7 + 1) or 333/106, and then (1 * 333 + 22) / (1 * 106 + 7) or 355/113. The code uses a little trick which extends the numerators and denominators back two steps so that we can use our recursion for every step and then simply slices those two value off the final result.

And there we have it. By using the best rational approximations to a number, we can quickly find the smallest integer which, within a small tolerance, is a multiple of that number.

user_12436410

Here's every answer combined. The advantage of this is that it has a 'fallback' for each kind of input. If there's a terminating decimal, Endothermic_Dragon's first method is sufficient. If it is a repeating decimal, then a new method that finds an answer definitively is sufficient. If it is not sufficient, then the continued fraction is used as a fallback.

Note that the only reason I included the continued fraction last is because of the errors it sometimes causes with smaller decimals. I would just 'fix' the method, but I don't understand how it works, so I used it as a fallback.

//At the top so it is viewable
console.log(findMultiple(54.46333333333333)) //16339/300
console.log(findMultiple(8.333333333333333)) //25/3
console.log(findMultiple(14.05882352941176)) //Irrational
console.log(findMultiple(94.03820382038203)) //Irrational
console.log(findMultiple(623.0549383482724)) //1009349/1620
console.log(findMultiple(Math.PI)) //Irrational
console.log(findMultiple(13.000000221)) //1829587379722249/140737488355328
console.log(findMultiple(1.0000003333)) //1125900282105063/1125899906842624

//Main control
function findMultiple(num, interpretLiteral = false, epsilon = 1e-6) {
  if (num.toString().length < 17 || num % 1 == 0 || interpretLiteral) {
    return EndothermicDragonFirstMethod(num) //Terminating decimal
  }
  var checkRepeatingNum = CheckRepeating(num)
  if (checkRepeatingNum != false) {
    return Math.round(EndothermicDragonSecondMethod(num, checkRepeatingNum) * num) //Repeating decimal
  } else {
    return ScottSauyetFirstMethod(num, epsilon) //Continued fraction
  }
}


//Predifined functions

//GCD
function gcd(x, y){return !y ? x : gcd(y, x % y)};

//Check if digits repeat, if they do, return repeat period
function CheckRepeating(num) {
  var totalSearchLength = (num % 1).toString().split('.')[1].slice(0, -1).length
  var numTemp1 = (num % 1).toString().split('.')[1].slice(0, -1).split('').reverse().join('')
  for (var i = 1; i < Math.floor(totalSearchLength / 3); i++) {
    var numTemp2 = numTemp1.slice(0, 3 * i)
    var searchLength = i
    bool = numTemp2.slice(0, searchLength) == numTemp2.slice(searchLength, 2 * searchLength) && numTemp2.slice(0, searchLength) == numTemp2.slice(2 * searchLength, 3 * searchLength)
    if (bool) {
      return searchLength
    }
  }
  return false
}

//Terminating decimal
function EndothermicDragonFirstMethod(num) {
  var decimal = num % 1;
  var decimalPlaces = num.toString().split(".")[1]?.length || 0;
  var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * (10 ** decimalPlaces));
  return num * multiplier;
}

//Repeating decimal
function EndothermicDragonSecondMethod(num, repeatInterval) {
  var numArray = num.toString().split('.')[1].slice(-repeatInterval).split('').reverse()
  var restOfNum = num.toString().split('.')[1].slice(0, -repeatInterval * 3).split('').reverse()
  var counter = 0;
  var extraRepeat = 0;
  restOfNum.every(el => {
    if (el == numArray[counter]) {
      extraRepeat++;
      counter++;
      if (counter == numArray.length) {
        counter = 0
      }
      return true
    }
    return false
  })
  var repeatingPart = num.toString().split('.')[1].slice(-repeatInterval * 3 - extraRepeat, -repeatInterval * 2 - extraRepeat)
  var notRepeatingPart = num.toString().split('.')[1].slice(0, -repeatInterval * 3 - extraRepeat)
  var numerator = (parseInt(notRepeatingPart) * (parseInt("9".repeat(repeatingPart.length)))) + parseInt(repeatingPart)
  var denominator = (parseInt("9".repeat(repeatingPart.length)) * (10 ** notRepeatingPart.length))
  return denominator / gcd(numerator, denominator)
}

//Otherwise (irrational numbers or other)
function ScottSauyetFirstMethod(num, epsilon = 1e-6) {

  const contFrac = (n, d = 1, count = Infinity) =>
    count < 1 || d == 0 ? [] : [Math.floor(n / d)].concat(contFrac(d, n % d, count - 1))

  const bestApprox = (n, d = 1, c) =>
    contFrac(n, d, c)
    .reduce((a, n, i) => [
      ...a,
      {
        n: a[i].n + n * a[i + 1].n,
        d: a[i].d + n * a[i + 1].d
      }
    ], [{
      n: 0,
      d: 1
    }, {
      n: 1,
      d: 0
    }])
    .slice(2)

  const firstIntMultiple = (x, epsilon) =>
    bestApprox(x, 1)
    .find(({
      n,
      d
    }, i, a) => i == a.length - 1 || Math.abs(n / d - x) < epsilon)
    .n

  return firstIntMultiple(num, epsilon)
}

This results in accurate answers, no matter what in the world in the input is (even if it is a small decimal)!

user_142657490

Two competing answers. Which is the better one? There is no way of knowing until you test it out. So, that's what this new answer attempts to do.

These 'tests' (if you will) run each function 50 times, timing each iteration before clearing the console and logging the times' average.

8 Decimal Precision

Endothermic_Dragon:

const num = 3.14159265;


//Function start
const firstIntMultiple = () => {
  var decimal = num % 1;
  var decimalPlaces = num.toString().split(".")[1] ?.length || 0;
  const gcd = (x, y) => (!y ? x : gcd(y, x % y));
  var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * (10 ** decimalPlaces));
  return num * multiplier;
}
//Function end


var times = []

for (var i = 0; i < 50; i++) {
  var startTime = new Date()
  console.log(firstIntMultiple().toString())
  times.push((new Date() - startTime) / 1000)
}

console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")

Scott Sauyet:

const num = 3.14159265;


//Function start
const firstIntMultiple = (tol = 1e-8) => {
  let c = 1;
  while (Math.abs(num * c - Math.floor(num * c)) > tol) {
    c += 1
  }
  return num * c
}
//Function end


var times = []
for (var i = 0; i < 50; i++) {
  var startTime = new Date()
  console.log(firstIntMultiple().toString())
  times.push((new Date() - startTime) / 1000)
}

console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")

10 Decimal Precision

Endothermic_Dragon:

const num = 3.1415926535;


//Function start
const firstIntMultiple = () => {
  var decimal = num % 1;
  var decimalPlaces = num.toString().split(".")[1] ?.length || 0;
  const gcd = (x, y) => (!y ? x : gcd(y, x % y));
  var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * (10 ** decimalPlaces));
  return num * multiplier;
}
//Function end


var times = []

for (var i = 0; i < 50; i++) {
  var startTime = new Date()
  console.log(firstIntMultiple().toString())
  times.push((new Date() - startTime) / 1000)
}

console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")

Scott Sauyet:

const num = 3.1415926535;


//Function start
const firstIntMultiple = (tol = 1e-10) => {
  let c = 1;
  while (Math.abs(num * c - Math.floor(num * c)) > tol) {
    c += 1
  }
  return num * c
}
//Function end


var times = []
for (var i = 0; i < 50; i++) {
  var startTime = new Date()
  console.log(firstIntMultiple().toString())
  times.push((new Date() - startTime) / 1000)
}

console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")

Note that the functions will return slightly different results, due to slight differences in their inner mechanics. Endothermic_Dragon's answer tries to find the multiple which will return an exact whole number, whereas Scott Sauyet's answer attempts to find the multiplier which makes the number within the specified tolerance of a whole number.

These examples can be further scaled by adding more digits of pi on each and reducing the tolerance on Scott Sauyet's answer.

I was initially going to use decimal.js while testing this (https://mikemcl.github.io/decimal.js/), however, it turned out to be quite slow on Scott's method - it took 5.1243 seconds to calculate each iteration, whereas on Endothermic_Dragon's it took 0.0002 seconds each iteration. Note that this was done with 10 iterations on w3schools.

All of this analysis can show two conclusions:

  1. Endothermic_Dragon's answer is scalable and accurate on terminating decimals.
  2. Scott Sauyet's answer consumes some time but produces an accurate answer. This is especially useful when dealing with decimals that do not terminate, whether they are irrational or repeating.

Also, here's an extra test, because why not.

15 Decimal Precision

Endothermic_Dragon:

const num = 3.141592653589793;


//Function start
const firstIntMultiple = () => {
  var decimal = num % 1;
  var decimalPlaces = num.toString().split(".")[1] ?.length || 0;
  const gcd = (x, y) => (!y ? x : gcd(y, x % y));
  var multiplier = 10 ** decimalPlaces / gcd(10 ** decimalPlaces, decimal * (10 ** decimalPlaces));
  return num * multiplier;
}
//Function end


var times = []

for (var i = 0; i < 50; i++) {
  var startTime = new Date()
  console.log(firstIntMultiple().toString())
  times.push((new Date() - startTime) / 1000)
}

console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")

Scott Sauyet:

const num = 3.141592653589793;


//Function start
const firstIntMultiple = (tol = 1e-15) => {
  let c = 1;
  while (Math.abs(num * c - Math.floor(num * c)) > tol) {
    c += 1
  }
  return num * c
}
//Function end


var times = []
for (var i = 0; i < 50; i++) {
  var startTime = new Date()
  console.log(firstIntMultiple().toString())
  times.push((new Date() - startTime) / 1000)
}

console.clear()
console.log((times.reduce((a, b) => a + b, 0) / times.length) + " seconds on average")

user_142657490
Related