1
$\begingroup$

Suppose we have to do an intense calculation, like calculating $a^b$ for large $a$ and $b$. Then, instead of multiplying $a$ by itself $b$ times, could we just do some shortcut method with $a$ and $b$ which gives us the units digit of $a^{b}$, then another algorithm which gives the tens digit and hence, could we find the answer digit-by-digit?

I mean, could we have a function $f$ or any algorithm which takes three inputs: $a$, $b$, and $n$, such that $f(a,b,n)$ gives us the $n^{th}$ digit of $a^b$?

Similarly, could we have another algorithm, which takes inputs $a$ and $n$ and gives us the $n^{th}$ digit of $a!$, i.e. calculating factorials digit-wise?

Maybe, it's like a divisibility test where you have an algorithm to check whether $a$ is divisible by $b$ without actually dividing $a$ by $b$. Maybe, binary could be of some help in digit-wise calculation, because in binary, all the digits can have only two possible values.

$\endgroup$
3
  • $\begingroup$ Divisibility tests work easily because you get to throw away almost all the information in the original number. You can do all kinds of fiddling with the input digits before you apply the divisibility algorithm and still be sure to get the right answer. Raising a number to a high power gives you lots of digits every single one of which must be exactly so. That's much harder. $\endgroup$
    – David K
    Commented Mar 14, 2017 at 6:31
  • $\begingroup$ Sounds like you want to calculate the nth digit in poly log n time. You might want to look into a spigot algorithm. $\endgroup$
    – DanielV
    Commented Mar 14, 2017 at 6:52
  • $\begingroup$ $n! \pmod p$ is a really hard problem, I've search around for an answer but it seems no one has any clue on it. On the other hand, $${a \choose b} \pmod p$$ is solved quite nicely. $\endgroup$
    – DanielV
    Commented Mar 14, 2017 at 17:23

2 Answers 2

Reset to default
0
$\begingroup$

If $a$ is coprime to $10$, then $a^n \mod 10^k$ is periodic in $n$ with period dividing $\varphi(10^k) = 4 \times 10^{k-1}$. Thus the lowest $k$ decimal digits of $a^n$ are the same as those of $a^m$ where $n \equiv m \mod 4 \times 10^{k-1}$. For example, since $21 \equiv 1 \mod 4$, the lowest digit of $7^{21}$ is the same as that of $7^1$, namely $7$.

In the case of $7$, it turns out that the order of $7 \mod 1000$ is actually $20$, so the lowest three digits of $7^{21}$ are the same as those of $7^1$, namely $007$.

$\endgroup$
2
  • $\begingroup$ That looks good but that wasn't my main question. I already know that we can work out the lower digits by observing periodicity of lower digits. $\endgroup$
    – user402662
    Commented Mar 14, 2017 at 6:53
  • $\begingroup$ I think I should edit my question. $\endgroup$
    – user402662
    Commented Mar 14, 2017 at 6:55
0
$\begingroup$

I don't think that this is possible in general. But in some special cases we are lucky as in the following spectacular representation of $\pi$ (i.e. $a^b$ with $a=\pi$ and $b=1$) found by Bailey, Borwein and Plouffe in 1997. They got

\begin{align*} \pi=\sum_{n=0}^\infty\frac{1}{16^n}\left(\frac{4}{8n+1}-\frac{2}{8n+4}-\frac{1}{8n+5}-\frac{1}{8n+6}\right) \end{align*}

This rather simple formula was of particular interest to the three mathematicians due to the factor $\frac{1}{16^n}$ in the general term, as a factor of an arithmetically very simple function of $n$.

They were able to extract from this an algorithm (named BBP) to calculate the $d$-th digit of the expansion of $\pi$ individually in base $16$, and this even for very large $d$, without needing to know or calculate the digits preceding $d$. For example, the $10^{12}$th digit of $\pi$ in base $2$ is $1$.

$\endgroup$

You must log in to answer this question.