search

SChernykh / sqrt_v2

Square root for Cryptonight variant 2 - integer only operations
1 stars 1 forks source link

Fast Sqrt with other table sizes #2

Open ppereirasky opened 4 years ago

ppereirasky commented 4 years ago

Hi There,

First of all let me congratulate you for the wonderful work. Loved to see your code for a fast sqrt. Can you give me an insight of how do you came up with this solution? I would like to use the code but need table sizes of 128K, 64K and 32K - if possible please let me know, how can I generate the code to work with this tables sizes. Thanks a lot.

SChernykh commented 4 years ago

These tables are polynomial approximations of 1/sqrt(x) and were calculated using Remez algorithm to find the best matching polynomials for each interval. I don't have the generator code at hand unfortunately.

ppereirasky commented 4 years ago

Thanks for your answer. Why the 1/sqrt(x) instead of the actual sqrt(x)?

SChernykh commented 4 years ago

Because it's easier calculate 1/sqrt(x) with arbitrary precision using Newton's method, if needed. It requires only multiplications unlike sqrt(x). These tables can be used as an initial approximation and then each Newton method's iteration can double precision. I also tried direct sqrt(x) tables before, but precision was worse for the same table size.

The final square root is calculated using identity sqrt(x) = x * 1/sqrt(x).