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.
51
questions with no upvoted or accepted answers
8
votes
0
answers
647
views
Chained operations on sequences with two operators
Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation?
Can we learn from matrix chain multiplication? A generalization of matrix chain ...
- 6,191
4
votes
0
answers
149
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 ...
3
votes
0
answers
52
views
Quick calculation for $x^y \bmod 2^d$
I need to calculate $x^y \bmod 2^d$ in $O(d)$ summations/bitwise operations and $1$ multiplication by $y$. $x$ is restricted to be odd, $d\geq 3$.
$a$-bit arithmetic (for any $a$) is allowed, as this ...
- 156
3
votes
0
answers
43
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 ...
- 283
3
votes
0
answers
47
views
Running time for threshold function evaluation?
A threshold function is a function $f: \{0,1\}^n \to \{0,1\}$, defined by $n$ integer-valued weights $w_1, w_2, \ldots, w_n$ and an integer valued threshold value $w_0$. It works as follows:
$$f(x_1, ...
- 31
2
votes
0
answers
97
views
How does the structure of a Luk-Vuillemin multiplier differ from a Wallace or Dadda multiplier?
I've read that Luk-Vuillemin multipliers are similar to Wallace multipliers but partition their inputs in a different way. How exactly does this partitioning work, how does it change the structure of ...
- 73
2
votes
0
answers
334
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 ...
- 121
2
votes
0
answers
110
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 ...
- 493
2
votes
0
answers
40
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 ...
- 713
2
votes
0
answers
375
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]$ ...
- 247
2
votes
0
answers
414
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-...
- 121
2
votes
0
answers
94
views
Dual Signed Kahan Summation
NOTE: This is for a project I'm working on for fun, NOT production code.
So I'm working on a pet project that involves reading data in from a sensor and summing it up. The values are mostly ...
2
votes
0
answers
39
views
How can I determine if an algoritm can be expressed as a boolean circuit?
Suppose I want to express Data Encryption Standard(DES) encryption algorithm as a boolean circuit. How can I determine if what I want is practical, and if it is how can I do it?
- 425
2
votes
0
answers
547
views
Quick method for approximate integer square roots
I'm looking for an algorithm that -- given a positive integer $n$ -- outputs a positive integer $\bar{n}$ with the following two properties:
$(\bar{n}+1)^2>n$;
$(\bar{n}-1)^2<n$;
So we have $\...
- 166
1
vote
1
answer
76
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?
- 183
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, ...
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 ...
- 207
1
vote
0
answers
155
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 ...
- 11
1
vote
0
answers
60
views
Evaluating functions related by Mobius inversion formula
Problem
Consider two functions $f: \mathbb{N} \rightarrow \mathbb{N}$ and $g: \mathbb{N} \rightarrow \mathbb{N}$ such that $f(k) = \sum_{d | k} g(d)$ for all $k \in \mathbb{N}$. So, the questions ...
- 11
1
vote
0
answers
998
views
Advantages/Disadvantages of adaptive contexual arithmetic coding
What are the advantages and drawbacks of considering ever longer block lengths or context lengths, if one was to work with estimated probabilities(measuring on the fly: aka "adaptive") rather than ...
- 11
1
vote
0
answers
59
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 ...
- 121
1
vote
0
answers
38
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 ...
1
vote
0
answers
45
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 ...
- 713
1
vote
0
answers
104
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{...
- 713
1
vote
0
answers
352
views
2's complement division algorithm
I've managed to get a VM code of a function that performs integer division. After some work, I translated it into high-level language. I know the translation I made is correct, since I was able to ...
- 111
1
vote
0
answers
53
views
Understanding exponential computation by digit recurrence
I've met in a book the following algorithm that computes the exponential:
Input: $t, n$ ($n$ is the number of steps)
Output: $E_n$
$\begin{array}{l}
\mbox{define $t_0 = 0$ ; $E_0 = 1$} \\
\mbox{...
- 713
1
vote
0
answers
697
views
Dividing/Multiplying Numbers Stored in two memory locations
I have two numbers x and y.
The upper bits of x are stored at location m, while
the lower bits of x are stored at location n.
The upper bits of y are stored at location i, while
the lower bits of y ...
- 11
1
vote
0
answers
28
views
pragmatic way to compute/ search/ match MSBs operation
consider integers represented as base 2 (strings). define a relation called "n-msb matching" that is true when the 1st n msbs (MSB is "most significant bits") match (of two integers). what is a ...
- 11k
1
vote
0
answers
118
views
Are rational functions with positive integer coefficients honest?
For every rational function $p(x)/q(x)$ where $p$ and $q$ are polynomials with non-negative integer coefficients, does there exist a polynomial function $h$, such that, if you input a reduced fraction ...
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.
...
0
votes
0
answers
23
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 ...
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 ...
0
votes
0
answers
66
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 ...
0
votes
1
answer
185
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.
...
0
votes
0
answers
174
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 ...
- 137
0
votes
0
answers
957
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, ...
- 1
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-...
- 101
0
votes
0
answers
1k
views
Building an ALU on nandgame's website
I'm working on nandgame's website found here. I'm working on the ALU and here is an image of my implementation:
My Implementation:
And I compared it to this website's solution:
Solution
However when ...
- 131
0
votes
0
answers
47
views
Arithmetical representation $F(x,y,z)\Longleftrightarrow (x+z)=y \lor (y+z)=x$
I am kind of confused which function $f:\mathbb{N}^2\longrightarrow\mathbb{N}$
is presented by $F(x,y,z)\Longleftrightarrow (x+z)=y \lor (y+z)=x$
I know that $f(x,y)=y-x$ is represented by $F(x,y,z)\...
0
votes
0
answers
38
views
Same computation order using postfix notation?
I'm trying to understand arithmetic using stacks. Specifically converting infix notation to postfix notation. My question is how you convert an expression like: 1 + (2 + 3) + (4 + 5)
that computes in ...
- 33
0
votes
0
answers
198
views
Calculating the time complexity of an arithmetic progression
Can someone help me calculate the time complexity of the algorithm?
I have an array and I want to check if it's sorted or not I start in the middle of it and I check the numbers first to the right ...
- 1
0
votes
0
answers
106
views
What is the strongest arithmetic theory decidable by a DFA, DPDA or PDA?
It is known that WS1S can be decided by a DFA. Is this the strongest arithmetic theory decidable by a DFA? What happens when the automata class is extended to include DPDAs or PDAs?
- 123
0
votes
0
answers
29
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 ...
- 133
0
votes
0
answers
85
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
0
answers
1k
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 ...
- 219
0
votes
0
answers
83
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 ...
- 713
0
votes
0
answers
172
views
Representation of the number in two's complement
We have that MIMA (Neumann MInimal MAchine) has the following commands:
I want to write a MIMA program that takes the value $2^{23}-24=8.388.584$ to the memory cell $y$.
We have to take ...
- 431
0
votes
0
answers
747
views
Binary Division using logic gates
I am building a 64 bit CPU in Minecraft and I'm stuck on adding division into the ALU. I was told I should ask this here. Does anyone know how to divide in binary using only logic circuits? I can't ...
- 1
0
votes
0
answers
2k
views
Subtraction using 15s complement
I know 15s complement subtraction may not be much taught/popular one, but I just want to give it a try. Just trying to clear my basic digital logic/number systems concepts.
Here is what I am doing:
...
- 1,743
0
votes
0
answers
49
views
Logarithms using digit recurrence, how many bits to store in a LUT?
In a known method for approximating logarithms the following decomposition is adopted (assuming $x \in [1,2)$):
$$
log_2(x) = 1 + \sum_{j=1}^{+\infty} w_i log_2(1+2^{-j})
$$
Where all the ...
- 713