Prefix Computation

مسئله محاسبه نقلی با رشته های s, p , g  به طور خلاصه تر می تواند با Prefix Computation بیان شود. به صورت دقیق تر X_i نشاندهنده مقدار s,p,g برای iامین بیت از سمت راست جمع است. 

ضمن این باید چک کنیم که عملگر باینری در این محاسبات می بایستی شرکت پذیر باشد. 

کافیست جدول بالا را چک کنیم. هر مسئله ای که بتوان عملگر دودویی به طریقی که در اینجا تعریف شد برایش تعریف کنیم را می توان با همین روش و با یک درخت باینری کامل در 2D + 1 گام حل کرد. که D عمق درخت باینری است.

در جمع با پیش بینی نقلی در واقع عمل جمع شامل دو فاز متناوب می شود. در فاز اول هر گره داخلی حاصل دو داده ورودی را محاسبه می کند و در فاز دوم این نتیجه را به سمت پایین می فرستد به طوریکه برگ iام شامل ith prefix خواهد بود.