--- Log opened Tue Feb 07 00:00:36 2023
00:45 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
00:53 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has joined #secp256k1
04:48 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
06:02 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has joined #secp256k1
07:33 < roconnor> BTW, why do we use eta instead of delta?
07:55 < real_or_random> roconnor: see https://github.com/bitcoin-core/secp256k1/blob/master/doc/safegcd_implementation.md, grep for "applying the substitution"
07:55 < sipa> From safegcd_implementation.md:
07:55 < sipa> > It turns out that this can be implemented more efficiently by applying the substitution η=-δ. In this representation, negating δ corresponds to negating η, and incrementing δ corresponds to decrementing η. This allows us to remove the negation in the c1 computation:
07:55 < sipa> jinx
07:56 < sipa> roconnor: Perhaps you want to look at https://github.com/bitcoin-core/secp256k1/pull/1197, which switches back to delta.
07:56 < roconnor> But for the var time algorithm...
07:57 < sipa> ah no, we now have delta, eta=-delta, theta=delta-1/2, zeta=-delta-1/2
07:58 -!- hg [~halosghos@user/halosghost] has joined #secp256k1
07:58 < roconnor> I claim for the var time algorithm there is no difference between using eta and delta.  That said, the signedness is arbitrary to begin with...
07:59 < sipa> I believe for the vartime algorithm it's just using the same representation for consistency.
07:59 < roconnor> "same"
07:59 < sipa> But arguably it's exactly the same representation anyway because of the 1/2 offset.
07:59 < sipa> *isn't
08:12 < roconnor> secp256k1_modinv64_divsteps_62_var could probably get away with running somewhere between 62 and 124 divstep, ... basically until it runs out of bits from f0 and g0.
08:13 < sipa> Every divstep consumes 1 bit of each, so I don't see how it can run more than 62.
08:13 < roconnor> Oh, I thought it just consumed one bit of 1.
08:14 < sipa> Maybe "consuming" is not well-defined enough.
08:14 < sipa> To perform N divsteps, you need the N lower bits of the initial value of both f and g.
08:15 < roconnor> I'm not sure I buy that claim. Depending on how eta evolves and the values of f and g, you can get away with fewer
08:16 < roconnor> for example if delta is larger than 62 and g contains 62 0 bits, then you only use maybe 1 bit of f, depending on how you are counting.
08:16 < sipa> Ah, yes, indeed.
08:17 < roconnor> To perform N divsetps you might need N bits from f or N bits from g.
08:17 < sipa> Ok, I believe you.
08:18 < sipa> Well, it's not N bits from f OR from g; it's bits from linear combinations of both.
08:18 < roconnor> But to go larger than 62 steps, I see the translation matrix entries would have to be 128 bit.
08:18 < roconnor> What I'm imagining is tracking how many bits from f and g each have been consumed, and halting when one of them is about to exceed 62.
08:19 < sipa> But as soon as any f+g or g-f step has been computed, you have a value whose lower N bits depend on the lower N bits of both f and g.
08:19 < roconnor> oh hmm.
08:21 < sipa> I can imagine some cases may exist in which you can do more iterations knowing only the bottom 62 of initial f and g.
08:21 < sipa> But I'm not convinced, actually.
08:23 < roconnor> I mean, what you say is true, but I'm not sure it implies "To perform N divsteps, you need the N lower bits of the initial value of both f and g."  You clearly need the same number of bits of f and g, but you may still be able to perform more than N divsteps.
08:23 < sipa> Let me then try to find a counterexample.
08:24 < roconnor> presumably other than the someone exotic counter example I already gave where g has 62 zero bits.
08:24 < roconnor> somewhat.
08:25 < sipa> If g has 62 zero bits, you don't need to know f, I agree. But you still can't do more than 62 steps.
08:25 < roconnor> oh right.  Fair point.
08:26 < roconnor> afk
08:27 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
08:34 < sipa> For N=1..14, there exist no f,g for which the N+1'th divstep is a function of just (f & (2^N-1), g & (2^N-1))
08:38 < sipa> https://0bin.net/paste/riatXDn8#OIhRuRdCdId+AF3FlHS-iYkCoLghirgU5PhQeHfZxew
08:38 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has joined #secp256k1
08:39 < sipa> the docstring for gcd is wrong
08:48 < sipa> Update, N=1..15.
08:52 < roconnor> Can you try varying the starting delta value.   Maaaaybe this holds for the initial divstep group of 62, but not subsequent.
08:52 < sipa> Fair point.
08:53 < roconnor> Although I'm beginning to doubt my idea now.
08:54 < sipa> With delta ranging from -(2^N) to 2^N, the conclusion is the same from N=1..8
08:54 < sipa> Even for delta ranging -3*(2^N) to 3*(2^N)
08:58 < roconnor> Okay I guess I'm wrong.
09:00 < roconnor> When we have a g <- f + g / 2 case the the low but of the new g depends on both the second bit of the original g and the second bit of f.
09:01 < roconnor> So now I do see that it does seem to be maybe consuming both bits of f and g together.
09:02 < roconnor> ... although next time around f is unchanged so it still only consumes the second bit of f...
09:03 < roconnor> Anyhow your results show I am almost certainly wrong, even if I still don't quite get why.
09:07 -!- instagibbs [~instagibb@pool-100-15-126-231.washdc.fios.verizon.net] has quit [Ping timeout: 268 seconds]
09:10 < roconnor> Oh *all* of the bits of the new g depend on all of the bits of f.
09:11 -!- meshcollider [meshcollid@meshcollider.jujube.ircnow.org] has quit [Quit: :wave:]
09:13 -!- instagibbs [~instagibb@pool-100-15-126-231.washdc.fios.verizon.net] has joined #secp256k1
09:18 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
10:16 -!- jonatack1 [~jonatack@user/jonatack] has quit [Quit: WeeChat 3.8]
10:19 -!- jonatack [~jonatack@user/jonatack] has joined #secp256k1
10:19 -!- jonatack [~jonatack@user/jonatack] has quit [Client Quit]
10:25 -!- jonatack [~jonatack@user/jonatack] has joined #secp256k1
10:26 -!- jonatack [~jonatack@user/jonatack] has quit [Client Quit]
10:36 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has joined #secp256k1
10:43 -!- jonatack [~jonatack@user/jonatack] has joined #secp256k1
12:46 -!- jonatack [~jonatack@user/jonatack] has quit [Ping timeout: 260 seconds]
13:29 -!- jonatack [~jonatack@user/jonatack] has joined #secp256k1
13:57 < roconnor> https://github.com/bitcoin-core/secp256k1/blob/master/src/modinv64_impl.h#L243
13:57 < roconnor> I've been thinking about the loop invariant at this point.
13:59 < roconnor> The natural invariant would be, the matrix u,v,q,r upto this point is the matrix formed by the first n divsteps.
13:59 < sipa> @roconnor re #1210... in my gcc, at -O2, your change makes inversion 4% slower; at -O3, it makes it 2% faster.
14:00 < roconnor> But this isn't really true because the end of the loop ends up with some sort of half applied collection of divsteps that conincidently gets fixed up by the subsequent zeros step.
14:02 < roconnor> So now I'm toying with the idea of an invariant that says the u,v,q,r matrix is some matrix that when processed by the current f g eta values will yeild the correct end result for the orginal 62 steps starting from the original f0 g0 eta0.
14:02 < roconnor> sipa have we tried randomly assiging int64 to various int variables to see if performance improves?
14:07 < sipa> I don't believe we have.
14:07 < sipa> Peter Dettman may have prior to opening some of his PRs, though.
14:09 < sipa> roconnor: The invariant may be something like "at the beginning of the loop, applying a divide-out-powers-of-two-from-g, results in a matrix corresponding to N divsteps"
14:09 < roconnor> yeah, maybe.  I probably can make that work too.
14:11 < roconnor> But it is a bit akward because the "zero" step both finishes up the work and the end of the previous loop, and also makes forward progress on sequences of even g steps.
14:11 < sipa> Indeed.
14:12 < roconnor> There is no really right or wrong answer here.  There are lots of ways to phrase invariants.  Just a matter of finding ones that are easier to work with logically.
14:13 < sipa> I like "6 * 9 = 42" as invariant.
14:13 < roconnor> Well that is easy to work with, but probably doesn't establish the correctness of this function.
14:14 < sipa> The algorithm is clearly correct whenever the invariant holds.
14:14 < sipa> Let's say it's also a precondition, if that helps.
14:15 < roconnor> your invariant doesn't even establish that f is odd.  You are going to trip on those VERIFY CHECK statements at this rate.
14:16 < sipa> Pretty everything works fine if we add "|| !(6 * 9 == 42)" to all of them.
14:17 < roconnor> oops you are right.
14:17 < roconnor> it does establish that f is odd.
14:17 < roconnor> my bad.
14:17 < sipa> It also establishes the fact that the moon is green, except on prime-numbered days of the month.
14:17 < sipa> So perhaps not a good basis for reasoning.
14:18 < roconnor> idk, all the verify checks pass.
14:18 < sipa> Ok, let's ship it
14:58 -!- hg [~halosghos@user/halosghost] has quit [Quit: WeeChat 3.8]
15:19 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
19:07 -!- meshcollider [meshcollid@jujube.rpblc.net] has joined #secp256k1
--- Log closed Wed Feb 08 00:00:38 2023