Questions tagged [arithmetic]
Questions about implementing elementary arithmetic operations on a computer with hardware or algorithms. The numbers are often assumed to be in a binary representation, add the [floating-point] tag for arithmetic operations on numbers in a floating point representation.
334 questions
1
vote
2
answers
125
views
Time complexity of adding $n$ numbers with $n\log n$ bits each
I'm trying to determine the time complexity of adding $n$ numbers that each have a bit length of $n\log n$. I'm confused because sometimes I've seen the addition of two $n$ bit numbers as requiring $O(...
- 1,683
2
votes
1
answer
141
views
Formal analysis of floating point error
Is there a formal way of analyzing an algorithm on floating points (a list of operations of floats) such that the outputs of the operations becomes clear and the output of the algorithm can be bounded ...
- 67
3
votes
0
answers
90
views
Understanding the proof of a Theorem in Knuth's TAOCP about floating-point addition and subtraction
This is about the proof of Theorem A on pg. 235 of Knuth's "The Art of Computer Programming" Vol. 2, 3rd Ed.
Background:
By "normalized floating point number" Knuth means a number ...
- 350
0
votes
0
answers
93
views
Combinatorial binary multiplication whilst keeping k least significant bits
Given two sets of m binary variables representing two unsigned binary numbers, $a=(2^{m-1}a_{m-1}, 2^{m-2}a_{m-2},...,2^{0}a_{0})$, and $b=(2^{m-1}b_{m-1}, 2^{m-2}b_{m-2},...,2^{0}b_{0})$, where $a_i, ...
- 101
1
vote
1
answer
93
views
How does processor differentiate from signed and unsigned integers overflow and carry
since unsigned and signed integers uses same components to compute then how does the overflow and carry flags are set?
- 11
1
vote
0
answers
59
views
Möller-Granlund Reciprocal Calculation for Arbitrary Bases
In their paper Improved division by invariant integers, Niels Möoller and Torbjörn Granlund describe an algorithm (Algorithm 2 and Algorithm 3) based on Newton-Raphson iteration to efficiently ...
0
votes
0
answers
164
views
What is SRT division algorithm?
I have been studying the IEEE-754 standard and came across the information that floating-point division uses the SRT algorithm, ...
-1
votes
1
answer
91
views
Why is ot returning TRUE in first case and FALSE in the second?
I understand 0.3 does not have an accurate binary representation.
Suppose I run the following code:
Why is the answer "True" in the first case and "False" in the second? Shouldn't ...
- 101
0
votes
1
answer
110
views
Binary subset rank and unrank
Let there be "N" bits.
We want to rank and unrank a specific subset of bit combinations based on the following criteria -
...
- 25
0
votes
0
answers
53
views
Check if sum of positive integers is less than a W integer in CNF
As title says, what I am trying to do is to find a way to sum integers and later compare them with another integer W, in a manner that when the sum of integers is less or equal than W, using only CNF.
...
1
vote
1
answer
117
views
smoothness test
An integer is $k$-smooth if its prime factors are at most $k$.
In the case where $k$ is not tiny (say $10^8 < k < 10^{10}$),
are there algorithms to test for $k$-smoothness, other than trying ...
- 111
1
vote
2
answers
343
views
Binary logarithm of binary number using logic gates
I need to use logic gates to calculate the floor of binary logarithm of a binary number $x_{n-1}, ..., x_0$.
I know that this can be computed when I find the position of the most significant bit set ...
- 183
9
votes
2
answers
891
views
Usefulness of binary extension field GF(2^n)
The binary extension field, usually denoted as $\textsf{GF}(2^n)$ or $\mathbb{F}_{2^n}$, is a finite field of characteristic 2.
Are there any applications of $\textsf{GF}(2^n)$ (or more broadly, $\...
- 444
0
votes
1
answer
100
views
Finding solution to Mv=v over $\mathbb{Z}$={0,1} for matrix M given a set linearly independent v
Under mod 2 arithmetic ($\mathbb{Z}$={0,1}), given a set $V$ of $n$x$1$ linearly independent vectors $\{x_1,...,x_n\}$ I'd like to find a $n^2$ binary matrix $M$ such that $Mv=v$ where $v \in V$ and $...
- 394
1
vote
2
answers
225
views
Check if n-bit number is divisible by 7
Show how to check if n-bit number is divisible by 7 in logarithmic circuit depth.
How can I construct the circuit to be able to check the divisibility?
- 183