page_title: Booth's multiplication algorithm
section_title: A typical implementation
hierarchical_section_title: Booth's multiplication algorithm / A typical implementation
caption_attribution_description: Calculator Walther WSR160 build 1960 bei Walther, Germany
context_page_description: Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth's algorithm is of interest in the study of computer architecture.
context_section_description: Booth's algorithm can be implemented by repeatedly adding (with ordinary unsigned binary addition) one of two predetermined values A and S to a product P, then performing a rightward arithmetic shift on P.  Let m and r be the multiplicand and multiplier, respectively; and let x and y represent the number of bits in m and r.
  Determine the values of A and S, and the initial value of P.  All of these numbers should have a length equal to (x + y + 1).
  A: Fill the most significant (leftmost) bits with the value of m.  Fill the remaining (y + 1) bits with zeros.
  S: Fill the most significant bits with the value of (−m) in two's complement notation.  Fill the remaining (y + 1) bits with zeros.
  P: Fill the most significant x bits with zeros.  To the right of this, append the value of r.  Fill the least significant (rightmost) bit with a zero.
  Determine the two least significant (rightmost) bits of P.
  If they are 01, find the value of P + A.  Ignore any overflow.
  If they are 10, find the value of P + S.  Ignore any overflow.
  If they are 00, do nothing.  Use P directly in the next step.
  If they are 11, do nothing.  Use P directly in the next step.
  Arithmetically shift the value obtained in the 2nd step by a single place to the right.  Let P now equal this new value.
  Repeat steps 2 and 3 until they have been done y times.
  Drop the least significant (rightmost) bit from P.  This is the product of m and r.
caption: A Walther WSR160 arithmometer from 1960. Each turn of the crank handle adds (up) or subtracts (down) the operand set to the top register from the value in the accumulator register at the bottom. Shifting the adder left or right multiplies the effect by ten.
exif: {"Image Make": "LEICA", "Image Model": "DIGILUX 2", "Image Orientation": "Horizontal (normal)", "Image XResolution": "72", "Image YResolution": "72", "Image ResolutionUnit": "Pixels/Inch", "Image Software": "Adobe Photoshop 7.0", "Image DateTime": "2006:02:11 23:25:20", "Image Artist": "Leica", "Image YCbCrPositioning": "Co-sited", "Image PrintIM": "[80, 114, 105, 110, 116, 73, 77, 0, 48, 50, 53, 48, 0, 0, 14, 0, 1, 0, 22, 0, ... ]", "Image ExifOffset": "444", "Thumbnail Compression": "JPEG (old-style)", "Thumbnail XResolution": "72", "Thumbnail YResolution": "72", "Thumbnail ResolutionUnit": "Pixels/Inch", "Thumbnail JPEGInterchangeFormat": "1098", "Thumbnail JPEGInterchangeFormatLength": "5412", "EXIF ExposureTime": "1/60", "EXIF FNumber": "11", "EXIF ExposureProgram": "Aperture Priority", "EXIF ISOSpeedRatings": "100", "EXIF ExifVersion": "0220", "EXIF DateTimeOriginal": "2006:02:12 23:15:13", "EXIF DateTimeDigitized": "2006:02:12 23:15:13", "EXIF ComponentsConfiguration": "YCbCr", "EXIF CompressedBitsPerPixel": "8", "EXIF ShutterSpeedValue": "5907/1000", "EXIF ApertureValue": "69/10", "EXIF ExposureBiasValue": "0", "EXIF MaxApertureValue": "2", "EXIF MeteringMode": "Pattern", "EXIF LightSource": "Flash", "EXIF Flash": "Flash fired, compulsory flash mode", "EXIF FocalLength": "17", "EXIF FlashPixVersion": "0100", "EXIF ColorSpace": "sRGB", "EXIF ExifImageWidth": "2560", "EXIF ExifImageLength": "1920", "EXIF SensingMethod": "One-chip color area", "EXIF FileSource": "Digital Camera", "EXIF SceneType": "Directly Photographed", "EXIF CVAPattern": "[0, 2, 0, 2, 0, 1, 1, 2]", "EXIF CustomRendered": "Normal", "EXIF ExposureMode": "Auto Exposure", "EXIF WhiteBalance": "Auto", "EXIF DigitalZoomRatio": "0", "EXIF FocalLengthIn35mmFilm": "68", "EXIF SceneCaptureType": "Standard", "EXIF GainControl": "None", "EXIF Contrast": "Normal", "EXIF Saturation": "Normal", "EXIF Sharpness": "Normal", "EXIF SubjectDistanceRange": "1"}