ตัวบวกแบบเก็บตัวทด^{[ 1 ] [ 2 ] [ nb 1 ]} เป็น ตัวบวกดิจิทัลชนิดหนึ่งใช้ในการคำนวณผลรวมของ เลข ฐาน สองสามตัวขึ้นไปอย่างมีประสิทธิภาพ แตกต่างจากตัวบวกดิจิทัลอื่นๆ ตรงที่มันส่งออกตัวเลขสองตัว (หรือมากกว่า) และคำตอบของผลรวมเดิมสามารถหาได้โดยการบวกผลลัพธ์เหล่านี้เข้าด้วยกัน ตัวบวกแบบเก็บตัวทดมักใช้ในตัวคูณเลขฐานสอง เนื่องจากตัวคูณเลขฐานสองเกี่ยวข้องกับการบวกเลขฐานสองมากกว่าสองตัวหลังจากการคูณ ตัวบวกขนาดใหญ่ที่ใช้เทคนิคนี้มักจะเร็วกว่าการบวกเลขเหล่านั้นแบบธรรมดามาก

ลองพิจารณาผลรวมนี้ดู:

 12345678 + 87654322 = 100000000 

โดยใช้หลักการคำนวณพื้นฐาน เราคำนวณจากขวาไปซ้าย "8 + 2 = 0, ทด 1", "7 + 2 + 1 = 0, ทด 1", "6 + 3 + 1 = 0, ทด 1" และต่อไปเรื่อยๆ จนถึงตัวเลขสุดท้าย แม้ว่าเราจะรู้ตัวเลขหลักสุดท้ายของผลลัพธ์ได้ทันที แต่เราไม่สามารถรู้ตัวเลขหลักแรกได้จนกว่าเราจะคำนวณครบทุกหลัก โดยส่งค่าทดจากแต่ละหลักไปยังหลักทางซ้าย ดังนั้น การบวกเลขสอง จำนวนที่มี nหลัก จึงต้องใช้เวลาแปรผันตรงกับnแม้ว่าเครื่องมือที่เราใช้จะสามารถคำนวณพร้อมกันได้หลายๆ ครั้งก็ตาม

ในทางอิเล็กทรอนิกส์ โดยใช้หน่วยบิต หมายความว่า แม้ว่าเราจะมี ตัวบวกเลขหนึ่งบิตจำนวน nตัว แต่เราก็ยังต้องใช้เวลาที่แปรผันตามnเพื่อให้ตัวทด (carry) ที่อาจเกิดขึ้นนั้นแพร่กระจายจากปลายด้านหนึ่งของตัวเลขไปยังอีกด้านหนึ่ง จนกว่าเราจะทำเช่นนี้เสร็จ

1. เราไม่ทราบผลลัพธ์ของการบวก
2. เราไม่ทราบว่าผลลัพธ์ของการบวกนั้นมากกว่าหรือน้อยกว่าจำนวนที่กำหนด (ตัวอย่างเช่น เราไม่ทราบว่าเป็นค่าบวกหรือค่าลบ)

วงจรบวกแบบมองล่วงหน้าตัวทด (carry look-ahead adder)สามารถลดความล่าช้าได้ ในทางทฤษฎี ความล่าช้าสามารถลดลงได้จนเป็นสัดส่วนกับ log nแต่สำหรับตัวเลขขนาดใหญ่แล้วนั้นจะไม่เป็นเช่นนั้นอีกต่อไป เพราะแม้ว่าจะมีการใช้ carry look-ahead แล้ว ระยะทางที่สัญญาณต้องเดินทางบนชิปก็จะเพิ่มขึ้นเป็นสัดส่วนกับnและความล่าช้าในการแพร่กระจายก็จะเพิ่มขึ้นในอัตราเดียวกัน เมื่อเราไปถึงขนาดตัวเลข 512 บิตถึง 2048 บิต ซึ่งเป็นขนาดที่จำเป็นในระบบเข้ารหัสแบบกุญแจสาธารณะ carry look-ahead ก็จะไม่ค่อยมีประโยชน์มากนัก

