# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
2k views

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?
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. ...
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 ...
45 views

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 ... -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 ... 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 ... 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}$. ... 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 ... 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 ... 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 "... 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 ... 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 ... 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 ... 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 ... 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 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: ... 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 ... 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 ... 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$... 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
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 ...
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 ...
1 vote
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?
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
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 ...
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 ...
1 vote
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
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 ...
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 vote
557 views

### Is arithmetic a context free grammar?

Like including parenthesis (( and )), addition, subtraction, multiplication, and division, and the Order of Operations in mind. ...
1 vote
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? ...
1 vote
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)}{...
1 vote
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 ...
1 vote