Skip to main content

Questions tagged [computer-arithmetic]

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

Filter by
Sorted by
Tagged with
3 votes
1 answer
181 views

UPD: Structure of subgroups of $S_{2^n}$ generated by $\langle x \mapsto ax \mod 2^n \rangle$ and linear groups

It's a very well known result by Gauss that $(\mathbb{Z}/2^n \mathbb{Z})^\times = \langle -1 \rangle \times \langle 3 \rangle \cong C_2 \times C_{2^{n-2}}$. Consider a faithful action $\mathrm{mul}: (\...
Aleksei Averchenko's user avatar
2 votes
2 answers
99 views

Looking for an efficient (computerized) way to convert large ternary sequences into their decimal equivalents.

I am doing a project on Cantor Sets for my undergraduate and I need an efficient (computerized) way to convert large ternary expansions such as the following to their decimal equivalent. $$0....
Sidekiq's user avatar
  • 23
2 votes
1 answer
61 views

Find minimum sum of distance to all points in a vector, using an accumulator?

This is question will be about the theorem behind an efficient algorithm, which has been used in LeetCode problem 3086. Let me start by exposing the problem in a friendly way: You are a bus driver who ...
Murilo Perrone's user avatar
0 votes
1 answer
62 views

Algorithms on converting hex to IEEE-754 single-precision floating point number [closed]

I need help with finding algorithm converting hex to IEEE-754 single-precision floating point number (without coding). I couldn't find any on the internet :( For example, given input string ...
regina's user avatar
  • 27
0 votes
0 answers
30 views

What is the name of the quantization method where you truncate before adding a half?

Many years ago, when designing a fixed-point CORDIC algorithm in hardware, I stumbled across a method of quantization by which you could "round" by truncating to the desired precision before ...
mattgately's user avatar
1 vote
0 answers
47 views

Proof that $\epsilon_{mach} \leq \frac{1}{2} b^{1-n}$

I have a question about the proof of the following statement: For each set of machine numbers $F(b, n, E_{min}, E_{max})$ with $E_{min} < E_{max}$ the following inequality holds: $\epsilon_{mach} \...
Felix Gervasi's user avatar
4 votes
1 answer
141 views

Is there still a fast invsqrt magic number for float128?

...
steve02081504's user avatar
0 votes
1 answer
83 views

Why does adding 1 when converting to and from Two's Complement work?

I understand the steps for converting to and from two's complement. Represent the number as a positive base binary value, flip the bits, add 1. I don't understand why adding the 1 actually works ...
JoffLobster's user avatar
0 votes
0 answers
24 views

Similar colors to input color in hexadecimal format belongs to a set of $\bmod{17}$ remainders

Given an input color string in the format "#ABCDEF", representing a red-green-blue color, find the shorthand representation of that color that is most similar to the given color. Shorthand ...
Avv's user avatar
  • 1,189
1 vote
1 answer
160 views

On the axioms of floating-point arithmetic

As I understand there are two "axioms" that should be satisfied in floating-point arithmetic: $$\forall x\in \mathbb R,\ \exists |\varepsilon|\leq\varepsilon_{\text{machine}},\ \mbox{fl} (x) ...
Julián's user avatar
  • 1,335
0 votes
2 answers
164 views

Evaluating $a(b + c)$ more accurately with FMA

I'm using machine-precision floating-point arithmetic, and every so often it happens that I need to evaluate an expression of the form $a(b + c)$. I found that the accuracy can be improved using FMA (...
user2373145's user avatar
2 votes
0 answers
82 views

Numerically stable evaluation of factored univariate real polynomial

Suppose we have a real univariate factored polynomial, meaning we have its factors: an arbitrary number of polynomials of degree less than or equal to two. To simplify things, if necessary, let's ...
user2373145's user avatar
0 votes
0 answers
57 views

How can I deal with big numbers with big magnitude?

I'm trying to solve optimization problem with very big numbers with large magnitude: from $10^3$ up to $10^9$. I'm using LBFGS-b fortran solver, but almost always I get ...
Gleb  Vishnevsky's user avatar
0 votes
0 answers
404 views

How to calculate the difference between two numbers in a sequence that wraps around?

