Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Looking for math library

This thread is locked; no one can reply to it. rss feed Print
 1   2   3   4 
Looking for math library
William Labbett
Member #4,486
March 2004
avatar

This is what I can't grasp.

Isn't is simple ?

You've got an infinite number of rooms. Which means no matter how many you use, there'll also be more of them spare.

You just consider the odd numbered ones : you've still got the same situation. You won't run out of empty rooms no matter how people want to stay in them.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

This also bothers me (infinite guests in an infinite roomed hotel leaving ??? empty rooms?) :
<math>\infty - \infty \not\equiv 0</math>

@James Lohr
I think this
Coinductive definitions and real numbers
might be what you were looking for. In any case it is moot since we don't have infinite resources to compute with.

Even given that information, it is still far simpler to represent one tenth in decimal than binary. :P

Tobias Dammers
Member #2,604
August 2002
avatar

This is what I can't grasp.

It's quite simple. In layman's terms: If you want to count all the even-numbered rooms, you'll never finish. If you want to count all the rooms, you'll also never finish. That's what cardinality is about (in simplified terms).

Using the 2n proof: If you want to show that any whole number n exists for which 2*n does not exist, then you will have to walk the list of whole numbers and check each one, until you reach one that you cannot multiply by 2. If you do this, you will never stop walking the list, because it does not end.

Infinity is not a number, not even an incredibly large one. It's a concept. And because of this, the rules that apply to numbers do not apply to infinity. You cannot subtract anything from infinity, in fact, you cannot perform any arithmetic on it at all. It's not a number.
Mathematicians use the concept of infinity and the infinity symbol to indicate a series that does not end, or a number that grows without bounds ("approaches infinity" means just that).

Back to your original problem. Computers use binary numbers to do their calculations, which means they can, by nature, only deal with whole numbers (and a limited range of them at that). However, most things in life don't map nicely to whole numbers, so people invented a bunch of strategies to overcome this problem:

  • Big integers. This strategy uses an array of integers, each representing a part of the number; the array grows as needed, so there is no theoretical maximum to the size of the number you can represent this way. You're still bound to whole numbers only, and the amount of available and addressable RAM is of course still a constraint.

  • Fractions. Store each number as a pair of integers (or better yet, bigints), one for the numerator and one for the denominator. This way, you can represent all rational numbers (again, within the physical constraints of the hardware), but there are quite some limitations - the representation isn't automatically canonical (e.g. doing 2/3 * 3/2 naively will yield 6/6, which you want to reduce to 1/1 for all sorts of reasons), and canonicalizing your numbers can be quite costly. Also, finding good approximations for irrational numbers is really really complex matter.

  • Fixed-point. Store your number as an integer, but adjust your calculations so that it is understood to mean multiples of a step < 1. For example, 1/0x10000 used to be popular (giving you a binary fixed-point format with 16 bits for the whole-number part and 16 for the fractional part); for financial calculations, you rather want to use 1/100 or 1/10000, so that your integer represents cents or 1/100ths of cents. The advantage of this is that it's very fast (you do your calculations on native integers), and your precision is exactly the same over the entire range, in absolute terms - that is, adding 0.1 to a number always produces the same rounding error no matter what you add it to.

  • Floating-point. Store your number as a pair of integers, one for the mantissa and one for the exponent. This pair (m,e) is then understood to mean m * 2e, where both m and e may be negative. (Technically, it's implemented a tad bit different, but the general idea is the same). What this means is first of all, that the precision is roughly the same over the entire range, in relative terms. That is, if a certain number has a 0.01% rounding error when represented as a float, then ten thousand times that number will also have a 0.01% rounding error, approximately.

And now comes the problem. While each of these can represent a particular subset of the set of real numbers, none of them can represent them all. One can at least represent all rational numbers, the rest of them can't even do that. All but the fraction approach have one numeric base for which they can offer exact representations, while all other rational numbers can only be approximated.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

William Labbett
Member #4,486
March 2004
avatar

This also bothers me (infinite guests in an infinite roomed hotel leaving ??? empty rooms?) :

No, an infinite number of guest would match an inifinite number of rooms 1 for 1.

Oscar Giner
Member #2,207
April 2002
avatar

{2,4,6...2n}
{1,2,3...n} OOPS {n + 1,n + 2...2n} Is missing!

But those are finite sets. An infinite set doesn't have a last element (or it can have a last element, but then it cannot have a first element (for countable sets, which those both are)). So for those sets to be infinite, elements n+1, n+2... do actually exist.

So what you actually have is:
{2, 4, 6... 2n...}
{1, 2, 3... n...}

Quote:

The cardinality of {2,4...2n} will never equal the cardinality of {1,2...2n}

Of course the cardinality of {2,4...2n} is less than the cardinality of {1,2...2n}. But you did the same mistake: those are finite sets, not infinite.

And no, saying that n = infinite is not valid, because that would make you claim that an infinite set has a last element (thus not being infinite... so... are you saying that infinite sets are not infinite?).

The error you're doing again and again is extrapolating rules that apply to finite sets to infinite sets. You're trying to "prove" your believes on infinite sets by proving those believes are actually true for finite sets.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Evert
Member #794
November 2000
avatar

Why does this suddenly stop being true when you can no longer count n?

It does. You can easily show that it does. There's no more to it than that.
Consider the set N of all integers. Now construct a new set, E, such that E = {2n, for all n in N}. How many elements are there in the set E (what is the cardinality of E)? Well, the same as there are in N, by construction. However, also by construction, E contains all even integers. Conclusion: there are as many even integers as there are integers.
Similarly, construct the set O such that O = {2n+1, n in N} and lets say that 0 is in N. By construction, O has the same number of elements (same cardinality) as N. They're also all odd integers. Conclusion: there are as many odd integers as there are integers.
Suppose there are more integers than even integers. Then there must be an n in N for which 2n is not in E. But 2n is an even integer if n is an integer, and must be in E. Therefore there is no n in N for which 2n is not in E, and the number of elements in N is not larger than the number of elements in E.

Quote:

It's just not right.

It's 100% right. It's just counterintuitive (or rather, you don't have the right kind of intuition). If you want to raise an objection, find a fault in the logic of the proof. "I don't understand how this works" is not a valid objection.
So if you want to continue the debate, I suggest you try to find an error in the proof. Actually, I don't really suggest that you waste your time trying to do that. You're better off dropping this here.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

What's the limit of (2n/n) as n approaches infinity? Two. You'd have me believe it suddenly stops being 2 and becomes 1. That's hogwash.

Like I said before, you're comparing unequal ranges :
A {2,4,6...}
B {1,2,3...} OOPS We didn't bother to include 4,5,6. Guess we have to extend the range of A to {...8,10,12} OOPS we forgot to include 7-12 in B. Repeat ad nauseam...

The idea that there are twice as many integers as even integers cannot simultaneously be both true and false.

Don't try to convince me further. Arbitrarily breaking rules that apply to countable numbers just so uncountable numbers will work is crap.

Matthew Leverton
Supreme Loser
January 1999
avatar

Closing thread to save somebody from wasting time with a response.

 1   2   3   4 


Go to: