Вычисление очень высокого значения в C

Question

Как мне написать программу для вычисления 256 ^ 1075 в C?

Answer 1

Обычно вы используете библиотеку произвольной точности, такую ​​как GNU, библиотека с множественной точностью , но вы должны знать, что возможны проблемы в условиях нехватки памяти.

I 'Я никогда не нарушал эти условия, но я знаю, что условия нехватки памяти приведут к немедленному завершению вашей программы, что я нахожу неприемлемым в библиотеке общего назначения, но, если вы делаете это только для своих собственных целей, это не должноt имеет значение.

Имейте в виду, что 256 ¹⁰⁷⁵ идентично (2 ⁸ ) ¹⁰⁷⁵ или 2 ⁸⁶⁰⁰ или:

721045565498050462828429917412556960604513859802538081873122368911788732956439274225864001642461608356091365725323603142252816890626189696736401581541294285566741028376272823062550082359901794039986298615273210328345626639174106858187711940897476396213895651703726796167860201573778668219366631592506467139237002323894945941153960686586039536926241870456707773431653530015773116176434951659795353009608616446115667285058015334257480475355716852592096374283857537724899247971515783412616992513532848273632589782766271040851331142322771071088389134642984473643738402894918154707844431841213583945783472115999530525333230702437131754966569501527395804654100310782093087523454544803680095205341801516766904126220009222254803233164642288805608897794006153421451603745640461874549192070290357437146114880452134900474637206123870352090538836331361066166004436464109033091161352488478000098719880190760681371193735285926294088907830167065532134813127700660013120296469689114264938082654055243005796763472735288017236752393524167112741532230180683009642635285051448352066165988154443620228918244797456605592199738219102495045082871871749924042812549384175311386227917001287973740197921643037845849558150318478336659332771108283160669871266132735610748059899559920099443863366654359963046955454879286685604643947715878648144465182422254030934432611259761729817942775310594441161575096482080795830737357754824834800998303829642983396836712603779043678758682199370784619630670133509417248505984815076991190213057529038561414712293196578500202094308107205919199315320200458292071386081671529131600951998681568233398639959444445065478510490520755160963389572581156101890222014654426875152661583975418301230503338179030264748031565474013489922191542163505080668367247263962655310515879140996875431342720470207568056785833674837383415271437117705484330992559332192343925631412229552962036545540415751706420159717554066377068012543075927564020874743229021090897051464811533394676447682720815011281441416776254492629990245337221263347551732520660350422723450476787964270274004842480592145998773371409318922960548011085396129032280891833226972242152152697180727904068032245717969766455124404475396853520180332977812778205205309786385376490778465176664848989686125190816554372900664823875404669900296636521380983373661664523506680061456082816532587442510746466657123481269475703351673258759845855904933620481298280491486678485735718545306910493608385077316071337984438572796898083908719338999316913684243081318023001596539495236872846587809109071927554011535392907920457657750570940584466174298869849051365376

из echo '256^1075' | bc.

---

И, поскольку вы запросили программу на C, вот она.Он довольно специфичен для целей, поскольку он вычисляет только 256 ¹⁰⁷⁵ (или 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

и это занимает около четверти секунды на моем старом ноутбуке с глушителем (если я достаю линии обратного отсчета).

Answer 2

Вы можете использовать библиотеку gmp.В противном случае 256¹⁰⁷⁵ равно 2⁸⁶⁰⁰ = 1 << 8600. </p>

Answer 3

Может быть, это поможет использовать такую ​​библиотеку, как GMP .

Answer 4

256 ^ 1075 в двоичном виде

1000000....0000

, где 8600 нулей.

Answer 5

В Python просто: 256 ** 1075, возвращая число 2588 цифр. В C вы можете использовать GMP .

В качестве альтернативы вы можете реализовать алгоритм «карандаш-бумага» для умножения 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);

Answer 6

Вам нужно будет использовать внешнюю библиотеку, которая поддерживает такие огромные числа, или вы можете написать свою собственную (не рекомендуется, но очень интересно).

если вы действительно используете C++ Вы можете использовать http://gmplib.org/

Или просто переключитесь на Java и поиграйтесь с Big Integer (но я не знаю, какие у него ограничения, если они есть).