4 ms·
Do you think we'll ever get to a point where there is tooling to generate implementations for user specified functions? E.g. say I want log2(x!) (Picked that
by nullc 2y ago
Do you think we'll ever get to a point where there is tooling to generate implementations for user specified functions? E.g. say I want log2(x!) (Picked that example because the size of the intermediate value blocks computing it naively, and because it's a function I've had to implement before).
- thayne 2y agoTechnically, that isn't a continuous function, so I don't think the Remez algorithm and similar would work directly. But if you replace the factorial with the gamma function, you get a continuous function that is equivalent for positive integers. And you might be able to get something from that. But there might be something more efficient that can take advantage of the fact that the range of your function is positive integers. If you just need something that doesn't overflow, you can take advantage of the properties of logarithms to compute it as the sum of log2(n) for all n from 1 to x.
- thayne 2y agoAnd if you want an integer result, log2 can be quickly computed using the number of leading zeros.
- Cold_Miserable 2y agoIts not possible to automate. Log is one example. You can't just use log(x) but log(x+1). There are other problems like the "zero problem" and its still possible to devise better approximations with other elementary operations such as |x| or ABS(x).