On 16/08/25 00:40, Eduard Zingerman wrote:
> Could you please provide a selftest demonstrating a difference in
behavior?
> What technique did you employ to estimate the number of cases when
> precision is improved vs worsened? If this is some kind of a program
> doing randomized testing, could you please share a link to it?
Hi Eduard,
Thanks for the quick response! I've made the test program available here:
https://github.com/nandedamana/improved-tnum-mul
The repo contains the code for the test program, and a README file with some
explanation and a sample output. The program basically does a brute-force
comparison involving all combinations possible with N bits (which of course
doesn't scale very well).
I've done some random checks at 64 bits (which I'd like to incorporate
to the
program in future), and manual checks at lower bits. Still, I could've
made some
stupid mistakes, and I'm really thankful that you are interested in
verifying it.
For the record, let me paste the sample output here:
$ ./experi --bits 6
...
mine vs kernel (bits = 6):
better = 285059
same = 229058
worse = 17324
myprod optimal cases = 432406 / 531441
linprod optimal cases = 202444 / 531441
----------------------------------------------------------
is optimal? (bits = 6): 0
The above output shows the new algorithm was an improvement over the
current one
in 285k cases, and worse in 17k, while preserving the precision in 229k
cases. It achieved optimality in in 81% cases compared to the 38%
obtained by
the current algorithm. I had benchmarked an early version of the new
algorithm
at 8 bits as well, with similar (slightly better, actually) results.
Regarding adding selftests, I'll look into that as well. It'd be great
if you
have any specific strategy in mind, wrt to this particular change. BTW, any
set of BPF programs that are known to fail due to the imprecision in the
current
algorithm?
Thank you,
--
Nandakumar Edamana
