3
$\begingroup$

Let us have positive irrational numbers $a$ and $b$ represented by functions $f_a,f_b\colon\mathbb{N}\to\mathbb{N}$ respectively such that $f_a(0)=\left \lfloor{a}\right \rfloor$ and $f_a(i)$, $i>0$ is the ith digit of $a$, and similarly for $b$.

Is there some "standard" way to compute $f_{a^b}$ from $f_a$ and $f_b$? I would like to compute the some digits of $a^b$ and I'm convinced there are algorithms for this but I can't find any.

Improve this question
$\endgroup$
5
  • $\begingroup$ How would you do this for rational numbers given via digit-functions? $\endgroup$
    – adrianN
    Commented Oct 30, 2015 at 8:19
  • $\begingroup$ @adrianN I never thought about that. I guess we could treat given numbers as rational (approximations) by setting $f_a(i)=0$ starting from some $i$ and continue from there. $\endgroup$
    – user39297
    Commented Oct 30, 2015 at 9:20
  • $\begingroup$ If we used rationals here, would there be some algorithm off the shelf to deploy? $\endgroup$
    – user39297
    Commented Oct 30, 2015 at 9:21
  • 1
    $\begingroup$ You have to somehow be able to take the root of a number given its digit sequence. That seems rather difficult to me. Especially since it has to work if you only look at some constant number of digits at a time if you want to generalize it to irrationals. $\endgroup$
    – adrianN
    Commented Oct 30, 2015 at 10:06
  • 1
    $\begingroup$ See also this older MO question: mathoverflow.net/questions/13166/… $\endgroup$
    – François G. Dorais
    Commented Nov 6, 2015 at 20:27

2 Answers 2

Reset to default
8
$\begingroup$

I do not think there is an algorithm (or you have to change something to allow algorithms that never end with some data). Consider the two numbers $$a=(3/2)^\sqrt{2}=1.77431468418218794421950\dots\quad b=\frac{1}{\sqrt{2}}=0.70710678118654752440084436210\dots$$ We have $$a^b=\frac{3}{2}=1.5$$ Then slightly changing $a$ or $b$ will make the second digit after the decimal point equal to $9$ or to $0$. Therefore we need to know all the digits of $a$ or $b$ to determine this second digit.
If the given numbers are $a$ and $b$ you will need to test all its digit to determine this second digit.

Of course it is an issue. Since your data $f_a$ and $f_b$ are infinite, I assume that they act as oracles, i.e. your algorithm at any moment can ask for the value of $f_a(i)$ or $f_b(i)$. Assume that you give the above numbers and your program stop giving a value $0$ or $9$ for the second digit. Since your algorithm has stopped at a finite time he would have ask only for a finite number of values of $f_a(i)$ and $f_b(i)$. Meaning that this algorithm will give the same answer for any irrational with these values in common. But it is clear that there are other irrational numbers sharing these digits and for which the correct value is just the opposite your program gives. And also this value will not be equivalent because it will be a number not ending in all "0" or all "9".

So any algorithm will give wrong answers for some numbers.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Note that this speaks to what a terrible representation of numbers decimal expansions are, for computability purposes - in particular, many natural problems that feel like they should be easy are actually undecidable in decimal representations because they essentially come down to trying to answer the (hard) question 'is $a\gt b$?'. $\endgroup$
    – Steven Stadnicki
    Commented Nov 5, 2015 at 23:26
  • $\begingroup$ I am not sure if this is an issue. We have that $1.4999...=1.5$. We may have either of the representations in this case. $\endgroup$
    – user39297
    Commented Nov 6, 2015 at 0:29
  • 1
    $\begingroup$ @StevenStadnicki Of course any other representation is just as bad. Any nontrivial partition of $[0,1]$ into finitely many sets will have points on the boundary (because $[0,1]$ is connected), and if you only know an approximation of a number which happens to be on the boundary you can't tell which set it's in. $\endgroup$
    – Robert Israel
    Commented Nov 6, 2015 at 20:47
  • $\begingroup$ @RobertIsrael, but the representation as a sequence of nested diminishing intervals used in comptability is better, no? $\endgroup$
    – usul
    Commented Nov 7, 2015 at 1:31
  • $\begingroup$ Ok, now I see the problem involved. Thanks for the clarification. It seems I need to rethink the relation between $a$, $b$ and $a^b$. My initial motivation was to classify irrational numbers with computational methods, but I guess I have to refine my approach. $\endgroup$
    – user39297
    Commented Nov 9, 2015 at 7:41
0
$\begingroup$

The "standard" method should be along the lines of "forming" an approximation of a and b from their digit representations, then computing exp(b* log(a)) using standard routines for approximations. You should look at routines used in scientific calculators (the relevant search terms escape my memory).

Something that might be of interest: decide on a low precision (say bits=16), and compute $a^b$ where each has so many bits to twice the precision, and a and b are numbers in (0,1). Then run a logic minimizer on the table to see if you can build a small Boolean circuit that computes this. It may be interesting to see how much you can speed up numeric computations with a (minimized for depth) logic circuit.

Gerhard "Make Computations Wider And Faster" Paseman, 2015.11.05

Improve this answer
$\endgroup$

You must log in to answer this question.