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.

4
votes
1answer
49 views

How to represent calculable real numbers?

Suppose I want to do arithmetic without any loss of precision. Floats and doubles are inappropriate. I want to use dynamic memory allocations to store any real number obtained after a finite amount of ...
3
votes
2answers
114 views

How does the bitlength of the divisor affect the running-time complexity of division algorithms?

Wikipedia lists $O(M(n))$ as the best complexity (out of the algorithms listed) for division on two $n$-digit numbers, where $M(n)$ is the complexity of the multiplication algorithm of choice. This is ...
2
votes
1answer
53 views

Prove that the next multiple of 4 is obtained using the next formula

I was reading an assembly procedure that needed to align addresses on 4 bytes boundary for performance reasons so it has used the next statement that i formulated as a theorem to be proven. Let $s$ ...
1
vote
2answers
28 views

Running time complexity of finding maximal power of divisor that divides natural number

Given $n \in \mathbb{N}$, a divisor $p\vert n$, I would like to efficiently find $e\in\mathbb{N}$ with $p^e \vert n$, and $e$ maximal with this property. I will assume that multiplication/division of ...
16
votes
5answers
3k views

Signed and unsigned numbers

How would the ALU in a microprocessor differentiate between a signed number, -7 that is denoted by 1111 and an unsigned number 15, also denoted by 1111?
7
votes
5answers
526 views

Number of FLOPs (floating point operations) for exponentiation

What is the number of floating point operations needed to perform exponentiation (power of)? Assuming multiplication of two floats use one FLOP, the number of operations for $x^n$ will be $n-1$. ...
0
votes
0answers
19 views

arithmetic coding for generating random number with desired distribution

Hi i want to convert random number with uniform distribution to desired distribution using arithmetic coding. It has been done in the following research paper called arithmetic distribution coding ...
0
votes
1answer
78 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
57 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
45 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
36 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
68 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
19 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
114 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
81 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
65 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
47 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
67 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
65 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
324 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
40 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
229 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
116 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 ...
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
370 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
516 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
476 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
63 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
507 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
161 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) ...
5
votes
1answer
294 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
158 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
77 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
95 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
58 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
29 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
203 views

GCD binary representation time complexity

1. Consider the following algorithm for deciding GCD: “On input : ...
4
votes
1answer
41 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 ...