{"id":473462,"date":"2025-09-02T16:35:37","date_gmt":"2025-09-02T16:35:37","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=473462"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=473462","title":{"rendered":"\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430, \u0431\u0438\u0442\u044b, \u043c\u0430\u0433\u0438\u044f \u0438 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043d\u0435\u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0430 C<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n

\u0414\u043e\u0431\u0440\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0441\u0443\u0442\u043e\u043a, \u0433\u043e\u0441\u043f\u043e\u0434\u0430 \u0438 \u0434\u0430\u043c\u044b! \u0418\u043d\u043e\u0433\u0434\u0430 \u0443 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043b\u044e\u0434\u0435\u0439 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0436\u0435\u043b\u0430\u043d\u0438\u0435 \u0437\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u043e\u0442\u043a\u0440\u043e\u0432\u0435\u043d\u043d\u044b\u043c \u043d\u0435\u043f\u043e\u0442\u0440\u0435\u0431\u0441\u0442\u0432\u043e\u043c \u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u2014 \u0442\u043e, \u0447\u0442\u043e \u043d\u0435 \u043d\u0435\u0441\u0435\u0442 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u043e\u043b\u044c\u0437\u044b \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e, \u043d\u043e \u043f\u043e\u043c\u043e\u0433\u0430\u0435\u0442 \u0440\u0430\u0437\u0432\u043b\u0435\u0447\u044c\u0441\u044f. \u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u044f \u0445\u043e\u0447\u0443 \u0440\u0430\u0441\u0441\u043a\u0430\u0437\u0430\u0442\u044c \u0432\u0430\u043c \u043e \u043b\u0430\u0439\u0444\u0445\u0430\u043a\u0430\u0445, \u0442\u0440\u044e\u043a\u0430\u0445 (\u043c\u0430\u0433\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0438 \u043d\u0435 \u043e\u0447\u0435\u043d\u044c), \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u0445 \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 C!<\/p>\n

\u0418\u0434\u0435\u044f \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u044d\u0442\u0443 \u0441\u0442\u0430\u0442\u044c\u044e \u0437\u0430\u0440\u043e\u0434\u0438\u043b\u0430\u0441\u044c \u0438\u0437 \u043c\u043e\u0435\u0433\u043e \u043f\u043e\u0441\u0442\u0430<\/a>. \u0412 \u043d\u0435\u043c \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0437\u0430\u043b \u043e \u0442\u043e\u043c, \u0447\u0442\u043e \u0447\u0435\u0440\u0435\u0437 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u043c\u043e\u0436\u043d\u043e \u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043c\u0438\u043b\u0438 \u0432 \u043a\u0438\u043b\u043e\u043c\u0435\u0442\u0440\u044b \u0441 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c\u044e. \u0423\u0432\u0438\u0434\u0435\u0432, \u0447\u0442\u043e \u043c\u043d\u043e\u0433\u0438\u043c \u043f\u043e\u043d\u0440\u0430\u0432\u0438\u043b\u0430\u0441\u044c, \u044f \u0437\u0430\u0434\u0443\u043c\u0430\u043b\u0441\u044f: \u043f\u043e\u0447\u0435\u043c\u0443 \u0431\u044b \u043d\u0435 \u0438\u0437\u0443\u0447\u0438\u0442\u044c \u0435\u0449\u0435 \u043a\u0430\u043a\u0438\u0435-\u043d\u0438\u0431\u0443\u0434\u044c \u0442\u0440\u044e\u043a\u0438, \u0437\u0430\u043e\u0434\u043d\u043e \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0443\u044f\u0441\u044c \u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u043d\u0430 C?<\/p>\n

\u0412\u0441\u0435\u0445, \u043a\u0442\u043e \u0437\u0430\u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043e\u0432\u0430\u043b\u0441\u044f \u2014 \u043f\u0440\u043e\u0448\u0443 \u043f\u043e\u0434 \u043a\u0430\u0442.<\/p>\n\n

\u0420\u0430\u0437 \u044f \u0443\u0436\u0435 \u043d\u0430\u0447\u0430\u043b \u0440\u0430\u0441\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u043e \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438, \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0446\u0438\u0442\u0438\u0440\u0443\u044e \u0441\u0432\u043e\u0439 \u043f\u043e\u0441\u0442:<\/p>\n

\n

\u041f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u043c\u043e\u0436\u0435\u0442 \u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043c\u0438\u043b\u0438 \u0432 \u043a\u0438\u043b\u043e\u043c\u0435\u0442\u0440\u044b \u0441 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c\u044e. 5 \u043c\u0438\u043b\u044c \u2248 8 \u043a\u043c (5 \u0438 8 \u2014 \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438). \u0420\u0435\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c: 5 \u043c\u0438\u043b\u044c = 8.04672 \u043a\u043c. \u041f\u043e\u0447\u0435\u043c\u0443? 1 \u043c\u0438\u043b\u044f = 1.609344 \u043a\u0438\u043b\u043e\u043c\u0435\u0442\u0440\u0430 (\u0442\u043e\u0447\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435). \u0417\u043e\u043b\u043e\u0442\u043e\u0435 \u0441\u0435\u0447\u0435\u043d\u0438\u0435 (\u03c6) \u2248 1.618034. \u041f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435 F\u2099\u208a\u2081 \/ F\u2099 \u0441\u0442\u0440\u0435\u043c\u0438\u0442\u0441\u044f \u043a \u03c6 \u2248 1.618034, \u0430 \u0442\u043e\u0447\u043d\u043e\u0435 \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435 \u043c\u0438\u043b\u044f\/\u043a\u043c = 1.609344. \u041e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c: (1.618034 \u2014 1.609344) \/ 1.609344 * 100% \u2248 0.54%.<\/p>\n<\/blockquote>\n

\n

\u0424\u0430\u043d\u0444\u0430\u043a\u0442: \u0435\u0441\u043b\u0438 \u0432\u0437\u044f\u0442\u044c \u043a\u0443\u0431 \u0438 \u0448\u0430\u0440 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0433\u043e \u043e\u0431\u044a\u0451\u043c\u0430, \u0442\u043e \u0440\u0430\u0434\u0438\u0443\u0441 \u0448\u0430\u0440\u0430 \u0432 \u043c\u0438\u043b\u044f\u0445 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u0435\u043d \u0440\u0435\u0431\u0440\u0443 \u043a\u0443\u0431\u0430 \u0432 \u043a\u0438\u043b\u043e\u043c\u0435\u0442\u0440\u0430\u0445. \u041f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043a\u0443\u0431\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 (4\/3)pi \u043a\u0430\u043a \u0440\u0430\u0437 \u0440\u0430\u0432\u0435\u043d 1.61. @Enfriz<\/a><\/p>\n<\/blockquote>\n

\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c, \u043a\u0430\u043a \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0442\u0430\u043a\u043e\u0439 \u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0435\u0440 \u043d\u0430 C.<\/p>\n

\u0412\u043e\u0442 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c \u0435\u0441\u0442\u044c \u0442\u0430\u043a\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f:<\/p>\n

uint64_t fibonacci(int num) {     if (num < 0)         return 0;     if (num == 0)         return 0;      uint64_t a = 0;     uint64_t b = 1;      if (num == 1)         return b;      for (int i = 2; i <= num; i++) {         uint64_t next = a + b;         a = b;         b = next;     }      return b; } <\/code><\/pre>\n
\u042f \u0434\u0443\u043c\u0430\u044e \u0432\u044b \u0432\u0441\u0435 \u0437\u043d\u0430\u0435\u0442\u0435 \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0434\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u041f\u043e\u044f\u0441\u043d\u0438\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u0442\u043e\u0438\u0442 \u0447\u0442\u043e \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u043a\u0430\u043a \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442 \u0438\u043d\u043a\u0440\u0435\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043d\u0430 1 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043c\u0438\u043b\u0435\u0439 \u2014 \u0442\u043e \u0435\u0441\u0442\u044c \u0447\u0442\u043e\u0431\u044b \u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c 5 \u043c\u0438\u043b\u0435\u0439 \u0432 \u043a\u0438\u043b\u043e\u043c\u0435\u0442\u0440\u044b, \u043c\u044b \u043f\u0435\u0440\u0435\u0434\u0430\u0435\u043c 5+1=6 (\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u0447\u0438\u0441\u043b\u043e) \u0438 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c 8.<\/p>\n
\u0422\u0430\u043a\u0436\u0435, \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0437\u043e\u043b\u043e\u0442\u043e\u0433\u043e \u0441\u0435\u0447\u0435\u043d\u0438\u044f \u2014 \u0438\u0431\u043e \u043e\u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u0441\u0432\u044f\u0437\u0430\u043d\u043e \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c\u044e \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438.<\/p>\n
float fib_golden_ratio(float miles) {     const double PHI = (1.0 + sqrt(5.0)) \/ 2.0;      if (miles < 1e-5) {         return 0.0F;     }      double n = log(miles * sqrt(5.0)) \/ log(PHI);     int k = (int)floor(n);      double Fk = (pow(PHI, k) - pow(-PHI, -k)) \/ sqrt(5.0);     double Fk1 = (pow(PHI, k + 1) - pow(-PHI, -k - 1)) \/ sqrt(5.0);     double Fk2 = (pow(PHI, k + 2) - pow(-PHI, -k - 2)) \/ sqrt(5.0);      if (Fk1 - Fk < DBL_EPSILON) {         return basic_miles2km(miles);     }      return Fk1 + ((miles - Fk) * ((float)(Fk2 - Fk1) \/ (Fk1 - Fk))); } <\/code><\/pre>\n
\u041d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0447\u0438\u0441\u043b\u0430 \u03c6 ((1 + \u221a5) \/ 2) \u043c\u044b \u0442\u0430\u043a\u0436\u0435 \u043c\u043e\u0436\u0435\u043c \u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043c\u0438\u043b\u0438 \u0432 \u043a\u0438\u043b\u043e\u043c\u0435\u0442\u0440\u044b. \u0417\u043e\u043b\u043e\u0442\u043e\u0435 \u0441\u0435\u0447\u0435\u043d\u0438\u0435 \u03c6 \u2248 1.618 \u0431\u043b\u0438\u0437\u043a\u043e \u043a 1.609, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0438\u043c\u0438\u0442\u0438\u0440\u0443\u044e\u0442 \u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0430\u0446\u0438\u044e<\/p>\n
\u041f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f n \u0437\u0434\u0435\u0441\u044c \u2014 \u044d\u0442\u043e \u0438\u043d\u0434\u0435\u043a\u0441 \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e miles, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043d\u0430 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0435, \u0447\u0442\u043e F(n) \u2248 \u03c6^n \/ \u221a5. \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 n, \u0430 \u0437\u0430\u0442\u0435\u043c \u043e\u043a\u0440\u0443\u0433\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u0446\u0435\u043b\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 k.<\/p>\n
\u041f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 Fk, Fk1, Fk2 \u2014 \u044d\u0442\u043e \u0442\u0440\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438, \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c\u044b\u0435 \u0447\u0435\u0440\u0435\u0437 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u0411\u0438\u043d\u0435 \u0434\u043b\u044f \u0447\u0438\u0441\u0435\u043b \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438: F(n) = (\u03c6^n \u2014 (1 \u2014 \u03c6)^n) \/ \u221a5.<\/p>\n
\n
\u0424\u043e\u0440\u043c\u0443\u043b\u0430 \u0411\u0438\u043d\u0435 \u2014 \u044d\u0442\u043e \u044f\u0432\u043d\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f n-\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0431\u0435\u0437 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0433\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f. \u041e\u043d\u0430 \u043d\u0430\u0437\u0432\u0430\u043d\u0430 \u0432 \u0447\u0435\u0441\u0442\u044c \u0444\u0440\u0430\u043d\u0446\u0443\u0437\u0441\u043a\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0435\u0451 \u043e\u0442\u043a\u0440\u044b\u043b. \u0424\u043e\u0440\u043c\u0443\u043b\u0430 \u0411\u0438\u043d\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0437\u0430 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f (O(1)), \u0442\u043e\u0433\u0434\u0430 \u043a\u0430\u043a \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u043d\u044f\u0442\u044c \u044d\u043a\u0441\u043f\u043e\u043d\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u042d\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0411\u0438\u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0439 \u0432 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f\u0445, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0445 \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044f\u043c\u0438 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438.<\/p>\n<\/blockquote>\n
\u0415\u0441\u043b\u0438 \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u043c\u0435\u0436\u0434\u0443 F(k+1) \u0438 F(k) \u043c\u0435\u043d\u044c\u0448\u0435 DBL_EPSILON, \u044d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0447\u0442\u043e \u0447\u0438\u0441\u043b\u0430 \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u0431\u043b\u0438\u0437\u043a\u0438 \u0434\u0440\u0443\u0433 \u043a \u0434\u0440\u0443\u0433\u0443, \u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0432\u043c\u0435\u0441\u0442\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u0442 \u0444\u0443\u043d\u043a\u0446\u0438\u044e basic_miles2km.<\/p>\n
\u041d\u043e \u043f\u043e\u0447\u0435\u043c\u0443 \u043c\u044b \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u043c \u0432 basic_miles2km? \u041c\u044b \u0436\u0435 \u0441 \u0432\u0430\u043c\u0438 \u0437\u0430\u0442\u0440\u0430\u0433\u0438\u0432\u0430\u0435\u043c \u043d\u0435\u0442\u0438\u043f\u0438\u0447\u043d\u044b\u0435 \u0441\u043f\u043e\u0441\u043e\u0431\u044b \u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0430\u0446\u0438\u0438. \u041d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u044d\u0442\u043e \u2014 \u0437\u0430\u0449\u0438\u0442\u043d\u044b\u0439 \u043c\u0435\u0445\u0430\u043d\u0438\u0437\u043c. \u0415\u0441\u043b\u0438 Fk1 \u2248 Fk (\u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u043c\u0435\u043d\u044c\u0448\u0435 DBL_EPSILON), \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0440\u0435\u043c\u0438\u0442\u0441\u044f \u043a \u043d\u0443\u043b\u044e \u2192 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043d\u0435\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0451\u043d\u043d\u043e\u0441\u0442\u044c \u0438\u043b\u0438 NaN. \u0422\u0430\u043a\u0436\u0435 \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0411\u0438\u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u043d\u0435\u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043f\u0440\u0438 \u043c\u0430\u043b\u044b\u0445 n (\u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e n < 3).<\/p>\n
\u0423\u0441\u043b\u043e\u0432\u0438\u0435 (Fk1 — Fk < DBL_EPSILON) \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442: \u00ab\u0420\u0430\u0437\u043d\u0438\u0446\u0430 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u043e\u0440\u043e\u0433\u0430 \u0440\u0430\u0437\u043b\u0438\u0447\u0438\u043c\u043e\u0441\u0442\u0438 \u0447\u0438\u0441\u0435\u043b \u0441 \u043f\u043b\u0430\u0432\u0430\u044e\u0449\u0435\u0439 \u0442\u043e\u0447\u043a\u043e\u0439\u00bb. DBL_EPSILON \u2014 \u044d\u0442\u043e \u043c\u0430\u0448\u0438\u043d\u043d\u044b\u0439 \u044d\u043f\u0441\u0438\u043b\u043e\u043d \u0434\u043b\u044f \u0447\u0438\u0441\u0435\u043b \u0442\u0438\u043f\u0430 double (64 \u0431\u0438\u0442\u0430) \u0438\u0437 float.h, \u0440\u0430\u0432\u043d\u0430 2\u221252 \u2248 2,20e-16. \u041a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430 DBL_EPSILON \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u0435\u043b \u0441 \u043f\u043b\u0430\u0432\u0430\u044e\u0449\u0435\u0439 \u0442\u043e\u0447\u043a\u043e\u0439. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u0432\u0430 \u0447\u0438\u0441\u043b\u0430 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c\u0438 \u0441 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0438, \u0435\u0441\u043b\u0438 \u0438\u0445 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u043c\u0435\u043d\u044c\u0448\u0435 DBL_EPSILON.<\/p>\n
float basic_miles2km(float miles) {     return miles * 1.609344f; } <\/code><\/pre>\n
\u0418 \u0432 \u043a\u043e\u043d\u0446\u0435 \u0438\u0434\u0435\u0442 \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u044f\u0446\u0438\u044f \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438: return Fk1 + ((miles - Fk) * ((float)(Fk2 - Fk1) \/ (Fk1 - Fk)));<\/code>. \u0415\u0441\u043b\u0438 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u044f \u043d\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u044b, \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043b\u0438\u043d\u0435\u0439\u043d\u0443\u044e \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u044f\u0446\u0438\u044e, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u0442\u043e\u0447\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438, \u043e\u0441\u043d\u043e\u0432\u044b\u0432\u0430\u044f\u0441\u044c \u043d\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0438 miles. \u041d\u043e \u044d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 n \u043c\u043e\u0436\u0435\u0442 \u043d\u0430\u043a\u0430\u043f\u043b\u0438\u0432\u0430\u0442\u044c \u043e\u0448\u0438\u0431\u043a\u0438.<\/p>\n
\u041f\u0435\u0440\u0435\u0439\u0434\u0435\u043c \u043a \u0434\u0440\u0443\u0433\u043e\u0439 \u043f\u043e\u0445\u043e\u0436\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438:<\/p>\n
float fib_interpolate(float miles) {     if (miles < 5.0F) {         return basic_miles2km(miles);     }      uint64_t prev_mile = 0;     uint64_t prev_km = 1;     uint64_t curr_mile = 1;     uint64_t curr_km = 2;      while (curr_mile <= miles) {         prev_mile = curr_mile;         prev_km = curr_km;          curr_mile = prev_km;         curr_km = prev_mile + prev_km;          if (curr_km < prev_km || curr_mile < prev_mile) {             break;         }     }      return prev_km + ((miles - prev_mile) * ((float)(curr_km - prev_km) \/ (curr_mile - prev_mile))); } <\/code><\/pre>\n
\u0412 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043e\u0431\u044a\u044f\u0432\u043b\u0435\u043d\u044b \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0438\u0435 64-\u0431\u0438\u0442\u043d\u044b\u0435 \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0431\u0435\u0437 \u0437\u043d\u0430\u043a\u0430 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u043c\u0438\u043b\u044c \u0438 \u043a\u0438\u043b\u043e\u043c\u0435\u0442\u0440\u043e\u0432, \u0433\u0434\u0435 prev_mile \u0438 prev_km \u0445\u0440\u0430\u043d\u044f\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f, \u0430 curr_mile \u0438 curr_km \u2014 \u0442\u0435\u043a\u0443\u0449\u0438\u0435. \u0417\u0430\u0442\u0435\u043c \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u0446\u0438\u043a\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043c\u0438\u043b\u044c (curr_mile) \u043c\u0435\u043d\u044c\u0448\u0435 \u0438\u043b\u0438 \u0440\u0430\u0432\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e miles. \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u0446\u0438\u043a\u043b\u0430 \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0447\u0435\u0440\u0435\u0437 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0435 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438, \u0447\u0442\u043e \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 (\u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043c\u0438\u043b\u044c \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u0440\u0435\u0434\u0448\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0433\u043e \u043a\u0438\u043b\u043e\u043c\u0435\u0442\u0440\u0430, \u0430 \u043a\u0438\u043b\u043e\u043c\u0435\u0442\u0440\u044b \u0431\u0435\u0440\u0443\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0441\u0443\u043c\u043c\u044b \u0434\u0432\u0443\u0445 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445).<\/p>\n
\u0427\u0442\u043e\u0431\u044b \u043f\u0440\u0435\u0434\u043e\u0442\u0432\u0440\u0430\u0442\u0438\u0442\u044c \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u0432 \u0442\u0435\u043b\u0435 \u0446\u0438\u043a\u043b\u0430 \u0442\u0430\u043a\u0436\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0430: \u0435\u0441\u043b\u0438 \u043d\u043e\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043a\u0438\u043b\u043e\u043c\u0435\u0442\u0440\u043e\u0432 \u0438\u043b\u0438 \u043c\u0438\u043b\u044c \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e, \u0446\u0438\u043a\u043b \u043f\u0440\u0435\u0440\u044b\u0432\u0430\u0435\u0442\u0441\u044f. \u042d\u0442\u043e \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0441\u043b\u0443\u0436\u0438\u0442 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 \u043d\u0435\u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0445 \u043e\u0448\u0438\u0431\u043e\u043a \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f.<\/p>\n
\u041f\u043e\u0441\u043b\u0435 \u0437\u0430\u0432\u0435\u0440\u0448\u0435\u043d\u0438\u044f \u0446\u0438\u043a\u043b\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u044f\u0446\u0438\u044f \u0434\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043a\u0438\u043b\u043e\u043c\u0435\u0442\u0440\u043e\u0432 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u043f\u0440\u0435\u0434\u0448\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u0433\u0434\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u044f\u0446\u0438\u044f. \u042d\u0442\u043e\u0442 \u0440\u0430\u0441\u0447\u0435\u0442 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0431\u043e\u043b\u0435\u0435 \u0442\u043e\u0447\u043d\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0447\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430 \u0447\u0438\u0441\u043b\u0430\u0445 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438. \u0422\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u0442\u0430\u043a\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u044f\u0446\u0438\u044f \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0442\u043e\u0447\u043d\u043e\u0439 \u0434\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u043c\u0438\u043b\u044c, \u0447\u0442\u043e \u043e\u0441\u043b\u0430\u0431\u043b\u044f\u0435\u0442 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0430 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432.<\/p>\n
\u0412\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u0438 fib_interpolate<\/code> \u2014 O(n), \u0433\u0434\u0435 n \u2014 \u044d\u0442\u043e \u043f\u043e\u0437\u0438\u0446\u0438\u044f \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438.<\/p>\n
\u0411\u043e\u043b\u0435\u0435 \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e \u0432\u0435\u0441\u044c \u043a\u043e\u0434 \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u0440\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432 \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u0438 fib_miles2km<\/a> \u0438\u043b\u0438 \u043f\u0440\u044f\u043c\u043e \u0432 \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u0438-\u0441\u0431\u043e\u0440\u043d\u0438\u043a\u0435 \u0434\u043b\u044f \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 The Art Of Fun C<\/a>.<\/p>\n
\u276f \u0411\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c<\/h3>\n
\u0420\u0430\u0437 \u0443\u0436 \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0438 pow()<\/code> \u0432 \u0444\u043e\u0440\u043c\u0443\u043b\u0435 \u0411\u0438\u043d\u0435, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u043c \u0435\u0433\u043e \u0447\u0435\u0440\u0435\u0437 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435.<\/p>\n
\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0438\u043c\u043f\u043e\u0440\u0442\u043e\u0437\u0430\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 pow<\/code> \u043d\u0430\u0448\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c, \u0430 \u0442\u043e\u0447\u043d\u0435\u0435 \u2014 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u043c \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435\u043c \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u2014 O(log n).<\/p>\n
\u0428\u0438\u0440\u043e\u043a\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0432 \u0446\u0435\u043b\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0441 \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u043e\u0439 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e. \u041f\u0440\u0438\u043d\u0446\u0438\u043f \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f \u043f\u0440\u043e\u0441\u0442: \u0435\u0441\u0442\u044c \u0446\u0435\u043b\u0430\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u044c e, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e b \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043d\u0443\u0436\u043d\u043e \u0432\u043e\u0437\u0432\u0435\u0441\u0442\u0438 \u044d\u0442\u043e \u0447\u0438\u0441\u043b\u043e \u0432\u043e \u0432\u0441\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 1, 2, 4, \u2026 2n (\u0432 \u043a\u043e\u0434\u0435 \u044d\u0442\u043e\u043c\u0443 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 b *= b), \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u0441\u0434\u0432\u0438\u0433\u0430\u044f \u0431\u0438\u0442\u044b e \u0432\u043f\u0440\u0430\u0432\u043e (e >>= 1) \u043f\u043e\u043a\u0430 \u043e\u043d\u043e \u043d\u0435 \u0440\u0430\u0432\u043d\u043e 0 \u0438 \u0442\u043e\u0433\u0434\u0430, \u043a\u043e\u0433\u0434\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0431\u0438\u0442 e \u043d\u0435 \u0440\u0430\u0432\u0435\u043d \u043d\u0443\u043b\u044e ((e & 1) != 0), \u0434\u043e\u043c\u043d\u043e\u0436\u0430\u0442\u044c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 v \u043d\u0430 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u043e\u0435 b. \u042d\u0442\u043e\u0442 \u043c\u0435\u0442\u043e\u0434 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u043e\u0437\u0432\u0435\u0441\u0442\u0438 \u0447\u0438\u0441\u043b\u043e \u0432 \u0446\u0435\u043b\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0432\u0440\u0435\u043c\u044f, \u0447\u0442\u043e \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0432\u0430\u0436\u043d\u043e \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438.<\/p>\n
\u0412\u043e\u0437\u044c\u043c\u0451\u043c 2\u2075. \u0412\u043c\u0435\u0441\u0442\u043e 2\u00d72\u00d72\u00d72\u00d72 \u043c\u044b \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c 5 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u0432\u0438\u0434\u0435 (101) \u0438 \u0438\u0434\u0435\u043c \u043f\u043e \u0431\u0438\u0442\u0430\u043c \u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043b\u0435\u0432\u043e. \u041f\u0435\u0440\u0432\u044b\u0439 \u0431\u0438\u0442 (1) \u0440\u0430\u0432\u0435\u043d 2, \u0432\u0442\u043e\u0440\u043e\u0439 \u0431\u0438\u0442 (0) \u0440\u0430\u0432\u0435\u043d 2 \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0435, \u0438 \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u043c \u0442\u0440\u0435\u0442\u044c\u0435\u043c \u0431\u0438\u0442\u0443 (1) \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 (2) \u0443\u043c\u043d\u043e\u0436\u0430\u0435\u043c \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 (4\u00b2=16) \u2192 32.<\/p>\n
\u0422\u0435\u0445\u043d\u0438\u0447\u0435\u0441\u043a\u0438, \u043f\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u043c \u043f\u0440\u043e\u0445\u043e\u0434\u0435 \u0446\u0438\u043a\u043b\u0430, \u043c\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043c\u043b\u0430\u0434\u0448\u0438\u0439 \u0431\u0438\u0442 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 e. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e\u0442 \u0431\u0438\u0442 \u0440\u0430\u0432\u0435\u043d 1 (e & 1 != 0), \u043c\u044b \u0443\u043c\u043d\u043e\u0436\u0430\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 v \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0435 b. \u041f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u043c\u044b \u0443\u043c\u043d\u043e\u0436\u0430\u0435\u043c b \u043d\u0430 \u0441\u0430\u043c\u043e \u0441\u0435\u0431\u044f (\u043a\u0432\u0430\u0434\u0440\u0430\u0442), \u0447\u0442\u043e \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f. \u0423\u043c\u0435\u043d\u044c\u0448\u0430\u044f e \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0441\u0434\u0432\u0438\u0433\u0430 \u0432\u043f\u0440\u0430\u0432\u043e, \u043c\u044b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u0446\u0438\u043a\u043b, \u043f\u043e\u043a\u0430 e \u043d\u0435 \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442 \u043d\u0443\u043b\u044f, \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0447\u0435\u0433\u043e \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442.<\/p>\n
double binary_pow(double b, unsigned long long e) {     double v = 1.0;     while(e != 0) {             if((e & 1) != 0) {                     v *= b;             }             b *= b;             e >>= 1;     }     return v; } <\/code><\/pre>\n
\u0418 \u043f\u0440\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0438 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c 10.00 ** 2.00 = 100.00, 10.50 ** 2.00 = 110.25. \u041d\u043e \u0435\u0441\u043b\u0438 \u044d\u043a\u0441\u043f\u043e\u043d\u0435\u043d\u0442\u0430 \u043d\u0435 \u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u0442\u043e \u0434\u0430\u043d\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u043d\u0435 \u043f\u043e\u0434\u043e\u0439\u0434\u0435\u0442 (10.50^2.50 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u043a 110.25). \u0422\u0430\u043a \u0447\u0442\u043e \u0432\u0430\u0436\u043d\u043e \u043e\u0442\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u043a \u0446\u0435\u043b\u044b\u043c \u0447\u0438\u0441\u043b\u0430\u043c.<\/p>\n
\u041d\u0443 \u0438 \u0432\u043e\u0442 \u043f\u0440\u0438\u043c\u0435\u0440 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 fib_golden_ratio \u0438\u0437 \u043f\u0440\u043e\u0448\u043b\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u0430:<\/p>\n
float fib_golden_ratio_binary(float miles) {     const double PHI = (1.0 + sqrt(5.0)) \/ 2.0;      if (miles < 1e-5) {         return 0.0F;     }      double n = log(miles * sqrt(5.0)) \/ log(PHI);     int k = (int)floor(n);      double sign_k = (k % 2 == 0) ? 1.0 : -1.0;     double sign_k1 = ((k+1) % 2 == 0) ? 1.0 : -1.0;     double sign_k2 = ((k+2) % 2 == 0) ? 1.0 : -1.0;      double phi_k = binary_pow(PHI, k);     double phi_k1 = binary_pow(PHI, k+1);     double phi_k2 = binary_pow(PHI, k+2);      double Fk = (phi_k - sign_k \/ phi_k) \/ sqrt(5.0);     double Fk1 = (phi_k1 - sign_k1 \/ phi_k1) \/ sqrt(5.0);     double Fk2 = (phi_k2 - sign_k2 \/ phi_k2) \/ sqrt(5.0);      if (Fk1 - Fk < DBL_EPSILON) {         return basic_miles2km(miles);     }      return Fk1 + ((miles - Fk) * ((float)(Fk2 - Fk1) \/ (Fk1 - Fk))); } <\/code><\/pre>\n
\u276f \u0413\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u043f\u0441\u0435\u0432\u0434\u043e\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b Xorshift<\/h3>\n
\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u043c \u043a \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u2014 \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440\u0443 \u043f\u0441\u0435\u0432\u0434\u043e\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0441\u0432\u043e\u0439 \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u0442\u0430\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 Xorshift. Xorshift \u2014 \u044d\u0442\u043e \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u0441\u0435\u0432\u0434\u043e\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u0441\u0434\u0432\u0438\u0433\u0430 \u0438 \u0438\u0441\u043a\u043b\u044e\u0447\u0430\u044e\u0449\u0435\u0433\u043e \u0418\u041b\u0418 (XOR). \u041e\u043d\u0438 \u043f\u0440\u043e\u0441\u0442\u044b \u0432 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438, \u043e\u0447\u0435\u043d\u044c \u0431\u044b\u0441\u0442\u0440\u044b \u0438 \u0434\u0430\u044e\u0442 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0445\u043e\u0440\u043e\u0448\u0438\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0434\u043b\u044f \u043c\u043d\u043e\u0433\u0438\u0445 \u0437\u0430\u0434\u0430\u0447.<\/p>\n
uint64_t xorshift64(uint64_t *state) {     uint64_t x = *state;     x ^= x << 13;     x ^= x >> 7;     x ^= x << 17;     *state = x;     return x; } <\/code><\/pre>\n
\u0414\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0442\u0430\u043a:<\/p>\n
    \n
  1. \n
    \u0421\u0434\u0432\u0438\u0433 \u0432\u043b\u0435\u0432\u043e + XOR (x << 13): \u00ab\u0420\u0430\u0437\u043c\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u00bb \u0431\u0438\u0442\u044b \u0432 \u0441\u0442\u0430\u0440\u0448\u0438\u0435 \u0440\u0430\u0437\u0440\u044f\u0434\u044b. \u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f XOR \u0441\u043c\u0435\u0448\u0438\u0432\u0430\u0435\u0442 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0435 \u0431\u0438\u0442\u044b \u0441 \u0438\u0437\u043c\u0435\u043d\u0451\u043d\u043d\u044b\u043c\u0438.<\/p>\n<\/li>\n
  2. \n
    \u0421\u0434\u0432\u0438\u0433 \u0432\u043f\u0440\u0430\u0432\u043e + XOR (x >> 7): \u0420\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043a\u0430\u043a \u00ab\u043e\u0431\u0440\u0430\u0442\u043d\u044b\u0439\u00bb \u0448\u0430\u0433 \u2014 \u043a\u043e\u043c\u043f\u0435\u043d\u0441\u0438\u0440\u0443\u0435\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0439 \u0441\u0434\u0432\u0438\u0433, \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u044f \u043d\u0435\u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0441\u0442\u044c.<\/p>\n<\/li>\n
  3. \n
    \u0421\u0434\u0432\u0438\u0433 \u0432\u043b\u0435\u0432\u043e + XOR (x << 17): \u0424\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u0442 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0438 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u0435\u0442 \u043f\u043e\u043b\u043d\u043e\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u0448\u0438\u0432\u0430\u043d\u0438\u0435 \u0431\u0438\u0442\u043e\u0432. \u0427\u0438\u0441\u043b\u0430 13, 7, 17 \u043f\u043e\u0434\u043e\u0431\u0440\u0430\u043d\u044b \u044d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u043e \u0434\u043b\u044f \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430.<\/p>\n<\/li>\n<\/ol>\n
    \u041a\u043b\u044e\u0447\u0435\u0432\u043e\u0435 \u043f\u0440\u0435\u0438\u043c\u0443\u0449\u0435\u0441\u0442\u0432\u043e \u2014 \u0432\u0441\u0435\u0433\u043e 3 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043d\u0430 \u0447\u0438\u0441\u043b\u043e, \u0447\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0435\u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u044b\u043c \u2014 O(1) \u043d\u0430 \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044e \u0447\u0438\u0441\u043b\u0430.<\/p>\n
    \u0414\u043b\u044f \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 state \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043d\u0430\u043f\u0438\u0448\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u0442\u0430\u0439\u043c\u0441\u0442\u0435\u043c\u043f\u0430 \u0432 \u043c\u0438\u043a\u0440\u043e\u0441\u0435\u043a\u0443\u043d\u0434\u0430\u0445:<\/p>\n
    uint64_t get_seed() {     struct timeval tv;     gettimeofday(&tv,NULL);     return tv.tv_sec*(uint64_t)1000000+tv.tv_usec; } <\/code><\/pre>\n
    \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0434\u043b\u044f \u043f\u043e\u043b\u043d\u043e\u0442\u044b \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0434\u043b\u044f \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u043b\u0430\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0438 \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044e \u043f\u043e \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0443:<\/p>\n
    double rand_double(uint64_t *state) {     return (xorshift64(state) >> 11) * (1.0 \/ (UINT64_C(1) << 53)); } <\/code><\/pre>\n
    \u0414\u0430\u043d\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0432\u043e\u0437\u0432\u0440\u0430\u0442\u0438\u0442 \u0447\u0438\u0441\u043b\u043e \u0432 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0435 [0.0, 1.0)<\/code>. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u043c 64-\u0431\u0438\u0442\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0438 \u0441\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u043d\u0430 11 \u0431\u0438\u0442 \u0432\u043f\u0440\u0430\u0432\u043e. \u042d\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0447\u0442\u043e\u0431\u044b \u043e\u0442\u0431\u0440\u043e\u0441\u0438\u0442\u044c \u043c\u043b\u0430\u0434\u0448\u0438\u0435 \u0431\u0438\u0442\u044b. \u0412 \u0438\u0442\u043e\u0433\u0435 \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f 53 \u0431\u0438\u0442\u0430. \u041f\u043e\u0441\u043b\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c 1.0 \/ (UINT64_C(1) << 53)<\/code> (UINT64_C(1) << 53 = 2\u2075\u00b3 = 9,007,199,254,740,992.<\/code>). \u0412 \u0438\u0442\u043e\u0433\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0448\u0430\u0433 \u043c\u0435\u0436\u0434\u0443 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 double: 1.0 \/ 2\u2075\u00b3 \u2248 1.110223e-16. \u0418 \u043f\u043e\u0434 \u043a\u043e\u043d\u0435\u0446 \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0430\u0435\u043c 53 \u0431\u0438\u0442\u0430 \u043d\u0430 \u044d\u0442\u043e\u0442 \u0441\u0430\u043c\u044b\u0439 \u0448\u0430\u0433.<\/p>\n
    \n
    \u0415\u0441\u043b\u0438 \u0432\u044b \u0437\u0430\u0434\u0430\u043b\u0438\u0441\u044c \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u043c, \u043f\u043e\u0447\u0435\u043c\u0443 \u0438\u043c\u0435\u043d\u043d\u043e 53 \u0431\u0438\u0442\u0430 \u2014 \u0442\u043e \u0432 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u0435 IEEE 754 \u0442\u0438\u043f double \u0438\u043c\u0435\u0435\u0442 53 \u0431\u0438\u0442\u0430 \u043c\u0430\u043d\u0442\u0438\u0441\u0441\u044b. \u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0447\u0438\u0441\u043b\u0430 \u0434\u0432\u043e\u0439\u043d\u043e\u0439 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438: \u0437\u043d\u0430\u043a \u2014 1 \u0431\u0438\u0442, \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u2014 11 \u0431\u0438\u0442, \u043c\u0430\u043d\u0442\u0438\u0441\u0441\u0430 \u2014 52+1 \u0431\u0438\u0442.<\/p>\n<\/blockquote>\n
    \u0418 \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0432 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0435:<\/p>\n
    uint64_t rand_range(uint64_t *state, uint64_t min, uint64_t max) {     return min + xorshift64(state) % (max - min + 1); } <\/code><\/pre>\n
    \u041e\u043d \u0431\u0443\u0434\u0435\u0442 \u0443\u0436\u0435 \u043f\u043e\u043f\u0440\u043e\u0449\u0435: xorshift64(state) \u0434\u0430\u0451\u0442 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e. \u0427\u0435\u0440\u0435\u0437 % (max \u2014 min + 1)<\/code> \u0443\u0437\u043d\u0430\u0435\u043c \u043e\u0441\u0442\u0430\u0442\u043e\u043a \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 \u0434\u043b\u0438\u043d\u0443 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0430, \u0438 \u043f\u0440\u0438\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043a \u0438\u0442\u043e\u0433\u043e\u0432\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 min.<\/p>\n
    \u0418 \u0432 \u0438\u0442\u043e\u0433\u0435 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0440\u0430\u0431\u043e\u0442\u044b:<\/p>\n
    xorshift64 random number: 8549869788877919663 # \u0421\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e xorshift64 random num from 10 to 100: 72 # \u0421\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0432 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0435 xorshift64 double random number: 0.461347 # \u0421\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0435 \u0434\u0440\u043e\u0431\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e <\/code><\/pre>\n
    \u276f \u0413\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b xoshiro256pp<\/h3>\n
    \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u043c \u043a \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u043e\u043c\u0443, \u043d\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u043c\u0443 \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440\u0443 \u043f\u0441\u0435\u0432\u0434\u043e\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. \u0412 \u043e\u0442\u043b\u0438\u0447\u0438\u0438 \u043e\u0442 xorshift, \u044d\u0442\u043e\u0442 \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u0443\u0436\u0435 \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442\u044c \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0442\u0435\u0441\u0442\u044b.<\/p>\n
    \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0440\u0430\u0437\u0431\u0435\u0440\u0435\u043c \u043a\u043e\u0434:<\/p>\n
    typedef struct {     uint64_t s[4]; } xoshiro256pp_state;   static inline uint64_t rotl(const uint64_t x, int k) {     return (x << k) | (x >> (64 - k)); }  uint64_t xoshiro256pp_next(xoshiro256pp_state *state) {     uint64_t *s = state->s;     uint64_t result = rotl(s[0] + s[3], 23) + s[0];      uint64_t t = s[1] << 17;     s[2] ^= s[0];     s[3] ^= s[1];     s[1] ^= s[2];     s[0] ^= s[3];     s[2] ^= t;     s[3] = rotl(s[3], 45);      return result; }  void xoshiro256pp_init(xoshiro256pp_state *state, uint64_t seed) {     uint64_t tmp = seed;     for (int i = 0; i < 4; i++) {         tmp ^= tmp >> 30;         tmp *= 0xbf58476d1ce4e5b9;         tmp ^= tmp >> 27;         tmp *= 0x94d049bb133111eb;         tmp ^= tmp >> 31;         state->s[i] = tmp;     } } <\/code><\/pre>\n
      \n
    1. \n
      \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 xoshiro256pp_state<\/code>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043c\u0430\u0441\u0441\u0438\u0432 s \u0438\u0437 \u0447\u0435\u0442\u044b\u0440\u0435\u0445 64-\u0431\u0438\u0442\u043d\u044b\u0445 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b (\u0432\u0441\u0435\u0433\u043e 256 \u0431\u0438\u0442).<\/p>\n<\/li>\n
    2. \n
      \u0424\u0443\u043d\u043a\u0446\u0438\u044f rotl<\/code> \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u0446\u0438\u043a\u043b\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0441\u0434\u0432\u0438\u0433 \u0432\u043b\u0435\u0432\u043e \u0434\u043b\u044f 64-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 x \u043d\u0430 k \u043f\u043e\u0437\u0438\u0446\u0438\u0439. \u042d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0431\u0438\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u044b\u0445\u043e\u0434\u044f\u0442 \u0437\u0430 \u043f\u0440\u0435\u0434\u0435\u043b\u044b \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f, \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044e\u0442\u0441\u044f \u0432 \u043d\u0430\u0447\u0430\u043b\u043e.<\/p>\n<\/li>\n
    3. \n
      \u0424\u0443\u043d\u043a\u0446\u0438\u044f xoshiro256pp_init<\/code> \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440\u0430 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0441\u0438\u0434\u0430 (\u043c\u043e\u0436\u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044e get_seed \u0438\u0437 \u043f\u0440\u043e\u0448\u043b\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u0430). \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0446\u0438\u043a\u043b, \u0447\u0442\u043e\u0431\u044b \u0437\u0430\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u043c\u0430\u0441\u0441\u0438\u0432 s \u0447\u0435\u0442\u044b\u0440\u044c\u043c\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438.<\/p>\n<\/li>\n<\/ol>\n