No description provided.
Rewrite 5x52 normalize method to be faster #24
pull peterdettman wants to merge 1 commits into bitcoin-core:master from peterdettman:faster-64bit-normalize changing 1 files +33 −35-
peterdettman commented at 8:37 AM on June 2, 2014: contributor
-
sipa commented at 9:21 AM on June 2, 2014: contributor
Nice, this gives an actual measurable speedup for verification a few %.
I'm convinced that it's correct, but it took me a while. Some comments could help (which is equally true for the previous implementation, though...).
In the first block, you reduce a2^256 + b to a \ 0x1000003D1 + b, with b < 2^256. That results in at most 2^256 + (<2^64).
In the second block, you set x to (n >= 2^256 - 0x1000003D1), add x * 0x1000003D1, know that it overflows if x == 1, and remove 2^256 by masking t4. You could add an assert (x == t4 >> 48) before the masking, I think, as the adding of 0x1000003D1 and subtraction of 2^256 should always happen both or neither.
-
Rewrite 5x52 normalize method to be faster 9037707720
-
peterdettman commented at 12:17 PM on June 3, 2014: contributor
Yes, I think you described it pretty well! I've squashed in some comments now, and added a couple of asserts as suggested.
-
sipa commented at 1:50 PM on June 3, 2014: contributor
ACK
- sipa merged this on Jun 3, 2014
- sipa closed this on Jun 3, 2014
- sipa referenced this in commit b110f84bbb on Jun 3, 2014
- peterdettman cross-referenced this on Jun 22, 2014 from issue Test demonstrating discrepancy in sqr output by peterdettman
- peterdettman deleted the branch on Jun 22, 2014
- tecnovert referenced this in commit eca632d585 on Apr 18, 2022
Contributors