[HN Gopher] Faster practical modular inversion
       ___________________________________________________________________
        
       Faster practical modular inversion
        
       Author : todsacerdoti
       Score  : 56 points
       Date   : 2025-12-21 03:13 UTC (6 days ago)
        
 (HTM) web link (purplesyringa.moe)
 (TXT) w3m dump (purplesyringa.moe)
        
       | signa11 wrote:
       | dupe: https://news.ycombinator.com/item?id=46344548
        
         | 867-5309 wrote:
         | anachronism:
        
       | fn-mote wrote:
       | The article is quite interesting. It ranges from a mathematical
       | discussion (it explains Stein's variant of the GCD algorithm if
       | you make it far enough) to instruction-set-level issues.
       | 
       | For example:
       | 
       | > GCC documents __builtin_clz(0) as having an "undefined result",
       | so I initially assumed it means an indeterminate value. In
       | reality, GCC maintainers consider it UB and LLVM documents it as
       | UB... but the optimizers seem to model it exactly like an
       | indeterminate value? (e.g. LLVM considers @llvm.cttz(0) to
       | produce poison) This is frankly ridiculous, someone do something
       | about it
       | 
       | There is a very interesting table of raw timings, showing
       | variation from about 30% faster to 10% slower across a variety of
       | bit widths (of the numbers involved) and architectures. This is a
       | VERY thorough level of testing!!
       | 
       | PS It's not a dupe if no discussion occurred... that's just the
       | second chance pool.
        
       ___________________________________________________________________
       (page generated 2025-12-27 23:01 UTC)