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.
291
questions
0
votes
0
answers
22
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
65
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
0
answers
12
views
Computation of composition of analytic functions [closed]
There are several algorithms available for computing the approximate values of functions. These can involve methods like the arithmetic-geometric mean or the Taylor series. Given a set of analytic ...
- 11
1
vote
1
answer
64
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 ...
- 23
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
41
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
974
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
37
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 ...
- 532
1
vote
1
answer
150
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
86
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
48
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
54
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
54
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
259
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
270
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}$. ...
- 423
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
435
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
45
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
419
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
32
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 ...
- 495
0
votes
1
answer
495
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
168
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
220
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
125
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
795
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
139
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
69
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
145
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
136
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
757
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
350
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-...
1
vote
1
answer
93
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
118
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
143
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
3k
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
607
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
92
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
49
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
107
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
1k
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