Results 61 to 79 of 79

20190412, 06:08 AM (ISO 8601)
 Join Date
 Jun 2013
 Location
 Bristol, UK
Re: Finding a point in an infinite space
Last edited by halfeye; 20190412 at 06:09 AM.
The end of what Son? The story? There is no end. There's just the point where the storytellers stop talking.

20190412, 02:28 PM (ISO 8601)
 Join Date
 Feb 2012
 Location
 Boston, MA
 Gender
Re: Finding a point in an infinite space
Twice the amount of prime factors. For example:
Divisible by 2? Equal to 2? Yes. Divisible by 3? Yes. Equal to 6? No. Divisible by 5? No. Divisible by 7? Yes. Equal to 42? Yes.
In that example, 3 prime factors * 2 questions for each factor (is it divisible by p and is it equal to p * all the previous factors) + 1 prime less than the number that isn't a factor = 7 questions.
Of course, if we skipped asking whether it's equal to 2 and just went to whether it's divisible by 3, we'd get an answer and save one question. But the number could very well just be 2, or it could be 2 times an arbitrarily large prime and you wouldn't know the difference. There would certainly be more efficient algorithms for certain numbers, but I don't know if you can generalize that. If we're talking an infinite amount of possible numbers, then every prime combination should be equally likely.Last edited by JCarter426; 20190412 at 11:17 PM.

20190412, 02:39 PM (ISO 8601)
 Join Date
 Aug 2008
 Gender
Re: Finding a point in an infinite space
You should start off with Is it Prime? first. If Yes, you don't have to ask about factors, and if No, you don't have to ask Is it 2? Also, you need to ask Is it 1 before any prime search.
Edit: And Is it 0?Last edited by tonberrian; 20190412 at 02:42 PM.
The name is "tonberrian", even when it begins a sentence. It's magic, I ain't gotta 'splain why.
Rick Venture avatar by kpenguin, his GM.

20190412, 02:51 PM (ISO 8601)
 Join Date
 Dec 2009
 Location
 Birmingham, AL
 Gender
Re: Finding a point in an infinite space
Or just add "is it composite" after "is it prime."
Of course, "yes" to the first reduces the remainder to ∞ possibilities, "yes" to the second similarly leaves with you only ∞ possibilities, and the odds of it being 1 or 0 are 1 in ∞. But hey, if both those trigger a "no," go you!The Mod on the Silver Mountain avatars by the wonderfully talented Cuthalion!
If anyone has a crayon drawing they would like to put on the Kickstarter Reward Collection Thread, PM me.
Spoiler: Avatar collectionSpoiler: Come down with fireSpoiler: Lift my spirit higherSpoiler: Someone's screaming my name

20190412, 02:54 PM (ISO 8601)
 Join Date
 Aug 2005
 Location
 Mountain View, CA
 Gender
Re: Finding a point in an infinite space
Like 4X (aka Civilizationlike) gaming? Know programming? Interested in game development? Take a look.
Avatar by Ceika.
Archives:
SpoilerSaberhagen's Twelve Swords, some homebrew artifacts for 3.5 (please comment)
Isstinen Tonche for ECL 74 playtesting.
Team Solars: Powergaming beyond your wildest imagining, without infinite loops or epic. Yes, the DM asked for it.
Arcane Swordsage: Making it actually work (homebrew)

20190412, 03:18 PM (ISO 8601)
 Join Date
 Feb 2012
 Location
 Boston, MA
 Gender
Re: Finding a point in an infinite space
It does if that's the number the oracle is thinking of.

20190412, 03:42 PM (ISO 8601)
 Join Date
 Aug 2008
 Gender
Re: Finding a point in an infinite space
The name is "tonberrian", even when it begins a sentence. It's magic, I ain't gotta 'splain why.
Rick Venture avatar by kpenguin, his GM.

20190412, 04:07 PM (ISO 8601)
 Join Date
 Aug 2011
