Booth 演算法
/ Booth = booth (rhymes with tooth) /
Booth 演算法是一種聰明的有號數乘法，順帶還能在連續相同位元的長串上省工。日常畫面：用現金付款時，若某物賣 99 元，你不會數出九十九個一元——你遞出一百元再找回一元。Booth 把同樣的「加一大塊，再減一個修正」想法用到二進位上，把一長串 1 換成在它頭尾各一次加法與減法，而非許多次分開的加法。
機制上，Booth 掃描乘數的位元對，把每個位元連同它右邊那個位元一起看（想像在最低位下方多補一個 0）。在由低往高的 0 到 1 轉變處（當前位元 1、下位元 0）它在該位置減去被乘數；在 1 到 0 轉變處（當前位元 0、下位元 1）它加上；在相等位元的連續段內（00 或 11）它只移位、不做別的。於是一串 1 ...0111110... 在串的起點觸發一次減、終點觸發一次加，而非五次加。關鍵是：因為它用減法且在二補數下運作，它能正確地乘有號運算元，完全不必特別處理符號位元——這正是它出現在真實硬體裡的主因。
兩個誠實的注意點。其一，Booth 不一定比較快：對最壞情況、交替 0101... 的運算元，它幾乎每一步都得發出一次運算，所以這個好處取決於資料——現代設計用改良式（基數 4）Booth，無論位元樣式如何，總是把部分積數目減半。其二，Booth 減少了部分積的數目，但這些積仍得相加；把改良式 Booth 編碼搭配 Wallace 樹來快速相加，是標準的高速乘法器配方。
乘以 ...01111（四個 1 的連續段），天真做法需要四次加法。Booth 把這段看成 +10000 再 -00001：串起點一次減、串終點一次加——兩次運算而非四次——同一個技巧讓有號乘法自然成立。
把一串 1 換成一次加與一次減；減法正是讓符號生效的關鍵。
Booth 的速度取決於資料——最壞情況的交替樣式毫無節省。真實核心採用改良式基數 4 Booth，無論位元如何都固定部分積數目，再用快速樹把這些積相加。