1

Of course i know that there is a good pow() function in cmath(math.h), but not touching the background of the pow() what is the fastest way to power numbers with my own hands?

korzck
  • 198
  • 9
  • 2
    power value is integer or real number? – Marek R Sep 26 '21 at 19:54
  • @MarekR power value should be also a real number :) – korzck Sep 26 '21 at 19:55
  • 1
    you can start from `pow(a, b) = exp(b * log(a))` – Dmitry Bychenko Sep 26 '21 at 19:56
  • 1
    You should benchmark the `pow` function as a baseline. You can then compare this baseline with your attempts. Next, ask yourself whether using library functions are worth rewriting. – Thomas Matthews Sep 26 '21 at 19:58
  • 1
    If you can't use built-ins, then decomposing the exponent into powers of 2 is a good way. E.g 7->1 + 2 + 4, you generate `x2 = x*x`, `x4 = x2*x2` and then get `x7 = x*x2*x4`. I think there is a more effective way (still leveraging this I think). Now if you can get `sqrt` then this could be expanded to deal with floating point numbers though. Also you would usually have `sqrt` if you are on `x86`, because it is an instruction on the cpu, which you will not outperform I think. – Lala5th Sep 26 '21 at 19:58
  • @Lala5th yeah, that sounds good. But isn't it allows to power only to the integer power number? – korzck Sep 26 '21 at 20:02
  • @korzck Technically it can't do it with real numbers, but it does work with fractions, which is the best that the computer can actually store. If you have 7/16 for example you have to do some `sqrt`, but in the end the same should work fine. Now whether this is efficient on fractions is a very good question, but I would wager that it is not. You are probably better off doing some bit level magic with the specification of the double – Lala5th Sep 26 '21 at 20:07
  • fwiw, there are no real numbers on computers, `double` and `float` are quite rational (only `inf` and `-inf` arent) – 463035818_is_not_an_ai Sep 26 '21 at 20:44
  • 1
    [Gordon, 1998 Survey](https://www.sciencedirect.com/science/article/abs/pii/S0196677497909135), [Möller, 2003 Improved](https://link.springer.com/chapter/10.1007/3-540-36552-4_21), [Rahim et al, 2017 Prime](https://iopscience.iop.org/article/10.1088/1742-6596/930/1/012032/meta)? It depends on your use case. – Neil Sep 26 '21 at 21:20
  • 1
    @Lala5th *"Technically it can't do it with real numbers, but it does work with fractions,"* -- Technically, fractions *are* real numbers. You probably meant "irrational" instead of "real". (Or perhaps you meant "can't do it with **all** real numbers"?) – JaMiT Sep 26 '21 at 23:17
  • @JaMiT Of course they are, but so are integers. In this case "all" is clearly implied. If an algorithm works on real numbers, that implies that it works on the widest definition of that set not just some subset – Lala5th Sep 26 '21 at 23:27
  • @Lala5th *"In this case 'all' is clearly implied."* -- No, it is not. Another quite reasonable interpretation is "any", i.e. that no real numbers work. *"If an algorithm works on real numbers"* -- this is irrelevant, as your statement was that an algorithm does **not** work on real numbers. When you have a negation in play, there is a significant difference between "all real numbers" and "any real number". – JaMiT Sep 26 '21 at 23:48
  • @Lala5th For example, if we disallow imaginary numbers, consider the following two statements: *"Square roots cannot be done with negative numbers"* and *"Square roots cannot be done with real numbers"*. Which do you agree with? The latter follows the pattern of your earlier statement, in that square roots cannot be done with all real numbers, even though they can be done with some. – JaMiT Sep 26 '21 at 23:55
  • Back to the topic, the fastest wy is to use the floating-point hardware, which is exactly what `pow()` already does after taking care of the corner cases, using the formula provided by @DmitryBychenko – user207421 Sep 27 '21 at 00:15
  • see [Power by squaring for negative exponents](https://stackoverflow.com/a/30962495/2521214) and all sublinks in there. Fastest method depends on what case you have (range, form and datatype of base,exponent and result) and also on the HW used to compute. – Spektre Sep 27 '21 at 06:16

1 Answers1

2

You are asking two different questions:

  • What is the fastest way to power real numbers?
  • What is the fastest way to power numbers with my own hands?

These have different answers.

pow is fast. Standard library implementations are generally written by very smart people, reviewed by other smart people, and then refactored by even smarter people. Because of this, using a provided standard library implementation is almost always better than trying to re-implement the standard library yourself.

But, if you insist on creating your own implementation of pow, you should first implement exp and log using their Taylor series expansions. Then use the following property:

pow(base,power) = exp( power * log(base) )

Note that if base is negative, you should first compute pow(-base,power), then do a parity check on base to determine the sign of the result.

Aaron Stanek
  • 408
  • 2
  • 9