The tag has no usage guidance.

learn more… | top users | synonyms

-3
votes
1answer
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
22 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: ...
2
votes
1answer
62 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 ...
1
vote
0answers
49 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 ...
2
votes
1answer
87 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 ...
2
votes
2answers
113 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 ...
9
votes
1answer
242 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$ ...
1
vote
2answers
58 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 ...
-1
votes
1answer
28 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 ...
4
votes
1answer
296 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 ...
3
votes
3answers
427 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 ...
5
votes
2answers
248 views

Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?

According to page 53 of Modern Computer Arithmetic (pdf), all of the steps in the Schönhage–Strassen Algorithm cost $O(N \cdot \lg(N))$ except for the recursion step which ends up costing $O(N\cdot ...
7
votes
2answers
243 views

Why is the transform in Schönhage–Strassen's multiplication algorithm cheap?

The Schönhage–Strassen multiplication algorithm works by turning multiplications of size $N$ into many multiplications of size $lg(N)$ with a number-theoretic transform, and recursing. At least I ...
10
votes
1answer
1k views

Why doesn't Knuth's linear-time multiplication algorithm “count”?

The wikipedia page on multiplication algorithms mentions an interesting one by Donald Knuth. Basically, it involves combining fourier-transform multiplication with a precomputed table of ...
3
votes
1answer
642 views

Fast algorithm for matrix chain multiplication in special case

An exercise from the book Foundations of Algorithms Using Java Pseudocode: Write an efficient algorithm that will find an optimal order for multiplying $n$ matrices $A_1 \times A_2 \times \ldots ...
6
votes
2answers
165 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 ...
1
vote
1answer
163 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 ...
2
votes
3answers
193 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 ...
3
votes
1answer
481 views

Shift-and-or multiplication operation

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 ...
3
votes
2answers
388 views

Carry-free multiplication operation

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 ...