# Tagged Questions

The tag has no usage guidance.

59 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 ...
24 views

### Quantum circuits for multiplication

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 ...
23 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 !...
32 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 ...
69 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 ...
25 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/...
67 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 "...
53 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 ...
105 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 ...
130 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 ...
296 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$ ...
74 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 ...
30 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 ...
327 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 ...
521 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 ...
256 views

190 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 ...
167 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 ...
212 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-...