doc: include number of squares and multiplications in results

[kevaundray]

Perhaps add the number of squares and multiplications or doublings and additions alongside the chain length?

[mmcloughlin]

To clarify, are you talking about the results lists (readme and full results page)?

[kevaundray]

Yep, the readme list. For the program, I haven’t looked around, so I am not sure how hard it would be to in-cooperate the fact that squaring is usually cheaper than multiplying or whether it would be a useful heuristic?

…

On 22 May 2020, 23:08 +0100, Michael McLoughlin ***@***.***>, wrote: To clarify, are you talking about the results lists (readme and full results page)? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or unsubscribe.

[mmcloughlin]

Yes, I agree with you on showing the add/double counts (equivalent to multiplication/square). It's common for other work on the subject to present it that way too, for example https://eprint.iacr.org/2018/1038.

When you say incorporate, do you mean use a weighting when selecting the best chain from a bunch of results?

[kevaundray]

Yep, I mean to use a weighting. For example, setting the weighting of a squaring operation to be 0.85 the weighting of a multiplication operation. One possible drawback, if it has utility, is that the  actual weighting is implementation specific, so a blanket ratio may not be suitable.

…

On 23 May 2020, 03:20 +0100, Michael McLoughlin ***@***.***>, wrote: Yes, I agree with you on showing the add/double counts (equivalent to multiplication/square). It's common for other work on the subject to present it that way too, for example https://eprint.iacr.org/2018/1038. When you say incorporate, do you mean use a weighting when selecting the best chain from a bunch of results? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or unsubscribe.

[mmcloughlin]

Yep, I mean to use a weighting. For example, setting the weighting of a squaring operation to be 0.85 the weighting of a multiplication operation.

Right. I considered this a while back and forgot about it, so it didn't make it into the initial release, but I agree this would be a good feature. The fact that squares are cheaper is accounted for to some extent here:

addchain/internal/results/results_test.go

Lines 49 to 65 in fe56d67

	// Find the best.
	best := []exec.Result{rs[0]}
	for _, r := range rs[1:] {
	if len(r.Program) == len(best[0].Program) {
	best = append(best, r)
	} else if len(r.Program) < len(best[0].Program) {
	best = []exec.Result{r}
	}
	}
	sort.Slice(best, func(i, j int) bool {
	ai := best[i].Program.Adds()
	aj := best[j].Program.Adds()
	ni := best[i].Algorithm.String()
	nj := best[j].Algorithm.String()
	return ai < aj || (ai == aj && ni < nj)
	})

That is, among the shortest chains it picks the one with the fewest adds (equivalently the most doubles). After that it sorts by algorithm name... that was just a way to ensure the result was deterministic!

One possible drawback, if it has utility, is that the  actual weighting is implementation specific, so a blanket ratio may not be suitable.

Yes, agreed the exact weightings would need to be configurable.

I think there's an interesting question about what other heuristics you would use to choose the best chain, even among those that have the exact same number of adds and doubles. @briansmith in some private communication suggested both maximum number of live variables and pipeline stalls (dependencies between variables) as factors you might want to consider.

As long as you have some coarse score to narrow down to the top candidates, then you could just code generate the actual exponentiation function and benchmark it. I thought I remembered a paper that took this approach, maybe it was https://eprint.iacr.org/2019/403 but skimming it now I'm not sure.

[kevaundray]

I think the dependency between variables is a good one, it would be interesting to see to what extent this heuristic speeds up SIMD implementations, if at all.

…

On 23 May 2020, 06:06 +0100, Michael McLoughlin ***@***.***>, wrote: > Yep, I mean to use a weighting. For example, setting the weighting of a squaring operation to be 0.85 the weighting of a multiplication operation. Right. I considered this a while back and forgot about it, so it didn't make it into the initial release, but I agree this would be a good feature. The fact that squares are cheaper is accounted for to some extent here: https://github.com/mmcloughlin/addchain/blob/fe56d6780fb9b9417a1d7c2e7535d66b6effdfb5/internal/results/results_test.go#L49-L65 That is, among the shortest chains it picks the one with the fewest adds (equivalently the most doubles). After that it sorts by algorithm name... that was just a way to ensure the result was deterministic! > One possible drawback, if it has utility, is that the  actual weighting is implementation specific, so a blanket ratio may not be suitable. Yes, agreed the exact weightings would need to be configurable. I think there's an interesting question about what other heuristics you would use to choose the best chain, even among those that have the exact same number of adds and doubles. @briansmith in some private communication suggested both maximum number of live variables and pipeline stalls (dependencies between variables) as factors you might want to consider. As long as you have some coarse score to narrow down to the top candidates, then you could just code generate the actual exponentiation function and benchmark it. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or unsubscribe.