Questions tagged [computer-arithmetic]

For questions concerning finite precision arithmetic in computers and other related concepts.

Filter by
Sorted by
Tagged with
0
votes
1answer
27 views

Fast computation of the direction of a vector

I need to compute the direction of 2D vectors that are provided as a pair of 16 bit signed integers, and return an integer in range $[0,256)$. This can be achieved by the expression $$\frac{128}\pi\...
3
votes
3answers
17k views

Differences between signed and unsigned decimal values

What are examples of signed and unsigned decimal values? What are the differences between them?
2
votes
1answer
73 views

Are companion matrices useful for binary division?

The new find-first-set bit "ffs" CPU instruction found in the multi media extensions (MMX) 4 apparently made possible to start doing Newton-Raphson division (according to Wikipedia). Does someone ...
0
votes
0answers
62 views

How to Prove height of DFS Tree $\geq$ BFS tree for any undirected connected graph G. [closed]

I can prove this by giving some examples, but I'd like to prove this either by assuming towards contradiction, induction or proof by cases.
0
votes
0answers
5 views

How to generate Maximum Min-SW gray code?

I'm trying to generate Maximum min-SW gray code for structured light described in this paper. Can someone help to understand how to generate this 10 bit gray code?
0
votes
0answers
19 views

Identify all the RAW data dependencies in the following code.

Identify all the RAW data dependencies in the following code. Which dependencies are data hazards that will be resolved by forwarding? Which dependencies are data hazards that will cause a stall? ...
3
votes
1answer
24 views

How to represent subset using 5-bit binary code?

For the set $V=\{a, e, i, o, u\}$, give the $5$-bit binary string that codes each of the following subsets: $\{a, i,o\}; \{e\}; V; \emptyset$; Which subset is represented by the $5$-bit string $...
-1
votes
1answer
17 views

Asking about a union of languages and how they interact

if we take a language, $L= \{b^{2n}a^n \mid n \gt 0\} \cup \{b^{3n}a^n \mid n \gt 0\}$ would this be the same as $L=\{b^{2n}a^n b^{3n} a^n \mid n \gt 0\}$ ?
0
votes
0answers
21 views

ASCII code. Binary representation

A character representing the digit n is stored as an 8 bit ASCII code. Convert to an 8 bit sign magnitude for the negative numerical value,-n. What is the algorithm for doing this?
0
votes
0answers
16 views

IEEE 754 Exponent range

