INT Function

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Goemon
Posts: 442
Joined: Mon Nov 19, 2007 4:57 am UTC

INT Function

Postby Goemon » Thu Feb 04, 2016 4:16 am UTC

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...
Life is mostly plan "B"

User avatar
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

Postby jestingrabbit » Thu Feb 04, 2016 4:41 am UTC

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.

User avatar
ConMan
Shepherd's Pie?
Posts: 1691
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: INT Function

Postby ConMan » Thu Feb 04, 2016 4:41 am UTC

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 x-1.
4. If x < 0, stop. Your starting number is not an integer.
5. Return to step 2.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

Lothario O'Leary
Posts: 45
Joined: Fri Feb 05, 2016 3:39 pm UTC

Re: INT Function

Postby Lothario O'Leary » Fri Feb 05, 2016 10:22 pm UTC

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.

User avatar
Goemon
Posts: 442
Joined: Mon Nov 19, 2007 4:57 am UTC

Re: INT Function

Postby Goemon » Wed Feb 10, 2016 3:11 am UTC

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.
Life is mostly plan "B"

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6598
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: INT Function

Postby Thesh » Wed Feb 10, 2016 6:02 am UTC

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.

User avatar
notzeb
Without Warning
Posts: 629
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Re: INT Function

Postby notzeb » Wed Feb 10, 2016 6:36 am UTC

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 half-open intervals. This is known as o-minimality, 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.
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z

Tub
Posts: 475
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: INT Function

Postby Tub » Wed Feb 10, 2016 10:07 am UTC

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).

DR6
Posts: 171
Joined: Thu Nov 01, 2012 1:44 pm UTC

Re: INT Function

Postby DR6 » Wed Feb 10, 2016 8:24 pm UTC

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?).

BedderDanu
Posts: 39
Joined: Tue Jan 14, 2014 6:18 am UTC

Re: INT Function

Postby BedderDanu » Wed Feb 10, 2016 11:25 pm UTC

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

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6598
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: INT Function

Postby Thesh » Thu Feb 11, 2016 12:00 am UTC

How is modulus implied by the existence of a division operator? And how is it defined for non-integers? If you are not actually doing *integer* division (which doesn't make sense for non-integers) 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.

User avatar
ConMan
Shepherd's Pie?
Posts: 1691
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: INT Function

Postby ConMan » Thu Feb 11, 2016 3:11 am UTC

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:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

User avatar
Goemon
Posts: 442
Joined: Mon Nov 19, 2007 4:57 am UTC

Re: INT Function

Postby Goemon » Sat Feb 13, 2016 8:10 pm UTC

Yep, modulo is more or less the same function we're looking for.

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"

User avatar
cyanyoshi
Posts: 418
Joined: Thu Sep 23, 2010 3:30 am UTC

Re: INT Function

Postby cyanyoshi » Sun Feb 14, 2016 6:49 am UTC

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.2246e-16 (which is of course not an integer).


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 12 guests