แนวคิดเรื่องการชะลอการตัดสินผลทดจนถึงตอนท้าย หรือการเก็บทดไว้ มาจากJohn von Neumann ^{[ 3 ]}

ผลรวมของตัวเลขสองหลักไม่สามารถทดเกิน 1 ได้ และผลรวมของตัวเลขสองหลักบวก 1 ก็ไม่สามารถทดเกิน 1 ได้เช่นกัน ตัวอย่างเช่น ในระบบเลขฐานสิบซึ่งมีทดเป็น 1; ซึ่งมีทดเป็น 1 เช่นกัน เมื่อบวกตัวเลขสามหลัก เราสามารถบวกสองหลักแรกแล้วได้ผลรวมและตัวทด จากนั้นบวกผลรวมและตัวทดเข้ากับหลักที่สามแล้วได้ผลรวมและตัวทดเช่นกัน ในระบบเลขฐานสอง ตัวเลขมีเพียงศูนย์และหนึ่ง ดังนั้น , , และโดยมีตัวทดเป็น 1 การบวกบิตตัวทดจะให้ผลสูงสุดได้โดยมีตัวทดเป็น 1 ดังนั้นการบวกสามหลักจึงเป็นไปได้ ด้วยเหตุนี้ จึงเป็นไปได้ที่จะบวกตัวเลขสามหลักแรกแล้วได้ผลรวมและตัวทด สำหรับตัวเลขถัดไป ผลรวมและตัวทดจะเป็นสองพจน์ และตัวเลขเดี่ยวถัดไปจะถูกบวกเข้ากับพจน์เหล่านี้ ${\displaystyle 9+9=18}$${\displaystyle 9+9+1=19}$${\displaystyle 0+0=0}$${\displaystyle 0+1=1}$${\displaystyle 1+1=0}$${\displaystyle 1+1+1=1}$

ต่อไปนี้เป็นตัวอย่างผลรวมเลขฐานสองของเลขฐานสองยาว 3 ตัว:

 1011 1010 1010 1101 1111 0000 0000 1101 (ก) + 1101 1110 1010 1101 1011 1110 1110 1111 (b) + 0001 0010 1011 0111 0101 0011 0101 0010 (c) 

วิธีที่ตรงไปตรงมาที่สุดคือการคำนวณ (a+b) ก่อน แล้วจึงคำนวณ ((a+b)+c) การคำนวณแบบ Carry-save ทำงานโดยการละทิ้งการส่งต่อตัวทด (carry propagation) ทุกประเภท โดยจะคำนวณผลรวมทีละหลัก ดังนี้:

 1011 1010 1010 1101 1111 0000 0000 1101 (ก) + 1101 1110 1010 1101 1011 1110 1110 1111 (b) + 0001 0010 1011 0111 0101 0011 0101 0010 (c) = 2113 2130 3031 2313 2223 1121 1211 2222 

สัญลักษณ์ที่ใช้อาจไม่เป็นไปตามแบบแผนทั่วไป แต่ผลลัพธ์ก็ยังคงชัดเจน: Σ2 ⁱ d _iถ้าเราสมมติว่าตัวเลขทั้งสามคือ a, b และ c แล้วผลลัพธ์จะถูกอธิบายว่าเป็นผลรวมของเลขฐานสองสองจำนวน โดยที่จำนวนแรก S คือผลรวมที่ได้จากการบวกตัวเลขแต่ละหลัก (โดยไม่มีการทด) กล่าวคือ S _i = a _i ⊕ b _i ⊕ c _i และจำนวนที่สอง C คือผลรวมของตัวทดจากผลรวมแต่ละตัวก่อนหน้า กล่าวคือ C _i+1 = (a _i b _i ) + (b _i c _i ) + (c _i a _i ) :

 0111 0110 1011 0111 0001 1101 1011 0000 และ 1 0011 0101 0101 1011 1110 0100 1001 1110 

ตอนนี้เราสามารถส่งตัวเลข 2 ตัวนี้ไปยังวงจรบวกแบบส่งต่อตัวทด (carry-propagate adder) ซึ่งจะแสดงผลลัพธ์ออกมา