I am dealing with a problem that has a solution in this simplified problem's solution. Assume there is a sequence of numbers 0-99. There is a wrap-around such 99+1 = 0 and 0-1=99. The position 100 and ...
gyuunyuu's user avatar
  • 131
-1 votes
1 answer
39 views

Let $A(n)$ be the maximum number of intersections of $n$ lines. Show through induction that the following holds: [closed]

The following holds: $$A(n)=\sum_{k=0}^{n-1}k$$ How to do the induction?
Zelda Watcher's user avatar
1 vote
1 answer
241 views

Avoiding Loss of Significance Due to Subtractive Cancellation

I am having trouble figuring out how to avoid subtractive cancellation without using Taylor series expansion for this problem: $x − \sin x$ My initial thought is to use trig identities but I cannot ...
Devin G Arrants's user avatar
1 vote
0 answers
121 views

The gap size of floating point

In Trefethen Bau Numerical Algebra, floating point set F is defined by $\textbf{F} = \left\{\pm(m/\beta^{t})\beta ^{e}| 1 \leq m \leq \beta^{t}, e \in \mathbb{Z} \right\}$ Equivalently, by making $m$ ...
Chris's user avatar
  • 23
0 votes
1 answer
41 views

In ZFS RAID 6 implementation, why certain shifts are ⊕, but not the others?

ZFS is a computer filesystem, which has an implementation of the RAID 6. I understand the simplified example of the RAID 6 implementation in Wikipedia, which each data chunk D is bit-shifted by a ...
midnite's user avatar
  • 131
0 votes
0 answers
26 views

summation result

...
Dunder Mifflin's user avatar
2 votes
3 answers
356 views

Mapping logarithmic ranges to linear

I'm trying to map the table 3.2.5 from RFC1951 from its distance values to code values. The table as follows (ignore the bits column, ranges are inclusive): ...
jogerj's user avatar
  • 31
1 vote
1 answer
174 views

Why do some results for two's complement subtraction requires another conversion of two's complement again while some don't?

Currently a student studying computer arithmetic, came across two's complement subtraction and some of the questions that I did, their answers does not another conversion of two's complement again ...
Han's user avatar
  • 23
0 votes
1 answer
33 views

Why is $(1.01011100 ∗ ∗)_2 \times 2^{E} - (1.01011000 ∗ ∗)_2 \times 2^{E} = (1.00 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗)_2 \times 2^{E-6}$

I'm taking a numerical analysis course. This is one of the examples in my professor's notes: "Suppose we have 10 bits of precision and \begin{gather} x = (1.01011100 ∗ ∗)_2 × 2^{E}, \end{gather} ...
user avatar
1 vote
1 answer
134 views

Arithmetic in Lambert-W number system

$\DeclareMathOperator{\sign}{sign}$ The principal branch of Lambert-W function is defined like so: $$W(x) = f^{-1}(x)\\ \text{where} f(x)=xe^x$$ So $W(e) = 1$, $W(2e^2)$ is 2, $W(3e^3)$ is 3 etc. We ...
Nirvana's user avatar
  • 447
0 votes
0 answers
35 views

Modified ceiling and floor calculations that take into account binary digit sums

If we define $\nu(n)$ as the binary digit sum of the natural number $n$. I want to quickly calculate a strange floor and ceiling of a rational $x$: $\lceil x\rceil_b=\min(\{m\in N|m\ge x,\nu(m)\le b\})...
Neill Clift's user avatar
1 vote
0 answers
57 views

How to avoid overflows and numerical issues when computing derivatives?

I'm trying to compute the derivative of this quantity w.r.t to $\mu$ and $k$: $$ \mathcal{L}(t) = - \eta_n\log\left(1-P(t)\right) $$ Where $\eta_n$ is just a weighting factor and P(t) is the cdf of ...
ИванКарамазов's user avatar
1 vote
0 answers
83 views

Which of the two algorithms:fl(a+b+c+d) or fl(d+c+b+a), computes more accurate result(with smaller absolute error)?

It is known that if a and b have an exact representation in given t-bit arithmetic, then fl(a+b) = (a+b)(1 +$\delta$), where fl() denotes the result of an operation performed by a computer, and |$\...
userover8k's user avatar
0 votes
0 answers
238 views

Number of Flops in Pseudocode

