Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
34 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 - ...
Dave's user avatar
  • 23
0 votes
0 answers
10 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. ...
Francisco Jos Rodriguez Rugele's user avatar
1 vote
1 answer
75 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 ...
Pascal Ochem's user avatar
1 vote
2 answers
140 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 ...
popcorn's user avatar
  • 183
9 votes
2 answers
807 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, $\...
Tianren Liu's user avatar
0 votes
1 answer
38 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 $...
James Bowery's user avatar
1 vote
1 answer
86 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?
popcorn's user avatar
  • 183
0 votes
1 answer
51 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 ...
user153245's user avatar
0 votes
0 answers
24 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 ...
MrStealYourFrog's user avatar
0 votes
1 answer
174 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 ...
Tetie's user avatar
  • 103
1 vote
1 answer
80 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 ...
Dave's user avatar
  • 23
3 votes
1 answer
72 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 ...
Bob Aiden Scott's user avatar
0 votes
0 answers
38 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 ...
Gor Madatyan's user avatar
0 votes
0 answers
71 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 ...
Sahil Sharma's user avatar
5 votes
5 answers
989 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 ...
Ntwali B.'s user avatar
  • 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}...
mark's user avatar
  • 67
1 vote
2 answers
50 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 ...
chausies's user avatar
  • 532
1 vote
1 answer
206 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{...
Patrick's user avatar
  • 11
0 votes
4 answers
140 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 ...
Kamil Pietrzak 'Moneta''s user avatar
0 votes
2 answers
50 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 \...
tixerauRIP's user avatar
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. ...
Sebastian F.'s user avatar
-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 ...
Coo's user avatar
  • 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 ...
imi kim's user avatar
  • 101
1 vote
1 answer
336 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 ...
Fred's user avatar
  • 135
2 votes
1 answer
349 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}$. ...
SVMteamsTool's user avatar
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, ...
HelterSkelter's user avatar
2 votes
1 answer
636 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 ...
SNEED's user avatar
  • 21
1 vote
0 answers
47 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 ...
user3472's user avatar
  • 207
2 votes
3 answers
532 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 "...
Magnio's user avatar
  • 21
1 vote
1 answer
34 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 ...
Vahid Shams's user avatar
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 ...
Emil's user avatar
  • 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 ...
Daniel Donnelly's user avatar
0 votes
1 answer
993 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 ...
Bob's user avatar
  • 359
0 votes
1 answer
187 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. ...
Shreyash_Gupta's user avatar
3 votes
3 answers
290 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 ...
Anthony's user avatar
  • 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 ...
mattssoncode's user avatar
0 votes
0 answers
182 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 ...
StarBuck's user avatar
  • 137
0 votes
0 answers
977 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, ...
Hynisel's user avatar
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: ...
Avv's user avatar
  • 505
1 vote
0 answers
158 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 ...
trofchik's user avatar
1 vote
2 answers
76 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 ...
Henry Zhu's user avatar
  • 125
4 votes
2 answers
150 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 $...
user avatar
2 votes
1 answer
166 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 ...
Sebastian vargas torres's user avatar
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 ...
David's user avatar
  • 11
-4 votes
1 answer
874 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 ...
anirudh's user avatar
  • 111
1 vote
2 answers
505 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?
Roy Fischer's user avatar
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-...
Tony Gweesip's user avatar
1 vote
1 answer
153 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 ...
Scilla's user avatar
  • 13
3 votes
1 answer
162 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 ...
abergal's user avatar
  • 41
1 vote
3 answers
147 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 ...
Fabio Nardelli's user avatar

1
2 3 4 5 6