วิธีนี้มีข้อได้เปรียบอย่างมากในแง่ของเวลาหน่วง (เวลาในการคำนวณ) หากคุณบวกเลข 3 ตัวโดยใช้วิธีการแบบดั้งเดิม จะต้องใช้เวลาหน่วงเท่ากับเวลาหน่วงของตัวบวกแบบส่งต่อตัวทด (carry-propagate adder) 2 ครั้งจึงจะได้คำตอบ แต่ถ้าคุณใช้วิธีการประหยัดตัวทด (carry-save technique) คุณจะต้องการเวลาหน่วงของตัวบวกแบบส่งต่อตัวทดเพียง 1 ครั้ง และเวลาหน่วงของตัวบวกแบบเต็ม (full-adder) อีก 1 ครั้ง (ซึ่งน้อยกว่าเวลาหน่วงของตัวบวกแบบส่งต่อตัวทดมาก) ดังนั้น CSA จึงมักจะเร็วมาก

สมมติว่าเรามีพื้นที่เก็บข้อมูลสองบิตต่อหลัก เราสามารถใช้การแสดงเลขฐานสองแบบซ้ำซ้อนโดยเก็บค่า 0, 1, 2 หรือ 3 ในแต่ละตำแหน่งหลัก ดังนั้นจึงเห็นได้ชัดว่าสามารถเพิ่มเลขฐานสองอีกหนึ่งตัวลงในผลลัพธ์จากการคำนวณแบบ carry-save ได้โดยไม่ทำให้พื้นที่เก็บข้อมูลเต็ม: แต่หลังจากนั้นล่ะ?

กุญแจสู่ความสำเร็จคือ ในแต่ละครั้งที่ทำการบวกย่อย เราจะบวกสามบิตเข้าไป:

• 0 หรือ 1 จากจำนวนที่เรากำลังบวกกัน
• 0 ถ้าตัวเลขในร้านของเราเป็น 0 หรือ 2 หรือ 1 ถ้าเป็น 1 หรือ 3
• 0 ถ้าตัวเลขทางด้านขวาเป็น 0 หรือ 1 หรือ 1 ถ้าเป็น 2 หรือ 3

กล่าวอีกนัยหนึ่ง เรากำลังนำตัวเลขทดจากตำแหน่งทางด้านขวา และส่งตัวเลขทดนั้นไปยังตำแหน่งทางด้านซ้าย เช่นเดียวกับการบวกแบบทั่วไป แต่ตัวเลขทดที่เราส่งไปยังด้านซ้ายนั้นเป็นผลลัพธ์ของ การคำนวณ ครั้งก่อนไม่ใช่การคำนวณในปัจจุบัน ในแต่ละรอบสัญญาณนาฬิกา ตัวเลขทดจะต้องเคลื่อนที่ไปเพียงหนึ่งขั้นเท่านั้น ไม่ใช่nขั้นเหมือนในการบวกแบบทั่วไป

เนื่องจากสัญญาณไม่จำเป็นต้องเดินทางไกลมาก นาฬิกาจึงสามารถเดินได้เร็วขึ้นมาก

ยังคงมีความจำเป็นต้องแปลงผลลัพธ์เป็นเลขฐานสองในตอนท้ายของการคำนวณ ซึ่งโดยพื้นฐานแล้วหมายความว่าปล่อยให้ตัวทดเดินทางไปจนถึงเลขฐานสองเหมือนกับการบวกแบบทั่วไป แต่ถ้าเราทำการบวก 512 ครั้งในกระบวนการคูณ 512 บิต ค่าใช้จ่ายในการแปลงครั้งสุดท้ายนั้นจะถูกแบ่งเฉลี่ยไปในแต่ละการบวกทั้ง 512 ครั้ง ดังนั้นการบวกแต่ละครั้งจะมีค่าใช้จ่ายเพียง 1/512 ของค่าใช้จ่ายของการบวกแบบ "ทั่วไป" ครั้งสุดท้าย

ในแต่ละขั้นตอนของการบวกแบบ Carry-Save

