Ask Your Question
1

Testing if a result n is an Integer, for large n.

asked 2016-08-10 07:03:46 -0500

jbeatz gravatar image

I have a number x of size 2^160, and I perform the operation n = x*(x+1.5) and want to test if the result is an integer.

In python I would normally try, n.is_integer() or use an isinstance(), but this doesn't work in sage, I assume due to the fact sage integers are set up quite differently.

Upon scouring this site, I found someone recommend n is in ZZ, but this doesn't work (sage seems to loose accuracy at this level) Example:

n = 2^160

n in ZZ

Result: False

The only (terribly inefficient) way I can get this to work is to call n.divisors() and if I get the error "AttributeError: 'sage.rings.real_mpfr.RealNumber' object has no attribute 'divisors' " I know it was indeed not an integer.

There must be a better way?

edit retag flag offensive close merge delete

Comments

n.is_integer() should work in Sage but not in Python, I think.

John Palmieri gravatar imageJohn Palmieri ( 2016-08-10 13:15:43 -0500 )edit

If you do the operation x*(x+1.5) on a number of size 2^160, the result will be a float, because you add 1.5 to it. Furthermore, it would be a standard float, so you'd only have 53 bits worth of significant digits. That's not even enough to recover the integer if it were one, let alone enough precision to determine with any degree of reliability if it might be one.

You could do instead something like

R=RealField(2*160+50)
n=x*(x+R(3/2))
n-n.floor()

It will be up to you to decide how small the latter must be for you to believe that it's an integer.

If x is an integer to begin with then x*(x+3/2) is in fact an integer, but by computing it this way you'd get it represented as a rational ...(more)

nbruin gravatar imagenbruin ( 2016-08-10 22:12:45 -0500 )edit

Please provide the actual code you are running including defining x and n and your attempts to test if n is integer.

slelievre gravatar imageslelievre ( 2016-08-11 05:23:43 -0500 )edit

2 answers

Sort by ยป oldest newest most voted
0

answered 2016-08-11 05:22:37 -0500

Use n = x*(x+3/2) instead of n = x*(x+1.5). Is the number x you are starting from an integer?

edit flag offensive delete link more

Comments

Yup looks like this fixes the problem! Thank you!

jbeatz gravatar imagejbeatz ( 2016-08-11 05:48:23 -0500 )edit

@jbeatz Click the tick mark next to the answer to mark it as accepted. This will also mark the question as solved on Ask Sage's home. (It's helpful to see which questions are solved vs not solved.)

slelievre gravatar imageslelievre ( 2016-08-11 17:01:24 -0500 )edit
0

answered 2016-08-10 07:46:50 -0500

tmonteil gravatar image

I can not reproduce your problem:

sage: n = 2^160
sage: n
1461501637330902918203684832716283019655932542976
sage: n.parent()
Integer Ring
sage: n in ZZ
True

Could you please give us some informations so that someone can try to reproduce your problem:

  • which version of Sage did you use ?
  • which OS ?
  • did you install Sage from the binaries, and which ones ?
  • did you compile Sage yourself ?
  • which notebook did you use (Sage notebook or jupyter notebook) ?
  • did you use the command line ?
  • which commands did you type precisely to get the error ?
  • which error message did you get ?
  • ... ?
edit flag offensive delete link more

Comments

I am working on SageMath Online for the purposes of this demonstration n = 2^160 n1 = (2^ 160) +0.5

print n in ZZ print n1 in ZZ

True True

When clearly the second case shouldn't be! Looks like it can be fixed by changing 0.5 to 1/2 etc..

jbeatz gravatar imagejbeatz ( 2016-08-11 05:49:58 -0500 )edit

That's indeed a loss of precision. Basically, the question sage is answering is: "is there an integer that, as a float at this precision, would have the same representation", and the answer is "yes, many", due to rounding errors:

sage: ZZ(2^160+0.5) == ZZ(2^160+100.5)
True

If you make sure you're working with enough precision, you can see the difference:

sage: 2^160 + RealField(162)(1/2) in ZZ
False

Obviously, you need something about your number beforehand before you can decide at which precision you can see whether it's an integer or not.

nbruin gravatar imagenbruin ( 2016-08-11 10:41:03 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2016-08-10 07:03:46 -0500

Seen: 128 times

Last updated: Aug 11 '16