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.
298
questions
-1
votes
1
answer
42
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
51
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
14
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
76
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
181
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
831
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
40
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 $...
- 404
1
vote
2
answers
139
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
0
votes
2
answers
81
views
How does signed floating point adder implement?
The following picture is a block diagram of an arithmetic unit dedicated to IEEE 754 floating-point addition from Computer Organization and Design RISC-V Edition: The Hardware Software Interface 2nd ...
- 109
0
votes
0
answers
28
views
Binary Comparison Between Two Integers
Say I have two integers,i and j, which for the sake of example will be 2 and 5, represented by $010_2$ and $101_2$ respectively. I have a third bit set to 0. If $j \geq i$, then this bit should change ...
0
votes
1
answer
249
views
How do I multiply 2 signed 4 bit numbers in a logic circuit?
I've been experimenting with making a binary calculator lately, and I've got the addition and subtraction working. I now want to start making a multiplier, but I have no idea where to even start. I ...
- 103
1
vote
1
answer
87
views
Order in a subset
Lets consider a range of "K" binary digit numbers. In that range, we want to take a subset of those values which have (<="n" consecutive 0s) AND (<="n" consecutive ...
- 25
3
votes
1
answer
78
views
Division of Large Numbers with Known Factors
Consider two large numbers $a$ and $b$ of which some, not necessarily prime factors, are known. This means $a = a_1 \cdot \dots \cdot a_n$ and $b = b_1 \cdot \cdots \cdot b_m$. Required is their ...
- 151
0
votes
0
answers
41
views
Exact Definition of simple bit pattern?
I didn't find an exact description for this, but I know that any integer type is a simple bit pattern, it seems to me that the simple bit pattern should have a more exact description
as I understand ...
5
votes
5
answers
1k
views
Prove HAKMEM Item 23: connection between arithmetic operations and bitwise operations on integers
Prove that for $A, B \in \mathbb{Z}$, $A + B = (A \operatorname{\&} B) + (A \mid B) = (A \oplus B) + 2(A \operatorname{\&} B)$ where $\&$ is bitwise AND, $|$ is bitwise OR and $\oplus$ is ...
- 161
3
votes
3
answers
3k
views
DFA that accepts strings whose 10th symbol from the right end is 1
Problem is "Constructing a DFA accepting set of all strings whose 10th symbol from the right end is $1$ over $\{0,1\}$"
The NFA is easy
$$(0+1)^*1(0+1)^9$$
but DFA has to have minimum $2^{10}...
- 67
1
vote
2
answers
66
views
An Arithmetic Encoding's length being ambiguous?
Say they are two tokens, A and B. A has probability weight 0.99 (and B has 0.01). If I want to encode the sequence "AAA", wouldn't the binary encoding just be "0"? And wouldn't ...
- 542
1
vote
1
answer
221
views
How to design a DFA that accepts the language of pairs of binary words (a,b) with 5a=b?
Let $\begin{bmatrix}0\\ 0\end{bmatrix}$ be a two-column vector with $0$ in the first row and $0$ in the second row.
Let $\Sigma_2 = \left\{
\begin{bmatrix}0\\ 0\end{bmatrix},
\begin{bmatrix}0\\ 1\end{...
- 11
0
votes
4
answers
176
views
I need to test the speed of performing arithmetic operations on binary numbers
As part of a college project, I need to compare the speed of arithmetic operations directly in binary on different processors.
Example:
At what speed will binary addition be performed on an Intel Core ...
0
votes
2
answers
52
views
Logical equivalence priority
I have the logical formula
$$
A \Leftrightarrow B \Leftrightarrow C
$$
In order to make the truth table I'm not sure wheither I should interpret it as
$A \Leftrightarrow B \Leftrightarrow C$ or $A \...
0
votes
1
answer
57
views
Boolean Logic for Floats
I would like to know whether a theory exists which generalizes boolean logic to floats.
Specifically, assume that instead of booleans 1 and 0, I have True/False tendencies, such as 0.9, where 0.1. ...
-2
votes
2
answers
65
views
Java | If a=250, b=3, c=(a + b/2)/b * b, Why doesn't c equal 251 but rather 249?
If
int a = 250;
int b = 3;
int c = (a + b/2)/b * b;
Why doesn't c equal 251, but rather 249?
How is it that ...
- 109
-2
votes
1
answer
57
views
Approximate x*(a/b)^(c/d) using integer arithmetic only (assembler)
0 < x,a,b,c,d < M are all positive integers (uint64).
also, a<b if that helps.
we have assembler (integer only) operations available (e.g. division only yields integers).
we want to ...
- 101
1
vote
1
answer
385
views
How would I show function $f(x)=4x$ is Turing computable?
How to show $f: \mathbb{N} \to\mathbb{N}$ with $f(x)=4x$ where $x$ is in the set of natural numbers $x\in\mathbb{N}$) is Turing Computable?
My guess is obviously there is a finite number of operations ...
- 135
2
votes
1
answer
384
views
Cost of increasing a binary counter with a starting value n times
Consider a k-bit binary counter and suppose that in the beginning the value of the i-th most significant bit is $b_i$ for each $i = 0, . . . , k − 1$. Let $b = b_0 + 2b_1 +· · · + 2^{k−1}
b_{k−1}$. ...
- 443
1
vote
0
answers
26
views
Why does an N retries failure rate is $(1-x)^N$?
I read this blog post Fixing retries with token buckets and circuit breakers (by Marc Brooker), which goes through several retry strategies.
For the "N retries" strategy (i.e. on failure, ...
2
votes
1
answer
793
views
Addition in Lambda calculus
Found this term for a supposed 'adder' in lambda calculus.
λabcd.ac(bcd)
Although I know about alpha-conversion and beta-reduction and all that stuff, I don't know ...
- 21
1
vote
0
answers
48
views
Proving the least number of operators required equals $min((x-target)*2, (target*2)-1)$
Here is the source for the problem below: https://leetcode.com/problems/least-operators-to-express-number/discuss/1675169/java-or-recursion-or-greedy-or-math
For completeness, below is the problem ...
- 207
2
votes
3
answers
604
views
when is 2's complement used, or called into use in hardware
so when doing digital design, lets say building a calculator we only take the 2s complement of a negative number.
13+(-12)=1
001101 + 110100 = (1)000001
the 1 in parenthesis is overflow that "...
- 31
1
vote
1
answer
35
views
Buchi arithmetic meaning
I am studying this article. But I have trouble with understanding the Buchi arithmetic. It says in section IV:
... Formulas in this fragment generalise classical integer programming and are of the ...
- 113
0
votes
1
answer
36
views
Compute accuracy of program?
Is there a tool to compute the accuracy of a function in a program? Perhaps a static tool or some debugger-based tool that logs each time an arithmetic operator is applied? So one can avoid quirks in ...
- 109
1
vote
1
answer
55
views
Efficient comparison, using only sum, product, difference, and conditional jump if zero
I was wondering how small we could make the instruction set of a typical machine that supports a single datatype: arbitrary integers. If you need a heap, you declare an integer variable $h$ where you ...
- 548
0
votes
1
answer
1k
views
Addition in One's Complement
It is my belief that addition in one's complement is done the same way as unsigned addition except that if there is a carry out in the most significant bit then that carry is added to the last ...
- 369
0
votes
1
answer
198
views
How do I determine the time and space complexity of the following algorithm?
I need to compute the time and space complexity in Big O notation for this algorithm I constructed for binary multiplication.
...
3
votes
3
answers
331
views
How many possible arithmetic operations are there between two N-bit numbers?
It's generally considered to be the case that there are sixteen possible logical operations between two N-bit numbers and four possible logical operations on one N-bit number. I'd like to know how ...
- 81
0
votes
1
answer
25
views
Determine if the following arithmetics are sentences
How would you determine if these arithmetics are sentences or not?
-(x + 2) > y
i++ == 2
i++ == 2 is this sentence True where i = 1
I understand it as if the ...
0
votes
0
answers
230
views
Is there a way to convert FLOPS to bit operation per second
My problem is the following: I have $N$ inner products to compute in parallel every second.
Each of the vectors in those inner product is composed of $7$ bits.
I want to know for which $N$ it starts ...
- 137
0
votes
0
answers
1k
views
Alu architecture of a Hack Computer
I'm currently studying the ALU architecture (of a Hack computer) and how it works.
As part of my assignments, I have been asked the following question:
If we want the ALU to compute the function y-1, ...
- 1
1
vote
1
answer
32
views
Replacing the moduleo operation with occasional subtraction and one comparison
Suppose we have the following equation:
$$k_{i + 1} = (k_i + 2i + 1) \bmod{n}, \quad k_0=k, \quad i\ge 0$$
Show how we can we replace the mod with one comparison and occasional subtraction.
Attempt: ...
- 515
1
vote
0
answers
170
views
Is it possible to find length of sum of two binary numbers without calculating sum?
I'm doing an assignment where I need to multiply two 16 bit numbers and store result as an 16 bit integer array.
a is binary with length of ...
- 11
1
vote
2
answers
79
views
Why is the time complexity of the Bit Manipulation solution to Binary Addition O(M + N)?
I am trying to understand why the time complexity of the Bit Manipulation solution (https://leetcode.com/problems/add-binary/solution/) to the Binary Addition problem is O(M + N), where M and N are ...
- 125
4
votes
2
answers
155
views
Is there a good algorithm to divide two integers without using division directly?
Problem. Given positive integers $a$ and $b$, obtain $\frac{a}{b}$ without using division ($/$) directly, though addition ($+$), subtraction ($-$), multiplication ($\times$) and bit-shifts ($\gg$ and $...
Milin
2
votes
1
answer
179
views
How can I do a subtraction with a two tape Turing machine
I have already made a Turing machine with just one tape that solves a subtraction between two numbers, but I trying to do the same but with TWO tapes.
As an example, how can I solve 4-2?
Taking ...
1
vote
2
answers
2k
views
Represent unsigned 12-bit octal numbers. Results in octal
I have an HW question where I found an answer that matches mine, but their breakdown confuses me.
Ques: What is 4365 - 3412 when these values represent unsigned 12-bit octal numbers? The result should ...
- 11
-4
votes
1
answer
920
views
Is squaring easier than multiplication? [duplicate]
Let $T_1(n)$ be the time complexity of computing the square of an $n$-bit integer, and let $T_2(n)$ be the time complexity of computing the product of two $n$-bit integers.
Assuming that addition is ...
- 111
1
vote
2
answers
544
views
Adding two numbers in base 2(floating point) vs Multiplying two numbers in base 2(floating point)
Is it true that adding two numbers in base 2 is more complex than multiplying them? If so can someone please explain why this is the case?
- 11
0
votes
0
answers
1k
views
How to do -8 x -8 in a 4 bit booth multiplier?
In the general case of an n bit booth multiplier, the maximum negative value is -2n-1. So with 4 bits we can represent -8 x -8 (M=1000, Q=1000). Now if we follow Booth's algorithm for multiplying n-...
- 101
1
vote
1
answer
169
views
2's complement substraction
I need to perform 2's complement operations on -50 - -48
From a mathematical point of view the following would be true.
-50 + 48 = -2
If I would follow the steps I would have:
I got to this result by ...
- 13
3
votes
1
answer
186
views
What's the average number of transistor switches needed to do an N-bit x N-bit multiply?
I want to know how switch-efficient a multiplier can be. If I need to do many $N$-bit by $N$-bit multiplies, and each bit is determined by flipping a coin, what's the average number of transistor ...
- 41
1
vote
3
answers
149
views
How to determine the set of real numbers corresponding to a given floating point number?
Let's say we consider IEEE 754 double precision floating-point numbers, and we use RNTE - Round To Nearest, Ties to Even - rounding.
I know that the RNTE rounding works this way:
given two consecutive ...