{"id":271808,"date":"2016-01-09T13:39:02","date_gmt":"2016-01-09T10:39:02","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=271808"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=271808","title":{"rendered":"\u0420\u0430\u0441\u0447\u0435\u0442 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0445 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432 \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0424\u0443\u0440\u044c\u0435-\u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439"},"content":{"rendered":"<p>       \u041f\u0440\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0438 \u0437\u0430\u0434\u0430\u0447 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0442\u043e\u0440\u0438\u043a\u0438 \u0447\u0430\u0441\u0442\u043e \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u0432 \u0440\u0430\u0441\u0447\u0435\u0442\u0435 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432. \u0411\u0438\u043d\u043e\u043c \u041d\u044c\u044e\u0442\u043e\u043d\u0430, \u0442.\u0435. \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/fad\/203\/7ac\/fad2037acc6dff013bb9e1b5307eb82c.png\" alt=\"image\"\/> \u0442\u0430\u043a\u0436\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b. \u0414\u043b\u044f \u0438\u0445 \u0440\u0430\u0441\u0447\u0435\u0442\u0430 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0444\u043e\u0440\u043c\u0443\u043b\u0443, \u0432\u044b\u0440\u0430\u0436\u0430\u044e\u0449\u0443\u044e \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u0447\u0435\u0440\u0435\u0437 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u044b: <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/01d\/df4\/164\/01ddf4164554f2f65f67842dd8ea7dbf.png\" alt=\"image\"\/> \u0438\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u0443\u044e \u0444\u043e\u0440\u043c\u0443\u043b\u0443:<img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/3f1\/8bd\/ee1\/3f18bdee1558db7cb7b6b6c3458cda5f.png\" alt=\"image\"\/> \u0418\u0437 \u0431\u0438\u043d\u043e\u043c\u0430 \u041d\u044c\u044e\u0442\u043e\u043d\u0430 \u0438 \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u043e\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u044f\u0441\u043d\u043e, \u0447\u0442\u043e \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u2014 \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430. <\/p>\n<p>  \u041e\u0434\u043d\u0438\u043c \u0438\u0437 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0445 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0424\u0443\u0440\u044c\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439 \u0438 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0445 \u0424\u0443\u0440\u044c\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439.<\/p>\n<p>  \u041d\u0430\u043b\u0438\u0447\u0438\u0435 \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a, \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0449\u0438\u0445 \u0424\u0443\u0440\u044c\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439 (\u0432\u043e \u0432\u0441\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430\u0445 \u0431\u044b\u0441\u0442\u0440\u044b\u0445 \u0432\u0435\u0440\u0441\u0438\u0439), \u0434\u0435\u043b\u0430\u0435\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u0441\u043b\u043e\u0436\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u0434\u043b\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f.<br \/>  \u0420\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0447\u0430\u0441\u0442\u044c\u044e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u043c \u043a\u043e\u0434\u043e\u043c FFTTools. \u0418\u043d\u0442\u0435\u0440\u043d\u0435\u0442-\u0430\u0434\u0440\u0435\u0441: <a href=\"https:\/\/github.com\/dprotopopov\/FFTTools\">github.com\/dprotopopov\/FFTTools<\/a><br \/>  <a name=\"habracut\"><\/a><\/p>\n<p>  \u041f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u0424\u0443\u0440\u044c\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 f \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0438\u043d\u0442\u0435\u0433\u0440\u0430\u043b\u044c\u043d\u044b\u043c \u0438 \u0437\u0430\u0434\u0430\u0451\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u043e\u0439:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/a78\/401\/195\/a784011956b6daeb35c695fc5036eb50.png\" alt=\"\u041f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u0424\u0443\u0440\u044c\u0435\"\/><\/p>\n<p>  \u0420\u0430\u0437\u043d\u044b\u0435 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438 \u043c\u043e\u0433\u0443\u0442 \u0434\u0430\u0432\u0430\u0442\u044c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f, \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u043e\u0442 \u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u0433\u043e \u0432\u044b\u0448\u0435 \u0432\u044b\u0431\u043e\u0440\u043e\u043c \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430 \u043f\u0435\u0440\u0435\u0434 \u0438\u043d\u0442\u0435\u0433\u0440\u0430\u043b\u043e\u043c, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0437\u043d\u0430\u043a\u0430 \u00ab\u2212\u00bb \u0432 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435 \u044d\u043a\u0441\u043f\u043e\u043d\u0435\u043d\u0442\u044b. \u041d\u043e \u0432\u0441\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u0431\u0443\u0434\u0443\u0442 \u0442\u0435 \u0436\u0435, \u0445\u043e\u0442\u044f \u0432\u0438\u0434 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0444\u043e\u0440\u043c\u0443\u043b \u043c\u043e\u0436\u0435\u0442 \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u044c\u0441\u044f.<\/p>\n<p>  \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0440\u0430\u0437\u043d\u043e\u043e\u0431\u0440\u0430\u0437\u043d\u044b\u0435 \u043e\u0431\u043e\u0431\u0449\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u043f\u043e\u043d\u044f\u0442\u0438\u044f.<\/p>\n<h2>\u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u0424\u0443\u0440\u044c\u0435<\/h2>\n<p>  \u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u0424\u0443\u0440\u044c\u0435 (\u0432 \u0430\u043d\u0433\u043b\u043e\u044f\u0437\u044b\u0447\u043d\u043e\u0439 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u0435 DFT, Discrete Fourier Transform) \u2014 \u044d\u0442\u043e \u043e\u0434\u043d\u043e \u0438\u0437 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439 \u0424\u0443\u0440\u044c\u0435, \u0448\u0438\u0440\u043e\u043a\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c\u044b\u0445 \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u0445 \u0446\u0438\u0444\u0440\u043e\u0432\u043e\u0439 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0441\u0438\u0433\u043d\u0430\u043b\u043e\u0432 (\u0435\u0433\u043e \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044e\u0442\u0441\u044f \u0432 \u0441\u0436\u0430\u0442\u0438\u0438 \u0437\u0432\u0443\u043a\u0430 \u0432 MP3, \u0441\u0436\u0430\u0442\u0438\u0438 \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0439 \u0432 JPEG \u0438 \u0434\u0440.), \u0430 \u0442\u0430\u043a\u0436\u0435 \u0432 \u0434\u0440\u0443\u0433\u0438\u0445 \u043e\u0431\u043b\u0430\u0441\u0442\u044f\u0445, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0445 \u0441 \u0430\u043d\u0430\u043b\u0438\u0437\u043e\u043c \u0447\u0430\u0441\u0442\u043e\u0442 \u0432 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u043c (\u043a \u043f\u0440\u0438\u043c\u0435\u0440\u0443, \u043e\u0446\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u0430\u043d\u0430\u043b\u043e\u0433\u043e\u0432\u043e\u043c) \u0441\u0438\u0433\u043d\u0430\u043b\u0435. \u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u0424\u0443\u0440\u044c\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0432\u0445\u043e\u0434\u0430 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e. \u0422\u0430\u043a\u0438\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0447\u0430\u0441\u0442\u043e \u0441\u043e\u0437\u0434\u0430\u044e\u0442\u0441\u044f \u043f\u0443\u0442\u0451\u043c \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u0438\u0437\u0430\u0446\u0438\u0438 (\u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0438\u0437 \u043d\u0435\u043f\u0440\u0435\u0440\u044b\u0432\u043d\u044b\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439). \u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0424\u0443\u0440\u044c\u0435 \u043f\u043e\u043c\u043e\u0433\u0430\u044e\u0442 \u0440\u0435\u0448\u0430\u0442\u044c \u0434\u0438\u0444\u0444\u0435\u0440\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0432 \u0447\u0430\u0441\u0442\u043d\u044b\u0445 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u043d\u044b\u0445 \u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u043a\u0430\u043a \u0441\u0432\u0451\u0440\u0442\u043a\u0438. \u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0424\u0443\u0440\u044c\u0435 \u0442\u0430\u043a\u0436\u0435 \u0430\u043a\u0442\u0438\u0432\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0432 \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0435, \u043f\u0440\u0438 \u0430\u043d\u0430\u043b\u0438\u0437\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0440\u044f\u0434\u043e\u0432. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u043c\u043d\u043e\u0433\u043e\u043c\u0435\u0440\u043d\u044b\u0435 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0424\u0443\u0440\u044c\u0435.<\/p>\n<h2>\u0424\u043e\u0440\u043c\u0443\u043b\u044b \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0445 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439<\/h2>\n<p>  \u041f\u0440\u044f\u043c\u043e\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/comment_images\/0fe\/66e\/fd0\/0fe66efd0c6151565e3a6a3bc3c5a888.png\" alt=\"image\"\/><\/p>\n<p>  \u041e\u0431\u0440\u0430\u0442\u043d\u043e\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/de5\/663\/408\/de56634082741492c8b949377fc3288c.png\" alt=\"image\"\/><\/p>\n<p>  \u0414\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u0424\u0443\u0440\u044c\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u043c \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0438\u0442 \u0432\u0435\u043a\u0442\u043e\u0440 \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043e\u0442\u0441\u0447\u0451\u0442\u043e\u0432 \u0432 \u0432\u0435\u043a\u0442\u043e\u0440 \u0441\u043f\u0435\u043a\u0442\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u043e\u0442\u0441\u0447\u0451\u0442\u043e\u0432 \u0442\u043e\u0439 \u0436\u0435 \u0434\u043b\u0438\u043d\u044b. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043e \u043a\u0430\u043a \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043d\u0430 \u0432\u0435\u043a\u0442\u043e\u0440:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/c7d\/125\/fae\/c7d125fae17a50b837e5e3e382d230fe.png\" alt=\"image\"\/><\/p>\n<h2>\u0424\u0443\u0440\u044c\u0435-\u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0441\u0432\u0451\u0440\u0442\u043a\u0438<\/h2>\n<p>  \u041e\u0434\u043d\u0438\u043c \u0438\u0437 \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0441\u0432\u043e\u0439\u0441\u0442\u0432 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439 \u0424\u0443\u0440\u044c\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043a\u043e\u0440\u0440\u0435\u043b\u044f\u0446\u0438\u0438 \u0434\u0432\u0443\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0451\u043d\u043d\u044b\u0445, \u043b\u0438\u0431\u043e \u043d\u0430 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u043c \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u0435 (\u043f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u044b), \u043b\u0438\u0431\u043e \u043d\u0430 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u043c \u043a\u043e\u043b\u044c\u0446\u0435 (\u043f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0445 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439).<\/p>\n<p>  \u0418 \u0445\u043e\u0442\u044f \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0435 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 \u043f\u0440\u0438\u0441\u0443\u0449\u0438 \u043c\u043d\u043e\u0433\u0438\u043c \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u043c \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f\u043c, \u0434\u043b\u044f \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f, \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u0432\u0451\u0440\u0442\u043a\u0438, \u0441\u043e\u0433\u043b\u0430\u0441\u043d\u043e \u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u043d\u0430\u043c\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044e, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430  <\/p>\n<blockquote><p>F\u0445G = BFT ( FFT(F)*FFT(G) )<\/p><\/blockquote>\n<p>  \u0413\u0434\u0435  <\/p>\n<ul>\n<li>FFT \u2013 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u0440\u044f\u043c\u043e\u0433\u043e \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0424\u0443\u0440\u044c\u0435<\/li>\n<li>BFT \u2013 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0424\u0443\u0440\u044c\u0435<\/li>\n<\/ul>\n<p>  \u041f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043b\u0435\u0433\u043a\u043e \u2013 \u044f\u0432\u043d\u043e \u043f\u043e\u0434\u0441\u0442\u0430\u0432\u0438\u0432 \u0432 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u0424\u0443\u0440\u044c\u0435-\u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439 \u0438 \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0432 \u043f\u043e\u043b\u0443\u0447\u0438\u0432\u0448\u0438\u0435\u0441\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u044b <\/p>\n<h2>\u0411\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b<\/h2>\n<p>  \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u043e\u043b\u0438\u043d\u043e\u043c F(x)=1+x \u0438 \u0435\u0433\u043e \u0441\u0432\u0451\u0440\u0442\u043a\u0443 \u0441 \u0441\u0430\u043c\u0438\u043c \u0441\u043e\u0431\u043e\u0439 n \u0440\u0430\u0437<br \/>  Fx..xF = SUM \u0421( i, n-1 )*x^i = BFT ( FFT(F)*&#8230;*FFT(F) )<br \/>  \u0422\u043e \u0435\u0441\u0442\u044c \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0421( i, n-1 ) \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u044b \u0438\u0437 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430 (1+x)^(n-1)<\/p>\n<h2>\u041f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u0443\u0435\u043c:<\/h2>\n<p>  <\/p>\n<pre><code class=\"cs\">using System; using System.Drawing; using System.Linq; using System.Numerics;  namespace FFTTools {     public class BinomialBuilder : BuilderBase, IBuilder     {         \/\/\/ &lt;summary&gt;         \/\/\/     Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources.         \/\/\/ &lt;\/summary&gt;         public void Dispose()         {         }          public static void GetLongs(long[] array, long x = 1)         {             if (array.Length &gt; 0) array[0] = 1;             for (var i = 1; i &lt; array.Length; i++)                 for (var j = i; j-- &gt; 0;)                     array[j + 1] += x*array[j];         }          public static void GetDoubles(double[] array, double x = 1.0)         {             var complex = new Complex[array.Length];             if (array.Length &gt; 0) complex[0] = Complex.One;             if (array.Length &gt; 1) complex[1] = x;             if (array.Length &gt; 0)             {                 Fourier(complex, FourierDirection.Forward);                 complex = complex.Select(                     value =&gt; Complex.Pow(value, array.Length - 1)\/array.Length).ToArray();                 Fourier(complex, FourierDirection.Backward);             }             var index = 0;             foreach (var value in complex) array[index++] = value.Magnitude;         }          public Bitmap ToBitmap(Bitmap source)         {             throw new NotImplementedException();         }     } } <\/code><\/pre>\n<h2>\u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c:<\/h2>\n<p>  <\/p>\n<pre><code class=\"cs\">using System; using System.Linq; using Microsoft.VisualStudio.TestTools.UnitTesting;  namespace FFTTools.UnitTest {     [TestClass]     public class BinomialUnitTest     {         [TestMethod]         public void BinomialTestMethod()         {             const int count = 10;             var doubles = new double[count];             var longs = new long[count];             BinomialBuilder.GetLongs(longs);             BinomialBuilder.GetDoubles(doubles);             Console.WriteLine(                 string.Join(Environment.NewLine,                     longs.Zip(doubles, (x, y) =&gt; string.Format(&quot;{0} - {1} = {2}&quot;, x, y, x - y))) +                 Environment.NewLine);             Assert.IsTrue(doubles.Zip(longs, (x, y) =&gt; x - y).All(x =&gt; Math.Abs(x) &lt; 0.001));         }     } } <\/code><\/pre>\n<h2>\u0417\u0430\u0447\u0435\u043c?<\/h2>\n<p>  \u041f\u0440\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0442\u0440\u0435\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430 \u041f\u0430\u0441\u043a\u0430\u043b\u044f \u0442\u0440\u0443\u0434\u043e\u0451\u043c\u043a\u043e\u0441\u0442\u044c \u0438\u043c\u0435\u0435\u0442 \u043e\u0446\u0435\u043d\u043a\u0443 O(n^2). <br \/>  \u041f\u0440\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0431\u044b\u0441\u0442\u0440\u044b\u0445 \u0424\u0443\u0440\u044c\u0435-\u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439 \u0442\u0440\u0443\u0434\u043e\u0451\u043c\u043a\u043e\u0441\u0442\u044c \u0438\u043c\u0435\u0435\u0442 \u043e\u0446\u0435\u043d\u043a\u0443 O(n*log n).               <\/p>\n<div class=\"clear\"><\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"http:\/\/habrahabr.ru\/post\/274729\/\"> http:\/\/habrahabr.ru\/post\/274729\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>       \u041f\u0440\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0438 \u0437\u0430\u0434\u0430\u0447 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0442\u043e\u0440\u0438\u043a\u0438 \u0447\u0430\u0441\u0442\u043e \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u0432 \u0440\u0430\u0441\u0447\u0435\u0442\u0435 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432. \u0411\u0438\u043d\u043e\u043c \u041d\u044c\u044e\u0442\u043e\u043d\u0430, \u0442.\u0435. \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/fad\/203\/7ac\/fad2037acc6dff013bb9e1b5307eb82c.png\" alt=\"image\"\/> \u0442\u0430\u043a\u0436\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b. \u0414\u043b\u044f \u0438\u0445 \u0440\u0430\u0441\u0447\u0435\u0442\u0430 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0444\u043e\u0440\u043c\u0443\u043b\u0443, \u0432\u044b\u0440\u0430\u0436\u0430\u044e\u0449\u0443\u044e \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u0447\u0435\u0440\u0435\u0437 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u044b: <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/01d\/df4\/164\/01ddf4164554f2f65f67842dd8ea7dbf.png\" alt=\"image\"\/> \u0438\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u0443\u044e \u0444\u043e\u0440\u043c\u0443\u043b\u0443:<img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/3f1\/8bd\/ee1\/3f18bdee1558db7cb7b6b6c3458cda5f.png\" alt=\"image\"\/> \u0418\u0437 \u0431\u0438\u043d\u043e\u043c\u0430 \u041d\u044c\u044e\u0442\u043e\u043d\u0430 \u0438 \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u043e\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u044f\u0441\u043d\u043e, \u0447\u0442\u043e \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u2014 \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430. <\/p>\n<p>  \u041e\u0434\u043d\u0438\u043c \u0438\u0437 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0445 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0424\u0443\u0440\u044c\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439 \u0438 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u0445 \u0424\u0443\u0440\u044c\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439.<\/p>\n<p>  \u041d\u0430\u043b\u0438\u0447\u0438\u0435 \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a, \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0449\u0438\u0445 \u0424\u0443\u0440\u044c\u0435 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439 (\u0432\u043e \u0432\u0441\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430\u0445 \u0431\u044b\u0441\u0442\u0440\u044b\u0445 \u0432\u0435\u0440\u0441\u0438\u0439), \u0434\u0435\u043b\u0430\u0435\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u0441\u043b\u043e\u0436\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u0434\u043b\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f.<br \/>  \u0420\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0447\u0430\u0441\u0442\u044c\u044e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u043c \u043a\u043e\u0434\u043e\u043c FFTTools. \u0418\u043d\u0442\u0435\u0440\u043d\u0435\u0442-\u0430\u0434\u0440\u0435\u0441: <a href=\"https:\/\/github.com\/dprotopopov\/FFTTools\">github.com\/dprotopopov\/FFTTools<\/a>  <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-271808","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/271808","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=271808"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/271808\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=271808"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=271808"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=271808"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}