3
$\begingroup$

My question is related to Calculating logs and fractional exponents by hand, but despite that question's title, all answers there focus on logarithms. I am interested in fractional exponents alone.

The programming language I am working with doesn't support floating-point numbers (i.e. fractional numbers). To work around this, I am emulating fractions via fixed-point representation with 18 decimals (the language can go as high as $2^{256} - 1$). For example, I would write $\pi$ as $3141592653589793238$.

I need to calculate the exponential function when the exponent is a fractional number, but I can only use:

  • Basic arithmetic operations like addition, subtraction, multiplication and division (note: division rounds down, no fractional part allowed)
  • The exponentiation function (**) but only if the exponent is a whole number

The language doesn't support roots or other advanced functions natively.

Is there any mathematical trick that I can use to accurately estimate fractional exponents?

$\endgroup$
2
  • $\begingroup$ There may be a much better way to do this, but my first thought would be to do $x^a = e^{x\ln a}$, since you already have access to a good way to do logs and $e^x$ isn't too bad. Does that work for your purposes? $\endgroup$
    – Stephen Donovan
    Commented Apr 3, 2021 at 10:06
  • $\begingroup$ Indeed, I have already implemented logs. Interesting idea with $e^{x*ln(a)}$, I'll see whether I can do something with it .. $\endgroup$
    – Paul Razvan Berg
    Commented Apr 3, 2021 at 10:18

1 Answer 1

Reset to default
4
$\begingroup$

You can handle the exponents as

$$x^{p/q}=\sqrt[q]{x^p}.$$

The powers $x^p$ aren't so problematic, though for large values you may have to truncate and use a form of floating-point. So your question amounts to taking $q^{\text{th}}$ roots. Several approaches are possible:

  • solve $y^q=x^p$ by dichotomic search. You'll need to compute the $q^{\text{th}}$ powers of several $y$ candidates. For the starting bracketing of $y$, you can try successive doublings ($y=1,y=2,y=4,\cdots$) until $y^q$ exceeds $x^p$.

  • solve $y^q=x^p$ by Newton's iterations,

$$y_{n+1}=\frac{(q-1)y_n^q+x^p}{qy_n^{q-1}}.$$

  • use the old decimal method where you start with the $q$ leftmost digits, find the $q^{\text{th}}$ root of that number (by trial and error), then append the next digit and find the new $q^{\text{th}}$ root... You will need the expansion

$$(10m+d)^q=\sum_{k=0}^q\binom qk10^km^kd^{q-k}.$$

Alternatively, write the fraction in binary, $$\frac pq\simeq\sum_{i=0}^lb_i2^{-i}.$$ Then use a square root algorithm to compute the powers $x^{2^{-i}}$ iteratively. Finally, take the product of the powers where the bit is $1$.

$\endgroup$
1
  • $\begingroup$ Unfortunately, I can't do any of the first three approaches, because $q$ may be as large as $1e18$ and $y^q$ would overflow the maximum value allowed by the programming language. But I can work with the last approach, i.e. write the fraction in binary. I learned a lot by pondering your suggestions, thank you very much. $\endgroup$
    – Paul Razvan Berg
    Commented Apr 3, 2021 at 12:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .