Questions tagged [real-numbers]
The real-numbers tag has no usage guidance.
52
questions
1
vote
2
answers
135
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
78
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 ...
- 5,790
0
votes
1
answer
42
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 ...
- 5,790
0
votes
1
answer
73
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 ...
- 163
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
312
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,...
- 239
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
69
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
179
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
120
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
2
votes
0
answers
50
views
Complexity of approximating a function value using queries
I am looking for information on problems of the following kind.
There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You ...
- 5,790
0
votes
1
answer
111
views
Doubt regarding Cantor's diagonalization argument [closed]
So, we use Cantor's diagonalization argument to prove that the Universal Turing Machine is not a decider.
I understand the overall argument but have a problem regarding one caveat mentioned in my ...
- 101
3
votes
4
answers
527
views
Is the calculation of infinite sums solvable by a computer?
The question is: I give the computer a sum, such as $\sum_{n=1}^\infty\frac{1}{n^3}$, the computer is expected to return an elegant closed-form solution, because the answer may be irrational. Has this ...
- 942
0
votes
1
answer
133
views
How can I develop a pseudo-polynomial time algorithm for a non-integer problem?
I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta_j$, i.e. the parameter is a real number and $\beta_j \leqslant 0.5, \exists j \in J$.
Since the problem ...
- 159
1
vote
0
answers
510
views
Finding a path with a smallest product
Let $G$ be a graph whose edges have integer weights between 1 and 255.
What is an efficient algorithm for finding a path between two vertices $s,t$, such that the product of weights on the path is ...
- 5,790
2
votes
0
answers
84
views
Is it a bad idea to require a correctness proof as part of a computable real number?
At 30:42 of Norman Wildberger's Difficulties with real numbers as infinite decimals (II) lecture, he raises the question whether "certificates of boundedness" (of the runtime of the algorithm to ...
- 5,362
0
votes
1
answer
180
views
Would Schmidhuber's theories of everything be capable of performing hypercomputation?
Jürgen Schmidhuber pointed out that a simple explanation of the universe would be a Turing machine analogy programmed to execute all possible programs computing all possible histories for all types of ...
- 41
3
votes
1
answer
445
views
Can generalized Turing machines compute all reals?
Super-recursive algorithms are theoretical super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines.
In this entry it ...
- 41
1
vote
1
answer
110
views
Real RAM computational mode
Given a real value $M>0$, I want to compute the greatest value of $\epsilon$ strictly smaller than $M$. Given the assumption that the computational model is Real-RAM, how to find a real number ...
- 13
2
votes
0
answers
55
views
Semidecidable properties of computable reals
By computable real I mean $x\in\mathbb{R}$ such that there is some computable total function $p_x$ that takes a natural number $n$ and returns a dyadic rational $r$ such that $|x-r|<2^{-n}$. I ...
- 21
2
votes
1
answer
142
views
How to represent symbolic knowledge using real numbers - theory about neural networks and natural/analog computing?
One can define the semantics of one definite word using the references to real world entities, relationships with the other words and other concepts and represent all this knowledge about this one ...
- 1,381
6
votes
1
answer
1k
views
Do "Type-2" Turing machines with infinite length inputs have more computational power?
Certain idealizations of a Turing machine yield an increase in computational power, such as an inductive Turing machine, which can (trivially) solve the halting problem if it has an infinite amount of ...
- 827
1
vote
2
answers
3k
views
How does conversion from fixed-point to floating-point happen?
I came across to the code that convert 32-bit signed fixed-point number (16.16) to a float and it looks like (pseudocode)
floating = fixed / 65536.0
Could you ...
- 13
11
votes
2
answers
577
views
Decidable properties of computable reals
Is "Rice's theorem for the computable reals" -- that is, no nontrivial property of the number represented by a given computable real is decidable -- true?
Does this correspond in some direct way to ...
- 213
4
votes
0
answers
81
views
Real RAMs with "reasonable" operations
There is a large body of literature on RAMs with "reasonable" and "unreasonable" operations, where "unreasonable" operations would yield a machine with too much power to be practically feasible.
For ...
- 827
0
votes
0
answers
35
views
When do you know whether an exponent represents a movement of the decimal point to the left?
I'm learning about floating point numbers and I don't quite understand when one should interpret an exponent as moving the decimal point to the left.
By book shows an example of converting -10.5 ...
- 113
3
votes
1
answer
110
views
Total functional computable real numbers
Is there any computable real number which can not be computed by a higher order primitive recursive algorithm?
For computable real number I mean those that can be computed by a Turing machine to any ...
- 475
3
votes
1
answer
383
views
Are IEEE floating point numbers intervals or point values?
The context is IEEE 754-2008 floating point number systems. The systems defined by the standard comprise, as far as I understand it, a bit-level representation and a set of guarantees on the precision ...
- 190
2
votes
0
answers
370
views
Why mantissa and exponent are stored differently in a float?
As we know, in IEEE 754 standard, float number's exponent and mantissa are stored differently. While the exponent is stored as an unsigned number, taking advantage of the bias, the mantissa is in sign-...
- 121
1
vote
2
answers
6k
views
Find out duplicate number between 1 to N numbers
I first saw this question on this website where I was trying on Java puzzles.
Here is the Question:-
...
- 115
3
votes
0
answers
83
views
Computational complexity of logistic map
My question is pretty simple and to the point. Is there a known way to efficiently compute logistic maps to within a specified precision? In other words, the input is a value $x$ and integers $d,n$; ...
- 3,790
2
votes
2
answers
385
views
Why is there more frequent overflow in normalised Floating Point
I read that overflow is more frequent when we work with normalised mantissas. Why is this? Is it because when we adopt a normalised representation, our range is smaller than in a unnormalised ...
- 33
0
votes
0
answers
31
views
Is there a good model of computation for real numbers? [duplicate]
/!\ I am not speaking about int or float, my question is about model of computation used to design and describe algorithms.
The integer numbers case
Many algorithms use integers and their ...
- 669
3
votes
1
answer
43
views
Extended version of the theory of reals and its decidability
It is well-known due to Tarski that the theory of reals $(\mathbb{R},+,\cdot,<,=)$ is decidable. I was asking my self whether one would lose the decidability by adding all real constants. More ...
- 31
-1
votes
1
answer
36
views
Efficient algorithms for finding the limit of a sub-sequence [closed]
Given a sequence $A_N={a_1,a_2,a_3...,a_N}$ of real numbers, and given that there exist some sub-sequence which generated from some deterministic converging sequence.
Are there any efficient ...
- 1
6
votes
1
answer
546
views
Can a probabilistic Turing Machine compute an uncomputable number?
Can a probabilistic Turing Machine compute an uncomputable number?
My question probably does not make sense, but, that being the case, is
there a reasonably simple formal explanation for it. I should ...
- 19.4k
7
votes
3
answers
564
views
Unreachable Real Numbers - Randomness & Computability
I've recently read that there were many real numbers that would never be reachable by humanity. The explanation itself says that we can write as many programs as integers which is infinite, but there ...
- 377
7
votes
2
answers
205
views
Computability of equality to zero for a simple language
Suppose we have a tree in which leaves are labeled with a set of numbers $L$, and internal nodes with a set of operations $O$.
In particular $L$ can be $\mathbb{N}, \mathbb{Z}$ or $\mathbb{Q}$, and ...
- 409
1
vote
1
answer
2k
views
Minimize sum of squared error
I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to ...
- 25
2
votes
2
answers
232
views
Is Newton's Method to compute the zeros of a function an algorithm?
Looking for Newton's method in Wikipedia, I read the following:
In numerical analysis, Newton's method (also known as the
Newton-Raphson method), named after Isaac Newton and Joseph Raphson,
is ...
- 19.4k
4
votes
1
answer
75
views
Computational complexity for more general problems
When I read computational complexity I encounter problems like 3-SAT, set cover, knapsack. In the first two variables are discrete. In knapsack the weights and values are integer and all three ...
- 215
15
votes
2
answers
978
views
Are there established complexity classes with real numbers?
A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of:
I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ (with ...
- 71.9k
10
votes
8
answers
4k
views
Represent a real number without loss of precision
Current floating point (ANSI C float, double) allow to represent an approximation of a real number.
Is there any way to represent real numbers without errors?
Here's an idea I had, which is anything ...
- 459
2
votes
1
answer
106
views
Can Turing Machines decide on computability? [closed]
Can a Turing Machine decide whether an arbitrary real number is computable or not? Does this even follow from the solution of the Halting problem? If not, who proved it?
- 29
2
votes
2
answers
157
views
Implement Mathematica's capability of rationalizing machine reals
If I have a variable x bound to a machine precision real in Mathematica, I can use
y = FromDigits[RealDigits[x]]
then y is ...
- 123
3
votes
1
answer
90
views
How to compute a level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $
I have a real function $f:\mathbb{{R}}^{d}\mapsto\mathbb{R}$, where
$d>1$. The question is how to compute the level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $.
I am a statistician ...
- 131
5
votes
1
answer
160
views
Minimal positive difference of a mulitset of real numbers
Motivated by Max-Flow: Detect if a given edge is found in some Min-Cut, I'd like to ask the following questions:
Given a multiset of real numbers $B$, how hard is it to compute the minimal positive ...
- 2,279
5
votes
1
answer
105
views
Rearrange a sequence of real numbers to satisfy polynomial inequalities
Assume we fix a degree $d$ polynomials $f$ of $k$ variables. (If it helps, let $t$ be the number of terms in $f$).
Consider a list of real numbers $a_1,\ldots,a_n$, does there exist a permutation $\pi$...
- 3,023
4
votes
1
answer
182
views
Why is solving of diagonal quadratic equations over $\mathbb R$ and $\mathbb C$ in $P$?
Let $\mathbb F\in\{\mathbb R, \mathbb C\}$ the field of real or complex numbers. Then [1, page 22 in the middle] claims that the following equation can easily be solved in deterministic polynomial ...
- 377
8
votes
2
answers
2k
views
Does there exist any work on creating a Real Number/Probability Theory Framework in COQ?
COQ is an interactive theorem prover that uses the calculus of inductive constructions, i.e. it relies heavily on inductive types. Using those, discrete structures like natural numbers, rational ...
- 858