Re: Finding a point in an infinite space
I'm gonna try to put numbers on the various techniques suggested so far. I'm just gonna make up names for convenience. Since the integer points on a plane are easily mapped to a number line, I'm often going to assume we're looking for an arbitrarily large positive integer.
exponential bound + binary search
The idea here is to put an upper bound on what X could be, then find X. To do that, start with some base b and ask if X <= b; if not, ask if X <= b^{2}, etc etc. Doing this will take log_{b}(X) (rounded up) questions to put an upper bound on X. After that, you do a binary search. If it took n questions to place the bound, the range you need to search is between b^{n} and b^{n1}, which leaves us with b^{n1}(b1) numbers to check. Doing a binary search will take roughly log_{2}(b^{n1}(b1)), which simplifies to nlog_{2}(b) for a very large b; since n = log_{b}(X), the search will take roughly log_{b}(X)log_{2}(b) questions.
So that gives us a total of log_{b}(X) + log_{b}(X)log_{2}(b) questions, or log_{b}(X)(1 + log_{2}(b)) questions. Since b is unbounded, we can choose one such that b is large enough that even log(b) >> 1, we can simplify to log_{b}(X)log_{2}(b), which through change of base simplifies to just log_{2}(X).
Assuming b = 2, we get a similar equation. Placing the upper bound takes log_{2}(X) questions, and doing the binary search takes log_{2}(X)  1 questions (the search space will always be exactly half the bound, so it takes 1 less question to search on average). So using b = 2 takes roughly 2log_{2}(x) questions.
So, we can actually do better if we pick a larger exponential base to work with, but we get diminishing returns because we can never get faster than log_{2}(X). We can even get considerably slower if we accidentally pick b such that b >> X. I would say just pick some arbitrary b that satisfies the above simplifications and be done with it. b = 2^{100} is probably good enough.
I did consider a faster growing scheme but I think you end up just creating more work for yourself. The speed of the binary search grows logarithmically. So if your bound grows faster than exponential growth, the binary search won't be able to keep up. You get less steps in the bound placing section but waaay more steps narrowing down on X after that. Consider growing things by up arrow notation. You ask if X <= 2, X<= 2^2, X <= 2^^2, ..., X<=2^{2}^2, etc. If it takes n steps to place the bound, the binary search will take roughly log_{2}(2^{n}^2), which works out to 2^{(n1)}^2 questions. I can't actually say if 2^{(n1)}^2 questions would be better than log_{2}(X) questions, I'm not really adept at manipulating up arrow notation. But my intuition is that it'd be astronomically slower to grow with up arrow notation rather than exponential notation.
All of this assume we're looking for a single point. If we blindly search of X and Y separately, it would take at most 2log_{2}(X) questions, assuming X>=Y. We could ask which is larger, then we can shave off some questions finding the larger one by finding the smaller one first; we start with a lower bound when finding the larger one. There might even be a way to get fancy and include some boolean logic by asking about X and Y in the same question to speed things up, though I can't think of one.
We could also just map the plane to a line: someone suggested using a square spiral to map the plane to a line and then just ask where the point gets mapped to on the line. I think this severely slows things down, but there might be other mapping techniques that could speed things up.
Radius search
Someone suggested growing a circle of radius R until we've encapsulated the point in question. I'd suggest growing the radius using the exp. growth and then binary search method, but we have a problem: most points on the plane don't fall on a rational radius. They only fall on a rational radius if X and Y are part of a Pythagorean triple (r = sqrt(X^2 + Y^2), and the sqrt of a whole number is only rational if it's whole). Take the point <1,1> for instance: you'll never narrow in on the exact radius. Now, you don't actually need to: if 2>r>1, then there's exactly 4 points that could possibly work, and you can just work through them exhaustively in 2 questions. But what about if 1323>r>1322? How many points fit in there? Are there any points in there? No idea.
Prime Factors
This one is really neat to me, but presents a few problems. The biggest problem is that we don't know all the primes. We have no way of reliably generating all the primes through anything else besides brute force. If we're willing to grant that we somehow have a list of all primes, or are willing to accept an answer like "the product of the primes with indices (3^^^^3) and (3^^^^3 + 1)" as an answer, than cool, we can continue.
The other issue is if there are any repeating prime factors. We can't just ask if X is divisible by 2: we also have to ask if it's divisible by 4, 8, 16, etc. And then again for 3, 5, 7. Doing this exhaustively would be incredibly slow.
So: first question to ask is if X is prime. If it is, we just find the index using whatever method you want. Prime density grows at X/ln(X), so this search would take log_{2}(X)  log_{2}(ln(X)) using the growth + binary search method.
If it isn't, my next question would probably be "how many prime factors does X have" (e.g. 12 in this case would have 3 prime factors, since 12 is 2x2x3). The most prime factors X could possibly have is log_{2}(X), which means this would take log_{2}(log_{2}(X)) to calculate. We'll call this number K, where K = log_{2}(X) at most.
Knowing K, I would then propose the following scheme: expand through the index of primes exponentially, at each index asking "are all prime factors below this index." The largest prime factor a number could possible have would be X/2^{K1} so in the worst case this will take log_{2}(X/2^{K1}/ln(X/2^{K1})). Note that K being small here is actually worse.
Having found this point, do a binary search through the range asking "are there more prime factors at or above this index than below it" to narrow in on all the prime factors. I'm not quite sure how to implement this search or how fast it would be, but I don't think it'd be much slower than searching for an individual prime factor, since you're recording information about where all the other factors are as you search.
One you hit a prime factor, you can start asking how many times that factor is a prime factor, which we've also gathered information on. Take this example: we know all the prime factors are smaller than the 100th prime, and there's 12 factors. We ask if there's more primes above or below index 50. There's fewer above. Of those above index 50, we ask if there's more prime factors above or below 75. There's fewer below. At this stage we know there are at most 5 factors above index 50, and at most 2 of those are between index 50 and 75. Even if we just stopped here and searched prime factors of index 50 to 75 exhaustively, we only need ask if they appear in the prime factorization once or twice. From 75 to 100, we need only ask if they appear in the prime factorization of X once, twice, or thrice. Say prime 65 appears twice, and primes 97, 98, and 99 each appear once: there's 7 primes remaining, and we can continue the process for all primes with index less than 50.
Now at this point we're well beyond my ability to quantify exactly how fast this process is. but I'm reasonably certain it's competitive with simple exponential growth coupled with binary search. It might even be faster.
I was going to add more, but this is getting long and I have work to do, so I'll take a proper stab at the others later.
No, they're just restricted to being specified by things other than "the number this oracle is thinking of". The ability to compute an arbitrary amount of digits for this one specific number does not help in finding the value of the 20th Busy Beaver number.
(I'm not sure telling the oracle what number to think of would eliminate all uncomputable numbers, but it would eliminate all the ones we know about and can describe).
Ergo, omniscient oracles can't exist...?Last edited by crayzz; 20190412 at 04:26 PM.
Originally Posted by crayzzOriginally Posted by jere7my

20190412, 04:14 PM (ISO 8601)
 Join Date
 Sep 2016
Re: Finding a point in an infinite space
I think we if we have a given method where we can say how many steps it needs for a given number, and it scales passably, then we can kind of argue the toss.
Linearly I think is not really ok. I can easily write the number of atoms in the universe in full, I can't do that many operations.
Logrithmically I think is better, in N questions we can only separate 2^{N} sets (so it is literally the best we can do), doing anything accurately with the number requires a similar number of steps.
It's a bit sophistic (as you say, there are a lot of numbers out there. But on the other hand if it really was 'just' much less than (((0.001)^100)^100^100)% of the numbers we'd only need to add a mere 10 million more questions, which would be a very sad lifetime but in theory doable.) For any number once we (by whatever magical means) have the resources to identify it and a non trivial proportion of the number line up to that point we also have the resources to identify it by binomial chop.
I do like the sound of the primes method, but I don't think it can gain too much in general. If n is a prime we use n/log(n) steps (prime number theorum) which is clearly worse (and I don't think that can be improved on). We do of course gain elsewhere, in 100 simple steps we can identify the number 229^{50} which would take us 400 steps by binomial chop (and Knaights variation could take us up much further).
Going back to the sophistry, the above was a bit tautological (both statements more or less boil down to we can write down the digits). There are of course many numbers we can express in other ways which grow quicker than our efforts to express them, e.g. Graham's number and which we can still do some stuff with (we can of course use binary chop on the ascii of the 'program' that computes it).
So something that very quickly gave an 'appropriate' ranged box (the range being almost 'identical' to the number, so effectively no progress towards an exact representation) would be interesting.

