Questions tagged [computer-arithmetic]
For questions concerning finite precision arithmetic in computers and other related concepts.
113
questions
0
votes
0
answers
11
views
Question on maths behind Floyd Cycle Finding Algorithm [duplicate]
So in our class our professor asked us a quesiton on the logic behind Floyd's Cycle Algorithm. FCA is based upon two pointers, one slow and one fast pointer, both of these pointers traverse the linked ...
3
votes
1
answer
231
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}: (\...
2
votes
2
answers
103
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....
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 ...
0
votes
1
answer
75
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 ...
0
votes
0
answers
35
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 ...
1
vote
0
answers
49
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} \...
4
votes
1
answer
151
views
0
votes
1
answer
90
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 ...
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 ...
1
vote
1
answer
168
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) ...
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 (...
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 ...
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 ...
0
votes
0
answers
446
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 ...