Многочлены: Горнер, деление с остатком, НОД, умножение и метод Карацубы — авторское изложение

ru · official · sha256:126c0351e02628d259c554e9de05fa5a46ee373b5340d0bcd07f5ecf0b81c087

§1. Многочлен, степень, канон и кольцо коэффициентов Многочлен одной переменной над полем есть конечная последовательность коэффициентов, занумерованных местами от нуля; коэффициент при месте k стоит при переменной в степени k. Степень многочлена — наибольшее место с ненулевым коэффициентом; у нулевого многочлена степень не определена, и это соглашение обязано называться, иначе оценки вида «степень меньше степени делителя» бессмысленны для нуля. Место и степень — разные вещи. Многочлен, предъявленный как 0·x² + 2x + 1, имеет три МЕСТА и степень один. Канон — представление, в котором старший коэффициент отличен от нуля. Различие не косметическое: степень произведения равна сумме степеней только в каноне. Кольцо коэффициентов существенно. Над ПОЛЕМ деление с остатком определено всегда: старший коэффициент делителя обратим. Над кольцом без деления — например, над целыми — деление с остатком в общем виде невозможно, и требуется псевдоделение с домножением делимого на степень старшего коэффициента делителя. Настоящее изложение всюду работает над полем и говорит об этом. Наибольший общий делитель многочленов определён с точностью до ненулевого множителя. Поэтому его нормируют: старший коэффициент делают единицей. Без нормировки утверждение о единственности ложно, и сравнение результатов двух вычислений невозможно. Тождество Безу для многочленов: для любых A и B, не равных нулю одновременно, существуют многочлены X и Y, при которых A·X + B·Y = НОД(A, B), причём степень X меньше степени B, делённой на степень наибольшего общего делителя, и симметрично для Y.

Ссылаются нормы: AnswersHere, f-0a1e0b1baeabbaa42ee8744a, f-10bc7fd5e3f16aa5031bcb91, f-1367c553c18b0f876c907ce6, f-1d3803e6afc69db4414731f7, f-25bc4633f6592e56b40f5bf5, f-331d103ec360ee5d7ea6edad, f-38351df3f8b9f375c3e76f08, f-4d8530cf7987f4687efc2a09, f-57aa14b7df9bb45aa6e575d5, f-59835d491b8e8fd521bd6e7e, f-5b11df1043d35f4fa51d6adb, f-5d7a1307c97c6cc4cd3bf50e, f-61b5df3a9c4f8079036fb293, f-6727ad9e472f38f934884077, f-69f86138460b704821842bd8, f-721a2bcb070e536322f4e58f, f-8d1de37c06a665f64903b9d6, f-90c9234d0a7da9d498ba8ed2, f-95488864e66017e067306f99, f-9f626ee3660ea23326246e24, f-a2695617d94e33ed609a7b26, f-a3711b339af3414880d368c7, f-aa06bbb3727a30419b4958eb, f-bab1a570053e66519f7ac9bf, f-cbdeb1c71446d849d8cf7d77, f-d074ac91c74f4e242be0783f, f-d1bd112179be640bc50e3b1e, f-d93dbe5315d8bbffc9d1fd04, f-de2313fcd7dba518bfa571a4, f-e52c557942b060aea732e336, f-e958214baf4cdaf5c8cc2e5b, f-eef2fc25de2e49ff8a83ae2b, f-f3a5fe571f830776a730bed0

ru · official · sha256:240a06914634ce4195f3a291f2213829ee5afdf7c5baf244620f36b7e59930b1

§2. Схема Горнера Задача: по многочлену и числу вычислить значение многочлена в этой точке. Вариант — накопитель, проходящий коэффициенты от старшего к младшему. Накопитель начинается со старшего коэффициента. На каждом шаге накопитель умножается на точку и к нему прибавляется очередной коэффициент. По исчерпании коэффициентов накопитель есть значение многочлена. Инвариант: после обработки первых k коэффициентов накопитель равен значению многочлена, составленного из этих коэффициентов. Он же объясняет, почему прямое вычисление степеней не нужно. Число умножений равно степени, число сложений — тоже. Это ОПТИМАЛЬНО среди методов, использующих только сложения и умножения без предварительной обработки коэффициентов, — утверждение источника, доказательство остаётся в нём. Схема Горнера даёт и частное от деления на x минус точка: промежуточные значения накопителя суть коэффициенты этого частного, а последнее значение — остаток. Это и есть теорема Безу о делении на линейный двучлен, и такое двойное употребление схемы обязано называться. Крайние случаи: многочлен нулевой степени — цикл не выполняется, значение равно единственному коэффициенту; точка, равная нулю, — значение равно свободному члену. Тот же приём вычисляет значение числа по его записи в позиционной системе; общее изложение вынесено в пакет школьной арифметики.

