Questions tagged [arithmetic]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
26 views

Who invented the adder, full-adder, half-adder?

I didn't find, in the digital design books, who invented the adders. The same person invented the half-adder and the full-adder? What's the oldest publication on digital arithmetic design?
1
vote
1answer
54 views

How can I calculate the maximum sum/product of sequence?

I am looking for an algorithm in $O(N^2)$ that finds the maximum value that be obtained from a sequence of real numbers greater than 0 (e.g. $\{ 1, 2, 3 , 4\}$) by inserting a plus ($+$) or ...
0
votes
0answers
9 views

Is Decimal (correctly-rounded arbitrary precision decimal floating point arithmetic) fixed-point, floating-point or something else?

The Decimal data type I am referring to is GNU MPFR(https://en.wikipedia.org/wiki/GNU_MPFR), or libmpdec (http://www.bytereef.org/mpdecimal/doc/libmpdec/index.html). I have been searching for ...
1
vote
4answers
66 views

How does a computer compute negative(-) and positive(+) Infinity?

If we divide (1.0/0.0) we will get +Infinity and if we divide (-1.0/0.0) we will get -Infinity. How does a computer calculate this value internally?
1
vote
0answers
30 views

Least computationally expensive bitwise addition

I am familiar with the oft-cited method of bitwise addition using XOR and left shift for the carry, applied recursively. I was wondering if this is the least computationally expensive way to achieve ...
0
votes
0answers
9 views

Number of bits for scalar product signal

let's consider two vectors $v_1[i]$, $v_2[i]$, for $i = 0, 1, ... , N$. Suppose you want to calculate the scalar product between them: it is simply the sum of all $v_1[i] * v_2[i]$ terms $(i=0,...,N)$...
1
vote
0answers
44 views

Can we represent $\sqrt{2}$ exactly even with infinite bits in mantissa [closed]

Can we represent $\sqrt{2}$ exactly even with infinite bits in mantissa in floating point notation or otherwise. We actually have to prove this is not possible. But why can't we if we have infinite ...
0
votes
1answer
32 views

Why does arithmetic left shift of negative number leads to positive number?

According to this Wikipedia article, when arithmetic left shift operation is applied to a signed number, the number is multiplied by 2. But there are certain situations where a negative number becomes ...
1
vote
1answer
29 views

What is the time complexity of a binary multiplication using Karatsuba Algorithm?

My apologies if the question sounds naive, but I'm trying wrap my head around the idea of time complexity. In general, the Karatsuba Multiplication is said to have a time complexity of ...
2
votes
1answer
51 views

Binary representation of 129 when using 8bits for two's complement?

I have this confusion regarding binary representation of decimal value 129 (or even 128). If 8 bits are used to represent numbers when doing the two's complement, then we know that '00000000' to '...
0
votes
0answers
24 views

Floating point substraction

if $x=1.0e38=1.0 * 10^{38}$ and $y=3.0$ i want to find $ (x-x)+y $ and $(x+y)-x$ i think the value of (x-x)+y will be just substract $x-x=0 + y=3.0 = 3.0$ but how can i perfom addition of different ...
0
votes
0answers
9 views

Why the multiplier and quotients can not store in the ACC?

When I study the Arithmetic Unit, there is the below information: there I have some questions: Why the multiplier must store in the MQ and the product must divide ...
4
votes
1answer
54 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
124 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
62 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
37 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
947 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
31 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
135 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
101 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
41 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
59 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
55 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
615 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
24 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
164 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
88 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
26 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
79 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
50 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
144 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
112 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
521 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
22 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
48 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
31 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
47 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
351 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
65 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
126 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
39 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 ...
3
votes
0answers
37 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
429 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
590 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
489 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
75 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
73 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
683 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 ...