Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [arithmetic]

The tag has no usage guidance.

0
votes
1answer
54 views

Is arithmetic turing complete?

Maybe my question doesn't make sense, because I lack some more thorough understanding, but I was curious if arithmetic was Turing complete? As I understand it, a "model of computation" is a mechanism ...
4
votes
1answer
46 views

Why integer division is of equal complexity as multiplication

I am trying to understand the fact that integer division is no more difficult than integer multiplication. I found some references - here and this lecture note. Wikipedia says if there is a way to ...
0
votes
1answer
40 views

Find value of $a$ or $b$ of two XOR equations

Is it possible to find $a$ or $b$ given that $a \oplus b = c$ and $c \oplus b = a$ when I only have the value of $b$?
1
vote
2answers
30 views

Increased rounding relative error when subtracting

I'm reading the book "Lessons in Scientific Computing" by Schoerghofer and it says: If x and y are real numbers of the same sign, their sum x + y has an absolute error that adds the two ...
1
vote
1answer
30 views

Addition errors in IEEE754 floating point representation

So in class, we were talking about the idea of floating point precision in IEEE754 format, and how, when some numbers are added, precision is lost. My professor then gave the following example of a ...
2
votes
1answer
32 views

Overflow rule in two's complement arithmetic

In the book by William Stallings the overflow rule overflow rule for 2's complement addition is stated as follows: Overflow rule: If two numbers are added, and they are both positive or both ...
0
votes
0answers
17 views

IEEE-754 and machine numbers

I've been trying to wrap my head around machine numbers like the unit roundoff (u) and epsilon (e) in combination with the IEEE 754 standard. My textbook states some things that don't really make ...
1
vote
1answer
105 views

Algorithms for elementary operations using other elementary operators

The question asks to provide an algorithm to compute $(i)$ The product of $n$-bit numbers using reciprocation operation and addition operation but not using multiplication and squaring. $(ii)$ The ...
2
votes
0answers
77 views

What is the simplest automaton that can compute the sum of two integers of arbitrary length?

It should be obvious that a Turing machine is capable of computing the sum of two integers. However, what is the simplest automaton that can compute the sum of two integers of arbitrary length? I ...
1
vote
1answer
25 views

Why Does The Division Alorithim Need [Register Size] + 1 Iterations

Following this flow diagram for division hardware I made a program to "simulate" division on $N^+$. ...
0
votes
2answers
63 views

Given $0 <(x, y) < z < 2^{64}$, How can I compute $\lfloor \frac{xy}{z} \rfloor$ using only 64-bit arithmetic operations?

I can compute this easily in the case that $xy < 2^{64}$. But I'm not sure how to do this if $xy \geq 2^{64}$. I know that $\lfloor \frac{xy}{z} \rfloor = \frac{xy - (xy\ \text{mod} \ z)}{z}$, but ...
0
votes
1answer
45 views

Efficient way to compute mod(w +1) or mod(w - 1) where w= 2^p

Knuth in his book provides a method of how to efficiently calculate mod(w +1) or mod(w-1) where w is a power of 2. I am not sure I could understand his assembly language completely. Could you explain ...
1
vote
1answer
40 views

IP Address CIDR Bitmask Conversion

In looking for a programming function to validate an IP address within a subnet, I had to calculate the subnet mask from a given CIDR bitmask value ie. 192.168.0.0/24, the value 24 in this example. ...
1
vote
1answer
58 views

Algorithm for implementing the modulus “%” operator?

How can an efficient modulus operator be implemented? Here's a naive way of defining A % B: given $(a,b) \in \mathbb{Z}$ (represented as ...
0
votes
0answers
247 views

Booth bit-pair recoding of multipliers

1) In Booth's bit-pair recording technique how to multiply a multiplicand with 2? 2) In booth's algorithm for multiplication/Booth's bit-pair recording of multipliers, the sign bit extension of the ...
2
votes
1answer
21 views

Emulating equal operator using multiplication

I have two values $A$ and $B$, I want to know if I can implement the equals $=$ operation as the product of the two values. I can apply any function to $A$ and any function to $B$, but I need to use ...
2
votes
1answer
34 views

Implementing Gauss–Legendre algorithm using arbitrary-length rationals