Ссылаются нормы: f-02bf5fc489fc606fb29600a4, f-0461639508869aeaf2c937ae, f-0914b3674f8c64d1b66f5ebc, f-10415df14cdd9d50b5b37565, f-1437396908a20938db68465a, f-17052ff4792d99711880f428, f-17d5638c49b9592abf245402, f-1bbca3b2b3f1655d9d609b19, f-1e7743b0c0397f14857c86ef, f-1eb486b51506ef3690b0b8c8, f-271e3e4cdab8f56431288ed6, f-28ef9f0874c90fe0ac59daaa, f-2a0652d0c846f88ad7d3da91, f-2b55a11214aab3cb6654e157, f-2cd1d417e959e5b86c99e0c4, f-31550b09a4a8fa3dac8c30cf, f-3240922ef6bc201647f2009a, f-3661537dc9acc8598cccb150, f-38d76a96252c4c73c2b47915, f-3d9a466facc643888a8c01f8, f-3e79b6b91e1b32d51636d5bb, f-42999da0868312f4e6470167, f-4a88e1fda00657f0cb5592f8, f-4bf19ac2cbbd3fed3c86e99b, f-4d483766b10e1af3b715efbc, f-4e66e4b155ac22ef79b9fb1c, f-4ec70c5c430dc9869263b32f, f-518b6aa73f2e63360d7b53f5, f-529d3ba999b6cfe5a6582ba3, f-56f4b25dbb63849fb3bd6b25, f-591780d7d57c449e7dfb2a63, f-5a3f1f7f7e61cab3c83fdc97, f-5b0102cbac812506fdaac07f, f-5c2a5021d73a0dbbef535254, f-5ff213fcab9aed12749c7a56, f-6148b6d27057a236aadc70e1, f-635756949c1614a0b64cefec, f-6eae963597ed2a6b3fc4c990, f-7062f10acec90406f95d78f9, f-70c2867bcc0b55129bc90ec3, f-7175b024918644f72ac063d3, f-7988cccc4da2195fc1ee5ce7, f-87790148df8e10b95dfa1cdf, f-88893442fb1f874ae2df6111, f-91ae57811d243e8ae1ae4a7f, f-91ee76eea8cee25051a1d09f, f-95373f394d5df2cd716bfffe, f-9f5804a7500af6b1b11cdd6d, f-a179070f1f72582199162e49, f-ac4ee7d64207cc129dcb18a1, f-ad1719f11b66eba63db42071, f-af98c745d6570bd4660bb6f3, f-b0ab908a3169f1ecc62dbcc0, f-b221ba03e3777913f5d456af, f-b70e9e786f50303e187d5629, f-b89cb08ba5f36c68462fabdd, f-ba5f0569f0194db8ba5d52cd, f-bf825691498d1a1c2cd6e627, f-c1487c3e7ac93e8ae7385146, f-c27738e37c9d5e952e2f9f2d, f-c63b9ccb6316fa79d415d22d, f-c6ff6848755da2b8d9f48a48, f-ccb9bc96c4f9a4e22241077f, f-cd520dbaf86238deb43108a7, f-d02c57157c316f5d98f939a6, f-d686259a27161f8a042c950d, f-d73e322c8c0d4982a6d7be2f, f-d8265bf6e6524ce07e217e8a, f-d88a5684b7d2e2812bc8c4c4, f-daf3f7d9b5e29af36fe70993, f-db989d379e868ae145d45655, f-dd9bd8eabea6fd394073ff88, f-dfaba9ae44715877b1faf5e7, f-e2e16d74f754efaead74e4f4, f-ea71438c99bc1ca045d8d08b, f-eb42e6f4f636e7004b302763, f-ec5173c8393adb83e0232065, f-ed0745a2e4c01de3d07fcfa9, f-ee897cd5c44a36edbd6f24ce, f-efec930d9e633bc3da8e784f, f-f47a405b8646be085e4812a0, f-fd78784227e6f1a3fe2a55c5

ru · official · sha256:189fa20068ada60e144bf3aeb3478329a74c0c20d21aac685f479cd9208115a7