It is about the normalized floating-point representation of real numbers (IEEE standard 754). Why does the data type double (64 bits) with mantissa length with 53 bits for the exponent range [-1022, ...
1
vote
0answers
20 views

Resultant of multivariate polynomials

I know little about resultant. As for as I know, if two univariate polynomials $f,g$ have a common zero iff $Res(f,g)=0$, is it right? Now I see an example using resultant of two multivariate ...
3
votes
2answers
120 views

Can my Home PC Handle the Lucas-Lehmer Test by Itself? (or Do I Need GIMPS)

Last year, the largest Mersenne prime $2^{82,589,933}$ that we now know of was discovered. It contains almost $25,000,000$ digits if expanded out. I do not understand much how GIMPS operates, other ...
0
votes
0answers
55 views

Required Precision in Calculating Reciprocals of $n$ and $\frac{1}{n}$ to Recover the Integer

Suppose I am given a large integer $n$ and a small positive value $\epsilon$ such that I am to compute $\frac{1}{n}$, and then compute the reciprocal of that, in order to recover $n$ to within an ...
3
votes
1answer
62 views

PARI/GP for High Pecision Arithmetic Calculation

I recently became aware that PARI/GP may be useful for high-precision calculations. Has anyone had experience with this software; if so, I would be grateful if you might provide me a couple of simple ...
0
votes
3answers
62 views

Possible combinations of binary digits

Why do we say 2 raised to a "n" ,where n is the number of digits = the possible combinations for that binary number For example: (00000000)2 Has 2 raised to 8 = 256 Why?
1
vote
1answer
39 views

Counting the amount of iterations to reach specific answer

I have the following function $f(x) = (x + y) \cdot z$ where $y$ is any positive number and $z \in (0,1) $. The way this works is that the output feeds the input such that $x_{n+1} = (x_n + y) \cdot z$...
0
votes
1answer
49 views

Single-precision floating-point format $2^{-23}$

In some lecture note I saw the following : "The distance between two consecutive mantissas is $2^{-23}$" What can it possible mean?
0
votes
1answer
17 views

Relative roundoff error in the simple precision.

I am struggling with a simple problem from the computer arithmetics. The goal is to find $|(fl(0.1)-0.1)/0.1|$. I have computed the binary representation of $0.1$, which is $(1.1001)_{2}\times2^{-4}$, ...
0
votes
2answers
52 views

Can someone help me simplify this boolean algebra [closed]

ABCD + AB(CD)' + (AB)'CD when i used basic rule it becomes weird but boolean calculator shows something else The Question is to simplify the expression using the boolean algebra so My solution was ...
3
votes
0answers
143 views

Error bound for floating-point interval dot product

In Handbook of Floating-Point Arithmetic (Birkhäuser, 2010, Chapter 6) Muller et al. presented the following absolute forward error bound for the floating-point recursive dot product: $$ \left|...
1
vote
0answers
77 views

Proof that the Booth encoding and the modified booth encoding are correct

In this book, sections 9.4 and 10.2 explains how to implement the booth encoding to speed up operations in hardware. I've being searching for some reference for a formal proof of why this encoding is ...
1
vote
1answer
56 views

Building a sequence that approximates given sequences

Suppose that we are given three sequences $a1,a2$ and $a3$ each describing a total ordering on $N$ 'entities'. For example, $$\langle a1\rangle=1<9<8<2<3<\cdots<N $$ means that ...
1
vote
0answers
36 views

Multiplication of medium sized integers

Implementations of integer multiplication often choose different algorithms for different input sizes: for smallest numbers the school book method is preferred, for largest sizes the method based on ...
1
vote
1answer
64 views

Rearranging a given sequence to satisfy order constraints on certain members

Suppose that we are given a sequences of $2N$ 'entities' (not numbers) with some total ordering defined among these entities. An example could be $$\langle a\rangle=1<4<8<2<3<\cdots<...
2
votes
1answer
53 views

Will the length of a minimum average slice of a numeric array ever be greater than 3? [closed]

Within a sequence of random numbers, is it theoretically possible for a slice of 4 adjacent numbers to be smaller than the average of any slice of 2 or 3 adjacent numbers? This question is based on a ...
2
votes
1answer
49 views

Prove that $x \& (x - 1)$ turns off the rightmost bit in a word.

Prove that for a n-bit word $x$ the operation $$x \& (x - 1)$$ with $\&$ being the bitwise AND-operator, turns off (inverts) the rightmost bit of $x$ (e.g. 0101100 -> 01010000). The example ...
1
vote
1answer
142 views

How to Efficiently Compute a Sum of Exponentials?

In embedded code I want to efficiently compute: $\sum_{k=1}^{N}y_k \cdot e^{a\cdot k}$, $\sum_{k=1}^{N}y_k\cdot k \cdot e^{a\cdot k}$ and $\sum_{k=1}^{N}y_k\cdot k^2 \cdot e^{a\cdot k}$. Here $...
1
vote
3answers
144 views

Floating point approximation to logarithms by powers and bit counting?

Earlier I both asked questions and found some interesting sources on the internet of how to do approximate division by combining and counting number of 0s following most significant bit in denominator....
1
vote
2answers
83 views

Relativistiv kinetic energy and floating point

My function is $E(v)=mc^2(\frac{1}{\sqrt{1-v^2/c^2}} - 1)$, (c=3e8, m=1) and I have to calculate it for values of v between 1e-6 and 2.99e8. The point of this problem is floating point precision. For ...
2
votes
0answers
30 views

Is there any way to predict the amount of “carries” one could get by doing a sum?

https://en.m.wikipedia.org/wiki/Carry_(arithmetic) Definition of carry in Wikipedia I'm guessing the answer is no but just to be sure I wanted to know of there is a way to predict the amount of ...
1
vote
1answer
56 views

Division-free Krylov methods?

I have been using various Krylov subspace methods for a long time, especially conjugate gradient. I'm wondering if there is some way to modify the algorithms to postpone / avoid the divisions that ...
2
votes
2answers
54 views

What is the symbol for a a result that overflows?

Suppose we have an unsigned $8$ bit number (min=$0$, max=$255$). the result of "$200 + 200$" overflows to $144$ the result of "$100 - 200$" (under?)overflows to $156$ Is there are mathematical ...
2
votes
0answers
83 views

SICP: Why does this recursion-based sine approximation work?

Here is the question and solution to Structure and Interpretation of Computer Programs' exercise 1.15 (see here). My problem is, I don't know how the combination of these formulae actually work: $$...
1
vote
1answer
94 views

Conjectures that are false for very large numbers [duplicate]

Hi I would like to teach my students about false conjectures and computer approaches to them. I need references and/or direct examples of statements of the form $(\forall n \geq n_0)P (n)$ where $P$ ...
3
votes
2answers
132 views

Converting $\frac{2}{7}$ to a binary number in a $32$ bit computer

I want to convert $\frac{2}{7}$ to a binary number in a $32$ bit computer. That is, $1$ bit is assigned to the sign of the number, $8$ bits are assigned to the exponent, and $23$ bits are assigned to ...
1
vote
1answer
39 views

Computing $x_+ - x$ where $x_+$ is the rounded binary number of $x$

This question stems directly from Converting $\frac{2}{7}$ to a binary number in a $32$ bit computer I want to check if $x_+$ (increase the value of the last bit by one unit and discard all the bits ...
11
votes
3answers
270 views

Why do so many computer programming language implementations have trouble with the remainders of negative integers?

As most of us know, or should know, $-7 \equiv 1 \pmod 4$. But if you use Java's modulus operator %, you get -3 for the answer, ...
4
votes
1answer
108 views

Mathematics of two's complement

I am trying to understand the underlying mathematics of two's complement. Googling the topic gives me a lot of articles on how to invert the digits and add one, and why computers use this system ...
0
votes
3answers
20k views

Arithmetic Overflow and Underflowing

I am a bit unclear about underflowing in terms of binary representation. Let's say that an unsigned 8-bit variable gets overflown from the addition of $150+150$. A signed 8-bit variable gets ...
1
vote
0answers
268 views

Solving BCD using 10s complement

25-7 is the question. (0010 0101 - 0111). Change 0111 to 0011 (using 10s complement) and add it, isn't it? I've been trying to solve using 10s complement but couldn't. Please help me solve the ...
1
vote
0answers
34 views

Error analysis of a non restoring division algorithm. Studying the iteration.

I'm not sure my derivation is correct, and I also need to find out the error of the iteration/sequence I'm about to derive, but I can't figure out the error once the iteration is finished. Let $x,y,q,...
1
vote
0answers
68 views

Coding for Mathematics

I don't think this is the appropriate group to ask but since most of the people dealing with mathematics are involved, I prefer to ask here instead of the Stack Overflow site. For my math works, it ...
0
votes
0answers
61 views

Tens Compliment Arithmetic.

For the following pairs of 4 digit decimal numbers, A and B, show the ten's complement of each, compute A + B and A – B using ten's complement arithmetic, indicate which of the 4 numbers (A, B, A + B, ...
0
votes
0answers
85 views

What is the maximum number of significant bits lost when the computer evaluates x − y using IEEE 64 bits?

Consider two positive numbers $x = p2^m$ and $y = q2^n$ such that $m > n$, $1 < p < 2$, and $1 < q < 2$. Both of these numbers can be stored using the IEEE 64 bit standard. What is ...
2
votes
1answer
59 views

On how accurate computations are performed

Following my answer to this question I wondered how WolframAlpha would tell me, so promptly and with so many decimal places, the result of $$\left(\frac{2^{64}-1}{2^{64}}\right)^{2^{56}}$$ I ...
0
votes
2answers
251 views

How to represent the decimal value $- 7.5$ as a floating point number?

Consider the following $32$-bit floating-point representation scheme as shown in the format below : A $1$ bit sign field A $24$ bit fraction field and a $7$ bit exponent field (in excess-$64$ ...
0
votes
1answer
588 views

Modulus of a big number by a big number. [closed]

I'm trying to perform the following calculation: $$ a\pmod m $$ where both $a$ and $m$ are numbers larger than $32$ bits. However, I'm only able to perform calculations on $32$ bit numbers. So I ...
1
vote
0answers
621 views

Hanek payne trigonometric range reduction detailed analysis of loss of significance.

I'm struggling to understand what is the actual problem described as "loss of significance" when a trigonometric range reduction argument is performed. I was trying to perform the analysis by myself ...
1
vote
1answer
2k views

Concatenation of languages and multiplying strings

I'm having a hard time understanding concatenation of languages. I'm trying to understand how the following can be possible: |L1L2| $\neq$ |L1| * |L2| That is, the number of strings in the language ...
2
votes
1answer
3k views

Machine numbers in a 32-bits (binary digits) computer?

I'm currently studying Numerical Analysis with the book "Numerical Analysis: Mathematics of Scientific Computing" by Kincaid. In this book, the authors have introduced a computer called "Marc-32" ...