Stack Exchange Network

Stack Exchange network consists of 174 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

The tag has no usage guidance.

0
votes
1answer
32 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
43 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
28 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
51 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
39 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
30 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
29 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
31 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
98 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
47 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
96 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
35 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
258 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
371 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
449 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
64 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
58 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
305 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
80 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 comp for represented in 8-bits. I had a discussion with a friend who explained that for ...
8
votes
4answers
4k 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
99 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
137 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
73 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
64 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
54 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
25 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
33 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
148 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 ...
61
votes
9answers
14k 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
290 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
106 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
183 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
184 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
49 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{...
10
votes
3answers
5k views

How does 0 have two values in one's complement?

It is said that in 2's complement 0 has only one value, while in 1's complement both +0 and -0 have separate values. What are they?
2
votes
2answers
74 views

Why does the app I downloaded say that 1 in binary is 00110001?

I've just started learning binary so mind me if I'm bad at this. I think that the binary for 1 ought to be just "1" but, when I key it in to an app I downloaded, the answer has extra 0s and 11s in it. ...
2
votes
1answer
1k views

Converting Polynomials into Binary form

How can a polynomial such as $x^3 + 1$ be converted to its binary form of $1001$. Likewise, $10100001 = x^7 + x^5 + 1.$
2
votes
3answers
314 views

Can CPU's 'shortcut' adding 0, multiplying by 1, and multiplying by 0?

I am currently writing a program where a lot of adding 0 to numbers and multiplying by 1 and 0 occurs and it got me to wondering if the CPU 'shortcuts' (drops), these operations. I'm a CS student and ...
0
votes
1answer
53 views

How to determine the carry vector of an integer addition

An integer addition can be represented as following: $A + B = A \oplus B \oplus carry_{vector}$ My question is how to determine the carry vector from $A$ and $B$ (not from the result)?
2
votes
1answer
91 views

Infix vs postfix vs prefix - which has the smallest processing time

Infix, prefix (polish notation) and postfix (reverse polish notation) are all forms of arithmetic operations. As I understand it, infix is what we use in maths where the rules of BODMAS (Bracket, ...
0
votes
0answers
53 views

Discarding Carry Bit

Suppose I have a 2-bit int register (i.e. with possible value 0-3). I have a signed integer in the range -2 to +2. I want to offset the signed integer by 2 to fit it into the 2-bit register. ...
0
votes
0answers
58 views

Data structures used for variable length integers

I've just had a thought about multiple precision number (i.e. variable length integers). The naive way to represent numbers is to use an array sized in such a way that the number of required bits can ...
3
votes
0answers
156 views

Why mantissa and exponent are stored differently in a float?

As we know, in IEEE 754 standard, float number's exponent and mantissa are stored differently. While the exponent is stored as an unsigned number, taking advantage of the bias, the mantissa is in sign-...
2
votes
0answers
189 views

Analysis of the long division algorithm in the Knuth book (Seminumerical algorithms) 1

I've been reading through the long division algorithm exposed in the Knuth book for a week and I still miss some details. There's an implementation of such algorithm in "Hacker's Delight" by Warren, ...