§3. Деление многочленов с остатком Задача: по делимому A и ненулевому делителю B над полем найти частное Q и остаток R, для которых A = Q·B + R и степень R меньше степени B либо R нулевой. Вариант — школьный столбиком: пока степень текущего остатка не меньше степени делителя, из него вычитается делитель, умноженный на одночлен, обнуляющий старший член. Одночлен вычисляется как отношение старших коэффициентов, умноженное на переменную в степени, равной разности степеней. Отношение существует потому, что старший коэффициент делителя обратим в поле — здесь и нужна принадлежность коэффициентов полю. Инвариант: A равно сумме произведения накопленного частного на делитель и текущего остатка. Мера убывания — степень текущего остатка: она строго убывает, потому что старший член обнуляется вычитанием. Единственность частного и остатка: если бы существовали две пары, их разности дали бы ненулевой многочлен степени меньше степени B, кратный B, чего быть не может. Утверждение принадлежит источнику. Крайние случаи: степень делимого меньше степени делителя — цикл не выполняется, частное нулевое, остаток равен делимому; нулевой делитель — задача не поставлена, и описание отвергает вход. Исполнимая реализация в репозитории — `calc.polynomials_q`: деление с остатком над ℚ.

Ссылаются нормы: f-0377cb0daa6c1bf5dc5b390a, f-096fef7911c9451a67f6e046, f-0b810c9e25cc2acba9755a12, f-0bc6ab06ff5aaa0b447e5df0, f-0c79ba2cc1e2e8acf7c9a406, f-0e9f3647496b9b7f25ef8fb1, f-12c9cba2083baaeaebd7d703, f-1a476ecafc5bd11fee67d211, f-1cb05d6362e18b4b4df7cd59, f-1ccdaac4003baca6069bfd38, f-22ab014f4aec788b55ccd27b, f-247e1780b6611c83e9044fb8, f-2bdd0621a940933d58861069, f-2d6864a1f5e87178a6007aeb, f-32c5cc3281da31c93af3000f, f-32d43e1fc6a7d222386314bc, f-36b539b0f35db709f9a7674d, f-3bc397bab1fd515f20fff8f8, f-3d5ba10fd56785523e8f6a7d, f-3e8d4b1e1c9d31b10a2a44f3, f-455da37a7abf0a374cff1d36, f-45703a52f5ab29a84cef8a70, f-480ef5790a47a9fe69ef32ea, f-4cfbf24748fa8b87894c000a, f-4dfe41aa889a3fdd4d9393c9, f-4e541fdb6d3e348aa4e7ebff, f-4e93b99a40da508710527844, f-4ed3e445769a2c406a36d538, f-550ba8daa4f9513b193646cd, f-55762b5563ac1680d8101971, f-55d85ff94d8b25d76b37aa09, f-5841fb7b3743a9149a306e22, f-59dbdb52d6b0b9672fef9654, f-63d43701321785ddfa33711a, f-63ef3f03326c0dd199c7761a, f-643b7c311dbba08293792ebd, f-649c66aa40cb13f3ee1efa8f, f-6806fa9c5dd9662df00ea1ed, f-705252e3a300399da9754dd2, f-70a30860da6134288099d9ba, f-70ed73d03853a568ab19bd5e, f-73642df4321a22df5064ef0e, f-74fafbbd34c45f80a2f9e367, f-78adfa0da12909aea3802757, f-78e22135225b083aa877faf9, f-7a8aa00250aad5e7eec10e91, f-8c0470f9c04282f6bf5165e8, f-8d220e94d215c152eafc91e2, f-8fbb8eed2a3627c2c479f5f9, f-90fcaed385145b538b8f3267, f-91091e41d489d27e7697fa8c, f-930543eec07dfda0782b1acd, f-960e3da3a5f301f658921a94, f-9a1de7523083204e3aad107d, f-9b9fc935562467cf218ae833, f-a2e2d8330935af023795ab55, f-a3b292cf832901ed0015158a, f-a5271d9297ea507678fa88e6, f-ad585d4ee431d76cfd16b745, f-b0f6b86aee943b6092e03b73, f-b6c82153c94b2360bbbd767b, f-b89f7134e2fb99480e31ba3b, f-bad07dd33434016ad3ce4010, f-bcb66afec8bb4276890f4d0c, f-bd0c2b10a9d03c6c066f6b69, f-be9bb4d5e956a9cd7e44b420, f-c62238d3c1b571c004e608fe, f-c7f8335d55c7d8eaa2fcbc6c, f-c9a807df4e135bd8d2380b25, f-cbbcf2637d7fba32c782743d, f-cc81a2c4355a4a5e37df0b9f, f-cd0608ff9d1b1ad22fc7f45e, f-cd3657ab0f948aa9d84e4655, f-ce81ef76a17c1eca363c5b93, f-d0d97af4c4eac235621fe9fd, f-d1e2bdad652b19f200a32bd0, f-d5f6d90262fb591a6cffc449, f-d6ae182b4f0c7fedec7a8f44, f-dc3e37082b2a52fad50ada97, f-e3ca21b6779168cc20f51ff8, f-e44ee01d026ab78a2400015b, f-e4abf1a834bf9b354ba7b6aa, f-e78bd39c986dda745dd285ee, f-e8afb2d5d0f4a184adc6862d, f-e91db10910a68c84a3f3516c, f-e99f0e4ddec858f4040d0fa4, f-f05f5c330a6dfdf145e9dff6, f-f38959162b5d18b6503af8be, f-f391c2d1fd208966a28d15bc, f-f8deb7220934e5fb9a866a92

