Questions tagged [computer-arithmetic]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
1 view

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
16 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
21 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
13 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
17 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
106 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
54 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
60 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
52 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
35 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
48 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
51 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 ...
1
vote
1answer
55 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
35 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
61 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<...
3
votes
0answers
142 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|...
2
votes
1answer
51 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
46 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
136 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
54 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
82 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
90 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$ ...
1
vote
1answer
36 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 ...
3
votes
2answers
131 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 ...
11
votes
3answers
266 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, ...
1
vote
0answers
267 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
33 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
59 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
67 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 ...
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
248 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$ ...
1
vote
0answers
74 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 ...
0
votes
1answer
568 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
603 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" ...
0
votes
1answer
27 views

Adder delay model in a ripple carry adder.

In section 5.3. of the following book an analysis of carry propagation in the ripple carry adder is performed. However the statistical analysis doesn't particularly convince me. Specifically at the ...
1
vote
2answers
2k views

truncation in two's complment

My textbook gives an example of truncating a signed number in two's complement from 4 bits to 3 bits. It truncates -4 to 4. I am little confused by this, because the binary representation of -4 is ...
1
vote
1answer
48 views

Mathematical Properties of Logical Shift

Many programming languages feature a logical shift operator, such as $(x >> n)$, where the bits of $x$ are shifted $n$ steps to the right (or left, $<<$), and the "vacated" bit positions ...
2
votes
2answers
229 views

How can I rearrange this logarithmic formula to be computer friendly?

I've had a look through the logarithmic identities on Wikipedia, but nothing fits the bill. Basically, I have a formula which shows how much more 'risky' one number is compared to another, where 0 = ...
0
votes
1answer
153 views

Implementing a (5,5;4) counter with FA and HA

I am trying to implement a (5,5;4)-counter using only FA's and HA's as building blocks. I tried using both Wallace and Dadda tree structures, but I was never able to end up with a 4-bit number as a ...