Ryan Castellucci :nonbinary_flag:
SHA2's "magic numbers" are uint32s: the fractional parts of the square roots of the first 8 primes and the fractional parts of the cube roots of the first 64 primes.
A precomputed table is 288 bytes.
How many bytes of x86_64 assembly would be needed to generate them?
Reply with your estimate.
Ryan Castellucci :nonbinary_flag:
@KingmaYpe that seems very optimistic, what would that look like?
Ype Kingma
About 20 instructions should do: 5 to generate the primes, 5 to find the square roots, 5-6 to find the cube roots, and a few more to select the fractional parts and to select the 8 or 64 primes.
(A few more for bisection or even Newton iteration for the square and cube roots, but that luxury is superfluous here.)
I wonder how many instructions a superoptimizer would leave of those about 20 instructions.
Ryan Castellucci :nonbinary_flag:
@KingmaYpe the score to beat is 164 bytes :-)
Ype Kingma
The bit sizes I mentioned are slightly off, I'd better show working code :)
Maybe later this weekend.
Ype Kingma
The program structure is just brute force, linear searches for primes, square roots and cubic roots. The max prime here is 311, and that has 9 bits.
I assumed one instruction to compute the square of a 32+9 bit number, and 2 instructions for its cube. That was probably too optimistic in both cases.
GNU social JP is a social network, courtesy of GNU social JP管理人. It runs on GNU social, version 2.0.2-dev, available under the GNU Affero General Public License.
All GNU social JP content and data are available under the Creative Commons Attribution 3.0 license.