بخش 1-2-1 جمع صحیح با الگوریتم پیش بینی نقلی
این الگوریتم جمع دو عدد N-bit در1 + lg N * 2 گام با درخت N برگی کامل. و افزایش سرعت زیاد نسبت به روش ترتیبی با N گام.
به سادگی با یک پردازنده می توان دو عدد N بیتی را در N+1 جمع کرد.
در نگاه اول به نظر میاد که نمیشه اینکار رو سریع تر از N گام انجام داد. اما با کمی هوشمندی و درخت دودویی کامل می توان اینکار را سریع تر انجام داد. با روش پیش بینی نقلی می توان با 1 + lg N * 2 میتوان دو عدد N بیتی را جمع زد.
نکته کلیدی در این روش در این است که نتیجه جمع دو بیت آیا نقلی را stop ، generate، یا propagate می کند. برای مثال جفت {0 , 0} بیت نقلی را STOP می کند. { 0 , 1 } بیت نقلی را propagate و { 1 , 1 } بیت نقلی را generate می کند.
در این روش نقلی ورودی از بیت i ام برابر است با سمت چپ ترین غیر p بیت های سمت راست.
در این ساختار محاسبه آخرین carry گام های مورد نیاز برابر 1 + lg N * 2 خواهد بود. در این روش در هر گام مقدار نود داخلی برابر سمت چپ ترین غیر P خواهد بود.
هر نود داخلی علاوه بر اینکه ورودی های خودش را از پسرانش دریافت می کند. مقدار فرزند سمت راست را به جای مقدار سمت چپ قرار داده و مقدار سمت راست را حذف می کند. و همینطور این پروسه ادامه پیدا می کند تا به یک برگ برسیم. و هر پردازنده برگ منتظر اولین ورودی non-p خود میماند.
