3 ms·

I understand why the second version might benchmark faster, but why is it more numerically stable?

• jart 5y ago
  Because it reduces worst case roundoff errors from being linear to logarithmic. Why is that the case? Best intuitive explanation I can think of is that floating point behaves more like VHS than DVD. If you wanted to bootleg a thousand copies of Titanic, then would you have each copy be made from the previous copy? No. It'd look terrible. You would instead have a stack of VCRs where the copies could be made in a hierarchical way that minimizes the critical path of copies. The overall number of operations may be the same, but if we consider that errors get worse the more errorful something becomes then it should be simple to understand why divide and conquer improves numerical stability.
• deleted 5y ago
  [deleted]