Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
37 views

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

The following program implements a simple algorithm for binary multiplication: ...
1
vote
4answers
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 ...
1
vote
1answer
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 ...
2
votes
2answers
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$. ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
3
votes
1answer
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) ...
2
votes
1answer
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 ...
1
vote
0answers
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, ...
0
votes
1answer
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 ...
1
vote
0answers
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, ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
2answers
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}\}$...
3
votes
1answer
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(...
0
votes
3answers
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 ...
1
vote
1answer
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 ...
4
votes
0answers
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 ...
-3
votes
1answer
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 !...
1
vote
0answers
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 ...
4
votes
1answer
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 ...
0
votes
1answer
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/...
2
votes
1answer
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 "...
1
vote
0answers
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 ...
4
votes
1answer
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 ...
2
votes
2answers
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 ...
9
votes
1answer
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$ ...
1
vote
1answer
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 ...
-1
votes
1answer
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 ...
5
votes
1answer
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 ...
4
votes
3answers
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 ...
6
votes
2answers
1k 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
439 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 ...
14
votes
1answer
2k 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
2k 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 \...
7
votes
2answers
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 ...
1
vote
1answer
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 ...
3
votes
3answers
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 ...
3
votes
1answer
537 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
885 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 long-...