# Tagged Questions

The tag has no usage guidance.

37 views

### Difficulty understanding the faster multiplication hardware

This is a picture of faster multiplication hardware taken from Computer Organization and Design (5th Edition). I'm having some difficulty understanding it. I was trying to simulate this for a test ...
38 views

### Booth bit-pair recoding of multipliers

1) In Booth's bit-pair recording technique how to multiply a multiplicand with 2? 2) In booth's algorithm for multiplication/Booth's bit-pair recording of multipliers, the sign bit extension of the ...
37 views

### Is there any bitwise multiplication algorithm that is sub O(n^2)?

The following program implements a simple algorithm for binary multiplication: ...
87 views

### Float multiplication

While doing the multiplication 1.4*0.8 in a python program, I got the result as 1.1199999999999999. Why didn't I get ...
41 views

### Efficiently compute parallel matrix-vector product for block vectors?

I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I now want to compute the matrix-vector product $$w = (E\otimes I_N)v$$ in parallel, where $\otimes$ is the ...
53 views

### Necessity of convolution operations for product of two polynomials via brute force method

Reference: Page 4 of this document Given two polynomials $p(x)$ and $q(x)$ each of degree $n$ represented in coefficient form, it takes $\mathcal{\Theta}(n)$ time to evaluate given some input $x$. ...
746 views

### Understanding 2's complement multiplication using Booth's algorithm

