کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421293 | 684181 | 2010 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order](/preview/png/421293.png)
چکیده انگلیسی
We prove that each OBDD (ordered binary decision diagram) for the middle bit of nn-bit integer multiplication for one of the variable orders which so far achieve the smallest OBDD sizes with respect to asymptotic order of growth, namely the pairwise ascending order x0,y0,…,xn−1,yn−1x0,y0,…,xn−1,yn−1, requires a size of Ω(2(6/5)n)Ω(2(6/5)n). This is asymptotically optimal due to a bound of the same order by Amano and Maruoka (2007) [1].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 11, 6 June 2010, Pages 1195–1204
Journal: Discrete Applied Mathematics - Volume 158, Issue 11, 6 June 2010, Pages 1195–1204
نویسندگان
Martin Sauerhoff,