Programming

I have to write a c program which takes a 3 digit number n and calculates the value of (2^n)+1 and then determines the number is prime or not.

I have tried to first calculate the value of 2^n and then adding one to it and then apply the logic of prime number.

but the ultimate problem is that if n is a 3 digit number for example 100
then 2^100 becomes a huge number for which my program is returning the same value of 2^100 and 2^100+1

for 2^50 and 2^50+1 it returns correct values with the diff of 1.

Code:

#include<stdio.h>
#include<conio.h>
#include<math.h>

main()
{
int n,i,a,count=0;
long double b,d,k=1.00;
clrscr();

printf("Enter any 3 digit number n::");

scanf("%d",&n);
b=pow(2,n);
d=b+k;
printf("%Lf\n%Lf",b,d);
}

Please help me out here.

Regards,
Prachi

Now that's a typical homework question. Which algorithm were you asked to implement? RSA, AES, or even ElGamal?

Your problem is due to the magnitude of the exponent i.e. 100.

The error in pow(x, y) is below about 2 ulps (Unit in Last Place or Unit of Least Precision) when its magnitude is moderate, but increases as pow(x, y) approaches the over/underflow thresholds until almost as many bits can be lost as are occupied by the floating-point format's exponent field, i.e. 11 bits for an IEEE 754 double. Moderate values of pow() are accurate enough that pow(int, int) is exact until it is bigger than 2**53 for IEEE 754. I do not have figures to hand for pow(int, double) but I seem to recall that there is no much difference.

If you require accuracy in the 2**100 range you need to use a arbitrary precision numeric library and not libm. Given that you appear to be on a DOS or WIN32 platform, this option may not be available to you.

<conio.h>: It looks like Turbo C 3.0; long int is 32 bit. There is no bignum library for it.
You already have seen the problem with double precision arithmetic and large numbers.

You need a different compiler.

Hi.

If I were doing this, I'd think about 2 facts: First, the base is a constant integer, second, that the exponents are all positive integers. That might lead us to consider an arithmetic package that need not be as general as things like bignum, perhaps one that we could write.

If this were not required to be in C, I think I would look at the scripting languages. I know that Icon for example has the capability to do extended range ( Integers in Icon can be arbitrarily large ... are represented by blocks of data that Icon manages ... large integers are supported in all arithmetic computations ... ).

On the other hand, I haven't had the need to write this, so this is really just a thought experiment ... cheers, drl

On the other hand, Turbo C supports something modern compilers do not: supersized 80-bit long doubles.

There is the The GNU MP Bignum Library library.