在 C 中计算一个非常高的值

Question

如何用 C 编写计算 256^1075 的程序？

Answer 1

您通常会使用像 GNU multiple precision library 这样的任意精度库，但您需要注意在内存不足的情况下可能会出现问题。

我从来没有遇到过这些情况，但我知道内存不足的情况会导致您的程序立即终止，我认为这在通用库中是 Not Acceptable ，但是，如果您只是为了自己的目的而这样做目的，应该无关紧要。

请记住，256¹⁰⁷⁵ 等同于 (2⁸)¹⁰⁷⁵ 或 2 ⁸⁶⁰⁰ 或:

721045565498050462828429917412556960604513859802538081873122368911788732956439274225864001642461608356091365725323603142252816890626189696736401581541294285566741028376272823062550082359901794039986298615273210328345626639174106858187711940897476396213895651703726796167860201573778668219366631592506467139237002323894945941153960686586039536926241870456707773431653530015773116176434951659795353009608616446115667285058015334257480475355716852592096374283857537724899247971515783412616992513532848273632589782766271040851331142322771071088389134642984473643738402894918154707844431841213583945783472115999530525333230702437131754966569501527395804654100310782093087523454544803680095205341801516766904126220009222254803233164642288805608897794006153421451603745640461874549192070290357437146114880452134900474637206123870352090538836331361066166004436464109033091161352488478000098719880190760681371193735285926294088907830167065532134813127700660013120296469689114264938082654055243005796763472735288017236752393524167112741532230180683009642635285051448352066165988154443620228918244797456605592199738219102495045082871871749924042812549384175311386227917001287973740197921643037845849558150318478336659332771108283160669871266132735610748059899559920099443863366654359963046955454879286685604643947715878648144465182422254030934432611259761729817942775310594441161575096482080795830737357754824834800998303829642983396836712603779043678758682199370784619630670133509417248505984815076991190213057529038561414712293196578500202094308107205919199315320200458292071386081671529131600951998681568233398639959444445065478510490520755160963389572581156101890222014654426875152661583975418301230503338179030264748031565474013489922191542163505080668367247263962655310515879140996875431342720470207568056785833674837383415271437117705484330992559332192343925631412229552962036545540415751706420159717554066377068012543075927564020874743229021090897051464811533394676447682720815011281441416776254492629990245337221263347551732520660350422723450476787964270274004842480592145998773371409318922960548011085396129032280891833226972242152152697180727904068032245717969766455124404475396853520180332977812778205205309786385376490778465176664848989686125190816554372900664823875404669900296636521380983373661664523506680061456082816532587442510746466657123481269475703351673258759845855904933620481298280491486678485735718545306910493608385077316071337984438572796898083908719338999316913684243081318023001596539495236872846587809109071927554011535392907920457657750570940584466174298869849051365376

来自 echo '256^1075' |公元前。

---

并且，由于您要求的是 C 程序，所以就在这里。它的目的非常具体，因为它只计算 256¹⁰⁷⁵(或 2⁸⁶⁰⁰，这是同一件事)，但如果您愿意，您可以计算其他 2 的幂。如果您提高 EXPONENT 并发生溢出，只需提高 DIGITS 即可。

#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;
}

输出是:

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

这在我的旧旧笔记本电脑上大约需要四分之一秒(如果我取出倒计时线)。