Looking for suitable datatype in C to handle two mathematical expressions

Question

I have to calculate following two mathematical formula in C programming language.

1. result = 48^108 // 108 should be 103
2. result%143 =9

To calculate this two equation I need some data type whose range is large enough.

I know the end result of equation 2 is 9. However, I did not get this answer after using several datatypes.

Here are some of my implementations.

1. #include <stdio.h>
#include<math.h>
int main()
{
     unsigned int a1=48,a2=103,a3, a4;
    a3= pow(48,103);
    printf("a3=%u",a3);
    a4= a3 % 143;
    printf("\n a4=%u",a4);
    return 0;
}

 Answer That I got:
 warning: overflow in conversion from ‘double’ to ‘unsigned int’ changes value from ‘1.4717954286441339e+173’ to ‘4294967295’ [-Woverflow]
   15 |     a3= pow(48,103);
      |         ^~~
a3=4294967295
 a4=47

2. int main()
{
    unsigned long a1=48,a2=103,a3, a4;
    a3= pow(48,103);
    printf("a3=%lu",a3);
    a4= a3 % 143;
    printf("\n a4=%lu",a4);
    return 0;
}


warning: overflow in conversion from ‘double’ to ‘long unsigned int’ changes value from ‘1.4717954286441339e+173’ to ‘18446744073709551615’ [-Woverflow]

15 | a3= pow(48,103); | ^~~ a3=18446744073709551615 a4=16

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

int main()
{
    long double a1=48,a2=103,a3, a4;
    a3= pow(48,103);
    printf("a3=%LF",a3);
    a4= fmod(a3,143);
    printf("\n a4=%LF",a4);
    return 0;
}

a3=147179542864413390695231668723836254417826202083285489645297997883519171141486480221363409432872885235091123842885421688012169987663834748443552551569845821059256315786821632.000000

a4=46.000000

Which data type should I use to handle the situation?

I apologies for my wrong equation on equation 1. It is 103 not 108. and if I use 103 the answer is 9.

Thank you for all your comments and process.

Answer 1

The remainder of 48¹⁰³ modulo 143 is easily calculated by decomposing the exponent into powers of two and keeping all the intermediate values reduced modulo 143, as illustrated in the following code. (This is not necessarily the method that uses the fewest arithmetic operations.)

#include <stdio.h>


int main(void)
{
    //  Set x, y, and m for which we will compute x**y modulo m.
    unsigned x = 48, y = 103, m = 143;

    /*  r starts at the remainder of x**0 modulo m and is updated to be
        remainders of x raised to various powers as we compute them.
    */
    unsigned r = 1;

    /*  p will be the remainder of x modulo m, then of x**2 modulo m, then of
        x**4, x**8, x**16, and so on.  e will track this exponent, first, 1,
        then 2, then 4, 8, 16, and so on.

        For each bit that is set in y, say the bit representing 16, we will
        multiply r by the corresponding power (modulo m).  Thus, if y is 49 = 1
        + 16 + 32, we will multiply r by x**1, x**16, and x**32, all modulo m.
        This forms x**1 * x**16 * x**32 = x**(1+16+32) = x**49.  In general,
        the result will be x**y modulo m.

        e and p start at 1 and x, as described above.

        The loop continues as long as e is within the bits set in y, hence e <=
        y.

        In each iteration, we double e to move it to the next bit value
        position and we square p.  The squaring is done modulo m.

        Whenever e corresponds to a bit that is set in y ("y & e" is true), we
        multiply the current power in p by r and reduce the product modulo m.
     */
    for (unsigned e = 1, p = x; e <= y; e <<= 1, p = p*p % m)
        if (y & e)
            r = r*p % m;

    printf("%u\n", r);
}

Answer 2

There is no such datatype in C language to store such a large number. You can use a formula that can directly give the answer to your equation.