I have the following pseudocode: And I want to find the number of flops (floating point operations) in the code. I need to write my final answer in terms of only $n$. Since every variable in each ...
sktsasus's user avatar
  • 2,042
1 vote
2 answers
119 views

Can a classical computer count beyond a finite number?

It seems since a classical computer has a finite number of transistors, it can only represent numbers up to a finite value. So a classical computer couldn't start at 1 and then count up to an ...
paleo's user avatar
  • 31
0 votes
0 answers
81 views

Accuracy in rounding

I want to see if the following two rounding statements are true or false. If it is true, I want to prove it, and if it is false, I want to give a counterexample. I assume no overflow occurs in the ...
fvvadda's user avatar
  • 11
1 vote
0 answers
40 views

A different type of IEEE single format

To practice with different kinds of IEEE single format types, I am trying a format where the width of the exponent field is $4$ instead of $8$ and the width of the fraction field is $4$ instead of $23$...
fvvadda's user avatar
  • 11
0 votes
2 answers
696 views

Converting $32$-bit $2$'s complement to decimal

What is the general procedure to convert a $32$-bit $2$'s complement number to decimal? For instance, if I was given the $2$'s complement representation: $11111111111111111111111111101011$ how would I ...
sktsasus's user avatar
  • 2,042
0 votes
3 answers
424 views

Cancellation in Numerical Analysis

How do you find the values of $x$ for which for example, $f(x) = 1-\cos(x)$ cannot be computed accurately? From different websites I see that this happens for large $x$-values, but I am not sure how ...
EM823823's user avatar
  • 463
1 vote
0 answers
33 views

What is the notation $F(a, b; -c, d)$ for computer numbers?

I've encountered the following question: Question: Find the number of elements in the set of computer numbers $F(6, 7; -6, 7)$. I haven't seen the notation $F(a, b; -c, d)$ and hence, can't solve the ...
Mohammad Ali Nematollahi's user avatar
1 vote
0 answers
96 views

Floating Point Rounding of 2 multiplied single precision numbers

I have built a floating point multiplier in Logisim (digital design tool) for only single precision normal inputs. I have realised 2 different round to even rounding algorithms and I am not sure which ...
R Mcgowan's user avatar
0 votes
0 answers
48 views

Which calculation is easier for a computer?

I have two problems and I want to know which one is easier to handle for a computer (running time, number of needed operations....): Given matrix $A \in \mathbb{Z}^{m \times n}$ and vector $d \in \...
samabu's user avatar
  • 723
1 vote
0 answers
40 views

Is there a way to quantify how well I solved a matrix? (Gauss-Jordan elimination efficiency)

I'm just starting to learn linear algebra and I'm finishing up the section of Gauss-Jordan elimination. Something that piqued my interest was the variety of different ways I could go about solving ...
sqrtpapi2001's user avatar
0 votes
2 answers
210 views

Proof of a different (Russian peasant) method of multiplication [duplicate]

I got this problem in the book Topics in the Theory of Numbers by Paul Erdos and Janos Suranyi and I found it very interesting. I have no idea how to prove this. (Although I believe it can be proved ...
SARTHAK GUPTA's user avatar
0 votes
0 answers
105 views

Can one do Conjugate Gradient for non-floating point arithmetics?

So the last few years I have used Krylov subspace methods (mostly Conjugate Gradient) for solving various kinds of problems in science and engineering, but in all of these applications I have only ...
mathreadler's user avatar
0 votes
1 answer
106 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\...
user avatar
3 votes
1 answer
253 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 $...
J_fruitty's user avatar
-1 votes
1 answer
20 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\}$ ?
Imd15's user avatar
  • 11
1 vote
0 answers
343 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 ...
Xiaosong Peng's user avatar
1 vote
2 answers
446 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 ...
DDS's user avatar
  • 3,209
0 votes
0 answers
98 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 ...
DDS's user avatar
  • 3,209
1 vote
1 answer
104 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 ...
DDS's user avatar
  • 3,209
1 vote
3 answers
2k 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?
user_'s user avatar
  • 253
1 vote
1 answer
108 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$...
rr1303's user avatar
  • 193
0 votes
1 answer
111 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?
gbox's user avatar
  • 12.9k
0 votes
1 answer
346 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}$, ...
user581250's user avatar
0 votes
2 answers
84 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 ...
Hydra Vizion's user avatar