5 ms·
The GitHub repo contains more details on how the algorithm works: https://github.com/AnonGit90210/RamanujanMachine https://github.com/AnonGit90210/RamanujanMach
by magnio 6y ago
The GitHub repo contains more details on how the algorithm works: https://github.com/AnonGit90210/RamanujanMachine https://github.com/AnonGit90210/RamanujanMachine
> We have continued fractions which are generated by polynomials. What does that mean? object of the type: a(0)+b(1)/(a(1)+b(2)/...)) where a,b are polynomials with integer coefficients. This is the RHS. On the LHS we have a function of some constant, either rational or ULCD. A ULCD function is of the type f(const)=(u/const + const/l + c)/d while a rational function is the ratio of two polynomials. We seek for a match between some LHS function on a constant to a continued fraction. To do this, we enumerate over the coefficients of a,b and those of the rational func on the LHS/the ulcd parameters. They're all integers. We actually don't compare between the LHS to a continued fraction, but to a continued fraction after we applied some function to it, e.g. contfrac^2, sqrt(contfrac), 1/contfrac etc. In order to enhance the algorithm's complexity, we first enumerate over the parameters of the RHS, saving the results to a hashtable, then enumerate over the LHS and look for a match in the table. This is a TMTO (time-memory tradeoff), it's called MITM (meet in the middle), you can look it up if it's not clear. We first find matches, then filter redundant results (discussed later on), filter only continued fractions that converge fastly, find how fast they are converging, and how many iterations we should calculate to get the desired precision. We calculate them to that precision, and filter again.
This doesn't seems that complicated, but at the same time probably gives no mathematical insights as to how to derive those formulaes. I can see how this would look pointless to some people.