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
1 answer
48 views

Boolean Logic for Floats

I would like to know whether a theory exists which generalizes boolean logic to floats. Specifically, assume that instead of booleans 1 and 0, I have True/False tendencies, such as 0.9, where 0.1. ...
user avatar
-2 votes
2 answers
59 views

Java | If a=250, b=3, c=(a + b/2)/b * b, Why doesn't c equal 251 but rather 249?

If int a = 250; int b = 3; int c = (a + b/2)/b * b; Why doesn't c equal 251, but rather 249? How is it that ...
user avatar
  • 109
-2 votes
1 answer
48 views

Approximate x*(a/b)^(c/d) using integer arithmetic only (assembler)

0 < x,a,b,c,d < M are all positive integers (uint64). also, a<b if that helps. we have assembler (integer only) operations available (e.g. division only yields integers). we want to ...
user avatar
1 vote
1 answer
126 views

How would I show function $f(x)=4x$ is Turing computable?

How to show $f: \mathbb{N} \to\mathbb{N}$ with $f(x)=4x$ where $x$ is in the set of natural numbers $x\in\mathbb{N}$) is Turing Computable? My guess is obviously there is a finite number of operations ...
user avatar
  • 133
2 votes
1 answer
59 views

Cost of increasing a binary counter with a starting value n times

Consider a k-bit binary counter and suppose that in the beginning the value of the i-th most significant bit is $b_i$ for each $i = 0, . . . , k − 1$. Let $b = b_0 + 2b_1 +· · · + 2^{k−1} b_{k−1}$. ...
user avatar
1 vote
0 answers
19 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, ...
user avatar
2 votes
1 answer
100 views

Addition in Lambda calculus

Found this term for a supposed 'adder' in lambda calculus. λabcd.ac(bcd) Although I know about alpha-conversion and beta-reduction and all that stuff, I don't know ...
user avatar
  • 21
1 vote
0 answers
37 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 ...
user avatar
1 vote
3 answers
70 views

when is 2's complement used, or called into use in hardware

so when doing digital design, lets say building a calculator we only take the 2s complement of a negative number. 13+(-12)=1 001101 + 110100 = (1)000001 the 1 in parenthesis is overflow that "...
user avatar
  • 11
1 vote
1 answer
24 views

Buchi arithmetic meaning

I am studying this article. But I have trouble with understanding the Buchi arithmetic. It says in section IV: ... Formulas in this fragment generalise classical integer programming and are of the ...
user avatar
0 votes
1 answer
33 views

Compute accuracy of program?

Is there a tool to compute the accuracy of a function in a program? Perhaps a static tool or some debugger-based tool that logs each time an arithmetic operator is applied? So one can avoid quirks in ...
user avatar
  • 109
0 votes
0 answers
13 views

Addition of signed ones' complement numbers

Currently I'm wondering about the behavior of addition of signed ones' complement numbers. After some searching, I got to know that there are three cases: (1) positive number + negative number (...
user avatar
  • 1
1 vote
1 answer
52 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 ...
user avatar
0 votes
1 answer
50 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 ...
user avatar
  • 349
0 votes
1 answer
48 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. ...
user avatar
3 votes
3 answers
153 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 ...
user avatar
  • 81
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
40 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 ...
user avatar
0 votes
0 answers
189 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, ...
user avatar
1 vote
1 answer
30 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: ...
user avatar
  • 459
0 votes
0 answers
21 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
user avatar
0 votes
0 answers
13 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 ...
user avatar
1 vote
0 answers
64 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 ...
user avatar
1 vote
2 answers
61 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 ...
user avatar
  • 125
4 votes
2 answers
126 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 $...
user avatar
2 votes
1 answer
52 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 ...
user avatar
1 vote
1 answer
625 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 ...
user avatar
  • 11
-4 votes
1 answer
430 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 ...
user avatar
  • 111
1 vote
2 answers
90 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?
user avatar
0 votes
0 answers
385 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-...
user avatar
1 vote
1 answer
37 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 ...
user avatar
  • 13
3 votes
1 answer
65 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 ...
user avatar
  • 41
0 votes
3 answers
106 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 ...
user avatar
1 vote
1 answer
1k 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 ...
user avatar
0 votes
1 answer
38 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?
user avatar
  • 1
1 vote
1 answer
337 views

Is arithmetic a context free grammar?

Like including parenthesis (( and )), addition, subtraction, multiplication, and division, and the Order of Operations in mind. ...
user avatar
  • 113
1 vote
2 answers
60 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? ...
user avatar
  • 11
1 vote
2 answers
45 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)}{...
user avatar
1 vote
2 answers
95 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 ...
user avatar
  • 124
1 vote
1 answer
40 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 ...
user avatar
  • 15
0 votes
1 answer
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 ! ...
user avatar
  • 15
0 votes
0 answers
308 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 ...
user avatar
0 votes
0 answers
45 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)\...
user avatar
0 votes
1 answer
202 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 ...
user avatar
0 votes
2 answers
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 ...
user avatar
0 votes
0 answers
34 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 ...
user avatar
1 vote
1 answer
37 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 $...
user avatar
1 vote
1 answer
28 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 ...
user avatar
1 vote
0 answers
58 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 ...
user avatar
  • 11
2 votes
1 answer
47 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, .....
user avatar
  • 344

1
2 3 4 5
7