ru · official · sha256:85501b19624dd728d38a4041220c1f48199dab50674ac661ebaea08d357bd0f9

§4. Наибольший общий делитель многочленов Задача: по двум многочленам, не равным нулю одновременно, найти их нормированный наибольший общий делитель. Вариант — алгоритм Евклида по остаткам от деления. Пара (A, B) заменяется парой (B, остаток от деления A на B), пока второй элемент не станет нулевым. Первый элемент последней пары и есть наибольший общий делитель; он нормируется делением на свой старший коэффициент. Основание шага — то же, что у целых чисел: множество общих делителей пары не меняется при замене A на остаток, потому что A = Q·B + R. НОРМИРОВКА обязательна: без неё результат определён лишь с точностью до ненулевого множителя, и два вычисления могут дать формально разные ответы. Это самое частое умолчание изложений. Мера убывания — степень второго элемента пары. Крайний случай: один из многочленов нулевой — ответом служит нормированный второй. Рост коэффициентов при точной арифметике над рациональными числами может быть значительным; субрезультантные варианты его ограничивают и составляют другие описания. Исполнимая реализация в репозитории — `calc.polynomials_q`.

Ссылаются нормы: f-01a6d7b77fa2103492b03f55, f-024318f2c3b9fd28ae870da9, f-02ba016db48a5d2087cbc865, f-039848788e8b19e5f57e7fe4, f-05e885f059223cc55ae5c81a, f-0682f1d12c78486ba91756c1, f-0a100afd0b2fb398ddb5f0cf, f-0ceaf5131c50718e577f9ace, f-0e4a28187dfa399c8b37dcff, f-0f79128380115087c41c632f, f-190a932edd66e2ce3f35ff0a, f-21aca1778a54f9d51ac2396d, f-22c09ca9de4c8022bdbc1e59, f-26f43f0d1646ae83ff44ac38, f-2dd707865399bc3a767d909b, f-2ea570b68940faf8b909fbb0, f-2f98d6fb45726650a4dfa328, f-31c1568fc1d9d9fb5ac63506, f-3a17325255ef192957c1d2c9, f-3acf10b1ef29b3b73b53c9b6, f-3b20c9e7dd1803b39d883387, f-3b3f95aaed0a7a98a8c44ae2, f-46e8753192afc721021b1bdb, f-47cf5dbe11d9614515d17c88, f-4841790b4f1ae24a1291b7d3, f-49750a46e92ee4398104d283, f-4aacb18528db224d44d481c6, f-4cd4bf9eff98fbb7e00824d4, f-4d901ae72b7f970b3f28aff5, f-4f3d368ecb3baf8d6e01dce3, f-4fe1b32c961fdf934543670b, f-5019b3ae9e6efd19b0b3a924, f-558e6dba4aa8c5edcb4dd8bb, f-567bdaf100f058d3afc4e488, f-5920b092705c1d7810284280, f-592f358525e49faacab7f68f, f-5bf85bca199b177643d3a6ba, f-5d06d587e85a24138501d4da, f-5ee03853fc2db1637a0e2912, f-5fc0336362755d4342c32abc, f-5ffb70aef1e592c7665530d9, f-66213c71d611d62acd9ba969, f-6659f848e8d9546e5aa05925, f-67af6b9fd17ae2e95a430d81, f-6c9842a3dddf0b8745a8bd79, f-706e8f5f2cb0564da7c10999, f-737be00309ed243432979e36, f-794a246c738ca075cb21ad61, f-7b2e1649d869bf816d8b8564, f-7c71bb0ddfca1a12ba542d94, f-80d9238c4c570e8bbca10055, f-815cf3e72840096042e64e32, f-819445c06f6e4b148567585f, f-845a2e263fb5069959e2539a, f-84b1ac83a9b1ad92e190b138, f-88a94c018771a1761ef8a0dd, f-89585921df30ce0c2813da5d, f-8c305ba4c352b5efde1b0592, f-927421fcb46fef4051a6e36c, f-9506fb609a2be2d7c7813765, f-95679a06e7cab09c22f521bb, f-9838cf84fcd002c4452192f0, f-992a31dfc71a16bf346a94cc, f-9cdef113e3bf5388d7196742, f-a25ce5ff05524b51f88857d3, f-a31776c0d6ee10f20525a789, f-a56ef491d1256c1abefbaf58, f-a7a4297e6f4bafec13154c55, f-a82d60b0b18571395d1a9b2e, f-b2255cf363b90e8a3b5c5d7f, f-b34fbb8b9aa634cd2f34ccba, f-b50204dbe38cd9c43e6b3bcf, f-b99ce161ca887690845a01a4, f-bff49a5beee2323108a4ef68, f-c03150c4e39f549b488c434b, f-c05885c91b9247ed9643cc62, f-c486be27add4b1dfebfb57ba, f-cdeb429f8b62148b602b06a9, f-ce1eab115ae98d6a562a80ac, f-d4946286a3de94ecafa6f32e, f-d57e9f92f1781fd803df66c6, f-d72252898cf5a55811cb29c9, f-d7e52dda68e8cf0619f54543, f-d837027c69328fc995d15b10, f-d9813d30e0e4b1027f510fa5, f-dc2c9c61221d15dfccbff21b, f-ddd0b64bade1631712d844c9, f-dec061a819c215d4b116bae3, f-e081483332a878f2dce51b75, f-e898ff9278015fb5f9d7f3bc, f-e94d9845043b9ed872d484b4, f-f0db4b111cbeacb4eba1526a, f-f0fa477deb3a441a15bf18cc, f-f938122ca25b63485c4ff145

