Calculating a very High Value in C

Question

How can I write a program for calculating 256^ 1075 in C?

Answer 1

You would normally use an arbitrary precision library like the GNU multiple precision library but you need to be aware that there are possible problems on out-of-memory conditions.

I've never struck those conditions but I know that out-of-memory conditions will result in immediate termination of your program, something I find unacceptable in a general purpose library but, if you're only doing it for your own purposes, it shouldn't matter.

Keep in mind that 256¹⁰⁷⁵ is identical to (2⁸)¹⁰⁷⁵ or 2⁸⁶⁰⁰ or:

721045565498050462828429917412556960604513859802538081873122368911788732956439274225864001642461608356091365725323603142252816890626189696736401581541294285566741028376272823062550082359901794039986298615273210328345626639174106858187711940897476396213895651703726796167860201573778668219366631592506467139237002323894945941153960686586039536926241870456707773431653530015773116176434951659795353009608616446115667285058015334257480475355716852592096374283857537724899247971515783412616992513532848273632589782766271040851331142322771071088389134642984473643738402894918154707844431841213583945783472115999530525333230702437131754966569501527395804654100310782093087523454544803680095205341801516766904126220009222254803233164642288805608897794006153421451603745640461874549192070290357437146114880452134900474637206123870352090538836331361066166004436464109033091161352488478000098719880190760681371193735285926294088907830167065532134813127700660013120296469689114264938082654055243005796763472735288017236752393524167112741532230180683009642635285051448352066165988154443620228918244797456605592199738219102495045082871871749924042812549384175311386227917001287973740197921643037845849558150318478336659332771108283160669871266132735610748059899559920099443863366654359963046955454879286685604643947715878648144465182422254030934432611259761729817942775310594441161575096482080795830737357754824834800998303829642983396836712603779043678758682199370784619630670133509417248505984815076991190213057529038561414712293196578500202094308107205919199315320200458292071386081671529131600951998681568233398639959444445065478510490520755160963389572581156101890222014654426875152661583975418301230503338179030264748031565474013489922191542163505080668367247263962655310515879140996875431342720470207568056785833674837383415271437117705484330992559332192343925631412229552962036545540415751706420159717554066377068012543075927564020874743229021090897051464811533394676447682720815011281441416776254492629990245337221263347551732520660350422723450476787964270274004842480592145998773371409318922960548011085396129032280891833226972242152152697180727904068032245717969766455124404475396853520180332977812778205205309786385376490778465176664848989686125190816554372900664823875404669900296636521380983373661664523506680061456082816532587442510746466657123481269475703351673258759845855904933620481298280491486678485735718545306910493608385077316071337984438572796898083908719338999316913684243081318023001596539495236872846587809109071927554011535392907920457657750570940584466174298869849051365376

from echo '256^1075' | bc.

---

And, since you asked for a C program, here it is. It's pretty specific for purpose in that it only calculates 256¹⁰⁷⁵ (or 2⁸⁶⁰⁰ which is the same thing) but you could do other powers of two if you wish. If you bump up the EXPONENT and get an overflow, just bump up the DIGITS as well.

#include <stdio.h>

// Allow for 2600 digits (trial and error) and 2^8600 (256^1075).

#define DIGITS 2600
#define EXPONENT 8600
static int digit[DIGITS];

// Function to print. 'started' is used to strip off leading zeros
//  and is passed in as 1 if overflow occurred.

static void printIt (int started) {
    int i;

    if (started) {
        printf ("Overflow: 1");
    }
    for (i = 0; i < DIGITS; i++) {
        if (started) {
            printf ("%d", digit[i]);
        } else {
            if (digit[i] > 0) {
                started = 1;
                printf ("%d", digit[i]);
            }
        }
    }
    printf ("\n");
}

 

// Doubles the number by using primary school addition with carry.

static int doubleIt (void) {
    int i, carry = 0;

    for (i = DIGITS - 1; i >= 0; i--) {
        digit[i] = digit[i] * 2 + carry;
        if (digit[i] > 9) {
            digit[i] = digit[i] - 10;
            carry = 1;
        } else {
            carry = 0;
        }
    }
    return carry;
}

// Main program to calculate the value. Starts with 1
//   and then keeps doubling until we're done.

int main (void) {
    int i, rc;

    digit[DIGITS-1] = 1;
    for (i = 0; i < EXPONENT; i++) {
        printf ("Countdown: %d\n", EXPONENT-i-1);
        if ((rc = doubleIt())) {
            break;
        }
    }
    printIt(rc);
    return 0;
}

The output is:

Countdown: 8599
Countdown: 8598
Countdown: 8597
Countdown: 8596
:
Countdown: 4
Countdown: 3
Countdown: 2
Countdown: 1
Countdown: 0

72104556549805046282842991741255696060451385980253808187312236891178
87329564392742258640016424616083560913657253236031422528168906261896
96736401581541294285566741028376272823062550082359901794039986298615
27321032834562663917410685818771194089747639621389565170372679616786
02015737786682193666315925064671392370023238949459411539606865860395
:
78091090719275540115353929079204576577505709405844661742988698490513
65376

and this takes about quarter of a second on my old clunker laptop (if I take out the Countdown lines).

Answer 2

Maybe it would help to use a library like GMP.

Answer 3

You could use the gmp library. Otherwise, 256¹⁰⁷⁵ is 2⁸⁶⁰⁰ = 1 << 8600.

Answer 4

256^1075 is, in binary,

1000000....0000

where there are 8600 zeros.

Answer 5

You will need to use an external Library which supports huge numbers like that, or you can write your own (not recommended but very fun to).

if you are indeed using C++ You can use http://gmplib.org/

Or Just switch over to Java and play with Big Integer (but I don't know what limits it has if any).

Answer 6

In Python is simple: 256 ** 1075, returning a 2588 digits number. In C, you can use GMP.

As an alternative, you can implement the pencil-and-paper algorithm to multiply 256 x 256 x ... x 256:

char [5000] tempresult;
strcpy(tempresult, "1");

for (i=0; i<1075; i++) {
    /* returns tempresult = tempresult * 256 */
    my_pencil_and_paper_mult(tempresult, "256");
}

printf("%s\n", tempresult);