Member Avatar for ranjithsnair

can anybody give me the program to solve booth algorithm............

  • 3 Contributors
  • 2 Replies
  • 56 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by jephthah

Dani AI

Generated

— you asked for a Booth algorithm program. and did not give a working answer, so here is a short, accurate explanation and compact pseudocode you can translate to C++.

Booth's algorithm multiplies two signed (two's complement) n-bit integers using registers A (accumulator), Q (multiplier), M (multiplicand) and a single bit Q_1. Initialize A = 0 and Q_1 = 0. Repeat n times: examine the pair (Q0, Q_1). If it is 01 then A = A + M; if it is 10 then A = A - M; otherwise do nothing. Then perform an arithmetic right shift on the concatenated (A, Q, Q_1). After n iterations the 2n-bit product is the concatenation of A and Q.

A = 0
Q = multiplier      # n-bit two's-complement
M = multiplicand    # n-bit two's-complement
Q_1 = 0
for i from 0 to n-1:
    q0 = Q & 1
    if (q0, Q_1) == (1,0):
        A = A - M
    elif (q0, Q_1) == (0,1):
        A = A + M
    (A, Q, Q_1) = arithmetic_right_shift(A, Q, Q_1)   # shift concatenated registers, preserve A's sign
# product = (A << n) | Q   # 2n-bit result

Implementation tips: use fixed-width types (int32_t/int64_t) and store the final 2n-bit result in a wider unsigned type to avoid overflow. Implement the arithmetic right shift explicitly (or use unsigned shifts with manual sign extension) because right-shifting signed negatives is implementation-defined in C++. Test thoroughly with positive, negative and mixed-sign cases (for example 73, -34, -7 * -3 and edge cases like INT_MIN). For background and worked examples see Booth's algorithm (Wikipedia) and . If desired, a concise C++ implementation can be posted next.

Recommended Answers

All 2 Replies

Member Avatar for jephthah

yes....

oops. i mean, no.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.