Need to verify if big numbers are integers
 

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.

[QUOTE=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.[/QUOTE]

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 [url]http://www.swox.com/gmp[/url]

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

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

[QUOTE=cheesehead]Perhaps Crook is referring to, for example, determining whether the result of 123456789012345678901234567890123456789^0.5 is an integer.[/QUOTE]
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

[QUOTE=cheesehead]Perhaps Crook is referring to, for example, determining whether the result of 123456789012345678901234567890123456789^0.5 is an integer.[/QUOTE]

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

With GMP the above is simple:-

[code]
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);
}
[/code]

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

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

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

[url]http://mathforum.org/library/drmath/view/55889.html[/url]

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.

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.

[QUOTE=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.[/QUOTE]
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

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

[QUOTE=xilman;66533]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.[/QUOTE]

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}