ru · official · sha256:41dd252389c81e5b08e67dc667fb140d78f8b02f8bd500dba5e19e03fb6e451d

§5. Расширенный алгоритм Евклида для многочленов Задача: по двум многочленам найти их наибольший общий делитель ВМЕСТЕ с многочленами X и Y тождества Безу. Вариант — итеративный с двумя тройками, как у целых чисел. Хранятся тройки (R, X, Y) с равенством A·X + B·Y = R. На каждом шаге вычисляется частное Q от деления остатка текущей тройки на остаток следующей, и обе тройки обновляются: следующая становится текущей, а новая следующая есть покомпонентная разность прежней текущей и прежней следующей, умноженной на Q. Инвариант — те же два равенства. Они сохраняются потому, что вычитание кратного одной тройки из другой сохраняет линейное выражение через A и B. Нормировка на выходе выполняется одновременно для всех трёх компонент: делятся и наибольший общий делитель, и оба коэффициента. Деление только делителя нарушило бы тождество Безу — эта ошибка встречается постоянно. Применение: обратный элемент в кольце многочленов по модулю неприводимого многочлена, то есть арифметика конечного поля. Условие взаимной простоты здесь то же, что у целых. Оценка: то же число делений, что у §4, с добавлением двух умножений и двух вычитаний многочленов на шаг. Исполнимая реализация в репозитории — `calc.polynomials_q`: расширенный алгоритм Евклида с тождеством Безу.