1. เราทราบผลลัพธ์ของการบวกได้ทันที
2. เรายังไม่ทราบว่าผลลัพธ์ของการบวกนั้นมากกว่าหรือน้อยกว่าจำนวนที่กำหนด (ตัวอย่างเช่น เราไม่ทราบว่าเป็นค่าบวกหรือค่าลบ)

ประเด็นหลังนี้เป็นข้อเสียเมื่อใช้ตัวบวกแบบ carry-save เพื่อดำเนินการคูณแบบโมดูลาร์ (การคูณตามด้วยการหาร โดยเก็บเฉพาะเศษเหลือ) ^{[ 4 ] [ 5 ]}หากเราไม่สามารถทราบได้ว่าผลลัพธ์ระหว่างกลางมากกว่าหรือน้อยกว่าโมดูลัส เราจะทราบได้อย่างไรว่าต้องลบโมดูลัสหรือไม่

การคูณแบบมอนต์โกเมอรีซึ่งขึ้นอยู่กับหลักขวาสุดของผลลัพธ์ เป็นหนึ่งในวิธีแก้ปัญหา แม้ว่ามันจะมีค่าใช้จ่ายคงที่คล้ายกับการบวกแบบเก็บตัวทด ดังนั้นการคูณแบบมอนต์โกเมอรีหลายๆ ครั้งจึงช่วยประหยัดเวลา แต่การคูณเพียงครั้งเดียวไม่ช่วยประหยัดเวลา โชคดีที่การยกกำลัง ซึ่งโดยพื้นฐานแล้วคือลำดับของการคูณ เป็นการดำเนินการที่พบได้บ่อยที่สุดในการเข้ารหัสแบบกุญแจสาธารณะ

การวิเคราะห์ข้อผิดพลาดอย่างระมัดระวัง^{[ 6 ]}ช่วยให้สามารถเลือกได้ว่าจะลบค่าสัมบูรณ์หรือไม่ แม้ว่าเราจะไม่ทราบแน่ชัดว่าผลลัพธ์ของการบวกมีขนาดใหญ่พอที่จะรับประกันการลบหรือไม่ เพื่อให้สิ่งนี้ใช้งานได้ จำเป็นต้องออกแบบวงจรให้สามารถบวก −2, −1, 0, +1 หรือ +2 เท่าของค่าสัมบูรณ์ได้ ข้อดีเหนือการคูณแบบมอนต์โกเมอรีคือไม่มีค่าใช้จ่ายคงที่ที่แนบมากับลำดับการคูณแต่ละครั้ง

หน่วย carry-save ประกอบด้วยตัวบวกเต็ม (full adder) จำนวน n ตัว โดยแต่ละตัวจะคำนวณผลรวมและบิตตัวทดเพียงบิตเดียวโดยอาศัยบิตที่สอดคล้องกันของตัวเลขอินพุตทั้งสามตัวเท่านั้น เมื่อกำหนด ตัวเลข nบิต สามตัวคือ a , bและcหน่วยนี้จะสร้างผลรวมย่อยpsและบิตตัวทด (shift-carry) sc :

${\displaystyle ps_{i}=a_{i}\oplus b_{i}\oplus c_{i},}$

${\displaystyle sc_{i}=(a_{i}\wedge b_{i})\vee (a_{i}\wedge c_{i})\vee (b_{i}\wedge c_{i}).}$

จากนั้นสามารถคำนวณผลรวมทั้งหมดได้โดยใช้สูตร:

1. เลื่อนลำดับการทดscไปทางซ้ายหนึ่งตำแหน่ง
2. การเพิ่มเลข 0 ไว้ข้างหน้า ( บิตที่มีนัยสำคัญที่สุด ) ของลำดับผลรวมย่อยps
3. ใช้ตัวบวกแบบริปเปิลแครี่เพื่อบวกค่าทั้งสองเข้าด้วยกันและสร้างค่าผลลัพธ์ที่มีขนาด ( n + 1) บิต

• ต้นไม้วอลเลซ

• Savard, John JG (2018) [2006]. "เทคนิคเลขคณิตขั้นสูง" . quadibloc . เก็บถาวรจากต้นฉบับเมื่อ 2018-07-03 . สืบค้นเมื่อ 2018-07-16 .