Questions tagged [real-numbers]
The real-numbers tag has no summary.
57 questions
0 votes
0 answers
44 views
A computing machinery using a continuous memory tape
Turing machines are defined over a discrete memory tape. Is it possible to use a continuous memory tape (i.e. symbolically) instead of a discrete one. Will such a machine be more powerful? https://en....
- 11
0 votes
1 answer
99 views
Approximate LCM of reals
Is there an efficient algorithm to find the approximate LCM of a list of reals? More precisely, given an epsilon, find the least L such that it is atmost epsilon away from a multiple of each real in ...
0 votes
0 answers
62 views
SMT solvers for quantified nonlinear real arithmetic?
Currently I am implementing a probabilistic programming language that requires solving a lot of quantified real constraints. Most of these constraints are solvable using Z3, but the ones involving ...
2 votes
2 answers
155 views
Attempt to find a real number whose computation of bits is NP-complete
Recall that every real number $x$ can be expressed as $b + m$, where $b \in \mathbb{Z}$ is the integral part and where $m \in [0,1)$ is the mantissa. Definition. A real number $x$ is said to be in a ...
- 391
0 votes
1 answer
186 views
Why Does Computable Analysis Use Type 2 Turing Machines Over Type 1 TM's?
I've been researching formal models for computing with real numbers and came across the field of computable analysis built on top of specifically the type 2 Turing machine, which allows for ...
- 1
1 vote
2 answers
699 views
Convert a rational number to a floating-point number exactly
We have two integers, $n$ and $d$. They are coprime (the only positive integer that is a divisor of both of them is $1$). They may be implemented as something that fits in a machine register, or they ...
- 201
2 votes
1 answer
134 views
Finding an approximate double-zero using binary search
Let $f$ be a continuous real function on $[-1,1]$. The function is accessible via queries: for any $x$, the value of $f(x)$ can be computed in constant time. If $f(-1)<0$ and $f(1)>0$, then by ...
- 6,087
0 votes
1 answer
84 views
Does "strongly-polynomial time" implies "polynomial time in the unit-cost model"?
Consider any computational problem in which the inputs are integers. As far as I understand, if the problem has a strongly-polynomial time algorithm, it means that the algorithm uses a polynomial ...
- 6,087
0 votes
1 answer
123 views
Is there a computationally efficient algorithm which can map back and forth a multi-dimensional real number (R^n) to a single dimensional real (R)?
I believe its possible to achieve this with natural numbers. The example below is for 2d to 1d conversions both ways, I do believe this generalizes to n-dimensions. The mapping should work in a way ...
- 173
7 votes
5 answers
2k views
What is the fastest algorithm to approximate an irrational number with specified precision?
Problem Background: Let $a\in(0,1)$ to be an irrational number. Suppose there is a black box, the input is a real number in $[0,1]\backslash \{a\}$, denoted as $x$, the black box outputs boolean ...
- 181
4 votes
1 answer
661 views
Why are complex numbers needed to define qubits?
I have started learning about quantum computing, and I have been told that you can forget about the physics and think of qubits as a natural generalization of the notion of bit. According to this view,...
- 259
15 votes
7 answers
6k views
How can a computer deal with real numbers
Computers are an exceptionally powerful tool for various computations, but they don't excel at storing decimal numbers. However, people have managed to overcome these issues: not storing the number in ...
- 185
-1 votes
1 answer
104 views
What is the computational class of a pushdown automaton with real values?
Say there is a push-down automaton, in this example I'll use a Deadfish-like set: +: increase x by 1 0: set x to 0 ...
0 votes
2 answers
236 views
What are the differences between the set of Real Numbers and the Java datatype float?
Besides the fact that the real numbers ℝ go on forever whereas the floats only go up to a certain point (Float.MAX_VALUE) in Java, what else could I compare between these two sets of numbers?
- 1
0 votes
1 answer
204 views
What's wrong with this "proof" that $\mathbb{R}$ is enumerable?
The fake proof: We know that $\mathbb{R}$ is uncountable, hence we cannot enumerate over it. But what we do know is that $\mathbb{Q}$, the set of rationals, is countable, and even denumerable. We ...
- 157