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.
290
questions
0
votes
1
answer
33
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 ...
- 11
3
votes
1
answer
69
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
34
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 ...
0
votes
0
answers
28
views
Calculation of compression ratio using arithmetic encoding?
Arithmetic encoding is one of the most famous entropy encoding techniques, and I am using it to encode an image.
For this, I am using the built-in function of Matlab that also gives other values such ...
5
votes
5
answers
968
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
2k
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
32
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 ...
- 512
1
vote
1
answer
131
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
0
answers
17
views
Converting regular expression to WS1S formula
Is there a "textbook" procedure to convert a regular expression such as $((0,1)(1,0))^*$ to a formula in WS1S?
- 2,240
0
votes
0
answers
13
views
How do I implement x2 and ÷2 in Digital, and what does this exactly mean in terms of circuits? This question is for the arithmetic unit
So the first picture is an example arithmetic unit I have to implement using Digital.
The second picture is all the work I have done, however I am stuck on the meaning and implementation of x2 and ÷2.
...
- 103
0
votes
4
answers
79
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
45
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
51
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
63
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
51
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
237
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
185
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}$. ...
- 413
1
vote
0
answers
25
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
336
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
43
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
358
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 "...
- 21
1
vote
1
answer
29
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
53
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 ...
0
votes
1
answer
206
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 ...
- 349
0
votes
1
answer
153
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
203
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
93
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 ...
0
votes
0
answers
688
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
31
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: ...
- 493
1
vote
0
answers
128
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
67
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
138
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
106
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
708
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
263
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
830
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-...
1
vote
1
answer
69
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
102
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
142
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 ...
1
vote
1
answer
2k
views
Arithmetic on signed 12-bit octal number stored in sign magnitude form
What is 4365 − 3412 when these values represent signed 12-bit
octal numbers stored in sign-magnitude format? The result should be written in
octal. Show your work.
Octal to binary:
4365: 100 011 110 ...
- 147
0
votes
1
answer
40
views
Why is the carry of any n base system equal to the radix in arithmetic?
In binary the carry/borrow is 2, in hex the carry is 16. What's the reason for this?
- 1
1
vote
1
answer
557
views
Is arithmetic a context free grammar?
Like including parenthesis (( and )), addition, subtraction, multiplication, and division, and the Order of Operations in mind.
...
- 113
1
vote
2
answers
90
views
Simple question about signed integer multiplication
If you have a signed integer int x = any
And then state that x < 0
Is the following statement true or false?
...
- 11
1
vote
2
answers
48
views
Floating-point oblivious way to compute multiset numbers
I have to compute $R = \left(\!\!{n + 1\choose k}\!\!\right)$, which happens to be:
$$
R = \left(\!\!{n+1\choose k }\!\!\right) = \binom{n+k}{k} = \frac{(n + k)!}{n!k!} = \frac{(n+1)(n+2)\cdots(n+k)}{...
- 457
1
vote
2
answers
105
views
How to convert $(0.11001100...)_2$ to a decimal number
I managed to find and understand algorithm for converting any $x \in \Bbb R$ from a decimal number to binary number.
But I have a hard time finding an algorithm for converting a binary number with ...
- 124
1
vote
1
answer
808
views
Conversion of fractional part of a hexadecimal number to binary
The Number is given as : (C012.25)Hexadecimal
I have to convert it into octal .
So I converted it into Binary First and got the result as : 1100000000010010.01000000
(Since each bit in hexadecimal ...
- 15
0
votes
1
answer
2k
views
Booth's algorithm Question : Binary Number Arithmetic (Multiplication)
It's being said booth's algorithm produces the output exactly as normal binary multiplication while reducing the number of operations performed and can be used for both positive and negative numbers !
...
- 15