The Order of the Stick: Utterly Dwarfed
The Order of the Stick: Utterly Dwarfed - Coming in December and available for pre-order now
Page 2 of 3 FirstFirst 123 LastLast
Results 31 to 60 of 79
  1. - Top - End - #31
    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
    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.
    Y = X bisects 2 of the quadrants, Y = -X bisects the other 2.
    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.

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

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by crayzz View Post
    Y = X bisects 2 of the quadrants, Y = -X bisects the other 2.
    And then that can in turn be extended with further similar lines to bisect the plane in a new way that narrows your search space from an 8th to a 16th, and so on. It'd probably be easiest to specify where the lines should be using radians, since that system is basically set up to divide circles up nicely, but it could be done with slopes and lines of the form y=mx as well. (All of those would pass through the origin, and you just keep adjusting your m to get the new slopes at the different angles.)

    The first few steps of the algorithm would be:

    Is the point a solution to x>0? (this answer determines if it's in combined Q1 and Q4, or combined Q2 and Q3)

    Is the point a solution to y>0? (this answer determines if it's in combined Q1 and Q2, or combined Q3 and Q4)

    At this point, we know which quadrant it's in. Then ask if it's a solution to y>x (if it's determined to be in Q1 or Q3) or y>-x (if it's in Q2 or Q4). You've now narrowed it down to an 8th of the space, or half a quadrant.

    Then ask about the similarly appropriate y>mx to bisect your 8th to get a 16th, and so on.

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

    Join Date
    Apr 2008
    Location
    Germany
    Gender
    Male

    Default Re: Finding a point in an infinite space

    I think the 'half your search area' part is pretty easy / obvious, but how do you continue afterwards? How do you find the distance systematically?

    (also, depending on how you phrase your questions, you may run into a problem this way, because at some point you want to know if it's on the line or in a sector)
    "What's done is done."

    Pony Avatar thanks to Elemental

  4. - Top - End - #34
    Troll in the Playground
     
    Griffon

    Join Date
    Jun 2013
    Location
    Bristol, UK

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Algeh View Post
    And then that can in turn be extended with further similar lines to bisect the plane in a new way that narrows your search space from an 8th to a 16th, and so on. It'd probably be easiest to specify where the lines should be using radians, since that system is basically set up to divide circles up nicely, but it could be done with slopes and lines of the form y=mx as well. (All of those would pass through the origin, and you just keep adjusting your m to get the new slopes at the different angles.)

    The first few steps of the algorithm would be:

    Is the point a solution to x>0? (this answer determines if it's in combined Q1 and Q4, or combined Q2 and Q3)

    Is the point a solution to y>0? (this answer determines if it's in combined Q1 and Q2, or combined Q3 and Q4)

    At this point, we know which quadrant it's in. Then ask if it's a solution to y>x (if it's determined to be in Q1 or Q3) or y>-x (if it's in Q2 or Q4). You've now narrowed it down to an 8th of the space, or half a quadrant.

    Then ask about the similarly appropriate y>mx to bisect your 8th to get a 16th, and so on.
    Yeah, and that is sort of good and not obvious either, but it still leaves you with an infinitly long line to find the point along, and the far end doesn't reduce to a line before you reach infinite accuracy in rotation.
    The end of what Son? The story? There is no end. There's just the point where the storytellers stop talking.

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

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by halfeye View Post
    Yeah, and that is sort of good and not obvious either, but it still leaves you with an infinitly long line to find the point along, and the far end doesn't reduce to a line before you reach infinite accuracy in rotation.
    Radius value you can search for in the same manner:

    1. Is x^2+y^2<r^2?
    If yes, then you have an upper bound and can bisect to get the exact result.
    If not, increase r and repeat until yes. Then the last and second to last r gives upper and lower bounds, so you can continue with bisection.

    Mix those questions with those concerning asimuth and it will be a fully fuctional algorithm, which for any finite (x,y) will give the sought point with arbitrary precision with finite number of questions. For integer pairs it will find the exact number in finite time, while for real number pairs it will require countable infinity of questions to be exact.

    I am not sure, which radius incrementation method would be optimal, but I would guess exponential. Anything faster would leave a much larger area to search through once you have the upper bound while anything slower will take way more questions to reach upper bound.
    In a war it doesn't matter who's right, only who's left.

  6. - Top - End - #36
    Barbarian in the Playground
     
    Caerulea's Avatar

    Join Date
    Aug 2018
    Location
    Sleeping in a paper bag.

    Default Re: Finding a point in an infinite space

    Warty Goblin's method also "bisects" the space of possible answers, in the sense that after each question the possible number of solutions is halved. (His method was asking if successive digits in the binary representation of each number are 0 or 1.) I don't believe it works for continuous spaces though. (Maybe one could add a step checking whether the number was less than a particular power of two, and then go to successively more precise digits?)

    —Caerulea
    Last edited by Caerulea; 2019-04-11 at 03:30 PM.
    Non caerulea sum, Caerulea nomen meus est.
    Extended Signature.
    I'm not a humanoid. Come not be one too.

  7. - Top - End - #37
    Barbarian in the Playground
     
    JCarter426's Avatar

    Join Date
    Feb 2012
    Location
    Boston, MA
    Gender
    Male

    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?
    I don't know if you can have an uncountably infinite number of questions. It seems like the set would inherently be countable because you can say this is the first question, this is the second question, etc... and thus count them. Of course if you need any sort of infinity to answer the question, you're going to have problems answering it in the real world.

    If you wanted to generalize the question for all numbers and be able to answer it realistically - i.e. without any sort of infinity - then I think you'd have to rephrase the question. Say, you aren't given an infinite amount of questions, but you also don't have to give all the digits, just enough for whatever degree of precision is specified. Like how we don't know all the digits of π but we can calculate it to whatever precision is required, given enough time.

    So the problem instead is to determine x and y to n decimal places, given a finite amount of questions (however many you want, but not infinite). Can that be done for all numbers?

    In that case, the answer is most certainly no, you can't do this for all numbers. You could do it for approximately 0% of numbers in existence. That's basically the definition of computable numbers, so of course it wouldn't work for uncomputable numbers, and most numbers are uncomputable.

    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
    The set of irrationals is uncountably infinite, but the amount of digits in an irrational number is countably infinite. So you can still brute force the problem by asking questions until each digit is known with only a countable amount of questions.

  8. - Top - End - #38
    Titan in the Playground
     
    Lizardfolk

    Join Date
    Oct 2010
    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?
    "Has the number ever been seen by a human before?" If yes the questions are now finite. If no begin infinite questions.
    Quote Originally Posted by The Glyphstone View Post
    Vibranium: If it was on the periodic table, its chemical symbol would be "Bs".

  9. - Top - End - #39
    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

    Quote Originally Posted by Caerulea View Post
    Warty Goblin's method also "bisects" the space of possible answers, in the sense that after each question the possible number of solutions is halved. (His method was asking if successive digits in the binary representation of each number are 0 or 1.) I don't believe it works for continuous spaces though. (Maybe one could add a step checking whether the number was less than a particular power of two, and then go to successively more precise digits?)

    —Caerulea
    For continuous spaces you can still reduce to a single number with a space-filling curve, then use a binary search between two whole numbers, but you will need an infinite number of questions to find an irrational number than way.

    Edit: finding a rational number is actually the same problem, you're just looking for (x/y) rather than (x, y).

    Quote Originally Posted by Tvtyrant View Post
    "Has the number ever been seen by a human before?" If yes the questions are now finite. If no begin infinite questions.
    If you know the number is finite, and that is implied by it being a number, you don't need infinite questions. If nothing else you can just ask "is it 0?", "is it 1?" and so on. Number of questions equal to the number, so still finite.
    Last edited by Excession; 2019-04-11 at 05:27 PM.

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

    Join Date
    Dec 2009
    Location
    Birmingham, AL
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Tvtyrant View Post
    "Has the number ever been seen by a human before?" If yes the questions are now finite. If no begin infinite questions.
    Well, there's a 1/∞ chance the answer will be yes, so....
    The Mod on the Silver Mountain avatar by the wonderfully talented Cuthalion!

    Quote Originally Posted by Heksefatter View Post
    All hail the dragon.

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

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by JCarter426 View Post
    So the problem instead is to determine x and y to n decimal places, given a finite amount of questions (however many you want, but not infinite). Can that be done for all numbers?

    In that case, the answer is most certainly no, you can't do this for all numbers. You could do it for approximately 0% of numbers in existence. That's basically the definition of computable numbers, so of course it wouldn't work for uncomputable numbers, and most numbers are uncomputable.


    The set of irrationals is uncountably infinite, but the amount of digits in an irrational number is countably infinite. So you can still brute force the problem by asking questions until each digit is known with only a countable amount of questions.
    You are actually disproving the point you make in the second paragraph with what you plainly state in the last one. Since one only needs countable infinity of questions to obtain any irrational number exactly, then getting just any finite number of digits will require finite amount of questions.

    In other words, if you prescribe a given precision p, you silce the whole plane into p by p squares. Since you have countable infinity of such squares and the problem is simplified to just finding the right square, then with finite amount of questions you will always reach the target.

    edit:
    Quote Originally Posted by Caerulea View Post
    Warty Goblin's method also "bisects" the space of possible answers, in the sense that after each question the possible number of solutions is halved. (His method was asking if successive digits in the binary representation of each number are 0 or 1.) I don't believe it works for continuous spaces though. (Maybe one could add a step checking whether the number was less than a particular power of two, and then go to successively more precise digits?)

    —Caerulea
    Warty Goblin's method does bisect the the plane every time and you can easily extend it, so it would work for continuum simply by asking not just about higher digits but the fracions as well. The only thing it does not do is to give a good approximation until it obtains the highest digit.
    Last edited by Radar; 2019-04-11 at 06:40 PM.
    In a war it doesn't matter who's right, only who's left.

  12. - Top - End - #42
    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 Radar View Post
    Warty Goblin's method does bisect the the plane every time and you can easily extend it, so it would work for continuum simply by asking not just about higher digits but the fracions as well. The only thing it does not do is to give a good approximation until it obtains the highest digit.
    Unless you run it backwards, and start by asking about the leading term of the binary representation of each coordinate. Only real change is asking whether the digit you just determined was the last before the decimal or not, instead of whether it's the last digit.
    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.

  13. - Top - End - #43
    Barbarian in the Playground
     
    JCarter426's Avatar

    Join Date
    Feb 2012
    Location
    Boston, MA
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Radar View Post
    You are actually disproving the point you make in the second paragraph with what you plainly state in the last one. Since one only needs countable infinity of questions to obtain any irrational number exactly, then getting just any finite number of digits will require finite amount of questions.
    Hrm, that depends on whether an answer with a finite amount of digits - a decimal approximation - is counted as a correct answer. Yes, I suppose if you accept a finite amount of digits as a valid response, then we're back in the realm of rational numbers, so of course you only need a finite amount of questions. But a decimal approximation isn't exactly the same number, is it? That's not the case for any irrational numbers, or even many rational ones in base 10. So the issue, I think, is that the person asking the question magically knows all the digits and is able to check them to decide whether our approximation should count... which is all certainly impossible. So my rephrasing of the question is still not a remotely realistic scenario, sorry.
    Last edited by JCarter426; 2019-04-11 at 10:49 PM.

  14. - Top - End - #44
    Orc in the Playground
     
    SwashbucklerGuy

    Join Date
    Aug 2011

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Radar View Post
    In other words, if you prescribe a given precision p, you silce the whole plane into p by p squares. Since you have countable infinity of such squares and the problem is simplified to just finding the right square, then with finite amount of questions you will always reach the target.
    I think this is a misunderstanding of infinity. Yeah, we can describe numbers, even irrational and transcendental ones, through countably infinite steps, but you won't actually reach the target. If it takes countably infinity steps, by definition you do not get to reach the target.

    Think of it this way: a lot of the methods suggested can only ever produce a rational number; some are worse and can only produce a decimal/binary number. Such a method could never reach an irrational or transcendental number. It could get close, as close as you want. But they necessarily can not reach the target.

    EDIT:

    We can reach the target in the same sense that we can calculate pi or describe 1/3 in decimal notation, which is to say we can't.

    In that case, the answer is most certainly no, you can't do this for all numbers. You could do it for approximately 0% of numbers in existence. That's basically the definition of computable numbers, so of course it wouldn't work for uncomputable numbers, and most numbers are uncomputable.
    I don't think Non-computability is the problem here. We don't have a function describing the number, we just magically get answers on yes/no questions about the number. Even if the number was non computable, as long as it has some magnitude, we could still narrow in on it.
    Last edited by crayzz; 2019-04-11 at 09:58 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.

  15. - Top - End - #45
    Barbarian in the Playground
     
    JCarter426's Avatar

    Join Date
    Feb 2012
    Location
    Boston, MA
    Gender
    Male

    Default Re: Finding a point in an infinite space

    I think we just proved uncomputable numbers don't exist in this hypothetical scenario, because there always exists a series of yes or no questions that we can ask our magic all-knowing questioner to compute any number to any degree of precision.

  16. - Top - End - #46
    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

    Quote Originally Posted by JCarter426 View Post
    I think we just proved uncomputable numbers don't exist in this hypothetical scenario, because there always exists a series of yes or no questions that we can ask our magic all-knowing questioner to compute any number to any degree of precision.
    I don't agree, because even an arbitrarily precise approximation isn't the actual number. Getting the exact irrational number would require infinite time, which I think doesn't match the definition of "computable".

    With the original question though, when it's only whole numbers, all possible numbers can be found. No questions of precision needed.
    Last edited by Excession; 2019-04-11 at 10:30 PM.

  17. - Top - End - #47
    Orc in the Playground
     
    SwashbucklerGuy

    Join Date
    Aug 2011

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by JCarter426 View Post
    I think we just proved uncomputable numbers don't exist in this hypothetical scenario, because there always exists a series of yes or no questions that we can ask our magic all-knowing questioner to compute any number to any degree of precision.
    Which is another way of saying this scenario could never exist.

    Which, I mean: that's obvious, but it's kinda neat stumbling over an actual proof for it.

    I don't agree, because even an arbitrarily precise approximation isn't the actual number. Getting the exact irrational number would require infinite time, which I think doesn't match the definition of "computable".
    It does match. Computability means being able to calculate an arbitrary digit of the decimal expansion. We can do this for numbers like sqrt(2), pi, e, and other constructed transcendentals. There are numbers we can't do this for, and a lot of them involve elements of randomness.
    Last edited by crayzz; 2019-04-11 at 10:44 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.

  18. - Top - End - #48
    Barbarian in the Playground
     
    JCarter426's Avatar

    Join Date
    Feb 2012
    Location
    Boston, MA
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Excession View Post
    I don't agree, because even an arbitrarily precise approximation isn't the actual number. Getting the exact irrational number would require infinite time, which I think doesn't match the definition of "computable".
    The definition of computable:
    Quote Originally Posted by Wolfram
    A number which can be computed to any number of digits desired by a Turing machine.
    That means a finite number of digits is fine.

    The issue isn't an infinite amount of digits - not all irrational numbers are uncomputable, and actually all the ones we know are computable. The issue is whether a finite process can determine what those digits are.

    A number like π is irrational and transcendental but still computable. We can take the ratio of a circle's circumference to its diameter to determine the value to whatever degree of precision we want. That's a finite amount of steps that can give us the number to whatever decimal place we want. In that sense it is computable.

    An uncomputable number is one for which no such process exists. You'd truly need an infinite amount of steps to determine the digits. Which is exactly what an unlimited series of yes/no guesses gives you, provided that somebody magically knows the answer already.

    Quote Originally Posted by crayzz View Post
    Which is another way of saying this scenario could never exist.

    Which, I mean: that's obvious, but it's kinda neat stumbling over an actual proof for it.
    Indeed.
    Last edited by JCarter426; 2019-04-11 at 10:55 PM.

  19. - Top - End - #49
    Barbarian in the Playground
     
    Caerulea's Avatar

    Join Date
    Aug 2018
    Location
    Sleeping in a paper bag.

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by crayzz View Post
    Think of it this way: a lot of the methods suggested can only ever produce a rational number; some are worse and can only produce a decimal/binary number. Such a method could never reach an irrational or transcendental number. It could get close, as close as you want. But they necessarily can not reach the target.
    These methods are not actually less powerful. The method that could determine a binary representation of the number, could determine a binary representation of anything. For instance, the binary encoding of any rational number, assuming there exists a way to uniquely encode rational numbers in binary, which there does.

    I think there is a misunderstanding with regards to countable infinity. Just because there are countably infinite steps does not mean that it is impossible, because time doesn't matter in this hypothetical scenario. Each step might be evaluated on a magical device so that it takes no time. Then we would arrive at an answer. The answer would have infinite information, but it would still be an answer. We can represent 1/3 in decimal notation, it is a 0.3 followed by infinite 3s. Just because actually writing it out would be impossible does not mean it doesn't exist, and neither does it not exist because there are infinite digits (side note, 2 has infinite digits in its decimal representation. It just so happens that most of them are 0). Numbers are not a process.

    Even if the algorithm did not take 0 seconds, it could still be completed in finite time. What if each successive step was executed twice as fast, and the first took 1 minute. Then the entire process would take 2 minutes.

    The point is, with a countably number of steps and an omniscient oracle, you can determine exactly a number so long as the steps take a finite amount of time in sum.

    —Caerulea
    Last edited by Caerulea; 2019-04-11 at 10:46 PM.
    Non caerulea sum, Caerulea nomen meus est.
    Extended Signature.
    I'm not a humanoid. Come not be one too.

  20. - Top - End - #50
    Orc in the Playground
     
    SwashbucklerGuy

    Join Date
    Aug 2011

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Caerulea View Post
    These methods are not actually less powerful. The method that could determine a binary representation of the number, could determine a binary representation of anything. For instance, the binary encoding of any rational number, assuming there exists a way to uniquely encode rational numbers in binary, which there does.

    I think there is a misunderstanding with regards to countable infinity. Just because there are countably infinite steps does not mean that it is impossible, because time doesn't matter in this hypothetical scenario. Each step might be evaluated on a magical device so that it takes no time. Then we would arrive at an answer. The answer would have infinite information, but it would still be an answer. We can represent 1/3 in decimal notation, it is a 0.3 followed by infinite 3s. Just because actually writing it out would be impossible does not mean it doesn't exist, and neither does it not exist because there are infinite digits (side note, 2 has infinite digits in its decimal representation. It just so happens that most of them are 0). Numbers are not a process.

    Even if the algorithm did not take 0 seconds, it could still be completed in finite time. What if each successive step was executed twice as fast, and the first took 1 minute. Then the entire process would take 2 minutes.

    The point is, with a countably number of steps and an omniscient oracle, you can determine exactly a number so long as the steps take a finite amount of time in sum.

    —Caerulea
    I shouldn't have said we can't describe 1/3 in decimal notation, since we have an actual notation for repeating decimals. But it is true that a algorithm that can only produce decimal numbers will never spit out 1/3.

    And that's exactly the point I was trying to argue against! If your algorithm can only produce a certain type of number, you can't get outside that type of number no matter what. Proposing countably infinite steps in finite time sounds nice, but I don't think it actually works. It violates what we know about computation for one thing. A turing machine of a given complexity will either halt or loop forever: you don't get to have it halt after infinite steps.

    This, incidentally, brings up a practical concern with actually implementing the algorithm even in the integer case: without knowing how big the number actually is, we can't know that we've chosen a turing machine "large" enough to handle it. But setting that aside, no turing machine could ever compute a transcendental number to exact precision, or an uncomputable number to even arbitary precision.
    Last edited by crayzz; 2019-04-11 at 11:02 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.

  21. - Top - End - #51
    Ogre 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

    As elegant as Warty's method is, it seems you need less questions if you use a larger numerical system. That's because for every time you ask "is the next digit 1?" you also have to ask "is there a digit after this?" you're distinguishing between three states for each digit, 1, 0 and not there, lowering efficiency.

    If you use for instance hexadecimal notation things get better. A hexadecimal digit represents 4 bits, and you can pin down the value of a hexadecimal digit in 4 questions (1-8, 1-4, 1-2, 1), but you only need a single questin after that to ask about the next digit.

    This means it becomes even more efficient when you take things a full byte at a time, or some even larger number. You could also try working with a notation system one short of the round numbers. "In a pentadecimal system, is the next digit between 8 and 15 or non-existent?" (If we start counting question length for efficiency this is going to kill it.)

    But I feel like there should be a cleverer way to get rid of those extra questions...
    The ultimate OOTS cookie cutter nameless soldier is the hobgoblin.

  22. - Top - End - #52
    Troll in the Playground
     
    tonberrian's Avatar

    Join Date
    Aug 2008
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Lvl 2 Expert View Post
    As elegant as Warty's method is, it seems you need less questions if you use a larger numerical system. That's because for every time you ask "is the next digit 1?" you also have to ask "is there a digit after this?" you're distinguishing between three states for each digit, 1, 0 and not there, lowering efficiency.

    If you use for instance hexadecimal notation things get better. A hexadecimal digit represents 4 bits, and you can pin down the value of a hexadecimal digit in 4 questions (1-8, 1-4, 1-2, 1), but you only need a single questin after that to ask about the next digit.

    This means it becomes even more efficient when you take things a full byte at a time, or some even larger number. You could also try working with a notation system one short of the round numbers. "In a pentadecimal system, is the next digit between 8 and 15 or non-existent?" (If we start counting question length for efficiency this is going to kill it.)

    But I feel like there should be a cleverer way to get rid of those extra questions...
    You always have a next digit. 1.0 and 1.00 are equivalent, etc.
    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.

  23. - Top - End - #53
    Ogre 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 tonberrian View Post
    You always have a next digit. 1.0 and 1.00 are equivalent, etc.
    They're all whole numbers, I assumed there were no decimal points, because why else tell us they're all whole numbers?
    The ultimate OOTS cookie cutter nameless soldier is the hobgoblin.

  24. - Top - End - #54
    Barbarian in the Playground
     
    PaladinGuy

    Join Date
    Sep 2016

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Lvl 2 Expert View Post
    As elegant as Warty's method is, it seems you need less questions if you use a larger numerical system. That's because for every time you ask "is the next digit 1?" you also have to ask "is there a digit after this?" you're distinguishing between three states for each digit, 1, 0 and not there, lowering efficiency.

    If you use for instance hexadecimal notation things get better. A hexadecimal digit represents 4 bits, and you can pin down the value of a hexadecimal digit in 4 questions (1-8, 1-4, 1-2, 1), but you only need a single question after that to ask about the next digit.

    This means it becomes even more efficient when you take things a full byte at a time, or some even larger number. You could also try working with a notation system one short of the round numbers. "In a pentadecimal system, is the next digit between 8 and 15 or non-existent?" (If we start counting question length for efficiency this is going to kill it.)

    But I feel like there should be a cleverer way to get rid of those extra questions...
    In Hex, the 4 questions you need to ask are basically equivalent to 4 "is the next bit" questions (except in reverse in your example). So it's basically the same as only asking every 4 bits. Which does make a lot of sense (I'd make it probabilistic, you only ask after an appropriate number of zeros).

    The Penta-decimal system is interesting.
    Alternatively once we stop to ask the question, we could also pick up on other short cuts. Finding the number of consecutive 1s and 0s will be quicker in some cases.

    *For non-existent read are all digits above this point zero.

    Regardless at worst for the integers (if they plan to use the number to full accuracy in any way), we can find it almost as easily as they can use it for size comparisons.
    Which I think counts for finding a number on a plane.

  25. - Top - End - #55
    Titan in the Playground
     
    Kato's Avatar

    Join Date
    Apr 2008
    Location
    Germany
    Gender
    Male

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Lvl 2 Expert View Post
    As elegant as Warty's method is, it seems you need less questions if you use a larger numerical system. That's because for every time you ask "is the next digit 1?" you also have to ask "is there a digit after this?" you're distinguishing between three states for each digit, 1, 0 and not there, lowering efficiency.
    Hm... Good point. Though 'not there isn't really a state, but you could add as many zeroes as necessary in front, even though it's highly unusual (1010 is as correct as 0001010 in theory, no?)

    Since we're limited to whole numbers, how efficient would be asking for divisibility? Is it divisible by 2 / 3/ 4... Skipping obviously wrong questions. (which is mostly just a way to get the binary approach to normal numbers) Is it much worse than other techniques?
    "What's done is done."

    Pony Avatar thanks to Elemental

  26. - Top - End - #56
    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

    Quote Originally Posted by crayzz View Post
    It does match. Computability means being able to calculate an arbitrary digit of the decimal expansion. We can do this for numbers like sqrt(2), pi, e, and other constructed transcendentals. There are numbers we can't do this for, and a lot of them involve elements of randomness.
    Ah, thanks. I guess it's been I while since I studied this stuff properly.

    Quote Originally Posted by tonberrian View Post
    You always have a next digit. 1.0 and 1.00 are equivalent, etc.
    For the binary digit version on real numbers, you would have to ask if the digits repeated, then narrow down the length of the repeat, and "1.00000..." is just a trivial case of that.
    Last edited by Excession; 2019-04-12 at 02:27 AM.

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

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by crayzz View Post
    I think this is a misunderstanding of infinity. Yeah, we can describe numbers, even irrational and transcendental ones, through countably infinite steps, but you won't actually reach the target. If it takes countably infinity steps, by definition you do not get to reach the target.

    Think of it this way: a lot of the methods suggested can only ever produce a rational number; some are worse and can only produce a decimal/binary number. Such a method could never reach an irrational or transcendental number. It could get close, as close as you want. But they necessarily can not reach the target.

    EDIT:

    We can reach the target in the same sense that we can calculate pi or describe 1/3 in decimal notation, which is to say we can't.
    Considering that the proposed problem allows infinite amount of questions as a valid solution then we actually do reach the sought number in the limit. Being infinitely close is the same as reaching the target as for example 1=0.9999999... by the very definition of real numbers. It would stop being true if we extended real numbers with infinitesimals, but it is not the case.

    Besides, the part you quoted concerns finite precision search, which boils down to searching for a pair of intigers and those can be always found with finite amount of questions, since they are countable.
    In a war it doesn't matter who's right, only who's left.

  28. - Top - End - #58
    Titan in the Playground
     
    Knaight's Avatar

    Join Date
    Aug 2008

    Default Re: Finding a point in an infinite space

    The whole tangent on finite sums of infinite series is irrelevant anyways - the numbers must be finite in a discrete space, which means the number of steps must be finite. As for an algorithm I'd take a page from various numerical methods. Specifically.
    1) Establish quadrant/origin (is X>0, is X<0, repeat for Y).
    2) Methodically use an open search method. I'd probably just use logarithms, sequentially asking is X >10, is X >100, >1000, >10000, etc. You could also do something like use Knuth up arrow notation to start with, for much larger steps.
    3) Once that hits I switch to a bisection search. As an example if I know it's between 10000 and 100000 I'd ask if X>55000. If I get another yes, is X>77500. Repeat until you find the number. I could also use a golden section search, which is theoretically faster, but whatever.
    4) Repeat steps 2 and 3 for Y.

    This should be faster than Warty's method. It can also be combined with Warty's method (e.g. using a base 1024 system and going digit by digit asking if it is greater than 513, then bisecting as needed. It gets the number of digits before the decimal pretty rapidly, then closes in O(log(n)) time. This also works with any arbitrary space that has the singular point, not just a plane.
    Last edited by Knaight; 2019-04-12 at 05:22 AM.
    I would really like to see a game made by Obryn, Kurald Galain, and Knaight from these forums.

    I'm not joking one bit. I would buy the hell out of that.
    -- ChubbyRain

    Current Design Project: Legacy, a game of masters and apprentices for two players and a GM.

  29. - Top - End - #59
    Barbarian in the Playground
     
    Caerulea's Avatar

    Join Date
    Aug 2018
    Location
    Sleeping in a paper bag.

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Kato View Post
    Since we're limited to whole numbers, how efficient would be asking for divisibility? Is it divisible by 2 / 3/ 4... Skipping obviously wrong questions. (which is mostly just a way to get the binary approach to normal numbers) Is it much worse than other techniques?
    I think prime numbers would be best if you are looking at factors. Maybe something like:
    1. Is the number divisible by prime p?
    2. If Yes: store p and ask about two again, If no:
    3. Is the next prime large than the number? If so: break. (There is probably a smaller end condition that could be used).
    4. Is the number divisible by the next prime? Goto step 2


    It takes iterations equal to amount of the number's prime factors + the number of primes less than the number that are not prime factors.

    —Caerulea
    Non caerulea sum, Caerulea nomen meus est.
    Extended Signature.
    I'm not a humanoid. Come not be one too.

  30. - Top - End - #60
    Titan in the Playground
     
    Knaight's Avatar

    Join Date
    Aug 2008

    Default Re: Finding a point in an infinite space

    Quote Originally Posted by Caerulea View Post
    I think prime numbers would be best if you are looking at factors. Maybe something like:
    1. Is the number divisible by prime p?
    2. If Yes: store p and ask about two again, If no:
    3. Is the next prime large than the number? If so: break. (There is probably a smaller end condition that could be used).
    4. Is the number divisible by the next prime? Goto step 2


    It takes iterations equal to amount of the number's prime factors + the number of primes less than the number that are not prime factors.

    —Caerulea
    I like it - if it's prime you'll get there eventually, if not you'll find factors well before getting there. That said this could use some modifications - whenever you find p checking p^k for k = 2, 3, 4, 5, .....
    I would really like to see a game made by Obryn, Kurald Galain, and Knaight from these forums.

    I'm not joking one bit. I would buy the hell out of that.
    -- ChubbyRain

    Current Design Project: Legacy, a game of masters and apprentices for two players and a GM.

Posting Permissions

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