20190412, 04:25 PM (ISO 8601)
 Join Date
 Aug 2018
 Location
 Sleeping on a blanket.
Re: Finding a point in an infinite space
Well done.
Jayem, I can't really tell what you are trying to say. Are you saying that for large numbers, actually running the algorithm is hard? I don't think anyone disputes it, but if we can ask countably infinitely many questions we probably have an infinite amount of time.
—CaeruleaNon caerulea sum, Caerulea nomen meus est.
Extended Signature.
I'm not a humanoid. Come not be one too.

20190412, 04:35 PM (ISO 8601)
 Join Date
 Aug 2011
Re: Finding a point in an infinite space
Not a real suggestion, but: assuming we could generate arbitrary algorithms, we could always just go through a list of them and ask if that one is the fastest, then implement it.
Though I'd be hard pressed to think of a slower method of doing things.Originally Posted by crayzzOriginally Posted by jere7my

20190412, 05:36 PM (ISO 8601)
 Join Date
 Dec 2009
 Location
 Birmingham, AL
 Gender
Re: Finding a point in an infinite space
The Mod on the Silver Mountain avatars by the wonderfully talented Cuthalion!
If anyone has a crayon drawing they would like to put on the Kickstarter Reward Collection Thread, PM me.
Spoiler: Avatar collectionSpoiler: Come down with fireSpoiler: Lift my spirit higherSpoiler: Someone's screaming my name

20190412, 06:00 PM (ISO 8601)
 Join Date
 Aug 2018
 Location
 Sleeping on a blanket.
Non caerulea sum, Caerulea nomen meus est.
Extended Signature.
I'm not a humanoid. Come not be one too.

20190412, 06:15 PM (ISO 8601)
 Join Date
 Sep 2016
