2

Is it quicker to do:

const reciprocal = denominator => 1.0/denominator

Or

const reciprocal = denominator => Math.pow(denominator, -1) //or denominator**(-1)?

Or some other trick?

The denominator is a large (~1e50) integer (in fact it's a factorial) and I need to do lots of similar calculations (roughly 6e5 times).

AncientSwordRage
  • 7,086
  • 19
  • 90
  • 173
  • 1/x is certainly faster and more precise than a call to a function that approximate powers... But doing operations on such big numbers will likely lose precision ([see also](https://stackoverflow.com/questions/41072787/why-is-powint-int-so-slow)). – Déjà vu Feb 13 '22 at 13:52
  • @Déjàvu I sort of suspected the speed, but not the precision, of plain division. Not sure if there's any optimisation happening under the hood. If I absolutely have to, I can use Number.js but that might be overkill – AncientSwordRage Feb 13 '22 at 14:07
  • 1
    Even 1/3 will be inexact since the javascript Number is a binary floating point type. The *best* way to compute something is dependent on the entire computation and your goals. Numerical computations often require some restructuring to optimize them. Also, when doing many calculations it might be possible to use an amortized optimization e.g. if for some reason 1/a were unusually expensive but you have to do it for 5 different numbers a, b, c, d, and e then you might compute abcde, then 1/abcde, then multiply the reciprocal by the partial products to get 1/a, 1/b, 1/c, 1/d, and 1/e. – President James K. Polk Feb 13 '22 at 14:17
  • @PresidentJamesK.Polk it just so happens these large numbers are factorials – AncientSwordRage Feb 13 '22 at 14:34
  • If you can be more specific about the context we can give better advice. Changing the order of surrounding calculations can potentially improve things. – trincot Feb 13 '22 at 16:35
  • Usually, formulas written with factorials were written by mathematicians, not computer programmers. You can usually rewrite the formula to get rid of the factorial. Mathematicians use factorials because they are more convenient for proving things. They are terrible for calculating things, though. – Raymond Chen Feb 13 '22 at 16:39
  • @trincot I'm basically calculating the denominators of a Taylor Expansion series (up to term *n*) for factorials, as explained [here](https://math.stackexchange.com/a/4371621/20792), then multiplying all the polynomials together.... And after that, multiplying it all by *n!*. – AncientSwordRage Feb 13 '22 at 16:41
  • 1
    Be aware that floating point (IEEE 754 standard) can not represent 22! correctly, let be a factorial that is near 1e50. You need to simplify numerators and denominators first by eliminating common factors. Avoid actually calculating them in full. – trincot Feb 13 '22 at 16:43
  • @trincot that will be extremely tricky... In fact the reason I'm doing this via programming is because I can't think of how to simplify it – AncientSwordRage Feb 13 '22 at 16:46
  • 1
    Well, you don't have that many options: either you eliminate common factors to keep the size down to what floating point can handle, or you don't, but then you will lose precision, and should really go for some BigDecimal solution, which comes with a performance cost. Still, you might consider it, as you can base it on the native BigInt. See for ideas [this answer](https://stackoverflow.com/questions/16742578/bigdecimal-in-javascript/66939244#66939244). – trincot Feb 13 '22 at 16:50
  • Your [link](https://math.stackexchange.com/a/4371621/20792) is not a Taylor series. It's a combinatorial generating function. (You evaluate the function at `x`.) The actual formula you're calculating is `n!/(p!q!r!...)`. You can do this without factorials by alternating between factors in the numerator and denominator. This avoids having to deal with extremely large or extremely small numbers. – Raymond Chen Feb 13 '22 at 21:22
  • @raymondchen I've got to multiply a lot of polynomials first, how'm I going to do that without calculating the factorials? – AncientSwordRage Feb 13 '22 at 21:39
  • Can you describe your problem more clearly? "Multiplying polynomials" sounds like symbolic math, not calculations. – Raymond Chen Feb 13 '22 at 21:48
  • @ray the example in my question over there is simplified. I have too many things (~900) involved in the permutations, and I'm not picking *n* of them either (I'm picking fewer, let's call it *m*). The simplest way (that I've found) to calculate it instead is to multiply the polynomials (similar to the question I linked to you) and take the *mth* term, and multiply by *n!* you get the desired answer. – AncientSwordRage Feb 13 '22 at 22:04
  • Clear the denominators before you multiply. That will remove the need to divide by a factorial. – Raymond Chen Feb 13 '22 at 22:29
  • @raymondchen... Perhaps it's the late hour here, or I've misread that maths.se answer but the denominators are the factorials? If I had `6!*(1/0!+x/1!+x^2/2!+x^3/3!)*(1/0!+x/1!+x^2/2!+x^3/3!)*(1/0!+x/1!+x^2/2!+x^3/3!)*(1/0!+x/1!+x^2/2!+x^3/3!)*(1/0!+x/1!+x^2/2!+x^3/3!)` and 'cleared' the factorial I'd only get to multiple the polynomials by 6! once, which won't clear out all the denominators. Like `6×(1/3)×(1/3) = 2×(1/3) = (2/3)` not `(6×(1/3))*(6×(1/3))=2×2=4`... Right? Or am I going mad? – AncientSwordRage Feb 14 '22 at 00:40
  • You'd end up with: `6!*(1/0!+x/1!+x^2/2!+x^3/3!)*(1/0!+x/1!+x^2/2!+x^3/3!)*(1/0!+x/1!+x^2/2!+x^3/3!)*(1/0!+x/1!+x^2/2!+x^3/3!)*(1/0!+x/1!+x^2/2!+x^3/3!)`=`(6!*/0!+6!*x/1!+6*5*4*3*x^2+6*5*4*x^3)*(1/0!+x/1!+x^2/2!+x^3/3!)*(1/0!+x/1!+x^2/2!+x^3/3!)*(1/0!+x/1!+x^2/2!+x^3/3!)*(1/0!+x/1!+x^2/2!+x^3/3!)` – AncientSwordRage Feb 14 '22 at 00:43
  • If you multiply by (3!)^5 then that would clear all the denominators. But if you have 900 of these polynomials, then clearing the denominator would create integers that are too large for Number. It may be that the numbers involved are simply too big for double-precision floating point. – Raymond Chen Feb 14 '22 at 04:31
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/241995/discussion-between-ancientswordrage-and-raymond-chen). – AncientSwordRage Feb 14 '22 at 07:56
  • and what was said in the chat ? I wish to compute period length of primes reciprocal, so it's interesting to know what did you talked about :) – Ch'nycos Jun 16 '22 at 12:32
  • @Ch'nycos nothing else from what I remember – AncientSwordRage Jun 16 '22 at 13:59

0 Answers0