A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [computer-arithmetic]

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

Filter by
Sorted by
Tagged with
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, ...
6
votes
1answer
1k views

Prerequisite reading for Concrete Mathematics? [closed]

I'm a freshman computer science major who has just started reading Concrete Mathematics, mathematics for computer science. Is there any prerequisite reading or learning I should do before embarking on ...
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 ...
3
votes
2answers
118 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 ...
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?
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 ...
3
votes
1answer
23 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 $...
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|...
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 ...
2
votes
2answers
231 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 = ...
2
votes
1answer
158 views

IEEE754 32-bit single precision format

I have a question like this: Show how the number $-12.75$D is stored in the computer's storage using IEEE754 32-bit single precision format. You are required to show your conversion steps clearly. ...
2
votes
1answer
52 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
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
1answer
68 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 ...
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" ...
2
votes
1answer
127 views

Determine sign of sum of square roots

Problem Given positive square-free integers $r_i$ and non-zero integers $a_i$, is there an algorithm for determining the sign of $\sum_{i=1}^n a_i\sqrt{r_i}$ without calculating approximations for ...
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 ...
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 ...
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: $$...
2
votes
2answers
61 views

How do I prove that these are equal using laws of logic?

Prove that $\lnot(p\lor(\lnot p\land q)$ is equivalent to $\lnot p\land\lnot q$ I always end up at $\lnot p$, here's my solution: \begin{equation} \lnot(p\lor(\lnot p\land q))=\lnot p\land\lnot q \...
2
votes
1answer
445 views

How would you reduce roundoff error in “mod” when implementing a periodic function?

I recently wrote How calculators do trigonometry where I wrote a simple program for computing $\sin(x)$. For completeness, I include a slightly modified version of the program here: ...
2
votes
1answer
146 views

Numerical error analysis

I stand before the following task and I do not know how to solve it. The input parameter $$a=10^6, b=10^6 + 10^{-2}$$ will be round internally to $$a^*, b^*$$ with $$a=a^*(1 + \epsilon_1)$$ $$b=b^*(...
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
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 ...
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
109 views

Bitwise ops - The relationship between $a$, $b$, $a \wedge b$, $a \vee b$ and $a \oplus b$

In computer programming, the term bitwise operation is used to denote the use of boolean operators (and $\wedge$, or $\vee$, exclusive or $\oplus$) on corresponding bits of two numbers. Bits, in this ...
1
vote
1answer
448 views

Complexity of computing $N!$

Question: Complexity of computing $N!$, considering that each multiplication cost about $O(\log^2{n})$. Attempt: There's $n-1$ multiplication. Each multiplication leads to a bigger number, thus $n-1$ ...
1
vote
1answer
38 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$...
1
vote
1answer
139 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
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 ...
1
vote
1answer
91 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
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 ...
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 ...
1
vote
1answer
52 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 ...
1
vote
1answer
172 views

How to encode a list of integers, how to find an arithmetical formula for a sequence?

I have the following list of integers : $$t={0, 15, 73, 27, 73, 105, 25, 65, 26, 8, 84, 72, 15, 73, 27, 73, 105, 25, 65}$$ And I want to find a function or (an expression) such that $f(k)$ is always ...
1
vote
1answer
86 views

Determining if the result of adding (subtracting) two binary numbers is correct as NBC and 2's

My task is to convert two numbers to binary, add them and determine if the result is correct as a NBC and 2's. Then I have to subtract B from A by converting by using 2's for calculating -B [that is A+...
1
vote
2answers
561 views

Use Weak Mathematical Induction to show that in a full binary tree the number of leaves is one more than the number of internal nodes

Use Weak Mathematical Induction to show that in a full binary tree the number of leaves is one more than the number of internal nodes (i.e., $L = I + 1$). Induct on the number of leaves. What is the ...
1
vote
1answer
43 views

Mistake in generating random numbers - no irrational ones

Hi I just wondered if the probability densities have to be corrected when using them on a PC since the number representation is not at all continuous. So we cant simulate any irrational numbers and ...
1
vote
2answers
4k views

Most negative number (in octal and hex) of a 16-bit one's complement system?

In a 16-bit one's complement system, how do you represent the most negative number in octal and hex? One's complement: http://en.wikipedia.org/wiki/Ones'_complement The most negative 16-bit number ...
1
vote
1answer
799 views

Logic Circuits And Equations Issue - Multiply Binary Number By 3

I am trying to build a logic circuit that multiplies any 4 digit binary number by 3. I know that if I multiply/divide number by 2 it moves left/right the digits, but what I'm doing with multiply by ...
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 ...
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
63 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<...
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 ...
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
0answers
615 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 ...