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.

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

Correctness of addition in 1's complement number representation

The one's complement representation of integer numbers in computer memory is generally defined as the system prescribes to invert all bits (all but the sign one) of a negative signed number. It didn't ...
0
votes
0answers
13 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-...
1
vote
1answer
13 views

2's complement substraction

I need to perform 2's complement operations on -50 - -48 From a mathematical point of view the following would be true. -50 + 48 = -2 If I would follow the steps I would have: I got to this result by ...
0
votes
0answers
37 views

Logarithm and square root in prime fields

I got an interesting question. Introduction: Let $p$ be a prime number and $a,b\in \mathbb{Z}$ with $\gcd(a,p)=1$ and $\exists r\in \mathbb{Z}:r^2\equiv a\mod p$ as well as $\exists l\in \mathbb{Z}:b^...
0
votes
0answers
30 views

Computer Architecture: How does the parallel prefix adder speed up carry generation?

I am confused by how the parallel prefix adder (the one described in this presentation: https://users.encs.concordia.ca/~asim/COEN_6501/Lecture_Notes/Parallel%20prefix%20adders%20presentation.pdf) ...
3
votes
1answer
55 views

What's the average number of transistor switches needed to do an N-bit x N-bit multiply?

I want to know how switch-efficient a multiplier can be. If I need to do many $N$-bit by $N$-bit multiplies, and each bit is determined by flipping a coin, what's the average number of transistor ...
0
votes
0answers
22 views

State machine to convert from base 2 to base 10?

Is there a state machine which can convert base 2 decimals to base 10 decimals in a streaming fashion? Integers?
0
votes
2answers
63 views

How to determine the set of real numbers corresponding to a given floating point number?

Let's say we consider IEEE 754 double precision floating-point numbers, and we use RNTE - Round To Nearest, Ties to Even - rounding. I know that the RNTE rounding works this way: given two consecutive ...
1
vote
1answer
108 views

Arithmetic on signed 12-bit octal number stored in sign magnitude form

What is 4365 − 3412 when these values represent signed 12-bit octal numbers stored in sign-magnitude format? The result should be written in octal. Show your work. Octal to binary: 4365: 100 011 110 ...
0
votes
1answer
35 views

Why is the carry of any n base system equal to the radix in arithmetic?

In binary the carry/borrow is 2, in hex the carry is 16. What's the reason for this?
1
vote
1answer
71 views

Is arithmetic a context free grammar?

Like including parenthesis (( and )), addition, subtraction, multiplication, and division, and the Order of Operations in mind. ...
1
vote
2answers
41 views

Simple question about signed integer multiplication

If you have a signed integer int x = any And then state that x < 0 Is the following statement true or false? ...
1
vote
2answers
42 views

Floating-point oblivious way to compute multiset numbers

I have to compute $R = \left(\!\!{n + 1\choose k}\!\!\right)$, which happens to be: $$ R = \left(\!\!{n+1\choose k }\!\!\right) = \binom{n+k}{k} = \frac{(n + k)!}{n!k!} = \frac{(n+1)(n+2)\cdots(n+k)}{...
1
vote
2answers
76 views

How to convert $(0.11001100…)_2$ to a decimal number

I managed to find and understand algorithm for converting any $x \in \Bbb R$ from a decimal number to binary number. But I have a hard time finding an algorithm for converting a binary number with ...
1
vote
1answer
18 views

Conversion of fractional part of a hexadecimal number to binary

The Number is given as : (C012.25)Hexadecimal I have to convert it into octal . So I converted it into Binary First and got the result as : 1100000000010010.01000000 (Since each bit in hexadecimal ...
0
votes
1answer
479 views

Booth's algorithm Question : Binary Number Arithmetic (Multiplication)

It's being said booth's algorithm produces the output exactly as normal binary multiplication while reducing the number of operations performed and can be used for both positive and negative numbers ! ...
0
votes
0answers
44 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 ...
0
votes
0answers
44 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
0answers
23 views

Adder-Subtractor Circuit With Negative Results

So, I understand how binary arithmetic works, and I understand how an adder-subtractor works for signed numbers. There is only one thing I am not sure about: All the cases work ok in the circuit I ...
0
votes
2answers
130 views

Binary subtraction with numbers in 2's complement

How can i perform binary subtraction of two numbers that are already in 2's complement? I have to subtract 01010011 from 10100110,both numbers are in 2's complement. I know that 10100110 is -90,and ...
0
votes
0answers
30 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 ...
1
vote
1answer
16 views

Help comparing relative error for different parenthesizations of addition

I am given two functions: $ fl(fl(x+y)+z) $ and $ fl(x+fl(y+z)) $ and asked to derive their relative error. Then, given a set of conditions: a) $ x < y < x $ b) $ x > 0, y < 0, z > 0 $...
1
vote
1answer
24 views

Many-one reductions between the set of true sentences and a particular arithmetical set

Never used this site before so not sure the best way to get help. However, I've been looking at many-one reductions in relations to sentences in logic. Let TH(N) = {ϕ : ϕ is a first order sentence ...
1
vote
0answers
54 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 ...
2
votes
1answer
43 views

Sums of $2^{-l}$ that add to 1

Consider the following problem: You are given a finite set of numbers $(l_k)_{k\in \{ 1, ..., n \}}$ such that $\sum_{k=1}^n2^{-l_k}<1$. Describe an algorithm to find a set $(l'_k)_{k\in \{ 1, .....
1
vote
1answer
109 views

Calculating direct sum of 2 binary numbers

If we have say,key=‘0110‘ and 𝑚=‘1100‘, how will 𝑚⊕key mod 2 be calculated and what will be the answer equal to?
5
votes
2answers
89 views

Does time or space complexity of arithmetic operations get affected by the number of digits?

Suppose I have two 5-digit numbers (A and B) and two 50-digit numbers(C and D). Do the operations A+B and C+D have equal complexity in terms of time and space? or C+D is more complex due to the size ...
0
votes
0answers
115 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
vote
3answers
111 views

Alternative algorithms for calculating x^2?

I'm emulating 128-bit arithmetic. At the moment I'm calculating $x^2$ by computing $x\cdot x$. What might be some alternative methods that aren't simply dressing up multiplication?
2
votes
1answer
58 views

Multiplication mod 2 without extra registers

For an arbitrary bitstring $(x_1, x_2,\ldots, x_n)$ and an $n\times n$ invertible binary matrix $M$ (fixed ahead of time), I would like to construct a circuit $C$ acting on these $n$ bits whose output ...
1
vote
0answers
19 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 ...
0
votes
1answer
28 views

Embedded arithmetic set expressions

In set builder notation, we can represent the set: $$\{ 2, 7\}$$ as: $$\{ x | x=2 \vee x=7 \}$$. Therefore, the PA arithmetic predicate: $$φ(x) := x=2 \vee x=7$$ is capable of representing this set....
0
votes
0answers
52 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?
4
votes
3answers
410 views

Do we need to check for mantissa overflow in floating point multiplication?

We do check for the mantisas overflow in floating point addition e.g. If we are adding $8.02 \times 10^3 + 9.01 \times 10^3 =17.03 \times 10^3$ i.e we get an overflow, so we shift the number right ...
0
votes
1answer
83 views

Why do we need/use operator precedence for Arithmetic operators?

Why do we use operator precedence rule for Arithmatic operators? Can't we simply just do the operation in a linear manner from left to right or vice-versa and deal with the operator that comes first. ...
3
votes
0answers
704 views

Replacing 0x1021 polynomial with 0x8005 in this CRC-16 code

I have some highly optimized code for a CRC-16 implementation. It focuses on speed rather than flexibility, and as a result, it is hard-coded to model the specific unreflected polynomial ...
1
vote
0answers
383 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 ...
1
vote
0answers
32 views

How do you compute and compare the delays between a (4:2) compressor and (3,2) counter carry save tree?

My question: How is Table 6.8 shown below computed for different operands? For example, for 3 operands how did they compute: Number of levels using (3,2) = 1 Number of levels using (4;2) = 1 ...
3
votes
0answers
48 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 ...
0
votes
2answers
1k views

Minimum number of bits to represent negative number

Minimum number of bits required to represent $(+32)_{base10}$ and $(-32)_{base10}$ in signed two's compliment form? My attempt: 32 = 0100000 ( 1st zero - sign bit as positive) So to represent +32 we ...
0
votes
2answers
126 views

How to convert 010111 to decimal using only odd numbered positions while still applying the correct positional exponent?

I am trying to understand what this question is asking in terms of conversion. I know how to convert binary to decimal and vice versa, but the method you need to use has me confused. I need to ...
1
vote
1answer
30 views

What's the least signifcant bit of a mantissa system?

If Mantissa is a 1-dot-M fixed-point number whose most significant bit is always 1 then, how is the least significant bit calculated? I know the least and most significant bit of the mantissa ...
0
votes
1answer
151 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
164 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 ...
1
vote
4answers
76 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
33 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 ...
1
vote
0answers
54 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
453 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 ...
2
votes
1answer
554 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
520 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 '...

1
2 3 4 5 6