I was referring Booth's algorithm for 2's complement multiplication from William Stallings book. It was explained as follows (please ignore two starting words "As before", it still makes complete ...
50 views

### Use of FFT in order to multiply two positive integers of $n$ digits

We're given two positive integers $t$ and $s$ of length $n$ in binary representation. Suppose we divide the numbers into ${n \over k}$ blocks of size $k=\lg n$ using FFT algorithm. Suppose ...
24 views

### Comparison of two place-value multiplying methods for n-digit positive integers

I'd like to know some theory behind the two ways of multiplying two n-digit numbers n>0. My initial was to create an algorithm for multiplying numbers encoded in place-value format. Few of the ...
191 views

### Karatsuba Multiplication with n/3 division of large number

I was studying Karatsuba multiplication where the complexity is reduced as compared to classical algorithm by splitting each number into two parts. Now I'm trying to understand how the multiplication ...
114 views

### Linear time multiplication on RAM machine?

This page says following: Integer Multiplication has an O-optimal linear-time algorithm on a RAM or SMM Is this page fooling me or how can we multiply 2 numbers in linear time (bitwise complexity) ...
192 views

### Lower Bound of Matrix Multiplication

I am reading the textbook algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani The authors state in page $67$: The preceding formula implies an $O(n^3)$ algorithm for matrix ...
219 views

### Matrix Vector Multiplication Parallel

CLRS book has the following algorithm for parallel for matrix vector multiplication My problem is, can't we use a simple approach like this, ...
266 views

### Lower bound on multiplication

I was told that the fastest possible algorithm for integer multiplication is $O\left(n{\log}(n)\right)$. Why would this so?   Can you please show why the fastest multiplication algorithm would ...
30 views

### Largest parallelization speedup for multiplication of very large numbers

I have recently come across the following papers: S. Baktir and E. Savas. Highly-parallel Montgomery multiplication for multi-core general-purpose microprocessors. In E. Gelenbe and R. Lent, editors, ...
59 views

### Swap elements using integer addition and multiplication gates

I need to swap two integers using only integer addition and multiplication gates. I can't subtract them. I'm dealing with a sorting network, so I need to compare and swap. The compare and swap ...
182 views

### Minimum depth of addition and multiplication circuit using XOR and AND gates

What are the minimum depth circuits possible for addition and multiplication of two n-bit numbers using just AND and XOR gates? I read somewhere that we can achieve constant depth for addition if we ...
1k views

### Karatsuba multiplication on numbers with odd length

I am learning about Karatsuba-Ofman multiplication. I don't quite understand how to multiply two numbers with odd length. Let's take two 3-digit numbers $a = 234; b = 857$ with base $B = 10$ and ...
70 views

### $(max,+)$ matrix product with limited number of values

I read that there is a $\Omega(n^3)$ lower bound for $(max,+)$ matrix multiplication (with $n\times n$ matrices). This is the matrix product defined as: $(A\cdot B)_{ij}:=\max^n_{k=1}\{A_{ik}+B_{kj}\}$...
170 views

### Can Strassen's multiplication algorithm be improved if we divide matrices to 3x3 or axa in general?

Strassen's algorithm uses the divide and conquer approach to divide the matrix multiplication of two nxn matrices to multiplication of 7 2x2 matrices to get an overall complexity O(n^c) where c=log_2(...
7k views

### Booth bit-pair recoding technique

In Booth's bit-pair recording technique how to multiply a multiplicand with -2 or 2? For example while multiplying 01101(+13, multiplicand) and 11010(-6, multiplier), we get 01101 x 0-1-2. How to ...
136 views

### Long multiplication school method: number of primitive operations to calculate first partial product?

Having got some basics down in regard to addition and explaining it in terms of primitive operations (addition and multiplication), I am now again stuck on understanding the more complicated long ...
74 views

### Quantum circuits for multiply-accumulation

Classically, multiplication can be done in $O(n \ \lg(n) \ 8^{\lg^* n})$ steps on a multi-tape Turing machine via Fürer's algorithm. Using that algorithm, combined with uncomputing, you can make a ...
164 views

### calculate result of multiplication between two 32 bits vars into two 32 bit vars [closed]

how would I go about multiplying two 32 bit numbers (lets say unsigned) and putting the result into two 32 bit vars , one for the msbits and one for lsbits . It should be simple but im stuck thanks !...
36 views

### How to compute multiplication in $\mathbb{Z} / n\mathbb{Z}$? [closed]

Good day, I have heard about the Montgomery modular multiplication, and the Barrett_reduction; (or any other) But in practice I don't understand how could I implement a multiplication algorithm in a ...
138 views

### Is matrix “adjoint-squaring” faster than general matrix multiplication?

The best known algorithm(s) for matrix multiplication of $n$-dimensional matrices take $O(n^{2.37})$ time. However, that's for matrices with totally independent contents. When the two matrices are ...
146 views

### EPI question on multiplying two integers

The Elements of Programming Interviews book has a question on "computing x*y without arithmetical operators" (question 5.5). The solution is here: https://github.com/epibook/epibook.github.io/blob/...
1k views

### How many basic operations are there in an algorithm for the simple multiplication of two numbers of equal length?

BACKGROUND: Note: The following question arose in my mind when watching this lecture (watch at 5:30 minutes if you will). Assumption: Just for the sake of this question, let's assume that the term "...
311 views

### Dividing/Multiplying Numbers Stored in two memory locations

I have two numbers x and y. The upper bits of x are stored at location m, while the lower bits of x are stored at location n. The upper bits of y are stored at location i, while the lower bits of y ...
532 views

### In fast multiplier circuits, what is the difference between a Counter and a Compressor?

When working on fast parallel multiplier circuit designs, like Wallace tree multipliers or Dada tree multipliers I found many papers and books refer to different components used in the tree to reduce ...
959 views

### Controlling overflow and loss of precision during floating point multiplication

I have a large number of floating point numbers (~10,000 numbers) , each having 6 digits after decimal. Now, the multiplication of all these numbers would yield about 60,000 digits. But the double ...
850 views

### Algorithm for multiplying multivariate polynomials

Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multidimensional polynomials in $R$ with maximal total degree $\delta$. How fast can we compute the product of $f$ ...
217 views

### Efficient (sublinear) approximation algorithms for matrix-vector multiplication?

Given a matrix $A \in \mathbb{R}^{n \times p}$ and a vector $x \in \mathbb{R}^p$, I am interested in computing the value of the mean matrix-vector product: $$v = \frac{1}{n} Ax$$ If I did this using ...
67 views

### Scalar by N component vector multiplication faster than O(N)?

Is there a way to multiply scalar by vector faster than just multiplying each element of the vector by that scalar? It feels to me that there should be some exploit to do that. After all we will ...
642 views

### Fixed base exponentiation with precomputations

I'm trying to compute $g^m$ mod $n$ where $m,n$ are 1024-bit numbers. The method I want to use is fixed base exponentiation with precomputations, also known as fixed-base windowing.The paper I'm ...
3k views

### How can I compute an exponential modulo a large integer?

Does anyone have the computational power to check whether or not $F(m)^d \equiv m \pmod n$, where the values of the variables are found below. According to Wolfram Alpha, I found the result of the ...
1k views

258 views

### Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial

I'm reading this Intel white paper on carry-less multiplication. It describes multiplication of polynomials in $\text{GF}(2^n)$. On a high level, this is performed in two steps: (1) multiplication of ...
247 views

### NFA for right left multiplication

Given the following multiplication table how could one construct an NFA such that it accepts all strings that have a certain product (say a) ? The string "abcb" would be evaluated as (a(b(cb))) = a ...
1k views

### Does the performance of matrix multiplication depend on the storage of the array?

Two matrices can be stored in either row major or column major order in contiguous memory. Does the time complexity of computing their multiplication vary depending on the storage scheme? That is, I ...
Continuing in the same vein as Carry-free multiplication operation, a followup question is as follows (differences in bold): Let $r = p \oplus q$ be an operation similar to multiplication, but ...
In long-multiplication, you shift and add, once for each $1$ bit in the lower number. Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-...