To accelerate the analytical solution, there are more obvious techniques, like replacing trigonometric opetations with series. This is a 10x improvement in https://ashvardanian.com/posts/google-benchmark/#slow-trigon...
When Greedy Algorithms Can Be Faster [C++]
11–20 of 30 posts
Re: When Greedy Algorithms Can Be Faster [C++]
#12I don't know how numerics in hardware works, but would the use of functions like sin, cos, sqrt incur a penalty as well, even if only a slight one? It's really fascinating to think about how all of this would work.
Yes, and at least for sqrt(), internally it's likely implemented as a heuristic guess followed by a fixed number of iterations of Newton's Method. (In software, you'd normally iterate Newton's Method until the change in the result is less than some threshold; in hardware, I'm guessing that it might be simpler to figure out the maximum number of iterations that would ever be needed for any input, and always run that many, but I don't know.)
Re: When Greedy Algorithms Can Be Faster [C++]
#13This isn't really what the article is about, but I don't think that the term "Greedy algorithm" means what the author thinks. Greedy algorithms are about making locally optimal choices. They are not "brute force" algorithms or inefficient ones. In fact, greedy algorithms are almost always faster. They are faster because they consider only local information instead of the entire data set. In exchange for that, a greed…
Yeah, greedy is not what he thinks it is. I think of change making algorithm when working retail. Greedy is you always use the largest coin you can, and then the next largest and so on. It works with sensible coin denominations but there are sets of coins where the greedy algorithm is not optimal.
Relevant link: https://en.wikipedia.org/wiki/Change-making_problem
Looking at cases where greedy isn't optimal, I see two patterns. Either:
* there are two coins close in value (ratio of less than 2), e.g. both 20¢ and 25¢; or
* there is a "missing" coin at the GCD of two larger coins.
I'm pretty sure you can precompute extra "virtual coins" (e.g. 40¢) to make greedy optimal again, but you have to place restrictions on how many of them you're allowed to use.
Re: When Greedy Algorithms Can Be Faster [C++]
#14I’m surprised they didn’t mention the reason that the rejection sampling method is surprisingly fast: the probability of needing to resample N times decreases exponentially with N. So even for the 3D case, where 50% of your samples get rejected, the EV for number of samples required is about 2.
This is also a good case study on the difference between throughput sensitive vs latency sensitive applications. The rejection sampling is fast on average, but the analytical solution likely has a much tighter upper bound on how long it can take. In a throughput application you care about EV. But if you need to minimize latency, then you care about the upper bound.
Re: When Greedy Algorithms Can Be Faster [C++]
#15I don't know how numerics in hardware works, but would the use of functions like sin, cos, sqrt incur a penalty as well, even if only a slight one? It's really fascinating to think about how all of this would work.
Yes, and at least for sqrt(), internally it's likely implemented as a heuristic guess followed by a fixed number of iterations of Newton's Method. (In software, you'd normally iterate Newton's Method until the change in the result is less than some threshold; in hardware, I'm guessing that it might be simpler to figure out the maximum number of iterations that would ever be needed for any input, and always run that m…
> at least for sqrt(), internally it's likely implemented as a heuristic guess
Square roots are implemented in hardware: https://www.felixcloutier.com/x86/sqrtsd
> In software, you'd normally iterate Newton's Method
Software normally computes trigonometric functions (and other complicated ones like exponents and std::erf) with a high-degree polynomial approximation.
Re: When Greedy Algorithms Can Be Faster [C++]
#16Earlier quoted context omitted.
Yes, and at least for sqrt(), internally it's likely implemented as a heuristic guess followed by a fixed number of iterations of Newton's Method. (In software, you'd normally iterate Newton's Method until the change in the result is less than some threshold; in hardware, I'm guessing that it might be simpler to figure out the maximum number of iterations that would ever be needed for any input, and always run that m…
> at least for sqrt(), internally it's likely implemented as a heuristic guess Square roots are implemented in hardware: https://www.felixcloutier.com/x86/sqrtsd > In software, you'd normally iterate Newton's Method Software normally computes trigonometric functions (and other complicated ones like exponents and std::erf) with a high-degree polynomial approximation.
sqrt is the one exception to this. the newton series is really good and the polynomials aren't great (and the newton based approach prevents you from having to do range reduction)
Re: When Greedy Algorithms Can Be Faster [C++]
#17Earlier quoted context omitted.
Yes, and at least for sqrt(), internally it's likely implemented as a heuristic guess followed by a fixed number of iterations of Newton's Method. (In software, you'd normally iterate Newton's Method until the change in the result is less than some threshold; in hardware, I'm guessing that it might be simpler to figure out the maximum number of iterations that would ever be needed for any input, and always run that m…
> at least for sqrt(), internally it's likely implemented as a heuristic guess Square roots are implemented in hardware: https://www.felixcloutier.com/x86/sqrtsd > In software, you'd normally iterate Newton's Method Software normally computes trigonometric functions (and other complicated ones like exponents and std::erf) with a high-degree polynomial approximation.
>Square roots are implemented in hardware
But how does that hardware implementation work internally?
The point I'm trying to make is that it is probably an (in-hardware) loop that uses Newton's Method.
ETA: The point being that, although in the source code it looks like all looks have been eliminated, they really haven't been if you dig deeper.
Re: When Greedy Algorithms Can Be Faster [C++]
#18Earlier quoted context omitted.
> at least for sqrt(), internally it's likely implemented as a heuristic guess Square roots are implemented in hardware: https://www.felixcloutier.com/x86/sqrtsd > In software, you'd normally iterate Newton's Method Software normally computes trigonometric functions (and other complicated ones like exponents and std::erf) with a high-degree polynomial approximation.
>Square roots are implemented in hardware But how does that hardware implementation work internally? The point I'm trying to make is that it is probably an (in-hardware) loop that uses Newton's Method. ETA: The point being that, although in the source code it looks like all looks have been eliminated, they really haven't been if you dig deeper.
There are other methods used in hardware, eg (for example)
https://en.wikipedia.org/wiki/Methods_of_computing_square_ro...
Something like Heron's method is a special case of Newton's method.
Re: When Greedy Algorithms Can Be Faster [C++]
#19Earlier quoted context omitted.
>Square roots are implemented in hardware But how does that hardware implementation work internally? The point I'm trying to make is that it is probably an (in-hardware) loop that uses Newton's Method. ETA: The point being that, although in the source code it looks like all looks have been eliminated, they really haven't been if you dig deeper.
There are other methods used in hardware, eg (for example) https://en.wikipedia.org/wiki/Methods_of_computing_square_ro... Something like Heron's method is a special case of Newton's method.
Interesting that your linked algorithm manages to avoid costly divisions, but it uses an even longer loop than Newton's Method -- one iteration for every 2 bits. NM converges quadratically, doubling the number of correct bits each time, so a 32-bit number won't ever need more than 5 iterations, assuming >= 1 bit of accuracy in the initial estimate, which is easy to obtain just by shifting right by half the offset of the highest 1-bit.
Re: When Greedy Algorithms Can Be Faster [C++]
#20Earlier quoted context omitted.
There are other methods used in hardware, eg (for example) https://en.wikipedia.org/wiki/Methods_of_computing_square_ro... Something like Heron's method is a special case of Newton's method.
Interesting that your linked algorithm manages to avoid costly divisions, but it uses an even longer loop than Newton's Method -- one iteration for every 2 bits. NM converges quadratically, doubling the number of correct bits each time, so a 32-bit number won't ever need more than 5 iterations, assuming >= 1 bit of accuracy in the initial estimate, which is easy to obtain just by shifting right by half the offset of…
There are trade-offs (constant time, perhaps?) and many differing applications ...
For example: Pipelined RISC DSP chips have fat (many parallel streams) "one FFT result per clock cycle" pipelines that are rock solid (no cache hits or jitter).
The setup takes a few cyces but once primed it's
aquired data -> ( pipeline ) -> processed data
every clock cycle (with a pipeline delay, of course).
In that domain hardware implementations are chosen to work well with vector calculations and with consistent capped timings.
( To be clear, I haven't looked into that specific linked algo, I'm just pointing out it's not a N.R. only world )