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
1
vote
1answer
37 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
33 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
53 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
37 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
72 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
17 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
60 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
22 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
19 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
66 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
13 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
0answers
19 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
52 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
41 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
56 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
66 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
69 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
53 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
18 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
27 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
49 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
271 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
55 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
470 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
286 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
24 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
742 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
83 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
25 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
122 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
107 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
74 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
32 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
53 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
322 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
418 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
362 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
28 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
11 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
60 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
159 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
64 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
48 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 ...
17
votes
5answers
4k 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
2k 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$. ...

1
2 3 4 5 6