Ссылаются нормы: f-0779eb8b6af5bb534129d5f0, f-07c99393332f18a22641cd52, f-097f16f05094871e92b30486, f-09e62c17145caf44f2af5dc9, f-0c54fa3b1371a95481e9f2b7, f-0e3841880ddad011b008bdbb, f-0f59ff12fdb9b194039b208d, f-1077b07e2c38c8cba3404803, f-11fd9211d562d4a8fa4ecdf0, f-12d90c308115b0e5af581b67, f-1762d1fee20b6c6e18873053, f-1b9cbc638ae6f6240d43e2d4, f-2034949085533832dc8fc7ae, f-2236fbecbb39c5be4e851a7b, f-25be97765f19cb84a87976e7, f-290340fe24a8f3ee0fac8838, f-29a719d994d8e2c6bcdbf3c9, f-2c063abb3b09e1c246ba22fa, f-2c6bc11ab8cb2905368b9989, f-2e7466df494f5e36241ee740, f-3051e7cc6456ca5cebae9b4c, f-3238e563cbe3338907e0ac39, f-34fc2a82b4dff7bbada5d67e, f-35f4530bc1fed448813b9ede, f-3732dbb04635ce231985c30d, f-39a76ee232a9b275e3f362a0, f-3dec2d6dbfeec60057469e29, f-40a8e1d156c43116c38dcf1d, f-460347a959dc6c6cb66f7ea5, f-4e66afcac3ba6f3c19a8122a, f-4f1f11c82ee6115032073ed3, f-5620f5b932a275ede13d744d, f-567d40b9c9040c8ee8ea9af8, f-58a622f135076a6638b19fcd, f-5ba40debcb1ba95d1aff20ef, f-5d86599901f0fc38601a67aa, f-5f7a1d8560788eef14e2c05c, f-63522a5c35dfb803c1589d22, f-63dbacd2e25cc26aea72e460, f-6407674dea050278685840b1, f-6c4f8d6ab8f4021d464ca0fc, f-7031829e371abc9f774f5948, f-7e9e55aee009199b72ec7e04, f-7fe8270c311625f05a7e8f55, f-81abcfcb5f1e86615a8d4625, f-836cc8157855fb56151282d2, f-8429a91697339efca95bfd9d, f-8472d981c80dbc382fc5e739, f-86907bc991798c35326702f6, f-8b7f41c30bca27d520c9d327, f-8d5005bc9e86680020fafecf, f-8e32e7acb14298433012c243, f-902e70b58ebd3301db8546cb, f-90c13069a35e40da579598ce, f-9246b5cc8780d9a494efdd15, f-97e07b620174e84ae8f4d37c, f-9c0e0fdb5d6c34f9ef25e55b, f-9c5c212701c0ca80fdb58c15, f-a6fb9726990896dfc7d808d8, f-a99e9e818c6d2883dc77a974, f-a9dc26e3df36dfc96818ca4b, f-ab7ce9e28c5769c3fb245146, f-ad2386386e53c69b949630eb, f-ae46bcac7cd3838168da405e, f-af3ecb0035e306efbc993d83, f-b0a36d727c12aab75f5c41b4, f-b2437cb0df051d306d66a6b4, f-b5708bf5c5756af41d77e2db, f-b61c3334629799008cb1aa7e, f-b713b79a2b6988d2e9892832, f-b88218f34a36f53033efe316, f-b8f86b5ed4b0401b60aa0fc4, f-b93660fda595417f32b0c18d, f-bf2a033ee2f6f0842b763671, f-c1416b05e9fd04ab4b2982cf, f-c6146407b4e00cc57d54aec9, f-ca8d69ab5d80979249a45eec, f-caa028c6d6e65298fef004a7, f-cbeed109eb996f5d73ec35e6, f-cfb49065d3be4ea94d2f1b6c, f-d15a89f9d3f2eea1a31bbb4c, f-d1fe47d20f3cf74094994dbf, f-d3d041e9924da02156e2c32a, f-d924f20c1bb8cbff3b1316be, f-dc437d86b7d7537877f66ba9, f-dea4d6433a75c13d71ddc6dd, f-ded5676ee2fd59694b80adad, f-e6a511b135cb07e349864ad1, f-e7cae1832cae488b0992b6b6, f-ea1908b5ed394919c9199249, f-f0c20f0e60f86e33848fb6f1, f-f89cd71f57a8f8b1de4d4e20, f-f8e98013f9710c4a45985974, f-fed1aba40db92f4f8052812a

ru · official · sha256:94e15e1bc2f86e50e45d29094a68b2d2ad66af98cd2b7c2a119eca0c6f1fff77

§6. Обычное умножение многочленов Задача: по двум многочленам найти их произведение. Вариант — двойной цикл по местам с накоплением в результат. Коэффициент результата при месте k есть сумма произведений коэффициентов сомножителей по всем парам мест, дающим в сумме k. Двойной цикл перебирает все пары мест и добавляет произведение в нужное место результата. Число мест результата равно сумме чисел мест сомножителей минус единица. Степень произведения равна сумме степеней ТОЛЬКО в каноне: у многочленов с нулевыми старшими коэффициентами это не так, и различие названо в §1. Инвариант: после обработки первых i мест первого сомножителя результат равен произведению его начальной части на второй сомножитель. Оценка: число умножений равно произведению чисел мест. Для многочленов степени n это порядка квадрата n, и именно это улучшает §7. Крайние случаи: нулевой сомножитель — произведение нулевое; многочлен нулевой степени — умножение сводится к умножению на константу.

