I have a toy calculator I've been tasked to create for a class project. That's great - I have most of the normal calculator stuff done (order of operations, variables, precision settings, predefined functions). The issue is that, since I'm using rational arithmetic, there's no sin/cos function built-in, so I'll have to make my own.
And the issue with that is that sines are usually irrational, so I'll have to limit it to some precision or it'll run forever. I've successfully implemented the sine Maclaurin series in code. For reference, the relevant equation from the Wikipedia article is this:
$$\sin x = \sum_{n=0}^{\infty}{\frac{(-1)^n}{(2n + 1)!}x^{2n+1}} = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \frac{x^9}{9!} - \cdots$$
My program runs only until this condition is true:
$$\frac{x^i}{i!}<\frac{1}{10^p}$$
where $i = 2n + 1$ and $p$ is the desired precision in digits, but it gets very slow quite quickly (at least using a C++ interpreter, but I want it to run quickly there before I make it faster by compiling). There are some optimizations such as keeping the last numerator/denominator, but it's still not that fast.
Calculating the sine of $5\pi$ to 15 digits of precision (bad example, but it's to prove a point) using my program took 5 seconds across 34 iterations, since many later iterations end up multiplying integers greater than $1 \times 10^{900}$. $\pi$ has to be represented as a fraction, so there were very large integers involved.
I'm not sure where to ask for a better algorithm but here (or Stack Overflow, from which I've been banned for over a year, so that's not going to happen...). Even though I'm using rational arithmetic, I'm wondering if there's a more computationally efficient way to approximate a $\sin$ and $\cos$ to some amount of digits of precision. I know this isn't a programming site, but surely someone can help with the algorithm side? (preferably explained in plain English)
Note: I could offload the work onto some arbitrary-precision floating point library and then convert that back to a "rational", but that seems like cheating to me... it'll be more of a last resort.
No comments:
Post a Comment