کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874112 1441023 2018 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A probabilistic algorithm for verifying polynomial middle product in linear time
ترجمه فارسی عنوان
یک الگوریتم احتمالی برای تایید محصول متوسط ​​چندجملهای در زمان خطی
کلمات کلیدی
الگوریتم احتمالاتی، طراحی الگوریتم، محاسبه در چند جملهای، چندجملهای ضرب،
ترجمه چکیده
ضرب چندجمله ای و انواع آن یک عنصر کلیدی در جبر کامپیوتر است. در حالی که بررسی یک محصول چندجمله ای یک وظیفه شناخته شده است، هنوز مشخص نیست که چگونه می توان یک روش مشابه برای نوع محصول متوسط ​​خود را انجام داد. در این یادداشت کوتاه، ما یک الگوریتم جدید ارائه می دهیم که چنین تأییدی را با همان پیچیدگی و احتمال برای ضرب چند جمله ای کلاسیک فراهم می کند. علاوه بر این، ما الگوریتم ما را برای بررسی هر عملیاتی که تنها یک قطعه خاص از محصول را محاسبه می کنیم، مورد بررسی قرار می دهیم، که به عنوان نمونه عملیات کوتاه مدت شناخته شده است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
یک الگوریتم احتمالی برای تایید محصول متوسط ​​چندجملهای در زمان خطی
چکیده انگلیسی
Polynomial multiplication and its variants are a key ingredient in effective computer algebra. While verifying a polynomial product is a well known task, it was not yet clear how to do a similar approach for its middle product variant. In this short note, we present a new algorithm that provides such a verification with the same complexity and probability that for the classical polynomial multiplication. Furthermore, we extend our algorithm to verify any operations that compute only a certain chunk of the product, which is the case for instance of the well known short product operation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 139, November 2018, Pages 30-34
نویسندگان
,