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
46 views

Efficient comparison, using only sum, product, difference, and conditional jump if zero

I was wondering how small we could make the instruction set of a typical machine that supports a single datatype: arbitrary integers. If you need a heap, you declare an integer variable $h$ where you ...
0
votes
1answer
22 views

Addition in One's Complement

It is my belief that addition in one's complement is done the same way as unsigned addition except that if there is a carry out in the most significant bit then that carry is added to the last ...
0
votes
1answer
30 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. ...
3
votes
3answers
145 views

How many possible arithmetic operations are there between two N-bit numbers?

It's generally considered to be the case that there are sixteen possible logical operations between two N-bit numbers and four possible logical operations on one N-bit number. I'd like to know how ...
0
votes
1answer
23 views

Determine if the following arithmetics are sentences

How would you determine if these arithmetics are sentences or not? -(x + 2) > y i++ == 2 i++ == 2 is this sentence True where i = 1 I understand it as if the ...
0
votes
0answers
33 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 ...
0
votes
0answers
93 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
vote
1answer
25 views

Replacing the moduleo operation with occasional subtraction and one comparison

Suppose we have the following equation: $$k_{i + 1} = (k_i + 2i + 1) \bmod{n}, \quad k_0=k, \quad i\ge 0$$ Show how we can we replace the mod with one comparison and occasional subtraction. Attempt: ...
0
votes
0answers
19 views

hexadecimal addition of two numbers stored in a 16-bit register

"Which is the hexadecimal result of 6 + 7 (both base 10) if stored in a 16-bit register?" Could someone please explain me how to get the result to the question above? Thank you
0
votes
0answers
12 views

How does Sign-and-Magnitude representation allow for easier tracing of memory dumps?

Hey I've read in Wikipedia the following: Refer here link. "Sign & magnitude allowed for easier tracing of memory dumps (a common process in the 1960s) as small numeric values use fewer 1 ...
1
vote
0answers
42 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 ...
1
vote
2answers
53 views

Why is the time complexity of the Bit Manipulation solution to Binary Addition O(M + N)?

I am trying to understand why the time complexity of the Bit Manipulation solution (https://leetcode.com/problems/add-binary/solution/) to the Binary Addition problem is O(M + N), where M and N are ...
4
votes
2answers
121 views

Is there a good algorithm to divide two integers without using division directly?

Problem. Given positive integers $a$ and $b$, obtain $\frac{a}{b}$ without using division ($/$) directly, though addition ($+$), subtraction ($-$), multiplication ($\times$) and bit-shifts ($\gg$ and $...
0
votes
0answers
21 views

Computer arithmetic algorithm: what might I be doing wrong?

So I'm working with the following differences equation: $$y_n=\alpha y_{n-1}+(1-\alpha)x_n$$ I know this works with 16-fixed point arithmetic, and given some samples I'm trying to figure out how the ...
2
votes
1answer
36 views

How can I do a subtraction with a two tape Turing machine

I have already made a Turing machine with just one tape that solves a subtraction between two numbers, but I trying to do the same but with TWO tapes. As an example, how can I solve 4-2? Taking ...
1
vote
1answer
272 views

Represent unsigned 12-bit octal numbers. Results in octal

I have an HW question where I found an answer that matches mine, but their breakdown confuses me. Ques: What is 4365 - 3412 when these values represent unsigned 12-bit octal numbers? The result should ...
-4
votes
1answer
297 views

Is squaring easier than multiplication? [duplicate]

Let $T_1(n)$ be the time complexity of computing the square of an $n$-bit integer, and let $T_2(n)$ be the time complexity of computing the product of two $n$-bit integers. Assuming that addition is ...
1
vote
2answers
47 views

Adding two numbers in base 2(floating point) vs Multiplying two numbers in base 2(floating point)

Is it true that adding two numbers in base 2 is more complex than multiplying them? If so can someone please explain why this is the case?
0
votes
0answers
14 views

Multiplication of two binary numbers in fixed point arithmetic

So I'm performing some operations with fractional numbers in a 16-bit FIXED-POINT processor. I have to multiply the numbers $\ x=-6.35$, represented in $\ Q_{11}$, and $\ y=-0.1$, represented in $\ ...
0
votes
0answers
26 views

Confused about adding numbers in fixed-point

So I'm performing some operations with fractional numbers in a 16-bit FIXED-POINT processor. I have to add the numbers $\ x=-7.1$, represented in $\ Q_{12}$, and $\ y=0.75$, represent in $\ Q_{15}$. ...
0
votes
0answers
16 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
228 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
33 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
42 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^...
3
votes
1answer
63 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
2answers
88 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
657 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
37 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
226 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
47 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
44 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
86 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
21 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
1k 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
113 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
1answer
79 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
1k 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
32 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
32 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
27 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
56 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
44 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
239 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
179 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
175 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
114 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
92 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
31 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....

1
2 3 4 5
7