Re: On the complexity of determining whether n numbers are distinct


Markus Triska wrote:
1. We don't know a priori the size of the vector.

We enlarge it on demand.

Or better yet, we can find the largest number in the list and make the
vector that size.

2. This doesn't handle real numbers.

There's no algorithm for your problem over reals, since their equality
is undecidable.

OH!? That's interesting. Is it because some real numbers require an
infinite amount of memory to store them? The book where I got this
problem from uses the term "real numbers" which is why I asked.

How about floating point numbers? I guess since each floating point
number is represented as a string of bits which is just an integer,
then your algorithm applies.

The book must be implicitly restricting me to pair-wise comparison
operations. What do I do in this case?

.

Relevant Pages

  • Re: Bug in % (Float)?
    ... causing me to conclude something is amiss in the % operator algorithm. ... mathematical equations that are true for reals, ... dangerous in floating point arithmetic, but only when used near its ... I believe the % algorithm should take the points of discontinuity into account and tread very carefully in their neighborhoods. ...
    (comp.lang.ruby)
  • Re: On the complexity of determining whether n numbers are distinct
    ... We enlarge it on demand. ... There's no algorithm for your problem over reals, since their equality ...
    (comp.theory)
  • Re: Zenkins paper on Cantor (reply of Dr. Zenkin)
    ... What is "a function which is a bijection"? ... exists another function (algorithm), f^-1, with the property for all b ... well-defined (exists for all naturals n, m) and S is a bijection - ... of reals, S". ...
    (comp.theory)
  • Re: Zenkins paper on Cantor (reply of Dr. Zenkin)
    ... What is "a function which is a bijection"? ... exists another function (algorithm), f^-1, with the property for all b ... well-defined (exists for all naturals n, m) and S is a bijection - ... of reals, S". ...
    (sci.math)
  • Re: Find out if I/10^i = J/2^j (decadic - dyadic pairing)
    ... 0s with different valency towards infinity; ... but instead some sort of floating point number. ... The reals are sometimes ... algorithms that /do/ halt with the output of a symbol (marks on tape, ...
    (sci.math)