Hacker News Reader

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).

View on HN

Technically, 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.

And if you want an integer result, log2 can be quickly computed using the number of leading zeros.

Its 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).

Reply on news.ycombinator.com