New OOTS products from CafePress
New OOTS t-shirts, ornaments, mugs, bags, and more
Page 1 of 3 123 LastLast
Results 1 to 30 of 79
  1. - Top - End - #1
    Titan in the Playground
     
    AvatarVecna's Avatar

    Join Date
    Jan 2014

    Default Finding a point in an infinite space

    There is a plane where the X-axis goes from -∞ to ∞ and where the Y-axis goes from -∞ to ∞. You know that somewhere on the plane is a point whose X and Y values are both whole numbers. Your goal is to find this point, but you can only ask yes/no questions about the point; there's no limit on how many such questions you can ask, nor on the complexity of the questions, save that they must be answerable with a binary "yes" or "no" answer. Can you find the point, and if so what is your method?
    Last edited by AvatarVecna; 2019-04-06 at 08:08 PM.


    Currently Recruiting WW/Mafia: Logic's Deathloop Mafia and Book Wombat's A Small Wager - A Practical Guide To Evil

    Avatar by AsteriskAmp

    Quote Originally Posted by Xumtiil View Post
    An Abattoir Vecna, if you will.
    My Homebrew

  2. - Top - End - #2
    Titan in the Playground
     
    tyckspoon's Avatar

    Join Date
    Nov 2007
    Location
    Indianapolis
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Pretty easy; "is the y coordinate greater than 0?" Repeat for x. Now you know which quadrant it's in. Repeat basically the same questions, increase the number you ask about by.. Oh a billion or so until you get a broad zone to narrow into. There's probably a more efficient algorithm, but it's not hard to do.

  3. - Top - End - #3
    Titan in the Playground
     
    AvatarVecna's Avatar

    Join Date
    Jan 2014

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by tyckspoon View Post
    Pretty easy; "is the y coordinate greater than 0?" Repeat for x. Now you know which quadrant it's in. Repeat basically the same questions, increase the number you ask about by.. Oh a billion or so until you get a broad zone to narrow into. There's probably a more efficient algorithm, but it's not hard to do.
    That such a method can theoretically work for a vast number of points is obvious, but it runs into issues because of the nature of the infinite plane. Your own example does a good job of highlighting one of the issues I had in coming up with an answer myself, which is that any individual question cannot be more efficient than eliminating half of all possible points (that is to say, each question is at its most efficient when "yes" and "no" both correspond to half the remaining points, so that no matter what the point is, each question will eliminate half of the remaining possibilities). Your example shows this off well, in that your first two questions each divide the field in two, but your q3, q4, and so on are much tinier slivers of the whole. Q3 "is the Y coordinate greater than 1 billion" for example would eliminate either "1 billion" possibilities (if the answer is yes) or "∞ - 1 billion" possibilities (if the answer is no), and that second part is the problem: if the answer is no, your question has accomplished not quite nothing, but about as close to nothing as a question can accomplish. But then, what are the odds that the answer will be "yes" instead of "no", that we will eliminate everything except a billion possibilities rather than merely eliminating a billion possibilities? It's clearly not a 0% chance that the answer will be yes, but it's trending towards 0, which is the problem.

    And that's true whether the large number you increased by is one billion, one septillion, one google, one googleplexion, or any other non-infinite number; it doesn't matter how big the number you're increasing by is, infinite is infinitely bigger. If each of an infinite series of questions can only eliminate an infinitesimally small sliver of the remaining possibilities, can the point always be found? Even if the method is refined in such a way that you exactly eliminate half of all remaining possibilities, does dividing infinite by 2 produce something besides infinite, if done enough times?


    Currently Recruiting WW/Mafia: Logic's Deathloop Mafia and Book Wombat's A Small Wager - A Practical Guide To Evil

    Avatar by AsteriskAmp

    Quote Originally Posted by Xumtiil View Post
    An Abattoir Vecna, if you will.
    My Homebrew

  4. - Top - End - #4
    Firbolg in the Playground
    Join Date
    Dec 2010

    Default Re: Finding a point in an infinite space

    Do you have a countably infinite or uncountably infinite number of questions? If countably infinite, then sort the points into a line (for instance, by 2pi * distance first and then by angle) and ask one by one. That will take an infinite number of questions, but it's no less efficient than any other method that requires an infinite number of questions.

  5. - Top - End - #5
    Titan in the Playground
    Join Date
    May 2007
    Location
    Tail of the Bellcurve
    Gender
    Male

    Default Re: Finding a point in an infinite space

    A constructive method for locating the point is to do the following for each coordinate:
    1) ask "is the number zero" If it isn't continue
    2) ask "is the number positive?". Store the sign somewhere, and continue
    3) set n = 1
    4) ask "is the nth in the number's binary representation one?"
    5) ask "is there a n+1st term in the number's binary expansion?" If yes, set n = n + 1, return to step 3. If not, you are done.

    Repeat steps 3 and 4 until there isn't a next term. When you finish, you will have the binary representation of the number, hence the number. This method is guaranteed to terminate in no more than 2 + 2*d steps, where d is the number of digits in the binary representation.


    (Finding the point is, mathematically speaking, trivial. The cardinality of whole number pairs in R2 is countably infinite. Since you get unlimited questions, simply diagonalizing your way through all (x, y) pairs of whole numbers will get you the solution. However that answer's no fun at all.)
    Blood-red were his spurs i' the golden noon; wine-red 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.

  6. - Top - End - #6
    Bugbear in the Playground
     
    BlueWizardGirl

    Join Date
    Aug 2018
    Location
    six feet under
    Gender
    Female

    Default Re: Finding a point in an infinite space

    If you can only ask a finite number of questions, no the point can not be found in general. Otherwise, well...

    My method would be to ask about the factors of coordinates. Start with "is the x factor divisible by 2" which eliminates half the points. Then ask if it is divisible by 3, if the answer is no, and 3 * 2 if the answer is yes. Repeat for all primes. Because each number is uniquely factor able into primes I think you would get the answer. I suspect it would take ω steps though.

    Edit: I like warty goblins method too.

    —Caerulea
    Last edited by Caerulea; 2019-04-06 at 11:20 PM.
    Non caerulea sum, Caerulea nomen meum est.
    Extended Signature.
    I'm not not a humanoid. Come not not be one too.
    Answer trivial questions in the OOTS trivia thread!

    she/her



  7. - Top - End - #7
    Titan in the Playground
     
    tyckspoon's Avatar

    Join Date
    Nov 2007
    Location
    Indianapolis
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Your search space is infinite, but the value you are looking for is not, which means we can ask useful questions about it regardless of the infinities. How about something like "Assuming Times New Roman in a 12-point print, can the (x or y) coordinate be printed in its entirety on a single line of a standard 8.5 x 11 page of printer paper?" If not, ask again, but use scientific notation. If still no, go to whatever your favorite method of rotating excessively large numbers is. That will eventually get you a (admittedly very, very broad) placement of at least the magnitude of the number you are looking for, and once have that you can refine further...

    Or if want to brute force the whole process "Is the (nth) digit (0-9)? Is there an (n+1th) digit? Is the (n+1th) digit (0-9)?" Iterate until you are told there aren't any more digits. Super tedious, sure, but also the sort of thing that's really straightforward to feed into a computer and just come back later to check the progress.

  8. - Top - End - #8
    Titan in the Playground
     
    AvatarVecna's Avatar

    Join Date
    Jan 2014

    Default Re: Finding a point in an infinite space

    Hmm...the point about countable infinities vs uncountable is I think the stumbling block that was making it difficult for me to wrap my head around, but different degrees of infinite makes it a bit easier. Would an uncountably infinite number of questions be insufficient to determine the point if it was "numbers" instead of "whole numbers", since that opens up fractions and irrationals and makes the problem also an uncountable infinite, or is the uncountable infinite of the problem still not so large that the uncountable infinite of the solution couldn't solve?


    Currently Recruiting WW/Mafia: Logic's Deathloop Mafia and Book Wombat's A Small Wager - A Practical Guide To Evil

    Avatar by AsteriskAmp

    Quote Originally Posted by Xumtiil View Post
    An Abattoir Vecna, if you will.
    My Homebrew

  9. - Top - End - #9
    Firbolg in the Playground
    Join Date
    Dec 2010

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by AvatarVecna View Post
    Hmm...the point about countable infinities vs uncountable is I think the stumbling block that was making it difficult for me to wrap my head around, but different degrees of infinite makes it a bit easier. Would an uncountably infinite number of questions be insufficient to determine the point if it was "numbers" instead of "whole numbers", since that opens up fractions and irrationals and makes the problem also an uncountable infinite, or is the uncountable infinite of the problem still not so large that the uncountable infinite of the solution couldn't solve?
    A countably infinite number of questions can find the point (and, relatedly, rationals (fractions) are countably infinite).

    An uncountably infinite number of questions can determine the point if it's 'numbers', though 'uncountably infinite discrete objects' (e.g. questions) seems a bit of a suspect construction in its own right and probably requires a bit more care than I'm giving it. To be more careful, I think one would want to define a dense manifold of questions and then ask whether there's some aggregation function that collects the answers which identify the point uniquely from the manifold - e.g. the questions are given by Q(x,y) = delta( (x,y) - (point_x, point_y) ) and the location of the point is the integral dx dy (x,y) * Q(x,y).

  10. - Top - End - #10
    Troll in the Playground
     
    Lvl 2 Expert's Avatar

    Join Date
    Oct 2014
    Location
    Tulips Cheese & Rock&Roll
    Gender
    Male

    Default Re: Finding a point in an infinite space

    I think Tyckspoon's method gets a bit better if you start using powers. Don't divide the grid into blocks one billion by one billion, but rather 9 zeroes by 9 zeroes. The number, assuming it was picked by a human, is likely to be relatively small, so it makes sense to have a finer search grid in the low numbers, and expand it from there.

    This is still not fast enough to find something like Graham's number (or rather the coordinate Graham's number by -(Grahams number/pi)^146-77854) on a human asking questions timescale, but at that point I think even the most elegant methods will struggle.
    Last edited by Lvl 2 Expert; 2019-04-07 at 03:16 AM.

  11. - Top - End - #11
    Troll in the Playground
    Join Date
    Jan 2007

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Lvl 2 Expert View Post
    I think Tyckspoon's method gets a bit better if you start using powers. Don't divide the grid into blocks one billion by one billion, but rather 9 zeroes by 9 zeroes. The number, assuming it was picked by a human, is likely to be relatively small, so it makes sense to have a finer search grid in the low numbers, and expand it from there.

    This is still not fast enough to find something like Graham's number (or rather the coordinate Graham's number by -(Grahams number/pi)^146-77854) on a human asking questions timescale, but at that point I think even the most elegant methods will struggle.
    Instead, project the infinite plane on a finite one using any bound analytic function like for example ArcTan. For whole numbers this should be as fast as warty goblin's algorithm, since it also uses splitting the plane in halves regarding the specific digits in binary representation.

    By using more general questions and slicing the scaled down infinite plane in a natural geometric way, one can approximate any sought number much faster and obtain any desired precision in finite time even if we consider any real number pairs. Cosidering how real numbers are constructed as a limit of rational sequences, we will also obtain exact result in countable infinite questions as well.
    Last edited by Radar; 2019-04-07 at 05:21 AM.
    In a war it doesn't matter who's right, only who's left.

  12. - Top - End - #12
    Bugbear in the Playground
     
    MindFlayer

    Join Date
    Feb 2015

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Radar View Post
    Instead, project the infinite plane on a finite one using any bound analytic function like for example ArcTan. For whole numbers this should be as fast as warty goblin's algorithm, since it also uses splitting the plane in halves regarding the specific digits in binary representation.

    By using more general questions and slicing the scaled down infinite plane in a natural geometric way, one can approximate any sought number much faster and obtain any desired precision in finite time even if we consider any real number pairs. Cosidering how real numbers are constructed as a limit of rational sequences, we will also obtain exact result in countable infinite questions as well.
    Let's be clear here though, the number of questions required to reach a desired precision (in the original infinite space) depends on the point being sought. You can't say, give me an epsilon, and I will give you an N that will work for all (x,y) points. After N questions there are some points that share all answers with points arbitrarily larger.

  13. - Top - End - #13
    Troll in the Playground
    Join Date
    Jan 2007

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by DavidSh View Post
    Let's be clear here though, the number of questions required to reach a desired precision (in the original infinite space) depends on the point being sought. You can't say, give me an epsilon, and I will give you an N that will work for all (x,y) points. After N questions there are some points that share all answers with points arbitrarily larger.
    That is true. Still for any given number x, the number of questions needed is of order Log(x).
    In a war it doesn't matter who's right, only who's left.

  14. - Top - End - #14
    Barbarian in the Playground
     
    PaladinGuy

    Join Date
    Sep 2016

    Default Re: Finding a point in an infinite space

    [Merging a couple of cases given above and hopefully being a bit more explicit. Radar pretty much said the first 2 paragraphs, while the uncountable case was mentioned by Davidsh ]

    For something like the integers. If you have an finite range (x), you are never going to get better than Log2(x) on average, as that differentiates at most x numbers. On the other hand you can get the exact number in Log2(x) via fairly trivial methods (binary chop)

    You can trivially get the upper bound for a number (y) in the same time by working upwards, if you use faster growing strategies you save time here, but then your upper bound is crazily high (and the lower bound crazily low), I suspect there are ways to optimize that.

    IIUC the binary expansion given by Warty Goblin didn't explicitly terminate, but actually that might be the most efficient way round. Explicitly asking if you finish will get you the number in exactly Log2(x) but if you use a probabilistic approach so you only ask after a suspicious amount of zeros you could probably get much closer to Log2(x).

    For a plane you can basically do the 2 co-ordinates separately. You could probably save some steps by finding the (approximate) hypotenuse and then the smallest co-ordinate.

    Fractions get a bit more awkward. Treating X/Y as X,Y will of course work, or alternatively (and possibly more elegantly) continuing the binonial chop the other way until it's confirmed as repeating. But it feels (as a non-serious-mathmo) ugly. In the integer case, the bigger number takes a little more time, but it's a much bigger number so you'd expect it too. Anything better than linear seems reasonable too me. In the fractions case between any two fractions, there will be a fraction that will take a (countably) infinite amount of time to resolve but is also infinitesimally close.

    Irrational numbers, even a countably-infinite number of separations leaves an uncountably-infinite set of numbers in at least one 'box'. You could get arbitrarily close by continuing binary chop.

    Fairly given computational numbers I think I'd do binary chop for a decent while, then see if I can recognize it (doing some unofficial questions of my own). If sqrt[2]+10-1000 is fair game then I don't see a sensible way out unless there are clear limits. [ETA revised credit statements, and also in this case I'd ask them to write it down in words then build up the sentence letter by letter-sorted!!

    [10th Edit, Warty Goblin's method does of course include a termination. But not in the bits he repeats :sillyme:
    Last edited by jayem; 2019-04-07 at 04:08 PM.

  15. - Top - End - #15
    Troll in the Playground
    Join Date
    Jan 2007

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by jayem View Post
    Irrational numbers, even a countably-infinite number of separations leaves an uncountably-infinite set of numbers in at least one 'box'. You could get arbitrarily close by continuing binary chop.
    Actually even in continuum interval (or plane - doesn't matter) you can get an exact number after countable infinity of binary chops, since this is a consequence of the very definition of real numbers - more specifically the construction from Cauchy sequences. Getting arbitrarily close after countable infinite steps becomes an exact solution.
    In a war it doesn't matter who's right, only who's left.

  16. - Top - End - #16
    Titan in the Playground
    Join Date
    Oct 2010
    Location
    Dallas, TX
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Radar View Post
    Actually even in continuum interval (or plane - doesn't matter) you can get an exact number after countable infinity of binary chops, since this is a consequence of the very definition of real numbers - more specifically the construction from Cauchy sequences. Getting arbitrarily close after countable infinite steps becomes an exact solution.
    Yes. Unfortunately, if each question takes finite time to ask and answer, there is no such thing as "after" a countably infinite number of steps.

  17. - Top - End - #17
    Dragon in the Playground Moderator
     
    Peelee's Avatar

    Join Date
    Dec 2009
    Location
    Washington D.C.
    Gender
    Male

    Default Re: Finding a point in an infinite space

    I set the origin at -X, -Y away from a chosen spot, declare that I have thus found the exact point required, and take the trophy (I assume there's a trophy involved) for finding it in 0 questions.
    Cuthalion's art is the prettiest art of all the art. Like my avatar.

    Number of times Roland St. Jude has sworn revenge upon me: 2

  18. - Top - End - #18
    Librarian in the Playground Moderator
     
    LibraryOgre's Avatar

    Join Date
    Dec 2007
    Location
    San Antonio, Texas
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by AvatarVecna View Post
    There is a plane where the X-axis goes from -∞ to ∞ and where the Y-axis goes from -∞ to ∞. You know that somewhere on the plane is a point whose X and Y values are both whole numbers. Your goal is to find this point, but you can only ask yes/no questions about the point; there's no limit on how many such questions you can ask, nor on the complexity of the questions, save that they must be answerable with a binary "yes" or "no" answer. Can you find the point, and if so what is your method?
    Quote Originally Posted by tyckspoon View Post
    Pretty easy; "is the y coordinate greater than 0?" Repeat for x. Now you know which quadrant it's in. Repeat basically the same questions, increase the number you ask about by.. Oh a billion or so until you get a broad zone to narrow into. There's probably a more efficient algorithm, but it's not hard to do.
    (emphasis added)
    We already know which quadrant it's in; they're whole numbers, so they must be a positive integer or 0. No other quadrant is possible, unless the OP is edited to say "the absolute value of their X and Y values are whole numbers."
    The Cranky Gamer
    *It isn't realism, it's verisimilitude; the appearance of truth within the framework of the game.
    *Picard management tip: Debate honestly. The goal is to arrive at the truth, not at your preconception.
    *Mutant Dawn for Savage Worlds!
    *The One Deck Engine: Gaming on a budget
    Written by Me on DriveThru RPG
    There are almost 400,000 threads on this site. If you need me to address a thread as a moderator, include a link.

  19. - Top - End - #19
    Troll in the Playground
     
    Lvl 2 Expert's Avatar

    Join Date
    Oct 2014
    Location
    Tulips Cheese & Rock&Roll
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Mark Hall View Post
    (emphasis added)
    We already know which quadrant it's in; they're whole numbers, so they must be a positive integer or 0. No other quadrant is possible, unless the OP is edited to say "the absolute value of their X and Y values are whole numbers."
    According to Wikipedia whole numbers are integers and can de negative. Natural numbers are the ones that must be positive.
    The Hindsight Awards, results: See the best movies of 1999!

  20. - Top - End - #20
    Firbolg in the Playground
     
    Bohandas's Avatar

    Join Date
    Feb 2016

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by AvatarVecna View Post
    That such a method can theoretically work for a vast number of points is obvious, but it runs into issues because of the nature of the infinite plane.
    If the potential number of questions is infinite as well most if not all of those issues should be negated in theory, shouldn't they?

    EDIT:
    Now that I think of it, maybe not. If the space is continuous then the number of points is uncountably infinite whereas the number of questions must be countably infinite. It should work in an infinite grid of integer coordinates though
    Last edited by Bohandas; 2019-04-10 at 11:41 AM.
    "If you want to understand biology don't think about vibrant throbbing gels and oozes, think about information technology" -Richard Dawkins

    Omegaupdate Forum

    WoTC Forums Archive + Indexing Projext

    PostImage, a free and sensible alternative to Photobucket

    Temple+ Modding Project for Atari's Temple of Elemental Evil

    Morrus' RPG Forum (EN World v2)

  21. - Top - End - #21
    Troll in the Playground
    Join Date
    Jan 2007

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Bohandas View Post
    If the potential number of questions is infinite as well most if not all of those issues should be negated in theory, shouldn't they?

    EDIT:
    Now that I think of it, maybe not. If the space is continuous then the number of points is uncountably infinite whereas the number of questions must be countably infinite. It should work in an infinite grid of integer coordinates though
    With countable infinity of questions one can still pinpoint a... well... point within the continuum. It is the basic concept behind the very construction of real numbers in the version by Cauchy where a real number is defined by a class of convergent sequences, which also are convergent if you essentially mix them up with each other.

    With the yes/no questions one finds and refines upper and lower bound for the sought number. Subsequent values of those bound form a sequence. Since we can assure that there is always a finite number of questions we need to make our precision arbitrarily good, then those upper and lower bound sequences converge to a single real number.
    In a war it doesn't matter who's right, only who's left.

  22. - Top - End - #22
    Bugbear in the Playground
    Join Date
    Sep 2014

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by jayem View Post
    For a plane you can basically do the 2 co-ordinates separately. You could probably save some steps by finding the (approximate) hypotenuse and then the smallest co-ordinate.
    Would that be equivalent to a graphical method where you start by asking if it's a solution to the inequality y>0 and then go on to define smaller and smaller regions using systems of inequalities? It seems like it would be simple to divide each existing half of the graph in half again using that sort of method and various y>mx type equations. This method seems interesting to me because your guessing keeps narrowing the search space while telling you very little about how far away either coordinate is from the origin (since we're only considering integers, we do gradually eliminate coordinates closer to the origin as no integer coordinates are found within that particular narrow slice).

  23. - Top - End - #23
    Titan in the Playground
    Join Date
    May 2007
    Location
    Tail of the Bellcurve
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Algeh View Post
    Would that be equivalent to a graphical method where you start by asking if it's a solution to the inequality y>0 and then go on to define smaller and smaller regions using systems of inequalities? It seems like it would be simple to divide each existing half of the graph in half again using that sort of method and various y>mx type equations. This method seems interesting to me because your guessing keeps narrowing the search space while telling you very little about how far away either coordinate is from the origin (since we're only considering integers, we do gradually eliminate coordinates closer to the origin as no integer coordinates are found within that particular narrow slice).
    I was thinking about methods like that, and how to extract information about the distance from the origin. An algorithm I had considered was something like this:

    1: wlog, assume the point is in the first quadrant, since it only takes two questions to determine this.
    2: ask if the point is above the line bisecting the quadrant. Regardless of the answer, you now have contained the point between two known rays at unknown distance. Call the lower ray r1 and the upper r2
    3: Ask if the point is contained in a triangle determined by r1,, r2, and a line defining an isosceles triangle defined by r1 and r2 with the congruent legs of length, say, k!, where k is the number of questions you have asked.
    4: If the answer is yes, exhaustively search the whole number pairs in the triangle.
    5: If no, return to step 2, and bisect the angle determined by r1 and r2.

    There's probably an additional way to make it clever, by trying to learn something about how far to jump, I just chose k! because it grows quite quickly, but it may be more efficient in some sense to pick a growth value that keeps the number of points in the triangle reasonably constant.
    Blood-red were his spurs i' the golden noon; wine-red 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.

  24. - Top - End - #24
    Ettin in the Playground
     
    georgie_leech's Avatar

    Join Date
    Sep 2011
    Location
    Calgary, AB
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Er, how exactly does one bisect an infinite plane?
    Quote Originally Posted by Grod_The_Giant View Post
    We should try to make that a thing; I think it might help civility. Hey, GitP, let's try to make this a thing: when you're arguing optimization strategies, RAW-logic, and similar such things that you'd never actually use in a game, tag your post [THEORETICAL] and/or use green text

  25. - Top - End - #25
    Orc in the Playground
     
    SwashbucklerGuy

    Join Date
    Aug 2011

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by georgie_leech View Post
    Er, how exactly does one bisect an infinite plane?
    Right down the middle.

    More seriously: what I think they're proposing is to ask if the point on the plane is above or below the line y=x. Let's assume its below y=x. Knowing this, we can form a triangle using y=x, the x axis (y=0), and the line y = -x + k!, where k is the number of iterations. Eventually the point will be contained by the triangle, and we can search the remaining space.

    It's essentially the same as asking about the sum of |x| and |y| to constrain both x and y within some search space at the same time.



    Since any number can be expressed through a unique prime factorization, another approach would be to ask about the prime factors of X and Y. From what I can tell from some back of the napkin scribbles, the best case could be reasonably fast, but the worst cases crawl to a snails pace.

    EDIT: I didn't actually answer the question.

    Bisecting an infinite plane is easy: any line on an infinite plane bisects that plane. If that sounds confusing, think of it this way: there is a one to one mapping for every point on one side of the line to a point on the other side (reflection over the line being the simplest mapping I can think of).
    Last edited by crayzz; 2019-04-10 at 10:55 PM.
    Quote Originally Posted by crayzz
    That a given person is known for his sex appeal does not mean that he is only known for his sex appeal.
    Quote Originally Posted by jere7my
    For instance, I am also known for my humility.

  26. - Top - End - #26
    Bugbear in the Playground
     
    Excession's Avatar

    Join Date
    Jun 2008
    Location
    New Zealand
    Gender
    Male

    Default Re: Finding a point in an infinite space

    The infinite 2D plane just complicates things. So get rid of that first. Draw a continuous square spiral starting at the origin:
    (0, 0)
    (1, 0)
    (1, 1)
    (0, 1)
    (-1, 1)
    (-1, 0)
    (-1, -1)
    (0, -1)
    (1, -1)
    (2, -1)
    etc.

    This line goes through all points (x, y) on the infinite plane, mapping them to position n an infinite line with n ≥ 0.

    From there the trick of asking for each binary digit of n is more obvious, and I don't see any way of making it faster.

    Edit: you can do this with a real number plane as well. Space-filling curves are a lot of fun. I think the step of asking for binary digits won't work the same for real numbers, as a finite irrational number will have an infinite number of digits after the decimal point, and no repeating pattern to them.
    Last edited by Excession; 2019-04-10 at 11:04 PM.

  27. - Top - End - #27
    Barbarian in the Playground
     
    PaladinGuy

    Join Date
    Sep 2016

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Algeh View Post
    Would that be equivalent to a graphical method where you start by asking if it's a solution to the inequality y>0 and then go on to define smaller and smaller regions using systems of inequalities? It seems like it would be simple to divide each existing half of the graph in half again using that sort of method and various y>mx type equations. This method seems interesting to me because your guessing keeps narrowing the search space while telling you very little about how far away either coordinate is from the origin (since we're only considering integers, we do gradually eliminate coordinates closer to the origin as no integer coordinates are found within that particular narrow slice).
    I think so, but I did it the other way round.

    This I think has the potential to save some steps. Rather than having to do 2 rangefinder operations you only have to do 1.
    So using doubling the descartes method takes log(X)+log(X)+log(Y)+log(Y) steps whereas the polar method takes about log(1.4*X)+log(1.4*X)+log(1.4*2P*X)

    If X is about the same as Y you get 4 log(X) against 3 log(X) +C . (If Y is negligible you get 2 log (X) against 3 log(X) so it does lose out on the extreme edges)
    However I think you can do rangefinding a bit better than that.

    I think my way round (distance first) is slightly better than angle first as when you know the distance you know how many points are in the ring/diamond so you know when to stop (although alternating would be quite possible). I think to get the binary places to use diophantime equations would require as many steps as it saves.

    The space filling curve looks like it may be even better to me than that, at first thought. Again you get the single range.

  28. - Top - End - #28
    Librarian in the Playground Moderator
     
    LibraryOgre's Avatar

    Join Date
    Dec 2007
    Location
    San Antonio, Texas
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by georgie_leech View Post
    Er, how exactly does one bisect an infinite plane?
    You get arbitrary.... sort of like Star Trek, actually.

    The Terran System is Sector 001. There's no particular REASON for it to be 001; if they started at the galactic core, our sector would be far higher. But, they picked an arbitrary point (where they were standing) and declared that to be the center of their coordinate grid.

    If I say "This point I occupy is 0,0,0 on an xyz coordinate space, pointing to X, Y, and Z, and defining the length of an integer of distance in that space, I can then define other objects in that X,Y,Z space, regardless of any other arbitrary system. My coworker's chair is 2,0,0, since it is 2 meters ahead of me, and neither right nor left nor above or below me. It is a purely relational statement... but if you're looking for a point in space, you've at least cut the infinity you had to search into 8, smaller, infinities.
    The Cranky Gamer
    *It isn't realism, it's verisimilitude; the appearance of truth within the framework of the game.
    *Picard management tip: Debate honestly. The goal is to arrive at the truth, not at your preconception.
    *Mutant Dawn for Savage Worlds!
    *The One Deck Engine: Gaming on a budget
    Written by Me on DriveThru RPG
    There are almost 400,000 threads on this site. If you need me to address a thread as a moderator, include a link.

  29. - Top - End - #29
    Ettin in the Playground
     
    georgie_leech's Avatar

    Join Date
    Sep 2011
    Location
    Calgary, AB
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Mark Hall View Post
    You get arbitrary.... sort of like Star Trek, actually.

    The Terran System is Sector 001. There's no particular REASON for it to be 001; if they started at the galactic core, our sector would be far higher. But, they picked an arbitrary point (where they were standing) and declared that to be the center of their coordinate grid.

    If I say "This point I occupy is 0,0,0 on an xyz coordinate space, pointing to X, Y, and Z, and defining the length of an integer of distance in that space, I can then define other objects in that X,Y,Z space, regardless of any other arbitrary system. My coworker's chair is 2,0,0, since it is 2 meters ahead of me, and neither right nor left nor above or below me. It is a purely relational statement... but if you're looking for a point in space, you've at least cut the infinity you had to search into 8, smaller, infinities.
    But you'very already done that with the origin though, no? After narrowing it down to one of the 4 regular quadrants, you've effectively set boundaries that prevent proper bisecting. There will always be more of the infinite plane on the side opposite your line, so it's not halving anything, so much as dividing an area into 2 arbitrary pieces.
    Last edited by georgie_leech; 2019-04-11 at 10:31 AM.
    Quote Originally Posted by Grod_The_Giant View Post
    We should try to make that a thing; I think it might help civility. Hey, GitP, let's try to make this a thing: when you're arguing optimization strategies, RAW-logic, and similar such things that you'd never actually use in a game, tag your post [THEORETICAL] and/or use green text

  30. - Top - End - #30
    Librarian in the Playground Moderator
     
    LibraryOgre's Avatar

    Join Date
    Dec 2007
    Location
    San Antonio, Texas
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by georgie_leech View Post
    But you'very already done that with the origin though, no? After narrowing it down to one of the 4 regular quadrants, you've effectively set boundaries that prevent proper bisecting. There will always be more of the infinite plane on the side opposite your line, so it's not halving anything, so much as dividing an area into 2 arbitrary pieces.
    Setting that initial quadrant boundary is your act of bisecting infinity. You get one.

    After that, you have to sound things out, with "Is [x,y,z] less n", per the OP's "Infinite Yes/No questions"
    The Cranky Gamer
    *It isn't realism, it's verisimilitude; the appearance of truth within the framework of the game.
    *Picard management tip: Debate honestly. The goal is to arrive at the truth, not at your preconception.
    *Mutant Dawn for Savage Worlds!
    *The One Deck Engine: Gaming on a budget
    Written by Me on DriveThru RPG
    There are almost 400,000 threads on this site. If you need me to address a thread as a moderator, include a link.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •