INT Function
Moderators: gmalivuk, Moderators General, Prelates
INT Function
I'm thinking of a real number x.
Is there a procedure/program that given x as an input, can perform a finite series of arithmetic operations (addition, subtraction, multiplication, division) and simple comparison operations ( =, <, >) on x to determine whether or not x is an integer?
After thinking about this for a bit, it seems to me that there isn't. And for some reason, I find that startling...
Is there a procedure/program that given x as an input, can perform a finite series of arithmetic operations (addition, subtraction, multiplication, division) and simple comparison operations ( =, <, >) on x to determine whether or not x is an integer?
After thinking about this for a bit, it seems to me that there isn't. And for some reason, I find that startling...
Life is mostly plan "B"
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: INT Function
Code: Select all
if x > 0:
while x >0:
x = 1
return x == 0
elif:
while x >0:
x += 1
return x == 0
It'll do a finite number of steps for any integer, but its not the same steps for every integer, which is what you want I believe.
If that is what you want, the absence of such a formula feels like a consequence of the logical completeness of the axiomatic presentation of the reals and the imcompleteness of the integers.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: INT Function
Ninja'd by jestingrabbit, who provides essentially the same algorithm.
There is a simple algorithm that works as long as by "finite" you means "will always halt", and not "will always take less than N steps regardless of the value of x":
1. If x < 0, replace x with x.
2. If x = 0, stop. Your starting number is an integer.
3. Replace x with x1.
4. If x < 0, stop. Your starting number is not an integer.
5. Return to step 2.
There is a simple algorithm that works as long as by "finite" you means "will always halt", and not "will always take less than N steps regardless of the value of x":
1. If x < 0, replace x with x.
2. If x = 0, stop. Your starting number is an integer.
3. Replace x with x1.
4. If x < 0, stop. Your starting number is not an integer.
5. Return to step 2.
pollywog wrote:I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.

 Posts: 45
 Joined: Fri Feb 05, 2016 3:39 pm UTC
Re: INT Function
I'll add a slight modification:
1. If x=0, x is an integer. Halt.
2. Else, save x/x as a variable y.
3. Do either of the algorithms above, with y standing for 1 (i.e. reverse sign if x<0, substract y, check if result =0, if so integer, if not check if result <0, if so not integer, if not repeat from substracting y).
In other words: the problem as stated did not include the constant 1, but that one is fortunately easy (unless x=0, in which case we already have the answer).
There's a fairly easy proof that it's impossible to tell in a constant N steps; something to do with all possible results of operations and comparisons splitting the real line into finitely many pieces due to continuity. I don't recall enough logic at the moment to give the proof properly.
1. If x=0, x is an integer. Halt.
2. Else, save x/x as a variable y.
3. Do either of the algorithms above, with y standing for 1 (i.e. reverse sign if x<0, substract y, check if result =0, if so integer, if not check if result <0, if so not integer, if not repeat from substracting y).
In other words: the problem as stated did not include the constant 1, but that one is fortunately easy (unless x=0, in which case we already have the answer).
There's a fairly easy proof that it's impossible to tell in a constant N steps; something to do with all possible results of operations and comparisons splitting the real line into finitely many pieces due to continuity. I don't recall enough logic at the moment to give the proof properly.
Re: INT Function
So basically, the only way to tell if a number x is an integer is by saying "is it equal to zero? No? Well then, is it equal to 1? No? How about 2? How about three?" And just continue until either you hit upon a "yes" or you get to a number that's larger than x. (Reverse for x<0).
Not sure why, but that does seem a bit disturbing to me. You'd think there'd be an "algebraic" (and I do not mean to use this term in a strict sense) method for picking out an integer.
Perhaps it just boils down to the fact that there's nothing "special" about an integer as opposed to any other real number, so there no simple test that will make one stand out.
Not sure why, but that does seem a bit disturbing to me. You'd think there'd be an "algebraic" (and I do not mean to use this term in a strict sense) method for picking out an integer.
Perhaps it just boils down to the fact that there's nothing "special" about an integer as opposed to any other real number, so there no simple test that will make one stand out.
Life is mostly plan "B"
Re: INT Function
It doesn't mean that it's because there's nothing special about integers; if you are going to limit yourself to a small range of operators, of course you can find problems like that. Try finding sqrt with only add/subtract/multiply/divide and comparison.
Summum ius, summa iniuria.
Re: INT Function
Here's something a bit more general: consider logical propositions you can build out of real variables, real constants, addition, subtraction, multiplication, division, comparison (equality or inequality), exponentiation, logical connectives (and, or, if, parentheses), and logical quantifiers (for all, there exists). Which subsets of the real numbers can you define using these? For instance, I can define a set of real numbers by "the set of all numbers x such that for every y there exist real numbers w and z such that y^2 = x^3 + e^(w*z)  w^2 + yz, and w is either less than z or more than x+y." (Don't think too hard about that set, it's just a throwaway example.) Anyway, the big fact is that every set of real numbers that can be defined this way is a finite collection of points together with a finite collection of open, closed, and halfopen intervals. This is known as ominimality, and it's a really crucial fact in mathematical logic.
Here's one reason this is incredibly important. Suppose there was a way to define the integers with a finite logical statement (not an algorithm). Then we could chain that definition together with Gödel's Incompleteness Theorem to prove that there were unsolvable problems which could be stated as basic high school algebra problems (systems of inequalities, etc.)! That would be truly terrifying, and algebra would as a result be a mostly useless subject. Luckily this is not the case: the first order theory of the real numbers is decidable (and in fact, the decision procedure is actually used in modern computer algebra systems, such as Mathematica).
Edit: ah, I see that jestingrabbit and Lothario have already made these points.
Here's one reason this is incredibly important. Suppose there was a way to define the integers with a finite logical statement (not an algorithm). Then we could chain that definition together with Gödel's Incompleteness Theorem to prove that there were unsolvable problems which could be stated as basic high school algebra problems (systems of inequalities, etc.)! That would be truly terrifying, and algebra would as a result be a mostly useless subject. Luckily this is not the case: the first order theory of the real numbers is decidable (and in fact, the decision procedure is actually used in modern computer algebra systems, such as Mathematica).
Edit: ah, I see that jestingrabbit and Lothario have already made these points.
Zµ«VjÕ«ZµjÖZµ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«ZµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZ
Re: INT Function
Goemon wrote:So basically, the only way to tell if a number x is an integer is by saying "is it equal to zero? No? Well then, is it equal to 1? No? How about 2? How about three?" And just continue until either you hit upon a "yes" or you get to a number that's larger than x. (Reverse for x<0).
You can optimize the algorithm to take O(log(x)) steps instead of O(x), but you cannot do it in O(1).
Re: INT Function
What about checking whether sin(πx) is zero? (My guess is that it works but you need more than first order logic to define that, am I correct?).

 Posts: 39
 Joined: Tue Jan 14, 2014 6:18 am UTC
Re: INT Function
If division is allowed, and counts as one step, doesn't MOD solve this in one step?
Code: Select all
x % 1 == 0 Integer
x % 1 != 0 Non integer
pi % 1 = .14159...
e % 1 = .71828...
45 % 1 = 0 Integer
4.5 % 1 = .5
Re: INT Function
How is modulus implied by the existence of a division operator? And how is it defined for nonintegers? If you are not actually doing *integer* division (which doesn't make sense for nonintegers) then x/1 = x, and therefore to satisfy the equation x = 1*x + r, r must always equal zero. If your "division" operator only returns an integer, you don't need modulus anyway, as you can simply do "x/1 == x". At that point, you just have the floor function.
Summum ius, summa iniuria.
Re: INT Function
I think we all understand that assuming the existence of at least one function like modulus, integer division, or floor/ceiling/nearest integer, that it can be done in a fixed number of steps. However, such functions were out of the scope of the question which was asking about only elementary arithmetic operations and ternary comparisons. In fact, the modulus operation you're proposing is closely related to the residual output of the algorithm already discussed (keep subtracting one until you get a number less than or equal to zero).
pollywog wrote:I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
Re: INT Function
Yep, modulo is more or less the same function we're looking for.
Actually, I kind of like that. It might not actually provide a solution any faster  don't think you can calculate sin exactly in finite steps  but at least hints that there is something to be said for "uniqueness" of integers. If you start wrapping a string of length x around a drum of fixed r, you can count how many times you pass the starting point...
DR6 wrote:What about checking whether sin(πx) is zero?
Actually, I kind of like that. It might not actually provide a solution any faster  don't think you can calculate sin exactly in finite steps  but at least hints that there is something to be said for "uniqueness" of integers. If you start wrapping a string of length x around a drum of fixed r, you can count how many times you pass the starting point...
Life is mostly plan "B"
Re: INT Function
DR6 wrote:What about checking whether sin(πx) is zero? (My guess is that it works but you need more than first order logic to define that, am I correct?).
Practically, there may be some issues if you put that into a computer because the sine function and π are not perfect. MATLAB tells me that sin(pi) is not zero, but rather 1.2246e16 (which is of course not an integer).
Who is online
Users browsing this forum: No registered users and 5 guests