الگوریتم زیر برای ضرب دو عدد $n-1$ بیتی به کار می‌رود. ورودی این الگوریتم دو عدد $n-1$ بیتی $B$ به شکل $\overline{b_n…b_2b_1}$ و $Q$ به شکل $\overline{q_n…q_2q_1}$ است. بدیهی است که $b_n$ و $q_n$ صفر هستند. الگوریتم در طول اجرا از شمارنده‌ی $C$ و متغیر تک‌بیتی $q_0$ وعدد $n$ بیتی $A$ به شکل $\overline{a_n…a_2a_1}$ بهره می‌گیرد. خروجی الگوریتم، عدد $2n$ بیتی $\overline{a_n…a_2a_1q_n…q_2q_1}$ است. مراحل اجرای الگوریتم به شرح زیر می‌باشد:

• $A$ و $q_0$ را برابر صفر و $C$ را برابر $n$ قرار بده.
• با توجه به جدول زیر، مقدار $(\overline{q_1q_0})$ را محاسبه کن، حاصل را در $B$ ضرب کن، اگر حاصل منفی شد، به تعداد کافی $2^n$ به حاصل‌ضرب بیفزا تا حاصل مثبت شود. حال حاصل را با $A$ جمع کن و $n$ بیت سمت راست ($n$ بیت کم‌ارزش) حاصل جمع را در $A$ ذخیره کن.

• عدد $\overline{a_{n-1}…a_2a_1q_n…q_1q_0}$ را یک بیت به سمت راست انتقال بده و سپس $a_{n-1}$ را برابر $a_n$ قرار بده. پس از این عمل، مقدار قبلی $q_0$ جایگاهی نخواهد داشت.
• از $C$ یک واحد کم کن و اگر صفر شد، به اجرای الگوریتم خاتمه بده وگرنه، اجرا را از بند شماره‌ی ۲ ادامه بده.

برای مثال جدول ۲ روند اجرای الگوریتم برای ضرب دو عدد ۰۱۰ و ۰۱۱ نشان می‌دهد.

الف) درستی اجرای الگوریتم را ثابت کنید.

ب) برای افزایش سرعت، متغیر تک‌بیتی $q_{-1}$ را در نظر گرفته و الگوریتم را مطابق زی تغییر می‌دهیم.

1. $A$، $q_0$ و $q_{-1}$ را برابر صفر و $C$ را برابر $n$‌قرار بده.
2. با توجه به جدول، مقدار $g(\overline{q_1q_0q_{-1}})$ را محاسبه کن. اگر حاصل منفی شد، به تعداد کافی $2^n$ به حاصل ضرب بیفزا تا حاصل مثبت شود. حال حاصل را با $A$ جمع کن و $n$ بیت سمت راست ($n$ بیت کم‌ارزش) حاصل جمع را در $A$ ذخیره کن.
3. عدد $\overline{a_{n-1}…a_1a_1q_n…q_1q_0q_{-1}}$ را ۲ بیت به سمت راست انتقال بده و سپس $a_{n-1}$‌را برابر $a_n$‌قرار بده. پس از این عمل، مقدار قبلی $q_{-1}$‌جایگاهی نخواهد داشت.
4. از $C$ یک واحد کم کن واگر صفر شد، به اجرای الگوریتم خاتمه بده وگرنه، اجرا را از بند شماره‌ی ۲ ادامه بده.

جدول مربوط به مقادیر $g(x)$ را تنظیم کنید و درستی الگوریتم به دست آمده را نشان دهید.

• سوال بعد