Ссылаются нормы: f-0081bd880fbdc0e6a4b1436f, f-05ab10f41903526e6666b63a, f-09f9e0accd641ee77bb60005, f-0b0e3f17ec23e720b67313a3, f-0bca77254870084621b36a93, f-0ca138c26e7223b02dc4d14f, f-0d0ee57fe7b0a6143baef1cc, f-0dbbd52ca84a76b9df0782b3, f-15cf14a51ad597143321f049, f-163640eaa289808ee3ea4c92, f-18d70b9270f6f5c72b16602e, f-19e925c561f21a9f51e4d6d1, f-1b44c5abda613ab6b1db0e23, f-230d1eea2c38860fde54a13b, f-252f1a20989a6cfb566b766e, f-25603010049ab193f451696e, f-2e8a7d1d8950706aa0c14013, f-325fee8c735af7b10cd1cdcf, f-32d9aef3da5f0cddc1045c57, f-32ff2f89913505657261efce, f-3635ae13900cbe21bb402fc4, f-3708c382aca1ba5ae065930d, f-39739b5422174ace3de96814, f-3a64995567212009d19a7277, f-3c2f5b5528d7e8c497e15cec, f-3f3fe44f6b893eee2edfb197, f-40b1beb68e8cc9d6a112272c, f-43dfc6c387528b117b4243e9, f-47fae8d546e362352c92e82a, f-4d7231fb16a2d64df450f1f0, f-52380f24121dc6e07dcbbfdb, f-58e6051cd5abc120b06bdfed, f-5a043cfafc40bc5e6f30ea51, f-605f30e41d031f45a6769aa8, f-68e730f48bf9294c253d52a6, f-6ccb3d2024f585bc891ebf5d, f-7809645d313c8e43c50fce61, f-7ac313fe8d65e25783683a98, f-8618ce87c9a552ccf478c089, f-8c68ed696dfb92ea60e78842, f-9e2e420f18d346f5bb2bd45b, f-a365346e576b6e60f452232e, f-a68ce59eab64700a70d7c8da, f-a6beced13c386fd508d6d4a0, f-adfc03c959c52e48d6ff8802, f-adfef8f66ead9c4e1d90cc04, f-b72ffbda6a08459f80d61802, f-b76f8863bf66df8ff5a7bff6, f-bb6acc9330345831bc2bf44b, f-bd3edfd70667963999d43c37, f-c27558efcbc677805539f03a, f-c353aa0d360017b4ced13379, f-c76efc1aaff36bcfa28997c5, f-c8777b216804ab972e4cb47f, f-ca0f2ee0c7c9f07ec77cf2a8, f-cbba00dad9eedad915c0a733, f-d3afa24a3ee15ca3a3c58457, f-d42e7fc90da57eb3522e35b0, f-d4856e4c10c9573463b6b0c0, f-d7f57a10e9a086849ec970fa, f-dfae2b0f69fb40c85a3d6e59, f-dfb4f81cb78883958f065c2a, f-e102faf0fd3c6a8dcf7dfdde, f-e332253aed864a655a0b2413, f-ead8c3f2aadfcd5c75bf28c0, f-f06b4e2c9269895f9456952e, f-f1ba13e7dcdaf8a96b4719af, f-fee12179534a84b454bf54ff, f-ff1e1444f949519bd06271a8

ru · official · sha256:dde2ac3ed0f5671733fa0cdcf07c50eb51d29460835319d5691cb2c5249e5e96

§7. Умножение методом Карацубы Задача та же. Вариант — разделяй и властвуй с ТРЕМЯ умножениями половин вместо четырёх. Каждый многочлен делится на младшую и старшую половины по месту m. Произведение выражается через три произведения половин: младших, старших и сумм половин. Средний член получается вычитанием двух уже вычисленных произведений из третьего, а не отдельным умножением, — в этом всё содержание метода. Основание: тождество (A₁·x^m + A₀)·(B₁·x^m + B₀) = A₁B₁·x^(2m) + ((A₁+A₀)(B₁+B₀) − A₁B₁ − A₀B₀)·x^m + A₀B₀. Оно проверяется раскрытием скобок и принадлежит источнику. Рекуррентное соотношение T(n) = 3·T(n/2) + Θ(n) даёт оценку n в степени логарифма трёх по основанию два, то есть примерно n в степени 1,585. Порог перехода к обычному умножению обязан быть назван: на малых степенях накладные расходы делят и вычитаний превышают выигрыш. Порог есть ПАРАМЕТР варианта, а не деталь реализации, и описание без него неполно. Мера убывания — число мест обрабатываемого многочлена; база рекурсии — степень ниже порога. Крайние случаи: многочлены разной длины — короткий дополняется нулевыми местами; нечётная длина — деление пополам с округлением, и обе половины обрабатываются одинаково. Метод Карацубы применим и к длинным целым числам с тем же тождеством; там роль места играет разряд.