Re: Finding a point in an infinite space
Trying to convince myself (and halfeye) that it is 'reasonably' hard.
There's enough 11 correspondences already that messing about with them to exploit infinity is something that if I avoid I'd be happier. If it works on the infinity is just a big number level that strikes me as being for the good.
We could for instance just use the "Q1: Is it 1", "Q2: Is it 2"... approach.
The logrithmic timescale is of course the best we can do (for the finite case at least). And that kind of passes that subjective test in a "Log(infinity) is clearly much less than infinity." way [but it's also easy to see that we can always make it take much longer than any given amount of time, which shows how dodgy that statement is]Last edited by jayem; 20190412 at 06:18 PM.

20190412, 06:37 PM (ISO 8601)
 Join Date
 May 2007
 Location
 Tail of the Bellcurve
 Gender
Re: Finding a point in an infinite space
Strangely enough, one can't really talk about the probability of picking the correct number, or expected number of steps to convergence or anything like that, because there is no uniform probability distribution over the whole numbers (or any other countably infinite set). If the person generating the variable is doing so randomly, they're using a nonuniform distribution.
Bloodred were his spurs i' the golden noon; winered was his velvet coat,
When they shot him down on the highway,
Down like a dog on the highway,And he lay in his blood on the highway, with the bunch of lace at his throat.
Alfred Noyes, The Highwayman, 1906.

20190412, 08:07 PM (ISO 8601)
 Join Date
 Jan 2007
Re: Finding a point in an infinite space
As weird as it sounds at first, it pretty much has to be true. One thing we should most likely assume, that it is a distribution with a heavy tail, so the mean is infinite. Still, if one really insist on having a nonzero probability density everywhere, then it puts a specific condition on the disctribution f, which is that the integral over the whole distribution needs to be equal to 1 (here for 1D):
Integral^infinity_(infinity) dx f(x) = 1
For it to be true it has to be finite first, so
limit_(x>infinity) x*f(x) = 0
Interestingly, for more dimensions it will constrain the distribution even more. If we assume maximum randomness (so no angle dependencies), then
Integral^infinity_(infinity) dx dy f(x,y) = Integral_0^(infinity) dr f(r,phi)*r Integral_0^(2 Pi) dphi = 2 Pi*Integral_0^(infinity) dr f(r,phi)*r
So we have an extra r under the integral. This gives us the condition as
limit_(r>infinity) r^2*f(r) = 0
While you can have well defined distributions, which converge slower then that, but it can only happen in a well defined direction in the r>infinity limit. A simple example would be to take a 1D distribution in each direction and multiply them:
f(x,y)=f_1(x)f_2(y)
Along the axes the convergence will be as slow as in the 1D case, but this will happen only if we take the limit in a direction parallel to the X or Y axis. In any other direction the convergence is much faster and fits the asymptotic criterion.
In the same manner for n dimensions it will be
limit_(r>infinity) r^n*f(r) = 0
Still such distributions can easily have infinite mean value.In a war it doesn't matter who's right, only who's left.

20190412, 11:22 PM (ISO 8601)
 Join Date
 Feb 2012
 Location
 Boston, MA
 Gender
Re: Finding a point in an infinite space
Yes.
I mean, it's not incredibly profound, as we said before, but that's the paradox of it. If the question is whether the process is true for all reals, on the surface the answer should be no, because we know there are uncomputable numbers, so we shouldn't be able to find a process that works for them. But we can also demonstrate a process that does work if we have an oracle to confirm the answer. The conclusion, of course, is that they can't actually be thinking of an uncomputable number and can only know some finite approximation of it. But that goes against the premise of the question.

20190413, 12:32 AM (ISO 8601)
 Join Date
 Aug 2005
 Location
 Mountain View, CA
 Gender
Re: Finding a point in an infinite space
I think you're misinterpreting what it means for a number to be uncomputable. It does not mean that the number is impossible to represent. It means that the number is impossible to identify the value of from its definition.
For example, consider the two thousandth Busy Beaver number. It's a finite integer by the nature of its definition, so if someone actually knew its value and had enough time, space, and materials it would obviously be possible to write it down. At the same time, it has been proven to be uncomputable. This is not a contradiction, because it just means that no one will ever know which integer is "the two thousandth Busy Beaver number".Like 4X (aka Civilizationlike) gaming? Know programming? Interested in game development? Take a look.
Avatar by Ceika.
Archives:
SpoilerSaberhagen's Twelve Swords, some homebrew artifacts for 3.5 (please comment)
Isstinen Tonche for ECL 74 playtesting.
Team Solars: Powergaming beyond your wildest imagining, without infinite loops or epic. Yes, the DM asked for it.
Arcane Swordsage: Making it actually work (homebrew)

20190413, 01:38 AM (ISO 8601)
 Join Date
 Aug 2011
Re: Finding a point in an infinite space
Originally Posted by crayzzOriginally Posted by jere7my