I am trying to re-implement SuperPI myself in Rust, but the results I get are not very accurate. SuperPI computes pi using the Gauss-Legendre algorithm. The Gauss–Legendre algorithm is quite simple, ...
-1
votes
1answer
30 views

How can the binary OR function be computed by a MOD3 gate of constant fan-in?

I've been working on a problem and in order to prove the bigger picture, I need to understand how a binary OR function can be computed by a constant fan-in MOD3 gate. I would seem that the output ...
0
votes
1answer
36 views

Complexity of numerical operations

I have written a program which contains a while loop: while k < sqrt(n), so clearly my program evaluates $\sqrt{n}$ at each iteration of the while loop. (Note ...
1
vote
2answers
167 views

Is IEEE 754 float arithmetic associative, commutative, distributive, etc? Why?

Does the associative/commutative/distributive/etc property hold for arithmetic performed with IEEE 754 floats? Obviously the answer is no to most of those questions, but do any of the properties of ...
2
votes
2answers
50 views

Why is the number of digits (bits) in the binary representation of a positive integer $n$ is the integral part of $1 + \log_2 n$?

I've stumbled on this definition on Wikipedia, and I can't figure out why. I could probably start the demonstration by saying that, with $n$ bits, you can create $2^n$ possible different numbers, so $...
6
votes
1answer
112 views

Relation between “undecidability of arithmetic” and “godel's incompleteness theorem”?

There is a theorem that states that arithmetic is undecidable: i.e. $Th(\mathcal N)$, the set of all sentences in the standard arithmetic structure $\mathcal N=(\mathbb N,+,\cdot , 0,1)$ where the ...
0
votes
0answers
39 views

Could computers ever calculate faster using the decimal system? [duplicate]

I don't know exactly how computers calculate very big numbers but i'm guessing they store them in memory and calculate on the fly. But since memory can be very limited compared to a hard drive ...
1
vote
1answer
37 views

How to produce all the numbers in a range [0,1,…,n] for which if 0<=k<=n, then for a positive integer x, the expression: k & x = k?

I am trying to figure out an efficient way to produce all the numbers in a given range for which, their bitwise AND with a positive integer (say x) gives the same number; that means k & x = k. Is ...
1
vote
0answers
18 views

Ultrametric Binary States

All metric spaces obey the triangle inequality which is, for three points $a,b,c$, that $$d(a,c) \le d(a,b) + d(b,c)$$ One interesting special case of a metric space is one endowed with an ...
4
votes
0answers
36 views

Bridging inductive natural number and bits?

Most popular representation for the natural numbers in type systems is: Inductive nat : Set := | 0 : nat | S : nat -> nat. However, digital computers ...
4
votes
2answers
340 views

Two's complement addition

I am currently learning about a CPU's status register and was confused about the difference between the carry flag and the overflow flag. Then I found article [1] which explains it very well, but I ...
4
votes
2answers
493 views

Which number representation takes the largest amount of memory?

Options are: Signed magnitude One's complement Two's complement Excess notation This is the question from an 'example of a previous exam' I've been given at university. Answers were not provided. ...
6
votes
2answers
469 views

Arithmetic network to compute floor of binary logarithm

I wonder how to build efficient arithmetic network (using logical gates only) to compute floor of binary logarithm of the given input number. I have read some articles on stackoverflow.com about this ...
2
votes
0answers
70 views

Vandermonde matrix and its binary representation

Say one is given a Vandermonde matrix (https://en.wikipedia.org/wiki/Vandermonde_matrix) of dimension $2^q \times k$ such that the elements of the first column of it are $\{0,1,2,..,-1+2^q\}$. (This ...
4
votes
0answers
62 views

Bignum divisibility algorithm

I need to test whether an integer $b$ divides another integer $a$. Both integers are “bignums”, in the cryptography range ($10^2$ to $10^4$ bits). The integers are represented in binary. Assume that ...
1
vote
1answer
443 views

Signed and Unsigned Loads in a 32-bit Registers

I have a question over this quote directly out of Computer Organization and Design, 5e: Signed versus unsigned applies to loads as well as to arithmetic. The function of a signed load is to copy ...
1
vote
1answer
122 views

n-bit 2's Complement Conversion

I'm learning 2's complement conversion for positional number systems. For the most part I have only seen 2's complement for represented in 8-bits. I had a discussion with a friend who explained that ...
8
votes
4answers
5k views

How can I multiply a binary representation by ten using logic gates?

So I’m currently working on something and I have converted all decimal digits 0-9 into binary. But now I want to take say 6 in binary and increase its order of magnitude by base 10 (turning 6 into 60) ...
2
votes
0answers
202 views

Simple algorithm for IEEE-754 division on 8-bit CPU?

IEEE Std 754-2008 is the modern definition of Floating-Point Arithmetic. It requires that division (among other operations) performs as if it first produced an intermediate result correct to ...
3
votes
1answer
152 views

How would one use “BUT” logic in a ternary logic computer in a practical way?

Using three valued logic one can define a multitude of ternary operations. When dealing with 5:3:1[1] operations, its very easy to see how ...
3
votes
2answers
76 views

How to find the closest N to the power of X to the given number?

Let's say we have number 4920 and we want to find the closest $n^x$ to 4920 2 ^ 12 = 4096 but it's not the closest possible $n^x$, for example 17 ^ 3 = 4913 is closer to 4920 The question is, how do ...
1
vote
1answer
86 views

What are some of the practical applications of functions that extract the exponent and mantissa of a floating point number?

I'm talking about functions such as Python's math.frexp() : math.frexp(x) Return the mantissa and exponent of x as the pair (m, e). m is a float and e is an integer such that x == m * 2**e ...
1
vote
2answers
57 views

Are fractions more computationally “expensive” than whole numbers?

I have a problem where the values are represented to humans as [0, .5, 1, ..., 8] But the function is massively recursive (game trees for a set of increasingly intractable problems) so I'm wondering ...
1
vote
0answers
27 views

Bitwidth requirements for the division algorithm using redundant radix

I'm studying the chapter "Division by Digit Recurrence" in "Digital Arithmetic" of Ercegovac. I like this book is overall well written. Although sometimes I struggle understanding some aspect like the ...
4
votes
2answers
3k views

Computing exam averages in less than linear time

This is the question: A spreadsheet keeps track of student scores on all the exams in a course. Each row of the spreadsheet corresponds to one student, and each column in a row corresponds to his/...
3
votes
0answers
35 views

Is it correct to say that there are similarities between CORDIC and digit recurrence algorithm for division?

I've been studying recently some variations of the CORDIC, and it seems to me that the logic behind at least the basic cordic or the redundant CORDIC is very similar to the logic used to design digit ...
0
votes
1answer
191 views

GCD binary representation time complexity

1. Consider the following algorithm for deciding GCD: “On input : ...
4
votes
1answer
40 views

How many bits to represent a quantity $\omega$ bounded in a particular way?

I'm working out some details to implement a division algorithm, I'm following the explanation given in this book (chapter 5) for who is interested. Anyway I need to work out how many bits are ...
66
votes
9answers
15k views

Why is addition as fast as bit-wise operations in modern processors?

I know that bit-wise operations are so fast on modern processors, because they can operate on 32 or 64 bits on parallel, so bit-wise operations take only one clock cycle. However addition is a complex ...
3
votes
1answer
305 views

Subset of numbers whose XOR has least Hamming weight

I'm given $n$ numbers (let's say of some 100 bits or so). Is there a way to find a non-empty subset xor of these $n$ numbers which has the least Hamming weight (no. of set bits) in better than $O(2^n)$...
2
votes
0answers
145 views

Counter tree Fenwick for multiplication

I need to compute prefix product of an array. For this reason I want to use counter tree fenwick . Hehe is what I have for the usual Fenwick tree: An array $T$ indexded from $0$ to $n$. $T[i]$ ...
2
votes
1answer
222 views

Minimum depth of addition and multiplication circuit using XOR and AND gates

What are the minimum depth circuits possible for addition and multiplication of two n-bit numbers using just AND and XOR gates? I read somewhere that we can achieve constant depth for addition if we ...
0
votes
1answer
255 views

ignoring overflow in two's complement addition of numbers with different signs[specific case]

I understand the rule says that overflow cannot happen for two's complement addition of numbers with different signs, but do not understand why this specific case does not cause overflow: ...
1
vote
0answers
56 views

Implementing cordic in integer arithmetic

Referring to this reference... I'm trying to work out the details of an integer arithmetic implementation of the CORDIC iteration. The CORDIC pseudo-rotations can be summarized as $$ \left( \begin{...