Need to verify if big numbers are integers

[Crook]

I need to see if big numbers, for instance greater than 10^12, are integers? VB6, C++ and the others don't offer this possibility. Could you indicate me some useful programs? Thanks.

[Greenbank]

Originally Posted by Crook

I need to see if big numbers, for instance greater than 10^12, are integers? VB6, C++ and the others don't offer this possibility. Could you indicate me some useful programs? Thanks.

Are you sure you mean "integers" here? Did you mean "primes"? If not, post examples of what you mean.

In the mean time I guess you need to take a look at GMP http://www.swox.com/gmp

It's a multi-precision maths library that you can use from C++.

[cheesehead]

Perhaps Crook is referring to, for example, determining whether the result of 123456789012345678901234567890123456789^0.5 is an integer.

[drew]

Originally Posted by cheesehead

Perhaps Crook is referring to, for example, determining whether the result of 123456789012345678901234567890123456789^0.5 is an integer.

I think it needs to be divided out. An FFT wouldn't work in this case, since it has limited precision (not that the conventional method is very time conuming).

Drew

[Greenbank]

Originally Posted by cheesehead

Perhaps Crook is referring to, for example, determining whether the result of 123456789012345678901234567890123456789^0.5 is an integer.

Which is why I asked for an example of what he means.

With GMP the above is simple:-

int main(void) {
    mpz_t orig, sqrt, square;
    mpz_init( orig );
    mpz_init( sqrt );
    mpz_init( square );
    mpz_set_str( orig, "123456789012345678901234567890123456789", 10 );
    mpz_sqrt( sqrt, orig );
    mpz_mul( square, sqrt, sqrt );
    if( mpz_cmp( square, orig ) == 0 ) {
        gmp_printf( "%Zd is %Zd^2\n", orig, sqrt );
    } else {
        gmp_printf( "%Zd is not a square\n", orig );
    }
    return(0);
}

[Crook]

I need to verify, for instance, if (17^64-1)/24 is an integer. Just an example. Does GMP provide me this feature?

[Greenbank]

Yes GMP can do it, but it isn't necessary.

Here's a good explanation of some tricks that can help you.

http://mathforum.org/library/drmath/view/55889.html

Once you've read that consider this:

If you are checking whether (17^e)-1 is divisible by 24 then consider this:

17 mod 24 = 17

(17*17) mod 24 = 1

Therefore (17*17)-1 mod 24 = 0 and so (17^2)-1 is divisible by 24.

(17^2) * 17 mod 24 = 1 * 17 mod 24 = 17 mod 24.
(17^3) * 17 mod 24 = 17 * 17 mod 24 = 1 mod 24.

So all even n for (17^n)-1 are divisible by 24.

[ewmayer]

For numbers < 10000 digits or so and where one only needs to check a smallish number of instances, there's little point in spending time writing a custom GMP-based app - any halfway-decent "abritrary-precision" calculator (e.g. Unix/linux bc, mathematica, PARI) will serve for these kinds of things. I have PARI installed on my windows PC (it's a simple precompiled-binary download) and use it all the time. For certain things (e.g. binary and hex-format I/O) I find Unix bc more convenient.

[xilman]

Originally Posted by ewmayer

For numbers < 10000 digits or so and where one only needs to check a smallish number of instances, there's little point in spending time writing a custom GMP-based app - any halfway-decent "abritrary-precision" calculator (e.g. Unix/linux bc, mathematica, PARI) will serve for these kinds of things. I have PARI installed on my windows PC (it's a simple precompiled-binary download) and use it all the time. For certain things (e.g. binary and hex-format I/O) I find Unix bc more convenient.

Seconded.

I use bc or "bc -l" for most of my simple arithmetic and Pari/gp for anything more complicated, such as modular inverses or simple polynomial manipulation.

bc -l is good for units conversion (I very often need to convert seconds to hours or days) and for estimating sizes of integers in bits or digits. When I want a decent approximation to pi(x) I invariably use bc to calculate x/(l(x)-1) rather than fire up something heavyweight to obtain an exact answer.

If I have a small integer to factor, up to 40 or 50 digits say, it is often quicker to ask Pari/gp than to fire up a dedicated factoring program.

Paul

[VolMike]

If need to check k | a^b-c for positive integers k,a,b,c
using Mathematica -just evaluate
PowerMod[a,b,k]==c
If result is True, k divides a^b-c , otherwise - doesn't.

[ewmayer]

Originally Posted by xilman

bc -l is good for units conversion (I very often need to convert seconds to hours or days) and for estimating sizes of integers in bits or digits. When I want a decent approximation to pi(x) I invariably use bc to calculate x/(l(x)-1) rather than fire up something heavyweight to obtain an exact answer.

Speaking of "the other pi", it's a little annoying tha bc doesn't have predefines for famous constants, like simply typing "Pi" in PARI. My preferred formula for getting digits of Pi in bc -l is via arctan:

4*a(1)

If I need more than the default number of digits, I preface that with scale = {how many digits I need}