Questions tagged [real-numbers]
The real-numbers tag has no summary.
57 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
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....
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 ...
0
votes
1
answer
184
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
vote
2
answers
698
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 ...
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 ...
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 ...
0
votes
1
answer
122
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 ...
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 ...
4
votes
1
answer
659
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,...
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 ...
-1
votes
1
answer
103
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
233
views
What are the differences between the set of Real Numbers and the Java datatype float?
Besides the fact that the real numbers R 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?
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 ...