Ссылаются нормы: f-004d3a3c853032300c4333b3, f-011ab134a05190130b53e280, f-0341aa3388797f01688f7749, f-055c8c758cffe0f79e4444fd, f-09238bb2a5fb55a3c2e3fd9b, f-0efd0403fe876358a799adb3, f-1146c649fe5a3605d21615f6, f-1176eec677ab08b83164fc2d, f-129e75df3f2eafe17cf07084, f-12bf7eda68a5292ac44e186d, f-1393c9b3cd4fd2a13fc9277e, f-13a46b87ab0fb27ac7bc0a32, f-17a510fa6ec4572605799938, f-187e367eadc037bc8dd278db, f-1a3773909d5c78d65af08e67, f-1a8b6e567e1800b20cde5560, f-1d28e6464bd8cc1331352b7c, f-1e0805d924bd77c127b922f3, f-1ff0ae7735b4adb1cb096166, f-25315578a73adb0f0f4d395c, f-269da9e8f864fef0f5bb97a3, f-275f3bf20baccbbad9e1aa5b, f-27e55ab2a8b2e3195806db28, f-28c9799b17962ce2d6cb137b, f-297aabb8b7c5c0ecacffd193, f-2ad35ea5e68d89b030842ea3, f-2cdba534353934b637f14c50, f-2f95e018335f6b2aa9333ca6, f-304238d01dd4ed761bd019f7, f-312002d465017994ac23db31, f-31cd9505f36881dd2040e2d1, f-3314a32fc0cb5c85dfde84ab, f-380297f48c04ed090c0a429c, f-3d63d6ab00c669667c9ac47c, f-3f5209a5cd196f45e2a02ef5, f-4034b7de6d71863bfbbe2b79, f-403f0def71cf937f1a1e432b, f-42581e4dd67b3928f699be92, f-4729f8a6685c8aa494c65867, f-485847484bffd37220d94e0e, f-490d6af5a661cb0f0a962fe5, f-4a541c3680dff40490d5997a, f-4d95979f1a861de06f22f18c, f-54b74282f0dc6a2f23a69daa, f-5e865a8996a4cc32d69132c0, f-6278774049e0a54e61a8f165, f-65b0079fa594f57c60f9d49e, f-6698196f0eae0377dd493401, f-68bdac401b31a62186308cf8, f-6a2e3cb196848f1af2067306, f-6a7c1d0521fe031c0942081d, f-6ab28deaa8691492fadafeb9, f-6da9a571418c732dce61a311, f-74b172af4c532922abddb4ab, f-760d3b91ef72d6e149b3463f, f-77387f84a3b9794a3a2f33b7, f-775d6a46af2091722cfa1c1b, f-825dac16c329ec261c3f3055, f-88d9ecd0931759978b4ca2a9, f-9161946726e58f20306d00ba, f-9247f8be87bf793c18a68f27, f-9866ae88ecb2d44be985367c, f-9ef7abfe26ce92db34332438, f-9f41713fc8b8f189adb4ed27, f-a32e6694746993983a65f717, f-aa17c49640707cf4a1eee059, f-aa976f755956f607000c4f5c, f-ad1d6d4248ef1488bccac04a, f-ae20b2f866efc8fb7838f2d9, f-aeade8b176e5d8ecd2ab542b, f-b010d6f1a02b38151579ace6, f-b325b53a9e96538a21ef1e65, f-b3f170c6e22fedf124ec257e, f-b8464dcb687ba985597fd9af, f-b9bbd04f252cbf0d08570f70, f-bb24579b3739a3f3414d50a1, f-bd957d4f6a771b10c93adc03, f-c1b293ab2ae12bfe0d9d0fba, f-c648d1c7b2def872bb796cb7, f-c76acbbd621376b38ede9cb1, f-c8fb6b0f55240cc814bfe5da, f-cc98a913bed6febc265cd69d, f-ce605a2624b4744ad38c058b, f-cf48e0588cd9a4719ffcf416, f-cfbd1e2b60f3b46f8c42ad3b, f-d1ecbafed2403dc25f76f4ea, f-d5aa83601e10752142804154, f-d838b4e9e4d410969acaa5a4, f-d8df32a5a76032d23671b72a, f-e3ece1004ecc6460be855778, f-e41ea2a68c2e39a85a0bcd7e, f-e4ee1da9f01092843de23578, f-e558a771eb2a21d2e21c61aa, f-e558ec61c12c938925ca4bb8, f-e7b858602cfd378b0ef34a4d, f-ec490e470c5f917f89a91da9, f-edc4ae0c4d5468d7e58cee09, f-f08434b1d7a98abf95f10cb7, f-f1557ebcafc87de9338ace60, f-f2ceabcfea21e56eace25f59, f-f43189437fab211b8ee5a465, f-f7ce498b319f1c5f57c80220, f-f7fa5fa9bd6856b6e4fbff48

ru · official · sha256:a1ca0e725d170fec68e2ce517f1485a6c9f958731e5eb24277e1407e6a61faaa

МНОГОЧЛЕНЫ: СХЕМА ГОРНЕРА, ДЕЛЕНИЕ С ОСТАТКОМ, НОД, РАСШИРЕННЫЙ АЛГОРИТМ ЕВКЛИДА, УМНОЖЕНИЕ И МЕТОД КАРАЦУБЫ Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство шести алгоритмов над многочленами одной переменной: вычисления значения схемой Горнера, деления с остатком, нахождения наибольшего общего делителя, расширенного алгоритма Евклида с тождеством Безу, обычного умножения и умножения методом Карацубы. Изложение не воспроизводит ни один учебник; происхождение каждого алгоритма названо при его описании локатором. Описание отвечает на вопрос об устройстве алгоритма и не выполняет его: ни один многочлен здесь не вычисляется.